变长数组vector

本质上来说vector属于数据结构中数组的实现，由此对于其操作复杂度上查找为O(1)，插入删除为O(n)就非常容易理解了，因为物理上连续的存储方式导致了插入和删除的连锁移动导致的O(n)，支持变长使得使用者不必自行realloc内存用于扩充，vector会替你来做此事，能节省一些精力。

关于对于数组和链表的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108088361

头文件和命名空间

#include
using namespace std;

常用的成员函数

函数名	用途	功能说明	时间复杂度
size()	查询遍历	获取元素个数	O(1)
begin()	查询遍历	获取指向第一个元素的迭代器	O(1)
end()	查询遍历	获取末尾的迭代器	O(1)
insert(position,x)	插入	在position位置插入数据x	O(n)
erase(position)	删除	删除position位置上的元素	O(n)
push_back(x)	插入	在末尾插入数据x	O(1)
pop_back()	删除	删除最后一个元素	O(1)
clear()	删除	删除所有元素	O(n)

注：因为对于末尾的元素的插入和删除不涉及元素的连锁移动，所以复杂度为O(1)，另外成员函数中似乎未涉及更新，这是因为vecotr可以像数组一样直接使用下标方式访问和修改，其复杂度当然也是O(1)。

代码使用示例

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<char> v;
    cout << "Size of vector v : " << v.size() << endl;
    v.push_back('L');
    v.push_back('i');
    v.push_back('u');
    v.push_back('C');
    v.push_back('N');
    cout << "Size of vector v : " << v.size() << endl;
    for (int i=0; i<v.size(); i++) cout << v[i];
    vector<char>::iterator it = v.begin();
    cout << "begin(): [" << *it << "]" << endl;
    it = v.end();
    cout << "end():   [" << *it << "]" << endl;
    it--;
    cout << "end():   [" << *it << "]" << endl;
    it = v.begin() + 3;
    v.insert(it++, 'M');
    v.insert(it++, 'i');
    v.insert(it++, 'a');
    v.insert(it++, 'o');
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout << endl;
    it = v.begin() + 3;
    v.insert(it,' ');
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout << endl;
    v[3] = '*';
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout << endl;
    v.erase(v.begin()+3);
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout <<endl;
    v.push_back('!');
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout <<endl;
    v.pop_back();
    it = v.begin();
    while (it != v.end()) cout << *it++;
    cout <<endl;
    cout << "Size of vector v : " << v.size() << endl;
    v.clear();
    cout << "Size of vector v : " << v.size() << endl;
}

示例执行结果

Size of vector v : 0
Size of vector v : 5
LiuCNbegin(): [L]
end():   []
end():   [N]
LiuMiaoCN
Liu MiaoCN
Liu*MiaoCN
LiuMiaoCN
LiuMiaoCN!
LiuMiaoCN
Size of vector v : 9
Size of vector v : 0