c++——STL容器之vector

一、容器

STL包含了算法，容器和代器。其中容器又包含了以下几类：

1.序列式容器：vector,deque,list等。

2.关联式容器：map,set,multiset,multimap等。

3.无序关联容器：unordered_set,unordered_map,unordered_multiset,unordered_multimap等。

4.容器适配器：stack,queue,priority_queue。

二、vector容器

1.定义

vector是动态连续数组。

（1）支持随机访问，时间复杂度是O(1)。

  (2)   内存空间连续。

（3）空间大小可动态变化，会自动扩容存储空间。

2.底层原理

（1）vector内部使用3个指针指向对应的空间。代码如下：

template <typename T> class vector { private: T* start; // 指向容器的起始位置 T* finish; // 指向最后一个有效元素的下一个位置 T* end_of_storage; // 指向分配的内存末尾（总容量的终点） };

（2）根据上面的代码可得出：

容器中元素的个数size()=finish()-start()。

容器的容量capacity()=end_of_storage()-start()。

当capacity()==size()时，容器会自动扩容。

注意：

扩容不是在原有内存空间后面直接进行扩容，而是重新分配一块新的内存空间，将原有空间中的元素拷贝或者移动到新空间，删除掉原来的空间。

扩容后，原有的迭代器，引用，指针都会失效。

3.常用的成员函数

4.代码实现

（1）初始化，插入，删除，清空

#include <iostream> #include <vector> //容器的头文件 using namespace std; //vector:动态数组，支持快速随机访问且能自动扩容 int main() { /*----------vector的初始化-----------------------*/ std:: vector<int> v1; //空vector,容量为0 cout << "v1中元素的值："; for (int i = 0; i < v1.size(); ++i) { cout << v1[i] << " "; } cout << endl; cout << "v2中元素的值："; vector<int> v2(5);//初始化5个元素，每个元素的默认值为0 for (int i = 0; i < v2.size(); ++i) { cout << v2[i] << " "; } cout << endl; vector<int> v3(4, 100);//初始化4个元素，每个元素的值为100 cout << "v3中元素的值："; for (int i = 0; i < v3.size(); ++i) { cout << v3[i] << " "; } cout << endl; vector<int> v4(v3); //拷贝构造 cout << "v4中元素的值："; for (int i = 0; i < v4.size(); ++i) { cout<< v4[i] << " "; } cout << endl; int arr[] = { 3,4,5,6 }; vector<int> v5 = { arr,arr+4 }; cout << "v5中元素的值："; for (int i = 0; i < v5.size(); ++i) { cout << v5.at(i) << " "; } cout << endl; //使用迭代器初始化,end最后一个有效元素的下一个位置 vector<int> v6(v5.begin(), v5.end()); cout << "v5中元素的值："; for (int num : v5) { cout << num << " "; } cout << endl; /*-----------------元素的插入-------------------*/ v1.push_back(10); // 尾插，时间复杂度O(1） v1.push_back(20); v1.push_back(40); v1.insert(v1.begin()+2,30); //头部或者中间插入，时间复杂度O(n),需要移动元素 v1.insert(v1.end(), 3, 50); //使用insert在v1的尾部插入3个50 //打印v1 cout << "插入元素后v1中的元素值："; for (int num : v1) //使用范围for遍历 { cout << num << " "; } cout << endl; //10 20 30 40 50 50 50 cout << "v1的容量：" << v1.capacity(); cout << endl; /*----------------元素的删除---------------------*/ v1.pop_back();//尾删，不需要传递参数 v1.erase(v1.begin() + 2); //删除索引为2的元素（删除指定位置的元素） v1.erase(v1.begin() + 3, v1.end()-1); //删除索引为3到末尾-1的元素（左闭右开） cout << "删除元素后v1中的元素值："; for (int num : v1) { cout << num << " "; } cout << endl; //10 20 40 50 /*-----------元素的清空---------------------*/ v1.clear(); //clear清空仅清空元素，不会改变容量 cout << "清空后v1的size："<<v1.size() << endl; //大小变为0 cout << "清空后v1的capacity:" << v1.capacity() << endl; //容量不变 return 0; } #endif

（2）resize()和reserve()的区别

resize():调整大小，使得容量和元素的个数相同。

int main() { //resize(n)——填充n个元素，容量也为n std::vector<int> ar(5, 10); //尾插后，需要进行扩容，原有的空间会被释放，重新分配内存空间 ar.resize(10, 23); //元素的个数和容量的大小都是10 //输出结果：10 10 10 10 10 23 23 23 23 23 cout << ar.size() << endl; //10 cout << ar.capacity() << endl; //10 for (auto& x : ar) { cout << x << " "; } cout << endl; return 0; } 

reserve():只分配对应数目的容量。如果提前已知需要分配的元素个数，可以使用reserve()函数，避免频繁扩容。

int main() { //reserve(n)——容量为n，但不填充元素 std::vector<int> ar(5, 10); ar.reserve(20);//元素的个数是5，容量的大小是20 cout << ar.size() << endl; //5 cout << ar.capacity() << endl; //20 //输出结果：10 10 10 10 10 for (auto& x : ar) { cout << x << " "; } cout << endl; return 0; }

（3）data()

data（）函数的返回值是首元素地址，即开始指针指向的位置。

int main() { std::vector<int> ar = { 1,2,3,4,5 }; int* p = ar.data();//返回开始指针的指向位置 for (int i = 0; i < ar.size(); ++i) { std::cout << *p << std::endl; //1 2 3 4 5 p += 1; } return 0; }

（4）emplace_back()

直接在 vector尾部原位构造元素，消除临时对象的拷贝 / 移动开销，内部采用定位new实现。

int main() { std::vector<int> ar{ 12,23,45,56 }; ar.emplace_back(69); //原位构造，在原地址就地构建，内部调用的是定位new for (auto x : ar) { std::cout << x << " "; //12 23 45 56 69 } std::cout << std::endl; return 0; }

 （5）shrink_to_fit()

释放未使用的内存减少内存的使用，即用来回收空间。

int main() { std::vector<int>ar = { 12,23,34,45,56,67,78,89 }; ar.erase(ar.begin() + 2, ar.end()); std::cout << ar.capacity() << std::endl; //ar.shrink_to_fit(); //当容量与元素的个数差距太多，则可以使用该函数缩减容量 //底层实现：使用swap（）函数 //使用块域和swap缩减容量 { std::vector<int>(ar).swap(ar); //解释：使用ar初始化不具名的对象，因为是不具名对象，根据元素的个数分配容量的大小 //使用交换函数将原本的ar与不具名对象交换后，原本的ar容量的大小与元素的个数相同 //不具名的对象在块域结束后，会被销毁。 } std::cout << "ar.capacity:" << ar.capacity() << std::endl; return 0; }

5.迭代器失效

 （1）扩容导致迭代器失效

当元素的个数大于等于容器容量的个数时，就会发生扩容（在windows下以2倍进行扩容，在linux下以1.5倍进行扩容），当发生扩容时，会分配一块新的更大的存储区，将旧存储区的元素拷贝或者移动到新的存储区，释放旧存储区的内存。导致迭代器失效。

（2）插入/删除导致迭代器失效

（3）其他情况

①使用resize()改变 vector 大小，若新大小超过原容量(本质是扩容），迭代器失效；

②使用assign()替换 vector 内容，底层内存可能重新分配，迭代器失效；

③使用swap()交换两个 vector，原迭代器会指向交换后的 vector 对应元素（不算 “失效”，但逻辑上指向的内容变了）。

（4）示例

//vector的迭代器失效，插入或者删除都会导致迭代器的失效（因为会发生会扩容） //注意：释放空间时候是连续释放的，只是删除掉了元素 int main() { std::vector<int> ar{ 12,23,34,45,56,67,78,89 }; //std::vector<int>::iterator it = ar.begin(); auto it = ar.begin(); ar.insert(it,122); //扩容，删除掉原本的空间，但迭代器仍然还指向原本的空间 std::cout << "插入后的元素：" << std::endl; for (auto x : ar) { std::cout << x << " "; } std::cout << std::endl; //it=ar.erase(it); //程序崩溃，因为在插入过程后，迭代器已经失效，此时还在使用原本的迭代器 std::cout << "删除后的元素：" << std::endl; for (it=ar.begin(); it != ar.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; } 

6.避免迭代器失效

（1) 如果已知元素的个数，则可以使用reserve（）函数提前预留空间，避免频繁扩容导致迭代器失效。

（2）vector容器中，对于insert（）和erase（）函数时，使用返回值进行接收。返回值是新的有效迭代器。