第 9 章 顺序容器

C++Primer 学习记录 顺序容器

9.1 顺序容器概述

1. string和 vector，元素保存在连续空间中，优点是随机访问快，缺点是中间位置添加元素时很慢。

2. list和 forward_list，非连续存储，优点是任何位置的添加和删除元素都很快，缺点是不支持随机访问，为了访问一个元素，需要遍历在其之前的所有元素。

3. deque，双端队列，优点是支持快速随机访问、两端添加或删除元素很快，缺点是中间位置添加或删除元素较慢。

4. array，固定大小数组，与内置数组有些相似。优点是支持快速随机访问，缺点是不能改变容器大小。

5. forward_list，单项列表，可以达到与最好的手写的单向链表数据结构相当的性能。

6. 通常，使用 vector是最好的选择，除非你有很好的理由选择其他容器。当不确定使用那种容器时，可以在程序中只是用 vector和 list公共的操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时更换成 vector或 list都很方便。

9.2 容器库概览

1. 不同的容器对所存储的元素类型有其自己的特殊要求，可以为不支持特定操作需求的类型定义容器，但这种情况下就只能使用那些没有特殊要求的容器操作了。比如，

   // 假定 noDefault是一个没有默认构造函数的类型
   // init是一个 noDefault类对象，下面语句执行的是 noDefault的拷贝构造函数
   vector<noDefault> v1(10, init);  // 正确
   // 下面语句执行的是 noDefault的默认构造函数
   vector<noDefault> v1(10, init);  // 错误

2. forward_list不支持递减运算符(--)，因为它是一个单向链表，无法向后遍历。
3. 迭代器范围通常是左闭合区间[begin, end)。迭代器范围是标准库的基础，无论是顺序容器，还是关联容器；无论是否支持随机访问的容器，对其元素的访问都可以通过迭代器完成。这样，就为标准库中的所有容器都提供了一个统一的接口。
4. 构成迭代器范围的 begin和 end，它们要指向同一个容器中的元素或最后一个元素之后的位置，且 begin要在 end的前面。

5. auto与 begin或 end结合使用时，获得的迭代器类型依赖于容器类型；但以 c开头的版本总是可以获得 const_iterator的，与容器类型无关。

   auto it7 = a.begin();   // 仅当 a是 const时， it7是 const_iterator
   auto it8 = a.cbegin();  // it8是 const_iterator

6. 除 array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，而 array默认构造的容器是非空的：它包含了与其大小一样多的元素，这些元素都被默认初始化。

7. 使用一个容器的拷贝来创建另一个容器时，两个容器的类型及其元素类型必须当使用迭代器进行元素拷贝时，容器类型可以不同，元素类型也可以不同，只要能够进行转换即可。

   list<string> aut = { "the","then" }; 
   vector<const char*> aa = { "a","an" }; 
   vector<string> words1(aut);                  // 错误，容器类型不相同
   vector<string> words2(aa);                   // 错误，元素类型不相同
   list<string> words3(aa.begin(), aa.end());   // 正确，const char*可以转换为 string

8. 大小是 array类型的一部分，为了使用 array类型，必须同时指定元素类型和大小。

   array<int, 10>::size_type i;  // 容器类型包括元素类型和大小
   array<int>::size_type j;      // 错误，array<int>不是一个类型

9. 内置数组类型不可以进行拷贝或赋值操作，但 array并无此限制，但要求 array的元素类型和大小都必须一样。

   int digs[10] = {0, 1, 2};
   int cpy[3] = digs;            // 错误
   array<int, 3> digits = {0, 1, 2};
   array<int, 3> copy = digits;  // 正确

10. 调用 assign操作后，容器中旧元素会被替换，即调用 assign操作的对象容器的迭代器此时已经不可用，所以传递给 assign的迭代器不能指向调用 assign的容器。下面代码就是错误的。

    list<string> names = { "a","an", "the" };
    names.assign(names.cbegin() + 1, names.cend() - 1);  // 错误

11. 赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而 swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效（array和 string类型除外，它们仍然会失效）。不会失效可以理解为只是交换了指针所指向的地址，指针所指向的值本身并没有发生变化，所以迭代器（指向原来物理内存）仍旧有效。而真正交换元素，则会发生元素类型的拷贝构造和析构，因此物理内存发生了改变，原来的迭代器也就失效了。

12. 非成员版本的 swap在泛型编程中非常重要，统一使用非成员版本的 swap是一个好习惯！
13. 容器的相等运算符实际上是使用元素的 = 运算符实现比较的，而其他关系运算符是使用元素的 < 运算符。如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算符。

9.3 顺序容器操作

1. 用一个对象初始化容器，或将一个对象插入到容器中时，实际上放入倒容器中的是对象值的一个拷贝，而不是对象本身。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

2. insert允许我们在容器中的任意位置插入元素，而对于容器存在指向最后一个元素之后的尾后迭代器和指向第一个元素的迭代器，所以如果想在容器头部也能插入元素，insert只能将元素插入到迭代器所指定的位置之前。返回指向新添加的元素的迭代器。

3. emplace，直接利用参数来构造元素类型，并将其存储在容器中，省去了中间进行拷贝构造的过程，某些情况下运行效率会更高。
4. 对一个容器中的元素进行访问前，要先检查容器是否为空。对空容器进行访问元素的操作，就像使用一个越界的下标一样，是一种很严重的程序设计错误。
   
   • c[n]，返回元素引用，但不进行范围检查。如果下标越界，函数行为未定义！
   • c.at(n)，返回元素引用，编译器进行安全检查，如果越界，抛出 out_of_range异常。

5. 在容器中访问元素的成员函数返回的都是引用。所以，如果希望使用 auto变量来改变元素值，需要将变量定义为引用类型。

   auto  v1 = c.back();    // v1是一个值拷贝
   auto &v2 = c.back();    // v2是一个引用

6. erase操作，删除迭代器所指定的元素，返回一个指向被删除元素之后元素的迭代器。在遍历操作中删除某些特定值时，可以使用如下语句递增循环变量。
   iter = vec.erase(iter);

7. 由于 forward_list中结点只存有后继节点的地址，无法访问其前驱。所以添加和删除forward_\list中元素的操作是通过改变给定元素之后的元素来完成的。在遍历操作中对forward_\list进行删除或添加元素的操作，需要使用到两个迭代器————一个指向我们要处理的元素，另一个指向其前驱。
   
   • 定义了首前迭代器 before_begin，指向链表首元素之前并不存在的元素。
   • insert_after(p, n, t)，在迭代器 p之后的位置插入元素，返回指向最后一个插入元素的迭代器。
   • erase_after(p)，删除 p指向的位置之后的元素。

8. 改变容器元素大。如果当前大小大于所要求的大小，容器后部的元素会被删除；反之，会将新元素添加到容器后部:

   list<int> ilist(10, 42);
   ilist.resize(15);      // 将 5个值为 0的元素添加到末尾
   ilist.resize(25, -1);  // 将 10个值为 -1的元素添加到末尾
   ilist.resize(5);       // 从末尾删除 20个元素

9. 容器操作可能使迭代器、引用或指针失效，使用失效的迭代器、指针或引用是一种严重的程序设计错误。

   • vector和 string
     
     • 添加 如果存储空间被重新分配，则所有迭代器、指针或引用都会失效；如果未重新分配，则插入位置之前的还有效，之后的将会失效。
     • 删除 指向被删元素之前的迭代器、指针或引用仍会有效。
   • list和 forward_list，添加或删除元素后，指向容器的迭代器、指针或引用仍会有效。
   • deque
     
     • 添加 插入到首尾之外的任何位置都会导致迭代器、指针或引用失效；如果在首位置添加元素，则迭代器会失效，指向存在元素的引用和指针不会失效。
     • 删除 在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针或引用失效；如果是删除尾元素，则只有尾后迭代器会失效。删除首元素，则指向容器其他位置的迭代器、指针或引用仍会有效。
10. 如果在一个循环中插入/删除 deque、string和vector中的元素，不要缓存 end返回的迭代器，应该在每一步循环中都更新这个迭代器。

9.4 vector对象是如何增长的

1. 对于连续存储元素的容器，在添加新元素时，如果已有空间已满，则会将已有元素从旧位置空间移动到新位置空间，然后添加元素，释放旧存储空间。为了减少容器空间重新分配，标准库会预留一些空间。从而使得容器的元素数目size与容器的最大元素数目capacity往往并不相同。
2. 只有当所需空间超过当前容量时，reserve才会改变 vector的容量。如果需求大小小于或等于当前容量，reserve什么也不做，也不会退回内存空间。
3. 新标准库中，shrink_to_fit可以使得 deque、string和vector退回多余内存空间，但也可能会忽略这一请求。

9.5 额外的 string操作

1. 从一个 const char*创建 string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。如果不是以空字符结尾，则必须再传递一个计数值。如果未传递计数值且数组不是以空字符结尾，或者传递的计数值大于数组大小，则函数行为未定义。

   const char *cp = "Hello";
   char noNull = {'H', 'i'};
   string s1(cp);             // s1 == "Hello"
   string s2(noNull, 2);      // s2 == "Hi"
   string s3(noNull);         // 行为未定义！
   string s4(noNull, 3);      // 行为未定义！

2. string s(s2, pos2, len2)，不管 len2的值是多少，构造函数自多拷贝到 s2的末尾，不会报错。

3. string搜索函数返回 string::size_type值，该值是一个 unsigned类型，所以最好不要使用 int或其他带符号类型来保持这些函数的返回值！
4. 对于 string搜索函数，查找参数指定的字符串，若找到，则返回相应位置的下标，否则返回 npos。 npos是一个 const string::size_type类型，并初始化值为 -1，是一个 unsigned类型，此初始值意味着 npos等于任何 string最大的可能大小。

9.6 容器适配器

1. 适配器，使得某种事物的行为看起来像另外一种事物一样。标准库中，有容器、迭代器和函数适配器三种。

2. 标准库定义了三个顺序容器适配器，stack、queue和 priority_queue。所有适配器都要求底层容器具有添加和删除元素的能力，所以适配器不能构造在 array之上。另外，还都要求具有访问尾元素的能力，所以 forward_list也不行。

   • stack，默认是基于 deque实现的。只要求 push_back、pop_back、和 back操作，因此可以使用除 array和 forward_list之外的任何容器类型来构造。
   • queue，默认是基于 deque实现的。要求 back、push_back、front和 push_front，因此他可以构造于 list或 deque之上，而不能构造于 vector之上。
   • priority_queue，默认是基于 vector实现的。除了 front、push_back和 pop_back之外，还要求随机访问能力，因此可以构造于 vector和 deque之上，但不能构造于 list之上。
3. 对于容器适配器，只能使用适配器操作，而不能使用底层容器类型的操作。