vector的介绍
vector是封装动态数组的顺序容器。
就像数组一样,vector也采用的连续存储空间来存储元素。这也就意味着我们可以通过下标来获取vector的元素,和数组一样高效。但是又不像数组,vector的大小是可以动态改变的,且它的大小会被容器自动处理。
本质上,vector使用动态分配数组来存储它的元素。当新元素插入时,这个数组需要被重新分配大小,分配一个新的数组,然后将全部元素转移到这个数组。就时间而言,是一个代价相对较高的任务,因为每当一个新的元素加入容器时,vector并不分每次都重新分配大小。
vector空间分配策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
与其他动态序列容器相比,vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入,效率更低。
vector的使用
vector的定义
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初始化
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); //默认初始化为0 vector<int> v10(4); //默认初始化为空字符串 return 0; }
vector 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空间增长问题
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增删改查
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下极端