C++ Primer 顺序容器

一个容器就是一些特定类型对象的集合。

顺序容器 为程序员提供了控制元素存储和访问顺序的能力。

这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

下表列出了标准库中的顺序容器，所有的顺序容器都提供了快速顺序访问元素的能力。

tips: 通常使用 vector 是最好的选择，除非你有很好的理由选择其他容器。

• 除非你有很好的理由选择其他容器，否则应使用 vector。
  

  
  

• 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用 list 或 forward_list。
  

  
  

• 如果程序要求随机访问元素，应使用 vector 或 deque。
  

  
  

• 如果程序奥球在容器的中间插入或删除元素，应使用 list 或 forward_list。
  

  
  

• 如果程序需要在头尾位置插入和删除元素，但不会在中间位置进行插入或删除 *** 作，则使用 deque。
  

  
  

• 如果程序只有在读取输入时才需要在容器中间插入元素，随后需要随机访问元素，则
  • 首先，确定是否真的需要在容器中间位置添加元素。
    

    
    

    通常可以很容易地向 vector 追加数据。
    

    
    

  • 如果必须在中间位置插入元素，考虑在输入阶段使用 list，一旦输入完成，将 list 的内容拷贝到一个 vector 中。
    

    
    

注: 如果不确定应该使用哪种容器，那么可以在程序中只使用 vector 和 list 公共 *** 作：使用迭代器，不适用下标 *** 作，避免随机访问。

这样，在必要时选择使用 vector 或 list 都很方便。

顺序容器几乎可以保存任意类型的元素，甚至可以定义一个容器其元素的类型是另一个容器。

vector> lines;  // vector 的 vector
vector > lines;  // 较旧的编译器

此处 lines 是一个 vector，其元素类型是 string 的 vector。

注: 较旧的编译器可能需要在两个尖括号之间加一个空格。

标准库使用左闭合范围是因为这种范围有三种方便的性质。

假定 begin 和 end 构成一个合法的迭代器范围，则

• 如果 begin 和 end 相等，则范围为空。
  

  
  

• 如果 begin 和 end 不等，则范围至少包含一个元素，且 begin 指向该范围中的第一个元素
• 我们可以对 begin 递增若干次，使得 begin == end

zh意味着我们可以像下面的代码一样处理一个循环，而且还是安全的：

while(begin != end) {
    *begin = val;  // 范围非空，begin 指向一个元素
    ++begin;  // 移动迭代器，指向下素

注: 当不需要写访问时，应该使用 cbegin 和 cend。

每个容器类型都定义了一个默认构造函数。

除 array 之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器的大小和元素初始值参数。

如果元素类型时内置类型或者时具有默认构造函数的类类型，可以置为构造函数提供一个容器大小参数。

如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显式的元素初始值。

注: 只有顺序容器(不包括 array)的构造函数才能接受大小参数。

与内置数组一样，标准库 array 的大小也是类型的一部分。

当定义一个 array 时，除了指定元素类型，还必须指定容器大小：

array;  // 类型为：保存10个 string 的数组

为了使用array类型，我们必须同时指定元素类型和容器大小：

array::size_type i;  // 数组类型包括元素类型和数组大小
array::size_type j;  // 错误：array 不是一个类型

array 大小固定的特性也影响了它所定义的构造函数的行为。

与其它容器不同，一个默认构造的 array 是非空的：它包含与其大小一样多的元素。

如果进行列表初始化，初始值的数目必须等于或小于 array 的大小。

如果初始值数目小于 array 的大小，则它们被用来初始化 array 中考前的元素，所有剩余的元素都会进行值初始化。

虽然我们不能对内置数组进行拷贝或对象赋值 *** 作，但array并无此限制：

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;  // 错误 内置数组不支持拷贝或赋值
array digits= { 0,1,2,3,4,5,6,7,8,9 };
array copy = digits;  // 正确 只要数组类型匹配即合法

注1: assign *** 作不适用于关联容器和 array。

注2: 复制相关运算会导致指向左边容器内部的迭代器、引用和指针失效。

而 swap *** 作将容器内容交换不会导致只想容器的迭代器、引用和指针失效(容器类型为 array 和 string 的情况除外)。

顺序容器定义了一个 assign 成员，允许我们从一个不同但相容类型赋值，或者从容器的一个子序列赋值。

assign *** 作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。

例如，我们可以用 assign 实现一个 vector 中一段 char * 值赋予一个 list 中的 string：

list names;
vector oldstyle;
names = oldstyle;  // 错误：容器类型不匹配
// 正确：可以将const char* 转换为 string
names.assign(oldstyle.cbegin, oldstyle.cend);  

这段代码中对 assign 的调用将 names 中的元素替换为迭代器指定的范围中的元素的拷贝。

assign 的参数决定了容器中将有多少个元素以及它们的值都是什么。

注: 由于其旧元素被替换，因此传递给 assign 的迭代器不能指向调用 assign 的容器。

swap *** 作交换两个相同类型容器的内容。

调用 swap 之后，两个容器中的元素将会交换：

vector svec1(10);
vector svec2(24);
swap(svec1, svec2);

除 array 外，交换两个容器内容的 *** 作保证很快，因为元素本身并未交换，swap 只是交换了两个容器的内部数据结构。

注: 除 array 外，swap 不对任何元素进行拷贝、删除或插入 *** 作，因此可以保证在常数时间内完成。

元素不会移动的事实意味着，除 string 外，指向容器的迭代器、引用和指针在 swap *** 作之后不会失效，但是它们指向的元素已经属于不同的容器了。

例如，假定 iter 在 swap 之前指向 svec1[3] 的 string，那么在 swap 之后它指向 svec2[3] 的元素。

与其他容器不同，对一个 string 调用 swap 会导致迭代器、引用和指针失效。

与其他容器不同，swap 两个 array 会真正交换它们的元素。

因此交换两个 array 所需的时间与 array 中元素的数目成正比。

因此，对于 array，在 swap *** 作之后，迭代器、引用和指针所绑定的元素保持不变，但元素值已经与另一个 array 中对应元素的值进行了交换。

每个容器都支持相等运算符（== 和 !=）；除了无序关联容器外所有容器都支持关系运算符（>, >=, <, <=）。

关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。

比较两个容器实际上是进行元素的逐对比较：

• 如果两个容器具有相同大小且所有元素都两两对应相等，则两个容器相等，否则两个容器不相等。
  

  
  

• 如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
  

  
  

• 如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等元素的比较结果。
  

  
  

注: 只有当其元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。

顺序容器和关联容器的不同之处在于两者组织元素的方式。

这些不同之处直接关系到了元素如何存储、访问、添加以及删除。

向一个 vector、string 或 deque 插入元素回事所有只想容器的迭代器、引用和指针失效。

在一个 vector 或 string 的尾部之外的任何位置，或是一个 deque 的首尾之外的任何位置添加元素，都需要移动元素。

而且，向一个 vector 或 string 添加元素可能引起整个对象存储空间的重新分配。

重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。

push_back 将一个元素追加到一个容器的尾部。

除了 array 和 forward_list 之外，每个顺序容器（包括 stirng 类型）都支持 push_back。

关键概念: 当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。

push_front 将一个元素追加到一个容器的头部。

deque 像 vector 一样提供了随机访问元素的能力，但它提供了 vector 所不支持的 push_front。

deque 保证在容器首尾进行插入和删除元素的 *** 作都只花费常数时间。

与 vector 一样，在 deque 首尾之外的位置插入元素会很耗时。

insert成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。

vector、deque、list 和 string 都支持 insert 成员。

forward_list 则提供了特殊版本的insert成员。

每个 insert 函数都接受一个迭代器作为其第一个参数。

迭代器指出了在容器中什么位置放置新元素。

它可以指向容器中任何位置，包括容器尾部之后的下一个位置。

由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以 insert 函数将元素插入到迭代器所指定的位置之前。

slist.insert(iter,"Hello!");  // 将"Hello!"添加到 iter 之前的位置

注: 将元素插入到 vector、deque 和 string 中的任何位置都是合法的，然而这样做可能很耗时。

除了第一个迭代器参数之外，insert 函数还可以接受更多的参数，这与容器构造函数类似。

其中一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：

svec.insert(svec.end(),10,"Anna");

接受一对迭代器或一个初始化列表的 insert 版本将给定范围中的元素插入到指定位置之前：

vector v = {"quasin","simba',"frollo","nscarH");
// 将 v 的最后两个元素添加到 slist 的开始位置
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), ("these", “words”， "will", ngon,natn, "the", “end”});
// 运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器
slist.insert(slist.begin(), slist.begin(), slist.end);  

如果我们传递给 insert 一对迭代器，它们不能指向添加元素的目标容器。

在新标准下，接受元素个数或范围的 insert 版本返回指向第一个新加入元素的迭代器。

(在旧版本的标准库中，这些 *** 作返回void。

)如果范围为空，不插入任何元素， insert *** 作会将第一个参数返回。

通过使用 insert 的返回值，可以在容器中一个特定位置反复插入元素：

ist 1st; 
auto iter = 1st.begin(); 
while (cin » word) 
	iter = 1st. insert (iter, word);  // 等价于调用 push_front

在循环之前，我们将 iter 初始化为 lst.begin()。

第一次调用 insert 会将我们刚刚读入的 string 插入到 iter 所指向的元素之前的位置。

insert 返回的迭代器恰好指向这个新元素。

我们将此迭代器赋予 iter 并重复循环，读取下一个单词。

只要继续有单词读入，每步 while 循环就会将一个新元素插入到 iter 之前，并将 iter 改变为新加入元素的位置。

此元素为(新的)首元素。

因此，每步循环将一个新元素插入到 list 首元素之前的位置。

新标准引入了三个新成员 emplace_front、emplace 和 emplace_back，这些 *** 作构造而不是拷贝元素。

这些 *** 作分别对应 push_front、insert 和 push_back,允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。

当调用 push 或 insert 成员函数时，我们将元素类型的对象传递给它们，会创建一个局部临时对象，并将这些对象被拷贝到容器中。

而我们调用一个 emplace 成员函数时，则时将参数传递给元素类型的构造函数。

emplace 成员使用这些参数在容器管理的内存空间中直接构造元素。

注: emplace 函数在容器中直接构造元素传递给 emplace 函数的参数必须与元素类型的构造函数相匹配。

包括 array 在内的每个顺序容器都有一个 front 成员函数，而除 forward_list 之外的所有顺序容器都有一个 back 成员函数。

这两个 *** 作分别返回首元素和尾元素的引用。

程序可以通过两种不同方式来获取首元素和尾元素的引用。

直接的方法是调用 front 和 back。

间接的方法是通过解引用 begin 返回的迭代器来获得首元素的引用，以及通过递减然后解引用 end 返回的迭代器来获得尾元素的引用。

注: 对一个空容器调用 front 和 back，就像使用一个越界的下标一样，是一种严重的程序设计错误。

在容器中访问元素的成员函数（即，front、back、下标和 at）返回的都是引用。

如果容器是一个 const 对象，则返回值是 const 的引用。

如果容器不是const的，则返回值是普通引用。

提供快速随机访问的容器（string、vector、deque 和 array）也都提供下标运算符。

下标运算符接受一个下标参数，返问容器中该位置的元素的引用。

如果我们希望确保下标是合法的，可以使用 at 成员函数。

at 成员函数类似下标运算符，但如果下标越界，at 会抛出一个 out_of_range 异常。

vector svec;  // 空 vector
cout << svec[0];  // 运行时错误：svec中没有元素
cout << svec.at(0);  // 抛出一个out_of_range异常

删除元素的成员函数并不检查其参数，在删除元素之前，程序员必须确保它(们)是存在的。

pop_front 和 pop_back 成员函数分别删除首元素和尾元素。

与 vector 和 string 不支持 push_front 一样，这些类型也不支持 pop_front。

类似的，forward_list 不支持 pop_back。

这些 *** 作返回void。

如果你需要d出的元素的值，就必须在执行d出 *** 作之前保存它：

while(!list.empty()){
    process(ilist.front());  // 对ilist的首个元素进行一些处理
    ilist.pop_front();  // 完成之后删除首个元素
}

成员函数 erase 从容器中指定位置删除元素。

我们可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。

两种形式的 erase 都返回指向删除的(最后一个)元素之后位置的迭代器。

若 j 是 i 之后的元素，那么 erase(i) 将返回指向 j 的迭代器。

接受一对迭代器的 erase 版本允许我们删除一个范围内的元素：

// 删除两个迭代器表示的范围内的元素
// 返回指向最后一个被删元素之后位置的送代器
elem1 = slist.erase(elem1,elem2);  // 调用后，elem1==elem2

迭代器 elem1 指向我们要删除的第一个元素，elem2 指向我们要删除的最后一个元素之后的位置。

为了删除一个容器中的所有元素，我们既可以调用 clear，也可以用 begin 和 end 获得的迭代器作为参数调用 erase。

当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。

为了添加或删除一个元素，我们需要访问其前驱，以便改变前驱的链接。

但是，forward_list 是单向链表。

在一个单向链表中，没有简单的方法来获取一个元素的前驱。

出于这个原因，在一个 forward_list 中添加或删除元素的 *** 作是通过改变给定元素之后的元素来完成的。

这样，我们总是可以访问到被添加或删除 *** 作所影响的元素。

当在 forward_list 中添加或删除元素时，我们必须关注两个迭代器—— 一个指向我们要处理的元素，另一个指向其前驱。

我们可以用 resize 来增大或缩小容器，与往常一样，array 不支持 resize。

如果当前大小，大于所要求的大小，容器后部的元素会被删除；如果当前大小，小于新大小，会将新元素添加到容器后部：

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

resize *** 作接受一个可选的元素值参数，用来初始化添加到容器中的元素。

如果调用者未提供此参数，新元素进行值初始化。

如果容器保存的是类类型元素，且 resize 向容器添加新元素，则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。

注: 如果 resize 缩小容器，责之项背删除元素的迭代器、引用和指针都会失效；对 vector、string 或 deque 进行 resize 可能导致迭代器、指针和引用失效。

向容器中添加元素和从容器中删除元素的 *** 作可能会使指向容器元素的指针、引用或迭代器失效。

一个失效的指针、引用或迭代器将不再表示任何元素。

使用失效的指针、引用或迭代器是一种严重的程序设计错误，很可能引起与使用未初始化指针一样的问题。

在向容器添加元素后：

• 如果容器是 vector 或 string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。
  

  
  

  如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
  

  
  

• 对于 deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。
  

  
  

  如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
  

  
  

• 对于 list 和 forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
  

  
  

当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效，这应该不会令人惊讶。

毕竟，这些元素都已经被销毁了。

当我们删除一个元素后：

• 对于 list 和 forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
  

  
  

• 对于 deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。
  

  
  

  如果是删除 deque 的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
  

  
  

• 对于 vector 和 string，指向被删元素之前元素的迭代器、引用和指针仍有效。
  

  
  

  注意：当我们删除元素时，尾后迭代器总是会失效。
  

  
  

建议: 当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好方法。

由于向迭代器添加元素和删除元素的代码可能会是迭代器失效，因此必须保证每次改变容器的 *** 作之后都正确地重新定位迭代器。

这个建议对 vector、string 和 deque 尤为重要。

当我们添加/删除 vector 或 string 的元素后，或在 deque 中首元素之外任何位置添加/删除元素后，原来 end 返回的迭代器总是会失效。

因此，添加或删除元素的循环程序必须反复调用 end，而不能在循环之前保存 end 返回的迭代器，一直当作容器末尾使用。

为了支持快速随机访问，vector 将元素连续存储 —— 每个元素紧挨着前一个元素存储。

通常情况下，我们不必关心一个标准库类型是如何实现的，而只需关心它如何使用。

对于 vector 和 string，其部分实现渗透到了接口中。

向 vector 或 string 中添加元素时，如果没有空间容纳新元素，容器不可能简单地将它添加到内存中其他位置，因为元素必须连续存储。

容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。

如果我们每添加一个新元素，vector 就执行一次这样的内存分配和释放 *** 作，性能会慢到不可接受。

为了避免这种代价，标准库实现者采用了可以减少容器空间重新分配次数的策略。

当不得不获取新的内存空间时，vector 和 string 的实现通常会分配比新的空间需求更大的内存空间。

容器预留这些空间作为备用，可用来保存更多的新元素。

这样，就不需要每次添加新元素都重新分配容器的内存空间了。

这种分配策略比每次添加新元素时都重新分配容器内存空间的策略要高效得多。

其实际性能也表现得足够好，虽然 vector 在每次重新分配内存空间时都要移动所有元素，但使用此策略后，其扩张 *** 作通常比 list 和 deque 还要快。

注1: shrink_to_fit 只适用于 vector、string 和 deque。

注2: capacity 和 reserve 只适用于 vector 和 string。

注3: reserve 并不改变容器中元素的数量，它仅影响 vector 预先分配多大的内存空间。

有当需要的内存空间超过当前容量时，reserve 调用才会改变 vector 的容量。

如果需求大小大于当前容量，reserve 至少分配与需求一样大的内存空间(可能更大)。

如果需求大小小于或等于当前容量，reserve 什么也不做。

特别是，当需求大小小于当前容量时，容器不会退回内存空间。

容器的 size 是指它已经保存的元素的数目；而 capacity 则是在不分配新的内存空间的前提下它最多可以保存多少元素。

下面的代码展示了size和capacity之间的相互作用

vector ivec;
// size 应该为0 capacity 应该依赖于具体实现
cout << "ivec:size: " <::size_type ix = 0; ix != 24; ix++){
    ivec.push_back(ix);
}
// size 应该为24 capacity 应该大于等于24 具体依赖于标准库的实现
cout << "ivec:size: " <

ivec:size:0 capacity:0
ivec:size:24 capacity:32

ivec.reserve(50);  // 将 capacity 的容量设置至少为50 可能会更大
// size 的大小应该为24，capacity 的大小应该大于等于50 具体依赖于标准库的实现

ivec:size:24 capacity:50

while(ivec.size() != ivec.capacity()) {
	ivec.push_back(0);
}

ivec:size:50 capacity:50

ivec.push_back(42);  // 再添加一个元素

ivec:size:51 capacity:100

const char *cp = "Hello World!!!";  // 以空字符串结束的数组
char noNull[] = {'H', 'i'};  // 不是以空的字符串结束
string s1(cp);  // 拷贝cp中的字符直到遇到空的字符串 ，因此 s1 == "Hello World!!!"
string s2(noNull, 2);  // 从 noNull 拷贝两个字符 s2 == "Hi"
string s3(noNull);  // 未定义: noNull 不以空字符结束
string s4(cp + 6, 5);  // 从cp[6]开始拷贝5个字符 s4 == "Word" 
string s5(s1, 6, 5);  // 从s1[6]开始拷贝5个字符 s5 == "Word" 
string s6(s1, 6);  // 从s1[6]开始拷贝直至末尾 s6 == "Word" 
string s7(s1, 6, 20);  // 从s1[6]开始拷贝直至末尾 s7 == "Word" 
string s8(s1, 16);  // 抛出一个 out_of_range 的异常

s.insert(s.size(), 5, '!');  // 在 s 末尾插入5个感叹号
s.erase(s.size() - 5, 5);  // 从 s 删除最后5个字符

const char *cp = "Stately, plump Buck";
s.assign(cp, 7);  // s == "Statelyn"
s.insert(s.size(), cp + 7);  // s == "Stately, plump Buck"

string s("C++Primer"), s2 = s;  // 将s和s2初始化为"C++Primer"
s.insert(s.size(), "4thEd");  // s == "C++Primer 4th Ed."
s2.append("4thEd");  // 等价方法：将"4thEd."追加到s2

// 将 "4th" 替换为 "5th" 的等价方法
s.erase(11, 3);  // s == "C++Primer Ed."
s.insert(11, "5th");  // s == "C++ Primer 5th Ed."
// 从位置11开始，删除3个字符并插入 5th
s2.replace(11, 3, "5th");  // 等价方法：s == s2

string s2 = "pi=3.14"；
// 转换 s 中以数字开始的第一个子串，结果 d = 3.14
d=stod (s2.substr(s2.find_first_of(*'+-.0123456789*')));

stack stk(deq);  // 从 deq 拷贝元素到 stk

// 在 vector 实现的空栈
stack> str_stk;
// str_stk2 在 vector 上实现(默认底层是 deque)，初始化时保存 svec 的拷贝
stack> str_stk2(svec);  

stack 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();  // d出栈顶元素，继续循环
}