C++中的vector容器
文章目录
-
- vector的介绍
- vector的使用
-
- vector的定义
- vector初始化
- vector iterator的使用
- vector空间增长问题
- vector增删改查
- vector迭代器失效问题
vector的介绍
vector是封装动态数组的顺序容器。
就像数组一样，vector也采用的连续存储空间来存储元素。这也就意味着我们可以通过下标来获取vector的元素，和数组一样高效。但是又不像数组，vector的大小是可以动态改变的，且它的大小会被容器自动处理。
本质上，vector使用动态分配数组来存储它的元素。当新元素插入时，这个数组需要被重新分配大小，分配一个新的数组，然后将全部元素转移到这个数组。就时间而言，是一个代价相对较高的任务，因为每当一个新的元素加入容器时，vector并不分每次都重新分配大小。
vector空间分配策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其他动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入，效率更低。
vector的使用
vector的定义
| 构造函数声明 | 接口说明 |
|---|---|
| vector() | 无参构造 |
| vector(size_type n, const value_type& val = value_type()) | 构造并初始化n个val |
| vector(const vector& x) | 拷贝构造 |
| vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) | 用迭代器进行初始化构造 |
int main()
{vector<int> first;vector<int> second(4, 100);vector<int> third(second.begin(), second.end());vector<int> fourth(third);int myints[] = { 16, 2, 77, 29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\\n';return 0;
}
vector初始化
| 初始化方法 | 说明 |
|---|---|
| vector<T> v1 | v1是一个空vector，它潜在的元素是T类型的，执行默认初始化 |
| vector<T> v2(v1) | v2中包含有v1所有元素 |
| vector<T> v2 = v1 | 等价于v2(v1) |
| vector<T> v3(n, val) | v3包含了n个重复的元素，每个元素的值都是val |
| vector<T> v4(n) | v4包含了n个重复地执行了初始化的对象 |
| vector<T> v5(a,b,c…) | v5包含了初始值个数的元素，每个元素被赋予响应的初始值 |
| vector<T> v5={a,b,c…} | 等价于 |
int main()
{vector<int> v1;vector<string> v2;vector<vector<int>> v3; //这里相当于二维数组int a[n][n];vector<int> v4{ 1,2,3,4,5 };vector<int> v5 = { 1,2,3,4,5 }; //列表初始化,注意使用的是花括号vector<string> v6 = { "hi","my","name","is","lee" };vector<int> v7(5, -1); //初始化为-1,-1,-1,-1,-1。第一个参数是数目，第二个参数是要初始化的值vector<string> v8(3, "hi");vector<int> v9(10); //默认初始化为0vector<int> v10(4); //默认初始化为空字符串return 0;
}
vector iterator的使用
| iterator的使用 | 接口说明 |
|---|---|
| begin+end | 获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
int main()
{vector<int> myvector{ 1, 2, 3, 4, 5 };cout << *myvector.begin() << endl;cout << *(myvector.end() - 1) << endl;cout << *myvector.rbegin() << endl;cout << *(myvector.rend() - 1) << endl;return 0;
}
vector空间增长问题
| 容量空间 | 接口说明 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。vector具体增长多少是根据具体的需求定义的。vs是PJ版本的STL，g++是SGI版本的STL；
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题；
resize在开空间的同时还会进行初始化，影响size。
int main()
{vector<int> myints;cout << "0.size:" << myints.size() << endl;for (int i = 0; i < 10; i++)myints.push_back(i);cout << "1.size:" << myints.size() << endl;myints.insert(myints.end(), 10, 100);cout << "2.size:" << myints.size() << endl;myints.pop_back();cout << "3.size:" << myints.size() << endl;return 0;
}
int main()
{vector<int> myvector;for (int i = 0; i < 100; i++)myvector.push_back(i);cout << "size:" << (int)myvector.size() << endl;cout << "capacity:" << (int)myvector.capacity() << endl;cout << "max_size:" << (int)myvector.max_size() << endl;return 0;
}
int main()
{vector<int> myvector;int sum(0);for (int i = 1; i <= 10; i++)myvector.push_back(i);while (!myvector.empty()){sum += myvector.back();myvector.pop_back();}cout << "total:" << sum << endl;return 0;
}
int main()
{vector<int> myvector;for (int i = 1; i < 10; i++)myvector.push_back(i);cout << "0.size:" << myvector.size() << endl;myvector.resize(5);cout << "1.size:" << myvector.size() << endl;myvector.resize(8, 100);cout << "2.size:" << myvector.size() << endl;myvector.resize(12);cout << "3.size:" << myvector.size() << endl;cout << "myvector contains:";for (int i = 0; i < myvector.size(); i++)cout << ' ' << myvector[i];cout << endl;return 0;
}
vector增删改查
| vector增删改查 | 接口说明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找（不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 想数组一样访问 |
int main()
{vector<int> myvector;for (int i = 1; i <= 10; i++)myvector.push_back(i);for (int i = 0; i < myvector.size(); i++)cout << myvector[i] << ' ';cout << endl;for (int i = 0; i < 3; i++)myvector.pop_back();for (int i = 0; i < myvector.size(); i++)cout << myvector[i] << ' ';return 0;
}
int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;vector<int>::iterator pos = find(v.begin(), v.end(), 2);if (pos != v.end()){v.insert(pos, 20);}for (auto e : v){cout << e << " ";}cout << endl;pos = find(v.begin(), v.end(), 2);if (pos != v.end()){v.erase(pos);}for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin());for (auto e : v){cout << e << " ";}cout << endl;return 0;
}
int main()
{vector<int> myvector;for (int i = 1; i <= 10; i++)myvector.push_back(i);//删除指定位置数据myvector.erase(myvector.begin() + 5);//删除指定一个位置，到另一个位置间的所有数据myvector.erase(myvector.begin(), myvector.begin() + 3);cout << "myvector contains:";for (unsigned i = 0; i < myvector.size(); i++)cout << ' ' << myvector[i];cout << endl;return 0;
}
int main()
{vector<int> foo(3, 100);vector<int> bar(5, 200);foo.swap(bar);cout << "foo contains:";for (unsigned i = 0; i < foo.size(); i++)cout << ' ' << foo[i];cout << endl;cout << "bar contains:";for (unsigned i = 0; i < bar.size(); i++)cout << ' ' << bar[i];cout << endl;return 0;
}
vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装。因此迭代器失效，实际就是迭代器底层对应的指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃。
对于vector可能会导致其迭代器失效的操作：
- 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等；
- 指定位置元素的删除操作–erase；
- 注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。