【C++】解析C++中的容器
目录结构：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 contents structure [-]
1 顺序容器
1.1 顺序容器的种类
| 类型 | 描述 |
| vector | 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。 |
| deque | 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。 |
| list | 双向链表。只支持双向随机访问。在list中的任何位置插入/删除操作速度都很快。 |
| forward_list | 单向链表。只支持单向顺序访问。在链表任何位置插入/删除操作速度都很快。 |
| array | 固定大小数组。支持快速随机访问。不能添加或删除元素。 |
| string | 与vector类似的容器，单专门用于保存字符。随机访问快。在尾部插入/删除速度快。 |
除了array是固定大小外（不能插入/删除元素），其它容器都提供了高效、灵活的内存管理。
string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器的中间位置插入或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必需移动到新的存储空间。
list和forward_list都是链表结构，链表在容器的任何位置添加或删除操作都非常快速。作为代价，链表就不支持快速随机访问元素：在链表中，为了访问一个元素，需要遍历整个容器。与vector、deque和array相比，这两个容器的内存开销也很大。
deque是一个双端队列结构（队列数据结构：FIFO,First In First Out）。与vector/string类似，deque支持快速随机访问元素，在deque的中间位置插入或删除元素的代价（可能）很高。但是，在deque的两端添加或删除元素都是很快的。
1.2 顺序容器的操作
容器可以保存元素类型的限制
顺序容器几乎可以保存任意类型的元素。特别是，我们可以定义一个容器，其元素的类型是另外一种容器。这种容器的定义与其他容器类型完全一样：在尖括号中指定元素类型。
vector<vector<string>> lines;//vector的vector
此处的lines是一个vector，其元素的类型是string的vector。
注意：较旧的编译器可能需要在尖括号之间键入空格，例如，vector<vector<string> >。
虽然我们可以在元素中保存几乎任何类型，但某些容器对元素类型有自己的特殊要求。我们可以为不支持特定操作需求的类型定义元素，这种情况下就只能使用那些没有特殊要求的容器操作了。
例如，顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：
//假定 noDefault 是一个没有默认构造函数的类型 vector<noDefault> v1(10,init); // 正确：提供了元素初始化器 vector<noDefault> v2(10); //错误：必须提供一个元素的初始化器 vector<int> ivec(10,-1); //正确：提供了元素初始化器，10个int元素，每个都初始化为-1 vector<string> svec(10,"Hi"); //正确：提供了元素初始化器，10个string元素，每个都初始化为"Hi" vector<int> ivec(10); //正确：int有默认初始化器，10个int元素，每个都使用默认初始化器初始化为0 vector<string> svec(10) //正确：string有默认初始化器，10个string元素，每个都使用默认初始化器初始化为空string
容器的添加、删除、移动、访问元素
标准库中的容器提供了大量的方法，每种容器之间既有相同的操作方法，也有不同的操作方法，主要是依据容器的特性而定。比如：array容器是固定大小的，所以array容器不能有添加、删除操作方法。forward_list是单向链表结构，所以forward_list不支持push_back和emplace_back操作。
除此之外，每种容器之间既有相同点，也有差异点。这里笔者就不一一列举这些异同点了。下面笔者以vector容器展示容器的增、删、查、改操作：
#include <iostream> #include <vector> int main() { // 创建一个包含数字类型的vector容器 std::vector<int> v = {7, 5, 16, 8}; //添加数字到vector容器中 v.push_back(25); v.push_back(13); //插入元素 std::vector<int>::iterator it = v.begin(); it = v.insert(it, 200); // 迭代和打印vector容器中的内容 for(int n : v) { std::cout << n << '\n'; } //清除vector中的所有元素 v.clear(); }
vector与其它容器提供了其它丰富的容器操作方法，详情可以参见标准库文档。
1.3 容器操作可能使迭代器失效
向容器中添加元素和从容器中删除元素的操作可能会使容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误，很有可能引起与未初始化指针一样的问题。
向容器添加元素后：
如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、引用和指针都会失效。如果存储空间未重新分配，则指向插入位置之前的迭代器、指针或引用仍然有效，但指向插入位置之后元素的迭代器、指针户引用将会失效。
对于deque容器，插入到首位置之外的任何位置都会导致迭代器、指针或引用失效。如果在首元素位置插入元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
对于list和forward_list容器，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针或引用仍然有效。
当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用都会失效，这应该不会惊讶。毕竟，这些元素已经被销毁了。
向容器删除元素后：
对于list和forward_list，指向容器其它位置的迭代器、指针和引用仍然有效。
对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果删除的是deque的尾元素，则尾后迭代器会失效，但其它迭代器、引用和指针不受影响；如果删除首元素，其它的元素不会受影响。
对于vector和string，指向被删除元素之前元素的迭代器、指针和引用仍然有效，指向被删除元素之后元素的迭代器、指针和引用失效。
由于向迭代器添加元素和删除元素后可能会使迭代器失效，因此必须保证每次改变容器的操作后都正确的重新定位迭代器，尤其是vector,string和deque容器。
例如：
//删除偶数元素，复制每个奇数元素 vector<int> vi = {0,1,2,3,4,5,6,7,8,9}; vector<int>::iterator iter = vi.begin(); while(iter != vi.end()){ if(*iter % 2){//是奇数 iter = vi.insert(iter,*iter);//复制元素后，重新定位迭代器 iter += 2;//向前移动迭代器，跳过当前元素以及插入到它之前的元素 }else//是偶数 iter = vi.erase(iter);//删除偶数元素，重新定位迭代器 }
1.4 Vector容器的增长机制
为了支持快速随机访问，vector将元素连续存储-每个元素紧挨着前一个元素。
假定容器中的元素是连续存储的，且容器的大小是可变的，考虑向vector或string中添加元素会发生什么：如果没有空间容纳新元素，容器不可能简单地将它添加到内存中的其他位置-因为元素必须是连续存储的。容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。如果我们每添加一个元素，vector就执行一次这样的内存分配和释放操作，性能就会慢到不可接受。
为了避免这种代价，标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。这样，就不需要每次添加新元素都重新分配容器的内存空间了。
这种分配策略比每次添加新元素时都重新分配容器内存空间的策略要高效的多。其实际性能表现得也足够好-虽然vector在每次重新分配内存空间时都要移动所有的元素，但使用此策略后，其扩张操作通常比list和deque还快。
vector和string类型提供了一些成员函数，允许我们与它的实现内存部分互动。
| 操作 | 描述 |
| c.shrink_to_fit() | 将capacity()减少为与size()相同大小 |
| c.capacity() | 不重新分配内存空间的话，c可以保存多少个元素 |
| c.reserve(n) | 分配至少能容纳n个元素的内存空间 |
shrink_to_fit只适用于vector,string,deque。capacity和reserve只适用与vector和string。reserve并不改变容器中元素的数量，它仅影响vector预先分配多大的内存空间。
capacity和size的区别，size表示它已经保存的元素的数目，capacity表示在不分配内存空间的前提下它最多可以保存多少个元素。
例如：
vector<int> ivec; //size 应该为0，capacity依赖于具体的实现 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl; //向ivec添加24个元素。 for(vector<int>::size_type ix = 0; ix != 24 ; ix ++) ivec.push_back(ix); //size应该为24；capacity应该大于或等于24,具体值依赖标准库实现 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl; 输出结果为： ivec: size : 0 capacity : 0 ivec: size : 24 capacity : 32
我们可以看出ivec的当前状态应该如下图所示：
现在可以预分配一些额外空间：
ivec.reserve(50); // 将capacity至少设置为50，可能会更大 //size应为为24;capacity应该大于等于50，具体值依赖标准库的实现 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl
输出结果为
ivec: size : 24 capacity : 50
添加元素用光预留空间：
//添加元素用光多余容量 while(ivec.size() != ivec.capacity()) ivec.push_back(0); //capacity应该未改变，size和capacity相等 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl;
输出结果为：
ivec: size : 50 capacity : 50
由于我们用完了预留空间，因此没必要为vector重新分配新的空间。实际上，只要没有超出vector容量，vector就不会添加新的元素。
如果我们再添加一个元素，vector就不得不重新分配空间:
ivec.push_back(0);//再添加一个元素 //size应该为51，capacity应该大于等于51,具体值依赖标准库实现 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl;
输出结果为：
ivec: size : 51 capacity : 100
这表明vector的实现采用的策略似乎是在每次分配新的内存空间时将当前容量翻倍。
可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回给系统：
ivec.shrink_to_fit(); //要求归还内存 //size应该未改变，capacity的值依赖具体的标准库实现 cout << " ivec: size : " << ivec.size() << " capacity : " << ivec.capacity() << endl;
调用shrink_to_fit只是一个请求，标准库不保证退换内存。
1.5 容器适配器
除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue 和 priority_queue。适配器是标准库的一个通用概念。容器、迭代器和函数都有适配器。本质上，适配器是一种机制，能使某种事物的行为看起来像另外一种事物。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。例如：stack适配器接受一个顺序容器（除array或forward_list外），并使操作看起来像stack一样。
栈适配器
stack类型定义在stack头文件中。下面展示了如何使用stack:
stack<int> intStack; // 空栈 //填满栈 for(size_t ix = 0; ix != 10; ++ix) intStack.push(ix); // intStack 保存0到9十个数 while(!intStack.empty()){// intStack中有值就继续循环 int value = intStack.top(); //使用栈顶值的代码 intStack.pop();//弹出栈顶元素，继续循环 }
其中声明语句
stack<int> intStack;//空栈
定义了一个保存整形元素的栈intStack，初始时为空。for循环将10个元素添加到栈中，这些元素被初始化从0开始连续的整数。while循环遍历整个stack，获取top值，将其从栈中弹出，直至栈空。
队列适配器
queue和priority_queue适配器定义在queue头文件中。
标准库queue是一种先进先出的存储和访问策略。进入队列的对象被安置到队尾，而离开队列的对象则从队首删除。饭店按照客人的到达顺序来为他们安排座位，就一个先进先出的案例。
下面展示了如何使用queue:
#include <queue> #include <deque> #include <iostream> int main() { std::queue<int> q;//空队列 //填满队列 for(size_t ix = 0; ix != 10; ++ix){ q.push(ix); } while(!q.empty()){ int value = q.front(); //队列首位置的值 std::cout << value << " "; q.pop();//弹出首位置的值 } std::cout << std::endl; }
输出结果：
0 1 2 3 4 5 6 7 8 9
priority_queue运行我们为队列中的元素建立优先级。新加入的元素会安排在所有优先级低于它已有元素之前。饭店按照客人的预订时间而不是到达时间的早晚来为他们安排座位，就是一个队列优先的例子。priority_queue总是会优先输出较大元素，当然我们也可以指定自定义的大小比较器。
下面展示了如何使用priority_queue:
#include <functional> #include <queue> #include <vector> #include <iostream> template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << '\n'; } int main() { std::priority_queue<int> q; for(int n : {1,8,5,6,3,4,0,9,7,2}) q.push(n); print_queue(q); std::priority_queue<int, std::vector<int>, std::greater<int> > q2; for(int n : {1,8,5,6,3,4,0,9,7,2}) q2.push(n); print_queue(q2); // 使用lambda表达式比较元素 auto cmp = [](int left, int right) {return (left ^ 1) < (right ^ 1);}; std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp); for(int n : {8,9}) q3.push(n); print_queue(q3); }
输出结果：
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
8 9 6 7 4 5 2 3 0 1
