《C++ Primer 5th》笔记（9 / 19）：顺序容器

淩亂°似流年 2023-01-21 02:21 12阅读 0赞

### 文章目录 ###

*   *  顺序容器概述
     *   *  确定使用哪种顺序容器
     *  容器库概览
     *   *  迭代器
         *   *  迭代器范围
             *  使用左闭合范围蕴含的编程假定
         *  容器类型成员
         *  begin和end成员
         *  容器定义和初始化
         *   *  将一个容器初始化为另一个容器的拷贝
             *  列表初始化
             *  与顺序容器大小相关的构造函数
             *  标准库array具有固定大小
         *  赋值和swap
         *   *  使用assign（仅顺序容器）
             *  使用swap
         *  容器大小操作
         *  关系运算符
         *   *  容器的关系运算符使用元素的关系运算符完成比较
     *  顺序容器操作
     *   *  向顺序容器添加元素
         *   *  使用push\_back
             *  关键概念：容器元素是拷贝
             *  使用push\_front
             *  在容器中的特定位置添加元素
             *  插入范围内元素
             *  使用insert的返回值
             *  使用emplace 操作
         *  访问元素
         *   *  访问成员函数返回的是引用
             *  下标操作和安全的随机访问
         *  删除元素
         *   *  pop\_front和pop\_back成员函数
             *  从容器内部删除一个元素
             *  删除多个元素
         *  特殊的forward\_list操作
         *  改变容器大小
         *  容器操作可能使迭代器失效
         *   *  建议：管理迭代器
             *  编写改变容器的循环程序
             *  不要保存end返回的迭代器
     *  vector对象是如何增长
     *   *  管理容量的成员函数
         *  capacity和size
     *  额外的string操作
     *   *  构造string的其他方法
         *   *  substr操作
         *  改变string的其他方法
         *   *  append和replace函数
             *  改变string 的多种重载函数
         *  string搜索操作
         *   *  指定在哪里开始搜索
             *  逆向搜索
         *  compare函数
         *  数值转换
     *  容器适配器
     *   *  概述
         *   *  定义一个适配器
             *  栈适配器
             *  队列适配器
     *  小结

一个容器就是一些特定类型对象的集合。**顺序容器**（sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。与之相对的，将在第11章介绍的有序和无序关联容器，则根据关键字的值来存储元素。

标准库还提供了三种容器适配器，分别为容器操作定义了不同的接口，来与容器类型适配。我们将在本章末尾介绍适配器。

## 顺序容器概述 ##

下表列出了标准库中的顺序容器，所有顺序容器都提供了快速顺序访问元素的能力。但是，这些容器在以下方面都有不同的性能折中：

*  向容器添加或从容器中删除元素的代价
 *  非顺序访问容器中元素的代价

<table> 
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>vector</td> 
   <td>可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢</td> 
  </tr> 
  <tr> 
   <td>deque</td> 
   <td>双端队列。支持快速随机访问。在头尾位置插入/删除速度很快</td> 
  </tr> 
  <tr> 
   <td>list</td> 
   <td>双向链表。只支持双向顺序访问。在 list中任何位置进行插入/删除操作速度都很快</td> 
  </tr> 
  <tr> 
   <td>forward_list</td> 
   <td>单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快</td> 
  </tr> 
  <tr> 
   <td>array</td> 
   <td>固定大小数组。支持快速随机访问。不能添加或删除元素</td> 
  </tr> 
  <tr> 
   <td>string</td> 
   <td>与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快</td> 
  </tr> 
 </tbody> 
</table>

除了固定大小的array外，其他容器都提供高效、灵活的内存管理。我们可以添加和删除元素，扩张和收缩容器的大小。容器保存元素的策略对容器操作的效率有着固有的，有时是重大的影响。在某些情况下，存储策略还会影响特定容器是否支持特定操作。

例如，**string和vector**将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器的中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间中。（增删慢，读快）

**list和forward\_list**两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且，与vector、deque和 array相比，这两个容器的额外内存开销也很大（增删快，需要额外的内存，存指针）。

**deque**是一个更为复杂的数据结构。与string和 ector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价（可能）很高。但是，在 deque 的两端添加或删除元素都是很快的，与 list或forward\_list添加删除元素的速度相当。

**forward\_list和array**是新C++标准增加的类型。与内置数组相比，array是一种更安全、更容易使用的数组类型。与内置数组类似，array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。forward\_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward\_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。

**Note**：新标准库的容器比旧版本快得多，原因我们将在第13章解释。新标准库容器的性能几乎肯定与最精心优化过的同类数据结构一样好(通常会更好)。现代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。

### 确定使用哪种顺序容器 ###

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

以下是一些选择容器的基本原则：

*  除非你有很好的理由选择其他容器，否则应使用vector。
 *  如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward\_list。
 *  如果程序要求随机访问元素，应使用vector或deque。
 *  如果程序要求在容器的中间插入或删除元素，应使用list或forward\_list。如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque。（链表）
 *  如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
    
     *  首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数（第10章内容）来重排容器中的元素，从而避免在中间位置添加元素。
     *  如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。

如果程序既需要随机访问元素，又需要在容器中间位置插入元素，那该怎么办？答案取决于在list或forward\_list 中访问元素与vector或deque中插入/删除元素的相对性能。一般来说，应用中占主导地位的操作（执行的访问操作更多还是插入/删除更多）决定了容器类型的选择。在此情况下，对两种容器分别**测试**应用的性能可能就是必要的了。

**Best Praetices**：如果你不确定应该使用哪种容器，那么可以在程序中只使用vector和list公共的操作；使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用vector或list都很方便。

## 容器库概览 ##

容器类型上的操作形成了一种层次：

*  某些操作是所有容器类型都提供的（参见下表）。
 *  另外一些操作仅针对顺序容器（本章内容)、关联容器（第11章）或无序容器（第11章)。
 *  还有一些操作只适用于一小部分容器。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>类型别名</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>iterator</td> 
   <td>此容器类型的迭代器类型</td> 
  </tr> 
  <tr> 
   <td>const_iterator</td> 
   <td>可以读取元素，但不能修改元素的迭代器类型</td> 
  </tr> 
  <tr> 
   <td>size_type</td> 
   <td>无符号整数类型，足够保存此种容器类型最大可能容器的大小</td> 
  </tr> 
  <tr> 
   <td>difference_type</td> 
   <td>带符号整数类型，足够保存两个迭代器之间的距离</td> 
  </tr> 
  <tr> 
   <td>value_type</td> 
   <td>元素类型</td> 
  </tr> 
  <tr> 
   <td>reference</td> 
   <td>元素的左值类型；与value_type&amp;含义相同</td> 
  </tr> 
  <tr> 
   <td>const_reference</td> 
   <td>元素的const左值类型（即，const value_type&amp;）</td> 
  </tr> 
  <tr> 
   <td><strong>构造函数</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c;</td> 
   <td>默认构造函数，构造空容器（array）</td> 
  </tr> 
  <tr> 
   <td>C c1(c2);</td> 
   <td>构造c2的拷贝c1</td> 
  </tr> 
  <tr> 
   <td>C c(b,e);</td> 
   <td>构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持）</td> 
  </tr> 
  <tr> 
   <td>C c{a, b, c…};</td> 
   <td>列表初始化c</td> 
  </tr> 
  <tr> 
   <td><strong>赋值与swap</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>cl = c2</td> 
   <td>将c1中的元素替换为c2中元素</td> 
  </tr> 
  <tr> 
   <td>c1 = {a, b, c…}</td> 
   <td>将c1中的元素替换为列表中元素（不适用于array）</td> 
  </tr> 
  <tr> 
   <td>a.swap(b)</td> 
   <td>交换a和b的元素</td> 
  </tr> 
  <tr> 
   <td>swap(a, b)</td> 
   <td>与a.swap(b)等价</td> 
  </tr> 
  <tr> 
   <td><strong>大小</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.size()</td> 
   <td>c中元素的数目（不支持forward_list）</td> 
  </tr> 
  <tr> 
   <td>c.max_size()</td> 
   <td>c可保存的最大元素数目</td> 
  </tr> 
  <tr> 
   <td>c.empty()</td> 
   <td>若c中存储了元素，返回false，否则返回true</td> 
  </tr> 
  <tr> 
   <td><strong>添加/删除元素（不适用于array）<br>注：在不同容器中，这些操作的接口都不同</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(args)</td> 
   <td>将args中的元素拷贝进c</td> 
  </tr> 
  <tr> 
   <td>c.emplace(inits)</td> 
   <td>使用inits构造c中的一个元素</td> 
  </tr> 
  <tr> 
   <td>c.erase(args)</td> 
   <td>删除args指定的元素</td> 
  </tr> 
  <tr> 
   <td>c.clear()</td> 
   <td>删除c中的所有元素，返回void</td> 
  </tr> 
  <tr> 
   <td><strong>关系运算符</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>==，!=</td> 
   <td>所有容器都支持相等（不等）运算符</td> 
  </tr> 
  <tr> 
   <td>&lt;，&lt;=，&gt;，&gt;=</td> 
   <td>关系运算符（无序关联容器不支持）</td> 
  </tr> 
  <tr> 
   <td><strong>获取迭代器</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.begin()，c.end()</td> 
   <td>返回指向c的首元素和尾元素之后位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>c.cbegin()，c.cend()</td> 
   <td>返回const_iterator</td> 
  </tr> 
  <tr> 
   <td><strong>反向容器的额外成员（不支持forward_list）</strong></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>reverse_iterator</td> 
   <td>按逆序寻址元素的迭代器</td> 
  </tr> 
  <tr> 
   <td>const_reverse_iterator</td> 
   <td>不能修改元素的逆序迭代器</td> 
  </tr> 
  <tr> 
   <td>c.rbegin()，c.rend()</td> 
   <td>返回指向c的尾元素和首元素之前位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>c.crbegin()，c.crend()</td> 
   <td>返回const_reverse_iterator</td> 
  </tr> 
 </tbody> 
</table>

在本节中，我们将介绍对所有容器都适用的操作。本章剩余部分将聚焦于仅适用于顺序容器的操作。关联容器特有的操作将在第11章介绍。

一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义在头文件deque 中，list定义在头文件list中，以此类推。容器均定义为模板类。例如对vector，我们必须提供额外信息来生成特定的容器类型。对大多数，但不是所有容器，我们还需要额外提供元素类型信息：

list<Sales_data> //保存sales_data对象的list
    deque<double> //保存double的deque

**对容器可以保存的元素类型的限制**

顺序容器几乎可以保存任意类型的元素。特别是，我们可以定义一个容器，其元素的类型是另一个容器。这种容器的定义与任何其他容器类型完全一样:在尖括号中指定元素类型（此种情况下，是另一种容器类型）：

vector<vector<string>> lines; //vector的vector

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

**Note**：较旧的编译器可能需要在两个尖括号之间键入空格，例如，vector<vector<string> >。

虽然我们可以在容器中保存几乎任何类型，但某些容器操作对元素类型有其自己的特殊要求。我们可以为不支持特定操作需求的类型定义容器，但这种情况下就只能使用那些没有特殊要求的容器操作了。

例如，顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有默认构造函数。我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：

// assume noDefault is a type without a default constructor
    vector<noDefault> v1(10, init); // ok: element initializer supplied
    vector<noDefault> v2(10); // error: must supply an element initializer

### 迭代器 ###

与容器一样，迭代器有着公共的接口：如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。

例如，标准容器类型上的所有迭代器都允许我们访问容器中的元素，而所有迭代器都是通过解引用运算符来实现这个操作的。类似的，标准库容器的所有迭代器都定义了递增运算符，从当前元素移动到下一个元素。

下表关于容器迭代器支持的所有操作，其中有一个例外不符合公共接口特点——forward\_list迭代器不支持递减运算符（–）。（forward\_list是单向链表）

<table> 
 <thead> 
  <tr> 
   <th>.</th> 
   <th>.</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>*iter</td> 
   <td>返回迭代器iter所指元素的引用</td> 
  </tr> 
  <tr> 
   <td>iter-&gt;mem</td> 
   <td>解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem</td> 
  </tr> 
  <tr> 
   <td>++iter</td> 
   <td>令iter指示容器中的下一个元素</td> 
  </tr> 
  <tr> 
   <td>–iter</td> 
   <td>令iter指示容器中的上一个元素</td> 
  </tr> 
  <tr> 
   <td>iter1 == iter2</td> 
   <td>判断两个迭代器是否相等，<br>如果两个迭代器指示的是同一个元素<br>或者它们是同一个容器的尾后迭代器，则相等；反之，不相等</td> 
  </tr> 
  <tr> 
   <td>iter1 != iter2</td> 
   <td>判断两个迭代器是否不相等</td> 
  </tr> 
 </tbody> 
</table>

下表关于迭代器支持的算术运算，这些运算只能应用于string、vector、deque和 array的迭代器。我们不能将它们用于其他任何容器类型的迭代器。

<table> 
 <thead> 
  <tr> 
   <th>.</th> 
   <th>.</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>iter + n</td> 
   <td>迭代器加上一个整数值仍得一个迭代器，<br>迭代器指示的新位置与原来相比向前移动了若干个元素。<br>结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置</td> 
  </tr> 
  <tr> 
   <td>iter - n</td> 
   <td>迭代器减去一个整数值仍得一个迭代器，<br>迭代器指示的新位置与原来相比向后移动了若干个元素。<br>结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置</td> 
  </tr> 
  <tr> 
   <td>iter1 += n</td> 
   <td>迭代器加法的复合赋值语句，将iter1加n的结果赋给iter1</td> 
  </tr> 
  <tr> 
   <td>iter1 -= n</td> 
   <td>迭代器减法的复合赋值语句，将iter1减n的结果赋给iter1</td> 
  </tr> 
  <tr> 
   <td>iter1 - iter2</td> 
   <td>两个迭代器相减的结果是它们之间的距离，也就是说，<br>将运算符右侧的迭代器向前移动差值个元素后将得到左侧的迭代器。<br>参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置</td> 
  </tr> 
  <tr> 
   <td>&gt;、&gt;=、&lt;、&lt;=</td> 
   <td>迭代器的关系运算符，如果某迭代器指向的容器位置在另一个迭代器所指位置之前，<br>则说前者小于后者。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置</td> 
  </tr> 
 </tbody> 
</table>

#### 迭代器范围 ####

**Note**：迭代器范围的概念是标准库的基础。

一个**迭代器范围**（iterator range）由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是**尾元素之后的位置**（one past the last element）。这两个迭代器通常被称为begin和end，或者是first和last（可能有些误导），它们标记了容器中元素的一个范围。

虽然第二个迭代器常常被称为last，但这种叫法有些误导，因为第二个迭代器从来都不会指向范围中的最后一个元素，而是指向尾元素之后的位置。迭代器范围中的元素包含first所表示的元素以及从first开始直至last（但不包含last）之间的所有元素。

这种元素范围被称为**左闭合区间**（left-inclusive interval)，其标准数学描述为\[begin,end)。

表示范围自begin开始，于end之前结束。迭代器begin和end必须指向相同的容器。end可以与begin指向相同的位置，但不能指向begin之前的位置。

**对构成范围的迭代器的要求**

如果同时满足如下条件，两个迭代器begin和end构成一个迭代器范围：

*  它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置，
 *  我们可以通过反复递增begin来到达end。换句话说，end不在begin之前。

**WARNING**：编译器不会强制这些要求。确保程序符合这些约定是程序员的责任。

#### 使用左闭合范围蕴含的编程假定 ####

标准库使用左闭合范围是因为这种范围有三种方便的性质。假定 begin和end构成一个合法的迭代器范围，则

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

这些性质意味着我们可以像下面的代码一样用一个循环来处理一个元素范围，而这是安全的：

while (begin != end){ 
    	*begin = val;//正确:范围非空，因此begin指向一个元素
    	++begin;//移动迭代器,获取下一个元素
    }

### 容器类型成员 ###

每个容器都定义了多个类型，如在容器库概览的表格所示。在第3章，已经使用过其中三种：

1.  size\_type
2.  iterator
3.  const\_iterator

除了已经使用过的**迭代器类型**，大多数容器还提供反向迭代器。简单地说，反向迭代器就是一种反向遍历容器的迭代器，与正向迭代器相比,各种操作的含义也都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。我们将在第10章介绍更多关于反向迭代器的内容。

剩下的就是**类型别名**了，通过类型别名，我们可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用容器的value\_type。如果需要元素类型的一个引用，可以使用reference或const\_reference。这些元素相关的类型别名在泛型编程中非常有用，我们将在16章中介绍相关内容。

为了使用这些类型，我们必须显式使用其类名:

// iter是通过list<string>定义的一个迭代器类型
    list<string>::iterator iter;
    
    // count是通过vector<int>定义的一个difference_type类型
    vector<int>::difference_type count;//带符号整数类型，足够保存两个迭代器之间的距离

这些声明语句使用了作用域运算符来说明我们希望使用list<string>类的iterator成员及vector<int>类定义的difference\_type。

### begin和end成员 ###

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。

如在容器库概览的表格所示，begin和end有多个版本：带r的版本返回反向迭代器（见第10章）；以c开头的版本则返回const迭代器：

list<string> a = { "Milton", "Shakespeare", "Austen"};
    auto it1 = a.begin(); // list<string>::iterator
    auto it2 = a.rbegin(); // list<string>::reverse_iterator
    auto it3 = a.cbegin(); // list<string>::const_iterator
    auto it4 = a.crbegin();// list<string>::const_reverse_iterator

不以c开头的函数都是被重载过的。

也就是说，实际上有两个名为begin的成员。一个是const成员，返回容器的const\_iterator类型。另一个是非常量成员，返回容器的iterator类型。rbegin、end和rend的情况类似。

当我们对一个非常量对象调用这些成员时，得到的是返回 iterator 的版本。只有在对一个const对象调用这些函数时，才会得到一个const版本。与const指针和引用类似，可以将一个普通的iterator转换为对应的const\_iterator，但反之不行。

以c开头的版本是C++新标准引入的，用以支持auto与begin和end函数结合使用。过去，没有其他选择，只能显式声明希望使用哪种类型的迭代器：

// type is explicitly specified
    list<string>::iterator it5 = a.begin();
    list<string>::const_iterator it6 = a.begin();
    // iterator or const_iterator depending on a's type of a
    auto it7 = a.begin(); // const_iterator only if a is const
    auto it8 = a.cbegin(); // it8 is const_iterator

当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。但以c开头的版本还是可以获得const\_iterator的，而不管容器的类型是什么。

**Best Practies**：当**不需要写访问**时,应使用 cbegin和cend。

### 容器定义和初始化 ###

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

<table> 
 <thead> 
  <tr> 
   <th>构造器</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>C c;</td> 
   <td>默认构造函数。如果c是一个array，则c中元素按默认方式初始化；否则c为空</td> 
  </tr> 
  <tr> 
   <td>C c1(c2)</td> 
   <td>c1初始化为c2的拷贝。c1和c2必须是相同类型（即，它们必须是相同的容器类型，且保存的是相同的元素类型；对于array类型，两者还必须具有相同大小）</td> 
  </tr> 
  <tr> 
   <td>C c1=c2</td> 
   <td>同上条</td> 
  </tr> 
  <tr> 
   <td>C c{a,b,c…}</td> 
   <td>c初始化为初始化列表中元素的拷贝。列表中元素的类型必须与c的元素类型相容。对于array类型，列表中元素数目必须等于或小于array的大小，任何遗漏的元素都进行值初始化（参见第3章）</td> 
  </tr> 
  <tr> 
   <td>C c={a,b,c…}</td> 
   <td>同上条</td> 
  </tr> 
  <tr> 
   <td>C c(b, e)</td> 
   <td>c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与c的元素类型相容（array不适用）</td> 
  </tr> 
  <tr> 
   <td>只有顺序容器（不包括array）的构造函数才能接受大小参数</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C seq(n)</td> 
   <td>seq包含n个元素，这些元素进行了值初始化；此构造函数是explicit的。（string不适用）</td> 
  </tr> 
  <tr> 
   <td>C seq(n,t)</td> 
   <td>seq包含n个初始化为值t的元素</td> 
  </tr> 
 </tbody> 
</table>

#### 将一个容器初始化为另一个容器的拷贝 ####

将一个新容器创建为另一个容器的拷贝的方法有两种：可以直接拷贝整个容器，或者  
（array除外）拷贝由一个迭代器对指定的元素范围。

为了创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配。不过，当传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了。而且，新容器和原容器中的元素类型也可以不同，只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。

// each container has three elements, initialized from the given initializers
    list<string> authors = { "Milton", "Shakespeare", "Austen"};
    vector<const char*> articles = { "a", "an", "the"};
    list<string> list2(authors); // ok: types match
    deque<string> authList(authors); // error: container types don't match
    vector<string> words(articles); // error: element types must match
    // ok: converts const char* elements to string
    forward_list<string> words(articles.begin(), articles.end());

**Note：当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型都必须相同。**

接受两个迭代器参数的构造函数用这两个迭代器表示我们想要拷贝的一个元素范围。与以往一样，两个迭代器分别标记想要拷贝的第一个元素和尾元素之后的位置。新容器的大小与范围中元素的数目相同。新容器中的每个元素都用范围中对应元素的值进行初始化。

由于两个迭代器表示一个范围，因此可以使用这种构造函数来拷贝一个容器中的子序列。例如，我们可以编写如下代码：

//拷贝元素，直到(但不包括)it指向的元素
    deque<string> authList(authors.begin(), it);//假定迭代器it表示authors中的一个元素

#### 列表初始化 ####

在新标准中，我们可以对一个容器进行列表初始化

//每个容器有三个元素，用给定的初始化器进行初始化
    list<string> authors = { "Milton","Shakespeare"，"Austen"};
    vector<const char*> articles = {  "a", "an" ,"the" } ;

当这样做时，我们就显式地指定了容器中每个元素的值。对于除array之外的容器类型，初始化列表还隐含地指定了容器的大小：容器将包含与初始值一样多的元素。

#### 与顺序容器大小相关的构造函数 ####

除了与关联容器相同的构造函数外，顺序容器（array除外）还提供另一个构造函数，它接受一个容器大小和一个（可选的）元素初始值。如果我们不提供元素初始值，则标准库会创建一个值初始化器：

vector<int> ivec(10, -1); // ten int elements, each initialized to -1
    list<string> svec(10, "hi!"); // ten strings; each element is "hi!"
    forward_list<int> ivec(10); // ten elements, each initialized to 0
    deque<string> svec(10); // ten elements, each an empty string

如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数。如果元素类型没有默认构造函数，除了大小参数外，还必须指定一个显式的元素初始值。

**Note**：只有顺序容器的构造函数才接受大小参数，关联容器并不支持。

#### 标准库array具有固定大小 ####

与内置数组一样，标准库array的大小也是类型的一部分。当定义一个array时，除了指定元素类型，还要指定容器大小：

array<int, 42> //类型为:保存42个int的数组
    array<string, 10> //类型为:保存10个string的数组

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

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

由于大小是array类型的一部分，array不支持普通的容器构造函数。这些构造函数都会确定容器的大小，要么隐式地，要么显式地。而允许用户向一个 array构造函数传递大小参数，最好情况下也是多余的，而且容易出错。

array大小固定的特性也影响了它所定义的构造函数的行为。与其他容器不同，一个默认构造的array是非空的：它包含了与其大小一样多的元素。这些元素都被默认初始化，就像一个内置数组中的元素那样。

**如果我们对array进行列表初始化，初始值的数目必须等于或小于array的大小**。如果初始值数目小于array的大小，则它们被用来初始化array中靠前的元素，所有剩余元素都会进行值初始化。在这两种情况下，如果元素类型是一个类类型，那么该类必须有一个默认构造函数，以使值初始化能够进行：

array<int, 10> ial;//10个默认初始化的int
    array<int, 10> ia2 = { 0,1,2,3,4,5,6,7,8,9};//列表初始化
    array<int,10> ia3 ={ 42}; //ia3 [0]为42，剩余元素为0

值得注意的是，虽然我们不能对内置数组类型进行拷贝或对象赋值操作，但array并无此限制：

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

与其他容器一样，array也要求初始值的类型必须与要创建的容器类型相同。此外,array还要求元素类型和大小也都一样，因为大小是array类型的一部分。

### 赋值和swap ###

<table> 
 <thead> 
  <tr> 
   <th>容器赋值运算</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c1=c2</td> 
   <td>将c1中的元素替换为c2中元素的拷贝。c1和c2必须具有相同的类型</td> 
  </tr> 
  <tr> 
   <td>c={a,b,c…}</td> 
   <td>将c1中元素替换为初始化列表中元素的拷贝（array不适用）</td> 
  </tr> 
  <tr> 
   <td>swap(c1, c2)</td> 
   <td>交换c1和c2中的元素。c1和c2必须具有相同的类型。swap通常比从c2向c1拷贝元素快得多</td> 
  </tr> 
  <tr> 
   <td>cl.swap(c2)</td> 
   <td>同上条</td> 
  </tr> 
  <tr> 
   <td>assign操作不适用于关联容器和array</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>seq.assign(b, e)</td> 
   <td>将seq中的元素替换为迭代器b和e所表示的范围中的元素。迭代器b和e不能指向seq中的元素</td> 
  </tr> 
  <tr> 
   <td>seq.assign(il)</td> 
   <td>将seq中的元素替换为初始化列表il中的元素</td> 
  </tr> 
  <tr> 
   <td>seq.assign(n, t)</td> 
   <td>将seq中的元素替换为n个值为t的元素</td> 
  </tr> 
 </tbody> 
</table>

**WARNING**：赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效（容器类型为array和string的情况除外）。

上表中列出的与赋值相关的运算符可用于所有容器。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝：

c1 = c2;//将c1的内容替换为c2中元素的拷贝
    c1 = { a,b,c};//赋值后，c1大小为3

第一个赋值运算后，左边容器将与右边容器相等。如果两个容器原来大小不同，赋值运算后两者的大小都与右边容器的原大小相同。第二个赋值运算后，c1的size变为3，即花括号列表中值的数目。

与内置数组不同，标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型：

array<int,10> a1 ={ 0,1,2,3,4,5,6,7,8,9};
    array<int,10> a2 ={ 0}; //所有元素值均为0
    a1 = a2;//替换a1中的元素
    a2 = { 0};//错误:不能将一个花括号列表赋予数组

由于右边运算对象的大小可能与左边运算对象的大小不同，因此 array类型不支持assign，也不允许用花括号包围的值列表进行赋值。

#### 使用assign（仅顺序容器） ####

赋值运算符要求左边和右边的运算对象具有相同的类型。它将右边运算对象中所有元素拷贝到左边运算对象中。顺序容器（array除外）还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。例如，我们可以用assgin实现将一个vector中的一段char\*值赋予一个list中的string：

list<string> names;
    vector<const char*> oldstyle;
    names = oldstyle; // error: container types don't match
    // ok: can convert from const char*to string
    names.assign(oldstyle.cbegin(), oldstyle.cend());

这段代码中对assign的调用将names中的元素替换为迭代器指定的范围中的元素的拷贝。assign的参数决定了容器中将有多少个元素以及它们的值都是什么。

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

assign的第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素：

// equivalent to slist1.clear();
    // followed by slist1.insert(slist1.begin(), 10, "Hiya!");
    list<string> slist1(1); // one element, which is the empty string
    slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !

#### 使用swap ####

swap操作交换两个相同类型容器的内容。调用swap之后，两个容器中的元素将会交换：

vector<string> svec1(10); // 10个元素的vector
    vector<string> svec2(24);// 24个元素的vector
    swap (svec1, svec2) ;

调用swap后,svecl将包含24个string元素，svec2将包含10个string.除array外，交换两个容器内容的操作保证会很快——-元素本身并未交换，swap只是交换了两个容器的内部数据结构。

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

元素不会被移动的事实意味着，除string外，指向容器的迭代器、引用和指针在swap操作之后都不会失效。它们仍指向swap操作之前所指向的那些元素。但是，在swap之后，这些元素已经属于不同的容器了。例如，假定iter在swap之前指向svec1\[3\]的string，那么在swap之后它指向svec2\[3\]的元素。与其他容器不同，对一个string调用swap会导致迭代器、引用和指针失效。

**与其他容器不同，swap两个array会真正交换它们的元素**。因此，交换两个array所需的时间与array中元素的数目成正比。

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

在新标准库中，容器既提供成员函数版本的swap，也提供非成员版本的swap。而早期标准库版本只提供成员函数版本的swap。非成员版本的swap在泛型编程中是非常重要的。统一使用非成员版本的swap是一个好习惯。

### 容器大小操作 ###

除了一个例外，每个容器类型都有三个与大小相关的操作。

1.  成员函数size（参见第3章）返回容器中元素的数目;
2.  empty当size为0时返回布尔值true，否则返回 false;
3.  max\_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。

forward\_list支持max\_size和empty，但不支持size，原因我们将在下一节解释。

### 关系运算符 ###

每个容器类型都支持相等运算符（==和!=）;除了无序关联容器外的所有容器都支持关系运算符（>、>=、<、<=）。**关系运算符左右两边的运算对象必须是相同类型的容器**，且必须保存相同类型的元素。即,我们只能将一个vector<int>与另一个vector<int>进行比较，而不能将一个vector<int>与一个list<int>或一个vector<double>进行比较。

比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式**与string的关系运算类似**：

*  如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等；否则两个容器不等。
 *  如果两个容器大小不同，但较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
 *  如果两个容器之间都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不相等的元素的比较结果。

下面的例子展示了这些关系运算符是如何工作的：

vector<int> v1 = {  1, 3, 5, 7, 9, 12 };
    vector<int> v2 = {  1, 3, 9 };
    vector<int> v3 = {  1, 3, 5, 7 };
    vector<int> v4 = {  1, 3, 5, 7, 9, 12 };
    v1 < v2 // true; v1 and v2 differ at element [2]: v1[2] is less than v2[2]
    v1 < v3 // false; all elements are equal, but v3 has fewer of them;
    v1 == v4 // true; each element is equal and v1 and v4 have the same size()
    v1 == v2 // false; v2 has fewer elements than v1

#### 容器的关系运算符使用元素的关系运算符完成比较 ####

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

容器的相等运算符实际上是使用元素的==运算符实现比较的，而其他关系运算符是使用元素的<运算符。如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算。

例如，我们在第7章中定义的Sales\_data类型并未定义==和<运算。因此，就不能比较两个保存Sales\_data元素的容器：

vector<Sales_data> storeA, storeB;
    if (storeA < storeB) // error: Sales_data has no less-than operator

## 顺序容器操作 ##

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。上一节介绍了所有容器都支持的操作。本章剩余部分将介绍顺序容器所特有的操作。

### 向顺序容器添加元素 ###

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。下表列出了向顺序容器（非array）添加元素的操作。

注意：

*  这些操作会改变容器的大小; array不支持这些操作。
 *  forward\_list有自己专有版本的insert 和emplace;
 *  forward\_list不支持push\_back 和emplace\_back。
 *  vector和string不支持push\_front和emplace\_front。
 *  向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。

向顺序容器添加元素的操作

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.push_back(t)</td> 
   <td>在c的尾部创建一个值为t或由args 创建的元素。返回void</td> 
  </tr> 
  <tr> 
   <td>c.emplace_back(args)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>c.push_front(it)</td> 
   <td>在c的头部创建一个值为t或由args 创建的元素。返回void</td> 
  </tr> 
  <tr> 
   <td>c.emplace_front(args)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>c.insert(p,t)</td> 
   <td>在迭代器p指向的元素之前创建一个值为t或由args创建的元素。返回指向新添加的元素的迭代器</td> 
  </tr> 
  <tr> 
   <td>c.emplace(p, args)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>c.insert(p, n, t)</td> 
   <td>在迭代器p指向的元素之前插入n个值为t的元素。返回指向新添加的第一个元素的迭代器：若n为0，则返回p</td> 
  </tr> 
  <tr> 
   <td>c.insert(p, b, e)</td> 
   <td>将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器；若范围为空，则返回 p</td> 
  </tr> 
  <tr> 
   <td>c.insert(p, il)</td> 
   <td>il是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器;若列表为空，则返回p</td> 
  </tr> 
 </tbody> 
</table>

当我们使用这些操作时，**必须记得不同容器使用不同的策略来分配元素空间**，而这些策略直接影响性能。在一个vector或string的尾部之外的任何位置，或是一个deque的首尾之外的任何位置添加元素，都需要移动元素。而且，向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。

（MyNote：盲猜vector和deque底层是用数组实现。）

#### 使用push\_back ####

在第3章，看到push\_back将一个元素追加到一个vector的尾部。除 array和forward\_list之外，每个顺序容器（包括string类型）都支持push\_back。

例如，下面的循环每次读取一个string 到 word中，然后追加到容器尾部：

//从标准输入读取数据，将每个单词放到容器末尾
    string word;
    while (cin >> word)
    	container.push_back (word);

对push\_back的调用在container尾部创建了一个新的元素，将container的size增大了1。该元素的值为word的**一个拷贝**。container的类型可以是list、vector或deque。  
由于string是一个字符容器,我们也可以用push\_back在string末尾添加字符:

void pluralize(size_t cnt, string &word){ 
    if (cnt > 1)
    	word.push_back ('s'); //等价于word += 's'
    }

#### 关键概念：容器元素是拷贝 ####

当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递给非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

#### 使用push\_front ####

除了push\_back、list、forward\_list和deque容器还支持名为push\_front的类似操作。此操作将元素插入到容器头部：

list<int> ilist;
    //将元素添加到ilist开头
    for (size_t ix = 0; ix != 4; ++ix)
    	ilist.push_front (ix) ;

此循环将元素0、1、2、3添加到ilist头部。每个元素都插入到list的新的开始位置（new beginning）。即，当我们插入1时，它会被放置在0之前，2被放置在1之前，依此类推。因此，在循环中以这种方式将元素添加到容器中，最终会形成逆序。在循环执行完毕后，ilist保存序列3、2、1、0。

注意，deque像vector一样提供了随机访问元素的能力，但它提供了vector所  
不支持的push\_front。deque 保证在容器首尾进行插入和删除元素的操作都只花费常数时间。与vector一样，在deque首尾之外的位置插入元素会很耗时。

#### 在容器中的特定位置添加元素 ####

push\_back和push\_front操作提供了一种方便地在顺序容器尾部或头部插入单个元素的方法。insert成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。forward\_list提供了特殊版本的insert成员，随后介绍。

每个insert函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置，包括容器尾部之后的下一个位置。由于迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以insert函数将元素插入到迭代器所指定的位置之前。

例如，下面的语句

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

将一个值为"Hello"的string插入到iter指向的元素之前的位置。

虽然某些容器不支持 push\_front操作，但它们对于insert操作并无类似的限制(插入开始位置)。因此我们可以将元素插入到容器的开始位置，而不必担心容器是否支持push\_front：

vector<string> svec;
    list<string> slist;
    //等价于调用slist.push_front("Hello! ");
    slist.insert(slist.begin(), "Hello! ");
    
    //vector不支持push_front，但我们可以插入到begin()之前
    //警告:插入到vector末尾之外的任何位置都可能很慢
    svec.insert(svec.begin() , "Hello ! " );

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

#### 插入范围内元素 ####

除了第一个迭代器参数之外，insert函数还可以接受更多的参数，这与容器构造函数类似。其中一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：

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

这行代码将10个元素插入到svec的末尾，并将所有元素都初始化为string “Anna”。

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

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

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

在新标准下，接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。（在旧版本的标准库中，这些操作返回void。）如果范围为空，不插入任何元素，insert操作会将第一个参数返回。

#### 使用insert的返回值 ####

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

list<string> lst;
    auto iter = lst.begin();
    
    while (cin >> word)
        //insert返回的迭代器恰好指向新元素。
    	iter = lst.insert(iter, word); //等价于调用push_front

Note：理解这个循环是如何工作的非常重要，特别是理解这个循环为什么等价于调用push\_front尤为重要。

#### 使用emplace 操作 ####

新标准引入了三个新成员：

1.  emplace\_front、
2.  emplace
3.  emplace\_back，

**这些操作构造而不是拷贝元素。**

这些操作分别对应

1.  push\_front、
2.  insert
3.  push\_back，

允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。

当调用push或insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。**而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数**。emplace 成员使用这些参数在容器管理的内存空间中直接构造元素。例如，假定c保存Sales\_data（参见第7章）元素：

//在c的末尾构造一个Sales_data对象
    //使用三个参数的sales_data构造函数
    c.emplace_back("978-0590353403", 25, 15.99);
    
    //错误:没有接受三个参数的push_back版本
    c.push_back("978-0590353403", 25, 15.99);
    
    //正确:创建一个临时的sales_data对象传递给push_back
    c.push_back(Sales_data("978-0590353403"，25，15.99));

其中对emplace\_back的调用和第二个push\_back调用都会创建新的Sales\_data对象。在调用emplace\_back 时，会在容器管理的内存空间中直接创建对象。而调用push\_back则会创建一个局部临时对象，并将其压入容器中。

emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配：

//iter指向c中一个元素，其中保存了sales_data元素
    c.emplace_back() ; //使用sales_data的默认构造函数
    c.emplace(iter,"999-999999999");//使用sales_data (string)
    
    //使用sales_data的接受一个工SBN、一个count和一个price的构造函数
    c.emplace_front("978-0590353403"，25，15.99);

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

### 访问元素 ###

下表列出了我们可以用来在顺序容器中访问元素的操作。如果容器中没有元素，访问操作的结果是未定义的。

注意：

*  at和下标操作只适用于string、vector、 deque和array。
 *  back不适用于forward\_list。
 *  对一个空容器调用 front和back，就像使用一个越界的下标一样，是一种严重的程序设计错误。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.back()</td> 
   <td>返回c中尾元素的引用。若c为空，函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>c.front()</td> 
   <td>返回c中首元素的引用。若c为空，函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>c[n]</td> 
   <td>返回c中下标为n的元素的引用,n是一个无符号整数。若n&gt;=c.size()，则函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>c.at(n)</td> 
   <td>返回下标为n的元素的引用。如果下标越界，则抛出一out_of_range异常</td> 
  </tr> 
 </tbody> 
</table>

包括array在内的每个顺序容器都有一个front成员函数，而除forward\_list之外的所有顺序容器都有一个back 成员函数。这两个操作分别返回首元素和尾元素的引用：

//在解引用一个迭代器或调用front或 back之前检查是否有元素
    if(!c.empty()){ 
        // val 和val2是c中第一个元素值的拷贝
        auto val = *c.begin(), val2 = c.front();
        // val3和val4是c中最后一个元素值的拷贝
        auto last = c.end();
        auto val3 = *(--last); //不能递减forward_list选代器
        auto val4 = c.back(); // forward_list不支持
    }

此程序用两种不同方式来获取c中的首元素和尾元素的引用。直接的方法是调用front和 back。而间接的方法是通过解引用begin返回的迭代器来获得首元素的引用，以及通过递减然后解引用end返回的迭代器来获得尾元素的引用。

这个程序有两点值得注意：

1.  迭代器end指向的是容器尾元素之后的（不存在的）元素。为了获取尾元素，必须首先递减此迭代器。
2.  另一个重要之处是在调用front和back(或解引用begin和 end返回的迭代器）之前，要确保c非空。如果容器为空，if中操作的行为将是未定义的。

#### 访问成员函数返回的是引用 ####

在容器中访问元素的成员函数（即，front、back、下标和at）**返回的都是引用**。如果容器是一个const对象，则返回值是const 的引用。如果容器不是const的，则返回值是普通引用，我们可以用来改变元素的值：

if (!c.empty()){ 
        c.front () = 42;//将42赋予c中的第一个元素
        auto &v = c.back ();//获得指向最后一个元素的引用
        v= 1024;//改变c中的元素
        auto v2 = c.back () ;// v2不是一个引用，它是c.back ()的一个拷贝
        v2 = 0;//未改变c中的元素
    }

与往常一样，如果我们使用auto变量来保存这些函数的返回值，并且**希望使用此变量来改变元素的值，必须记得将变量定义为引用类型**。

#### 下标操作和安全的随机访问 ####

提供快速随机访问的容器（string、vector、deque和 array）也都提供下标运算符。就像我们已经看到的那样，下标运算符接受一个下标参数，返回容器中该位置的元素的引用。给定下标必须“在范围内”（即，大于等于0，且小于容器的大小）。

保证下标有效是程序员的责任，下标运算符并不检查下标是否在合法范围内。使用越界的下标是一种严重的程序设计错误，而且编译器并不检查这种错误。

如果我们希望确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，但如果下标越界，at会抛出一个out\_of\_range异常：

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

### 删除元素 ###

与添加元素的多种方式类似，(非 array）容器也有多种删除元素的方式。下表列出了这些成员函数。

注意：

*  这些操作会改变容器的大小，所以不适用于array。
 *  forward\_list有特殊版本的erase，随后介绍。
 *  forward\_list不支持pop\_back; vector和string不支持pop\_front。
 *  删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针ING都会失效。
 *  删除元素的成员函数并不检查其参数。在删除元素之前，程序员必须确保它(们)是存在的。

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.pop_back()</td> 
   <td>删除c中尾元素。若c为空，则函数行为未定义。函数返回void</td> 
  </tr> 
  <tr> 
   <td>c.pop_front()</td> 
   <td>删除c中首元素。若c为空，则函数行为未定义。函数返回void</td> 
  </tr> 
  <tr> 
   <td>c.erase§</td> 
   <td>删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后（off-the-end）迭代器。若p是尾后迭代器,则函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>c.erase(b,e)</td> 
   <td>删除deque中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。</td> 
  </tr> 
  <tr> 
   <td>c.clear()</td> 
   <td>删除元素的成员函数并不检查其参数。在删除元素之前，程序员必须确保它(们)是存在的。</td> 
  </tr> 
 </tbody> 
</table>

#### pop\_front和pop\_back成员函数 ####

pop\_front和pop\_back成员函数分别删除首元素和尾元素。与vector和string不支持 push\_front一样，这些类型也不支持pop\_front。类似的，forward\_list不支持pop\_back。与元素访问成员函数类似，不能对一个空容器执行弹出操作。

这些操作返回void。如果你需要弹出的元素的值，就必须在执行弹出操作之前保存它：

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

#### 从容器内部删除一个元素 ####

成员函数erase从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase 都返回指向删除的(最后一个)元素之后位置的迭代器。即,若j是i之后的元素,那么erase (i)将返回指向j的迭代器。

例如，下面的循环删除一个list 中的所有奇数元素：

list<int> lst = { 0,1,2,3,4,5,6,7,8,9};
    auto it = lst.begin() ;
    while (it != lst.end() )
    	if(*it % 2) //若元素为奇数
    		it = lst.erase (it); //删除此元素
    	else
    		++it;

每个循环步中，首先检查当前元素是否是奇数。如果是，就删除该元素，并将it设置为我们所删除的元素之后的元素。如果\*it为偶数，我们将it递增，从而在下一步循环检查下一个元素。

#### 删除多个元素 ####

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

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

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

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

slist.clear(); //删除容器中所有元素
    slist.erase(slist.begin(), slist.end()) ; //等价调用

### 特殊的forward\_list操作 ###

为了理解forward\_list为什么有特殊版本的添加和删除操作，考虑当我们从一个单向链表中删除一个元素时会发生什么。如下图所示，删除一个元素会改变序列中的链接。在此情况下，删除elem3会改变elem2，elem2原来指向elem3，但删除elem3后，elem2指向了elem4。

![在这里插入图片描述][2021051401423941.png_pic_center]

当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。为了添加或删除一个元素，我们需要访问其前驱，以便改变前驱的链接。但是，forward\_list 是单向链表。在一个单向链表中，没有简单的方法来获取一个元素的前驱。出于这个原因，在一个forward\_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。这样，我们总是可以访问到被添加或删除操作所影响的元素。

（MyNote：forward\_list 是数据结构种的单向链表。）

由于这些操作与其他容器上的操作的实现方式不同，forward\_list并未定义insert、emplace和erase，而是定义了名为insert\_after、emplace\_after和erase\_after的操作。例如，在我们的例子中，为了删除elem3，应该用指向elem2的迭代器调用erase\_after。为了支持这些操作，forward\_list也定义了before\_begin，它返回一个首前（ off-the-beginning）迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素（亦即在链表首元素之前添加删除元素）。

**在forward list中插入或删除元素的操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>lst.before_begin()</td> 
   <td>返回指向链表首元素之前不存在的元素的迭代器。<br>此迭代器不能解引用。cbefore_begin()返回一个const_iterator</td> 
  </tr> 
  <tr> 
   <td>lst.cbefore_begin()</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>lst.insert_after(p, t)</td> 
   <td>在迭代器p之后的位置插入元素。t是一个对象，n是数量，<br>b和e是表示范围的一对迭代器（b和e不能指向lst内），<br>il是一个花括号列表。返回一个指向最后一个插入元素的迭代器。<br>如果范围为空，则返回p。若p为尾后迭代器，则函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>lst.insert_after(p, n, t)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>lst.insert_after(p, b, e)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>lst.insert_after(p, il)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>emplace_after(p, args)</td> 
   <td>使用args在p指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。<br>若p为尾后迭代器，则函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>lst.erase_after§</td> 
   <td>删除p指向的位置之后的元素，或删除从b之后直到（但不包含）e之间的元素。<br>返回一个指向被删元素之后元素的迭代器，若不存在这样的元素，则返回尾后迭代器。<br>如果p 指向lst的尾元素或者是一个尾后迭代器，则函数行为未定义</td> 
  </tr> 
  <tr> 
   <td>lst.erase_after(b, e)</td> 
   <td>同上一条</td> 
  </tr> 
 </tbody> 
</table>

当在forward\_list 中添加或删除元素时，我们必须关注两个迭代器：

1.  一个指向我们要处理的元素，
2.  另一个指向其前驱。

例如，从list中删除奇数元素的循环程序，将其改为从forward\_list中删除元素：

forward_list<int> flst = { 0,1,2,3,4,5,6,7,8,9};
    auto prev = flst.before_begin(); // denotes element "off the start" of flst
    auto curr = flst.begin(); // denotes the first element in flst
    while (curr != flst.end()) {  // while there are still elements to process
        if (*curr % 2) // if the element is odd
            curr = flst.erase_after(prev); // erase it and move curr
        else { 
            prev = curr; // move the iterators to denote the next
            ++curr; // element and one before the nextelement
        }
    }

### 改变容器大小 ###

如下表所描述，我们可以用resize来增大或缩小容器，与往常一样，array不支持resize。如果当前大小大于所要求的大小，容器后部的元素会被删除;如果当前大小小于新大小，会将新元素添加到容器后部：

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

resize操作接受一个可选的元素值参数，用来初始化添加到容器中的元素。如果调用者未提供此参数，新元素进行值初始化。如果容器保存的是类类型元素，且resize向容器添加新元素，则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。

注意：

*  resize不使用于array。
 *  如果resize缩小容器，则指向被删除元素的迭代器、引用和指针都会失效；对vector、string或deque进行resize可能导致迭代器、指针和引用失效。

**顺序容器大小操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.resize(n)</td> 
   <td>调整c的大小为n个元素。若n&lt;c.size()，则多出的元素被丢弃。若必须添加新元素，对新元素进行值初始化</td> 
  </tr> 
  <tr> 
   <td>c.resize(n,t)</td> 
   <td>调整c的大小为n个元素。任何新添加的元素都初始化为值t</td> 
  </tr> 
 </tbody> 
</table>

### 容器操作可能使迭代器失效 ###

**向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效**。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误，很可能引起与使用未初始化指针一样的问题

在向容器**添加**元素后：

*  如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。（MyNote：底层是用连续空间的数组实现。）
 *  对于 deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
 *  对于list和forward\_list，指向容器的迭代器（包括尾后迭代器和首前迭代器)、指针和引用仍有效。

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

当我们**删除**一个元素后：

*  对于list和forward\_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器)、引用和指针仍有效。
 *  对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除 deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响;如果是删除首元素，这些也不会受影响。
 *  对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。

**WARNING**：使用失效的迭代器、指针或引用是严重的运行时错误。

#### 建议：管理迭代器 ####

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

由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对vector、string和deque尤为重要。

#### 编写改变容器的循环程序 ####

添加/删除vector、string 或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。如果循环中调用的是insert 或erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：

// silly loop to remove even-valued elements and insert a duplicate of odd-valued elements//这silly并不意味error,
    vector<int> vi = { 0,1,2,3,4,5,6,7,8,9};
    auto iter = vi.begin(); // call begin, not cbegin because we're changing vi
    while (iter != vi.end()) { 
        if (*iter % 2) { //奇数
    	    iter = vi.insert(iter, *iter); // duplicate the current element
        	iter += 2; // advance past this element and the one inserted before it
        } else { //偶数
    	    iter = vi.erase(iter); // remove even elements
        	// don't advance the iterator; iter denotes the element after the one we erased
        }
    }

此程序删除vector中的偶数值元素，并复制每个奇数值元素。**我们在调用insert和erase后都更新迭代器，因为两者都会使迭代器失效**。

在调用erase后，不必递增迭代器，因为 erase返回的迭代器已经指向序列中下一个元素。调用insert后，需要递增迭代器两次。记住，insert在给定位置之前插入新元素，然后返回指向新插入元素的迭代器。因此，在调用insert后，iter指向新插入元素，位于我们正在处理的元素之前。我们将迭代器递增两次，恰好越过了新添加的元素和正在处理的元素，指向下一个未处理的元素。

#### 不要保存end返回的迭代器 ####

当我们添加/删除vector或string 的元素后，或在 deque 中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效。因此，**添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用**。通常C++标准库的实现中end()操作都很快，部分就是因为这个原因。

例如，考虑这样一个循环，它处理容器中的每个元素，在其后添加一个新元素。我们希望循环能跳过新添加的元素，只处理原有元素。在每步循环之后，我们将定位迭代器，使其指向下一个原有元素。如果我们试图“优化”这个循环，在循环之前保存end()返回的迭代器，一直用作容器末尾，就会导致一场灾难：

//灾难：此循环的行为是未定义的
    auto begin = v.begin (),
    	end = v.end(); //保存尾迭代器的值是一个坏主意
    while (begin != end) { 
    	//做一些处理
    	//插入新值，对begin重新赋值，否则的话它就会失效
    	++begin; //向前移动begin，因为我们想在此元素之后插入元素
    	begin = v.insert(begin, 42); //插入新值
    	++begin; //向前移动begin跳过我们刚刚加入的元素
    }

此代码的行为是未定义的。在很多标准库实现上，**此代码会导致无限循环**。问题在于我们将end操作返回的迭代器保存在一个名为end 的局部变量中。在循环体中，我们向容器中添加了一个元素，这个操作使保存在end中的迭代器失效了。这个迭代器不再指向v中任何元素，或是v中尾元素之后的位置。

**Tip**：如果在一个循环中插入/删除 deque、string或 vector 中的元素，不要缓存end返回的迭代器。

必须在每次插入操作后重新调用end()，而不能在循环开始前保存它返回的迭代器：

// safer: recalculate end on each trip whenever the loop adds/erases elements
    while (begin != v.end()) { 
        // do some processing
        ++begin; // advance begin because we want to insert after this element
        begin = v.insert(begin, 42); // insert the new value
    	++begin; // advance begin past the element we just added 
    }

## vector对象是如何增长 ##

为了支持快速随机访问，vector将元素连续存储，也就是说每个元素紧挨着前一个元素存储。通常情况下，我们不必关心一个标准库类型是如何实现的，而只需关心它如何使用。**然而**，对于vector和 string，其部分实现渗透到了接口中。

（MyNote：C++的vector与Java的ArrayList类似。）

假定容器中元素是连续存储的，且容器的大小是可变的，考虑向vector或string中添加元素会发生什么：如果没有空间容纳新元素，容器不可能简单地将它添加到内存中其他位置——因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。（MyNote：扩容）如果我们每添加一个新元素，vector就执行一次这样的内存分配和释放操作，性能会慢到不可接受。

为了避免这种代价，标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string 的实现通常会分配比新的空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。这样，就不需要每次添加新元素都重新分配容器的内存空间了。

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

### 管理容量的成员函数 ###

如下表所示，vector和string类型提供了一些成员函数，允许我们与它的实现中内存分配部分互动。

*  capacity操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。
 *  reserve操作允许我们通知容器它应该准备保存多少个元素。

> reserve  
> 英 \[rɪˈzɜːv\] 美 \[rɪˈzɜːrv\]  
> v. 预订，预约(座位、席位、房间等);保留;贮备;拥有，保持，保留(某种权利)  
> n. 储备(量);储藏(量);(动植物)保护区;自然保护区;内向;寡言少语;矜持

> reverse  
> 英 \[rɪˈvɜːs\] 美 \[rɪˈvɜːrs\]  
> v. 颠倒;彻底转变;使完全相反;撤销，废除(决定、法律等);使反转;使次序颠倒  
> n. 相反的情况(或事物);后面;背面;反面;倒挡  
> adj. 相反的;反面的;反向的;背面的;后面的

（MyNote：reserve和reverse傻傻分不清楚。）

注意：

*  shrink\_to\_fit只适用于vector、 string和deque。
 *  capacity和reserve只适用于vector和string。

**容器大小管理操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.shrink_to_fit()</td> 
   <td>请将capacity()减少为与size()相同大小</td> 
  </tr> 
  <tr> 
   <td>c.capacity()</td> 
   <td>不重新分配内存空间的话，c可以保存多少元素</td> 
  </tr> 
  <tr> 
   <td>c.reserve(n)</td> 
   <td>分配至少能容纳n个元素的内存空间</td> 
  </tr> 
 </tbody> 
</table>

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

只有当需要的内存空间超过当前容量时，reserve调用才会改变vector的容量。如果需求大小大于（>）当前容量，reserve至少分配与需求一样大的内存空间（可能更大）。

如果需求大小小于或等于当前容量，reserve什么也不做。特别是，当需求大小小于（<）当前容量时，**容器不会退回内存空间**。因此，在调用reserve之后，capacity将会大于或等于传递给reserve的参数。

这样，调用reserve永远也不会减少容器占用的内存空间。类似的，resize成员函数只改变容器中元素的数目，而不是容器的容量。我们同样不能使用resize来减少容器预留的内存空间。（MyNote：注意reserve与最大容量有关，resize与实际容量有关。）

在新标准库中，我们可以调用shrink\_to\_fit来要求deque、vector或string退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，具体的实现可以选择忽略此请求。也就是说，调用shrink\_to\_fit也并不保证一定退回内存空间。（MyNote：shrink\_to\_fit会尽力了。）

### capacity和size ###

理解capacity和size的区别非常重要。容器的size是指它已经保存的元素的数目；而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。（MyNote：注意capacity与最大容量有关，size与实际容量有关。）

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

vector<int> ivec;
    // size should be zero; capacity is implementation defined
    cout << "ivec: size: " << ivec.size()
    	<< " capacity: " << ivec.capacity() << endl;
    
    // give ivec 24 elements
    for (vector<int>::size_type ix = 0; ix != 24; ++ix)
    	ivec.push_back(ix);
    
    // size should be 24; capacity will be >= 24 and is implementation defined
    cout << "ivec: size: " << ivec.size()
    	<< " capacity: " << ivec.capacity() << endl;

当在我们的系统上运行时，这段程序得到如下输出：

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

我们知道一个空vector的size为0，显然在我们的标准库实现中一个空vector的capacity也为0。当向vector中添加元素时，我们知道size与添加的元素数目相等。而capacity至少与size一样大，具体会分配多少额外空间则视标准库具体实现而定。在我们的标准库实现中，每次添加1个元素，共添加24个元素，会使capacity变为32。

可以想象ivec的当前状态如下图所示：

![在这里插入图片描述][20210514014312443.png_pic_center]

现在可以预分配一些额外空间：

ivec.reserve(50); //将capacity至少设定为50，可能会更大
    
    //size应该为24; capacity应该大于等于50，具体值依赖于标准库实现
    cout << "ivec: size: " << ivec.size()
    	<<" capacity: " << ivec.capacity() <<endl;

程序的输出表明reserve严格按照我们需求的大小分配了新的空间：

ivec: size: 24 capacity: 50

接下来可以用光这些预留空间：

//添加元素用光多余容量
    while (ivec.size() != ivec.capacity())
    	ivec.push_back(O);
    	
    //capacity应该未改变，size和capacity不相等
    cout << "ivec: size: " << ivec.size ()
    	<<" capacity: "<< ivec.capacity () << endl;

程序输出表明此时我们确实用光了预留空间，size和 capacity相等：

ivec: size: 50 capacity: 50

由于我们只使用了预留空间，因此没有必要为vector分配新的空间。实际上，只要没有操作需求超出vector的容量，vector就不能重新分配内存空间。

如果我们现在再添加一个新元素，vector就不得不重新分配空间：

ivec.push_back(42);//再添加一个元素
    // size应该为51; capacity应该大于等于51，具体值依赖于标准库实现
    
    cout<<"ivec: size: " << ivec.size()
    	<<" capacity: "<< ivec.capacity()<< endl;

这段程序的输出为

ivec: size: 51 capacity: 100

这表明vector的实现采用的策略似乎是在每次需要分配新内存空间时将当前容量翻倍。

（MyNote：真的不够用，才去扩容。）

可以调用shrink\_to\_fit来要求vector将超出当前大小的多余内存退回给系统：

ivec.shrink_to_fit(); //要求归还内存
    // size应该未改变;capacity的值依赖于具体实现
    cout <<"ivec: size: " << ivec.size()
    	<<" capacity: "<< ivec.capacity() <<endl;

调用shrink\_to\_fit只是一个请求，标准库并**不保证**退还内存。

**Note**：每个 vector实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：**只有当迫不得已时才可以分配新的内存空间**。

只有在执行insert操作时size与capacity相等，或者调用resize或reserve时给定的大小超过当前capacity，vector才可能重新分配内存空间。会分配多少超过给定容量的额外空间，取决于具体实现。

虽然不同的实现可以采用不同的分配策略，但所有实现都应遵循一个原则：**确保用push\_back向vector添加元素的操作有高效率**。从技术角度说，就是通过在一个初始为空的vector上调用n次push\_back来创建一个n个元素的vector，所花费的时间不能超过n的常数倍。

## 额外的string操作 ##

除了顺序容器共同的操作之外，string类型还提供了一些额外的操作。这些操作中的大部分要么是提供string类和C风格字符数组之间的相互转换，要么是增加了允许我们用下标代替迭代器的版本。

标准库string类型定义了大量函数。幸运的是，这些函数使用了重复的模式。可按需查阅。

### 构造string的其他方法 ###

第3章介绍过string部分构造函数，以及其他顺序容器相同的构造函数外，string类型还支持另外三个构造函数，如表所示：

注释：

*  n、len2和pos2都是无符号值

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>string s(cp, n)</td> 
   <td>s是cp指向的数组中前n个字符的拷贝。<br>此数组至少应该包含n个字符</td> 
  </tr> 
  <tr> 
   <td>string s(s2, pos2)</td> 
   <td>s 是 string s2从下标pos2开始的字符的拷贝。<br>若pos2 &gt; s2.size ()，构造函数的行为未定义</td> 
  </tr> 
  <tr> 
   <td>string s(s2, pos2, len2)</td> 
   <td>s是string s2从下标pos2开始len2个字符的拷贝。<br>若pos2 &gt; s2.size ()，构造函数的行为未定义。<br>不管len2的值是多少，构造函数至多拷贝s2.size()-pos2个字符</td> 
  </tr> 
 </tbody> 
</table>

这些构造函数接受一个string或一个const char\*参数，还接受（可选的）指定拷贝多少个字符的参数。当我们传递给它们的是一个string 时，还可以给定一个下标来指出从哪里开始拷贝：

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

1.  通常当我们从一个const char\*创建string 时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。如果我们还传递给构造函数一个计数值，数组就不必以空字符结尾。
2.  如果我们未传递计数值且数组也未以空字符结尾，或者给定计数值大于数组大小，则构造函数的行为是未定义的。
3.  当从一个string拷贝字符时，我们可以提供一个可选的开始位置和一个计数值。开始位置必须小于或等于给定的string的大小。如果位置大于size，则构造函数抛出一个out\_of\_range异常。
4.  如果我们传递了一个计数值，则从给定位置开始拷贝这么多个字符。不管我们要求拷贝多少个字符，标准库最多拷贝到string结尾，不会更多。

#### substr操作 ####

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s.substr(pos, n)</td> 
   <td>返回一个string，包含s中从pos开始的n个字符的拷贝。pos的默认值为0。n的默认值为s.size () - pos，即拷贝从pos开始的所有字符</td> 
  </tr> 
 </tbody> 
</table>

substr操作返回一个string，它是原始string的一部分或全部的拷贝。可以传递给substr一个可选的开始位置和计数值：

string s( "hello world");
    string s2 = s.substr(0,5);// s2 = hello
    string s3 = s.substr(6);//s3 = world
    string s4 = s.substr(6,11);//s3 = world
    string s5 = s.substr(12);//抛出一个out_of_range异常

如果开始位置超过了string的大小，则substr函数抛出一个out\_of\_range异常。

如果开始位置加上计数值大于string的大小，则substr会调整计数值，只拷贝到string的末尾。

### 改变string的其他方法 ###

string类型支持顺序容器的赋值运算符以及assign、insert和erase操作。除此之外，它还定义了额外的insert和erase版本。

除了接受迭代器的insert和erase版本外，string还提供了接受下标的版本。下标指出了开始删除的位置，或是insert到给定值之前的位置：

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

标准库string类型还提供了接受C风格字符数组的insert和 assign版本。例如，我们可以将以空字符结尾的字符数组insert到或assign给一个string：

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

此处我们首先通过调用assign替换s的内容。我们赋予s的是从cp指向的地址开始的7个字符。要求赋值的字符数必须小于或等于cp 指向的数组中的字符数（不包括结尾的空字符)。

接下来在s上调用insert，我们的意图是将字符插入到s\[size()\]处（不存在的）元素之前的位置。在此例中，我们将cp开始的7个字符（至多到结尾空字符之前）拷贝到s中。

我们也可以指定将来自其他string或子字符串的字符插入到当前string中或赋予当前string：

string s = "some string", s2 = "some other string";
    s.insert(0, s2);//在s中位置0之前插入s2的拷贝
    //在s[0]之前插入s2中s2[0]开始的s2.size()个字符
    s.insert(0,s2,0,s2.size());

#### append和replace函数 ####

string类定义了两个额外的成员函数：append和replace，这两个函数可以改变string的内容。下表描述了这两个函数的功能。

append操作是在string末尾进行插入操作的一种简写形式：

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

replace操作是调用erase和insert的一种简写形式:

//将"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

此例中调用replace时，插入的文本恰好与删除的文本一样长。这不是必须的，可以插入一个更长或更短的string：

s.replace(11, 3, "Fifth");// s == "C++ Primer Fifth Ed."

在此调用中，删除了3个字符，但在其位置插入了5个新字符。

**修改string的操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s.insert(pos, args)</td> 
   <td>在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。<br>接受下标的版本返回一个指向s的引用；<br>接受迭代器的版本返回指向第一个插入字符的迭代器</td> 
  </tr> 
  <tr> 
   <td>s.erase(pos, len)</td> 
   <td>删除从位置pos开始的len个字符。如果len被省略，<br>则删除从pos开始直至s末尾的所有字符。返回一个指向s的引用</td> 
  </tr> 
  <tr> 
   <td>s.assign(args)</td> 
   <td>将s中的字符替换为args指定的字符。返回一个指向s的引用</td> 
  </tr> 
  <tr> 
   <td>s.append(args)</td> 
   <td>将args追加到s。返回一个指向s的引用</td> 
  </tr> 
  <tr> 
   <td>s.replace(range, args)</td> 
   <td>删除s中范围range内的字符，替换为args指定的字符。<br>range或者是一个下标和一个长度，或者是一对指向s 的迭代器。<br>返回一个指向s的引用</td> 
  </tr> 
 </tbody> 
</table>

**上表的args可以是下列形式之一**; append和assign可以使用所有形式。

str不能与s相同（MyNote：str与s互不wweiei），迭代器b和e不能指向s。

<table> 
 <thead> 
  <tr> 
   <th>.</th> 
   <th>.</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>str</td> 
   <td>字符串str</td> 
  </tr> 
  <tr> 
   <td>str, pos, len</td> 
   <td>str中从pos开始最多len个字</td> 
  </tr> 
  <tr> 
   <td>cp, len</td> 
   <td>从cp指向的字符数组的前（最多） len个字符</td> 
  </tr> 
  <tr> 
   <td>cp</td> 
   <td>cp指向的以空字符结尾的字符数组</td> 
  </tr> 
  <tr> 
   <td>n, c</td> 
   <td>n个字符c</td> 
  </tr> 
  <tr> 
   <td>b, e</td> 
   <td>迭代器b和e指定的范围内的字符</td> 
  </tr> 
  <tr> 
   <td>初始化列表</td> 
   <td>花括号包围的，以逗号分隔的字符列表</td> 
  </tr> 
 </tbody> 
</table>

replace和insert所允许的args形式依赖于range和pos是如何指定的。

<table> 
 <thead> 
  <tr> 
   <th>replace<br>(pos, len, args)</th> 
   <th>replace<br>(b, e, args)</th> 
   <th>insert<br>(pos, args)</th> 
   <th>insert<br>(iter, args)</th> 
   <th>args是否可以是</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T</td> 
   <td>T</td> 
   <td>T</td> 
   <td></td> 
   <td>str</td> 
  </tr> 
  <tr> 
   <td>T</td> 
   <td></td> 
   <td>T</td> 
   <td></td> 
   <td>str, pos, len</td> 
  </tr> 
  <tr> 
   <td>T</td> 
   <td>T</td> 
   <td>T</td> 
   <td></td> 
   <td>cp, len</td> 
  </tr> 
  <tr> 
   <td>T</td> 
   <td>T</td> 
   <td></td> 
   <td></td> 
   <td>cp</td> 
  </tr> 
  <tr> 
   <td>T</td> 
   <td>T</td> 
   <td>T</td> 
   <td>T</td> 
   <td>n, c</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>T</td> 
   <td></td> 
   <td>T</td> 
   <td>b, e</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>T</td> 
   <td></td> 
   <td>T</td> 
   <td>初始化列表</td> 
  </tr> 
 </tbody> 
</table>

说明：空的表示F。

#### 改变string 的多种重载函数 ####

上面表列出的append、assign、insert和replace函数有多个重载版本。根据我们如何指定要添加的字符和string 中被替换的部分，这些函数的参数有不同版本。幸运的是，这些函数有共同的接口。

assign 和 append 函数无须指定要替换string中哪个部分：

*  assign总是替换string中的所有内容，
 *  append总是将新字符追加到string末尾。

replace函数提供了两种指定删除元素范围的方式。

1.  可以通过一个位置和一个长度来指定范围，
2.  也可以通过一个迭代器范围来指定。

insert函数允许我们用两种方式指定插入点：

1.  用一个下标
2.  或一个迭代器。

在两种情况下，新元素都会插入到给定下标（或迭代器）之前的位置。

可以用好几种方式来指定要添加到string中的字符。新字符可以

*  来自于另一个string，
 *  来自于一个字符指针（指向的字符数组)，
 *  来自于一个花括号包围的字符列表，或者是一个字符和一个计数值。

当字符来自于一个string或一个字符指针时，我们可以传递一个额外的参数来控制是拷贝部分还是全部字符。

并不是每个函数都支持所有形式的参数。例如，insert就不支持下标和初始化列表参数。类似的，如果我们希望用迭代器指定插入点，就不能用字符指针指定新字符的来源。

### string搜索操作 ###

string类提供了6个不同的搜索函数，每个函数都有4个重载版本。

下表描述了这些搜索成员函数及其参数。每个搜索操作都返回一个string:size\_type值，表示匹配发生位置的下标。

如果**搜索失败**，则返回一个名为string:npos的static成员。标准库将npos定义为一个const string:size\_type类型，并初始化为值-1。由于npos是一个unsigned类型，此初始值意味着npos等于任何string最大的可能大小。

WARNING：string搜索函数返回string::size\_type值，该类型是一个unsigned类型。因此，**用一个 int或其他带符号类型来保存这些函数的返回值不是一个好主意**。

**string搜索操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s.find(args)</td> 
   <td>查找s中args第一次出现的位置</td> 
  </tr> 
  <tr> 
   <td>s.rfind(args)</td> 
   <td>查找s中args最后一次出现的位置</td> 
  </tr> 
  <tr> 
   <td>s.find_first_of(args)</td> 
   <td>在s中查找args中任何一个字符第一次出现的位置</td> 
  </tr> 
  <tr> 
   <td>s.find_last_of(args)</td> 
   <td>在s中查找args中任何一个字符最后一次出现的位置</td> 
  </tr> 
  <tr> 
   <td>s.find_first_not_of(args)</td> 
   <td>在s中查找第一个不在args中的字符</td> 
  </tr> 
  <tr> 
   <td>s.find_last_not_of(args)</td> 
   <td>在s中查找最后一个不在args中的字符</td> 
  </tr> 
 </tbody> 
</table>

**args必须是以下形式之一**

<table> 
 <thead> 
  <tr> 
   <th>.</th> 
   <th>.</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c, pos</td> 
   <td>从s中位置pos开始查找字符c。pos默认为О</td> 
  </tr> 
  <tr> 
   <td>s2, pos</td> 
   <td>从s中位置pos开始查找字符串s2。pos默认为О</td> 
  </tr> 
  <tr> 
   <td>cp, pos</td> 
   <td>从s中位置pos开始查找指针cp指向的以空字符结尾的C风格字符串。pos默认为0</td> 
  </tr> 
  <tr> 
   <td>cp, pos, n</td> 
   <td>从s中位置pos开始查找指针cp指向的数组的前n个字符。pos和 n无默认值</td> 
  </tr> 
 </tbody> 
</table>

find函数完成最简单的搜索。它查找参数指定的字符串，若找到，则返回第一个匹配位置的下标，否则返回npos:

string name ( "AnnaBelle" ) ;
    auto pos1 = name.find ( "Anna"); //pos1 == 0

这段程序返回0，即子字符串"Anna"在"AnnaBelle"中第一次出现的下标。

搜索（以及其他string操作）是**大小写敏感的**。当在string中查找子字符串时，要注意大小写:

string lowercase("annabelle");
    pos1 = lowercase.find("Anna"); // posl == npos

这段代码会将pos1置为npos，因为Anna与anna不匹配。

一个更复杂一些的问题是查找与给定字符串中任何一个字符匹配的位置。例如，下面代码定位name中的第一个数字：

string numbers("0123456789"), name("r2d2");//返回1，即，name中第一个数字的下标
    auto pos = name.find_first_of(numbers) ;

如果是要搜索第一个不在参数中的字符，我们应该调用find\_first\_not\_of。例如，为了搜索一个string中第一个非数字字符，可以这样做：

string dept("03714p3");
    //返回5——字符'p'的下标
    auto pos = dept.find_first_not_of(numbers);

#### 指定在哪里开始搜索 ####

我们可以传递给find操作一个可选的开始位置。这个可选的参数指出从哪个位置开始进行搜索。默认情况下，此位置被置为0。一种常见的程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置：

string::size_type pos = 0;
    //每步循环查找name中下一个数
    while((pos = name.find_first_of(numbers, pos))
    	!= string::npos){ 
    	cout << "found number at index : " << pos
    		<< " element is " << name[pos] << endl;
    	++pos;//移动到下一个字符
    }

while的循环条件将pos重置为从 pos开始遇到的第一个数字的下标。只要find\_first\_of返回一个合法下标，我们就打印当前结果并递增pos。

如果我们忽略了递增pos，循环就永远也不会终止。为了搞清楚原因，考虑如果不做递增运算会发生什么。在第二步循环中，我们从 pos 指向的字符开始搜索。这个字符是一个数字，因此find\_first\_of会（重复地）返回pos!

#### 逆向搜索 ####

到现在为止,我们已经用过的find操作都是由左至右搜索。标准库还提供了类似的，但由右至左搜索的操作。rfind成员函数搜索最后一个匹配，即子字符串最靠右的出现位置：

string river("Mississippi");
    auto first_pos = river.find("is") ; //返回1
    auto last_pos = river.rfind("is"); //返回4

find返回下标1，表示第一个"is"的位置，而rfind返回下标4，表示最后一个"is"的位置。

类似的，find\_last函数的功能与find\_first函数相似，只是它们返回最后一个而不是第一个匹配：

*  find\_last\_of搜索与给定string 中任何一个字符匹配的最后一个字符。
 *  find\_last\_not\_of搜索最后一个不出现在给定string中的字符。

每个操作都接受一个可选的第二参数，可用来指出从什么位置开始搜索。

### compare函数 ###

除了关系运算符外，标准库string类型还提供了一组compare函数，这些函数与C标准库的strcmp函数很相似。类似strcmp，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0、正数或负数。

compare有6个版本。根据我们是要比较两个string还是一个string与一个字符数组，参数各有不同。在这两种情况下，都可以比较整个或一部分字符串。

**s.compare的几种参数形式**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s2</td> 
   <td>比较s和s2</td> 
  </tr> 
  <tr> 
   <td>pos1, n1, s2</td> 
   <td>将s中从pos1开始的n1个字符与s2进行比较</td> 
  </tr> 
  <tr> 
   <td>pos1, n1, s2, pos2, n2</td> 
   <td>将s中从pos1开始的n1个字符与s2中从pos2开始的n2个字符进行比较</td> 
  </tr> 
  <tr> 
   <td>cp</td> 
   <td>比较s与cp指向的以空字符结尾的字符数组</td> 
  </tr> 
  <tr> 
   <td>pos1, n1, cp</td> 
   <td>将s中从pos1开始的n1个字符与cp指向的以空字符结尾的字符数组进行比较</td> 
  </tr> 
  <tr> 
   <td>pos1, n1, cp, n2</td> 
   <td>将s中从pos1开始的n1个字符与指针cp指向的地址开始的n2个字符进行比较</td> 
  </tr> 
 </tbody> 
</table>

### 数值转换 ###

string和数值之间的转换：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>to_string(val)</td> 
   <td>一组重载函数，返回数值val的string表示。val可以是任何算术类型。对每个浮点类型和int或更大的整型，都有相应版本的to_string。与往常一样，小整型会被提升</td> 
  </tr> 
  <tr> 
   <td>stoi(s, p, b)</td> 
   <td>返回s的起始子串(表示整数内容)的数值,返回值类型分别是int、long、unsigned long、long long、unsigned long long。b表示转换所用的基数，默认值为10。p是size_t指针，用来保存s中第一个非数值字符的下标，p默认为0，即，函数不保存下标</td> 
  </tr> 
  <tr> 
   <td>stol(s, p, b)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>stoul(s, p, b)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>stoll(s, p, b)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>stoull(s, p,b)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>stof(s, p)</td> 
   <td>返回s的起始子串（表示浮点数内容）的数值，返回值类型分别是float、 double 或 long double。参数p的作用与整数转换函数中一样</td> 
  </tr> 
  <tr> 
   <td>stod(s, p)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>stold(s, p)</td> 
   <td>同上一条</td> 
  </tr> 
 </tbody> 
</table>

字符串中常常包含表示数值的字符。例如，我们用两个字符的string表示数值15——字符‘1’后跟字符’5’。一般情况，一个数的字符表示不同于其数值。数值15如果保存为16位的 short类型，则其二进制位模式为0000 0000 0000 1111，而字符串"15"存为两个Latin-1编码的char，二进制位模式为0011 0001 0011 0101。第一个字节表示字符’1’，其八进制值为061，第二个字节表示’5’，其 Latin-1编码为八进制值065。

新标准引入了多个函数，可以实现数值数据与标准库 string之间的转换;

int i = 42;
    string s = to_string(i); //将整数i转换为字符表示形式
    double d = stod(s);//将字符串s转换为浮点数

此例中我们调用to\_string 将42转换为其对应的string表示，然后调用stod将此string转换为浮点值。

要转换为数值的string中第一个非空白符必须是数值中可能出现的字符：

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

在这个stod调用中，我们调用了find\_first\_of来获得s中第一个可能是数值的一部分的字符的位置。我们将s中从此位置开始的子串传递给stod。stod函数读取此参数，处理其中的字符，直至遇到不可能是数值的一部分的字符。然后它就将找到的这个数值的字符串表示形式转换为对应的双精度浮点值。

string参数中第一个非空白符必须是符号（+ 或 -）或数字。它可以以0x或0x开头来表示十六进制数。对那些将字符串转换为浮点值的函数，string参数也可以以小数点（.）开头，并可以包含e或E来表示指数部分。对于那些将字符串转换为整型值的函数，根据基数不同，string参数可以包含字母字符，对应大于数字9的数。

**Note**：如果string不能转换为一个数值，这些函数抛出一个invalid\_argument异常。如果转换得到的数值无法用任何类型来表示，则抛出一个out\_of\_range异常。

## 容器适配器 ##

### 概述 ###

除了顺序容器外，标准库还定义了三个顺序容器适配器:

1.  stack
2.  queue
3.  priority\_queue

**适配器**（adaptor）是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上，**一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样**。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。例如，stack适配器接受一个顺序容器（除array或forward\_list外)，并使其操作起来像一个stack一样。下表列出了所有容器适配器都支持的操作和类型。

**所有容器适配器都支持的操作和类型**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size_type</td> 
   <td>一种类型，足以保存当前类型的最大对象的大小</td> 
  </tr> 
  <tr> 
   <td>value_type</td> 
   <td>元素类型</td> 
  </tr> 
  <tr> 
   <td>container_type</td> 
   <td>实现适配器的底层容器类型</td> 
  </tr> 
  <tr> 
   <td>A a;</td> 
   <td>创建一个名为a的空适配器</td> 
  </tr> 
  <tr> 
   <td>A a©;</td> 
   <td>创建一个名为a的适配器，带有容器c的一个拷贝</td> 
  </tr> 
  <tr> 
   <td>关系运算符</td> 
   <td>每个适配器都支持所有关系运算符：==、!=、&lt;、&lt;=、&gt;和&gt;=这些运算符返回底层容器的比较结果</td> 
  </tr> 
  <tr> 
   <td>a.empty()</td> 
   <td>若a包含任何元素，返回false，否则返回true</td> 
  </tr> 
  <tr> 
   <td>a.size()</td> 
   <td>返回a中的元素数目</td> 
  </tr> 
  <tr> 
   <td>swap(a,b)</td> 
   <td>交换a和b的内容，a和b必须有相同类型，包括底层容器类型也必须相同</td> 
  </tr> 
  <tr> 
   <td>a.swap(b)</td> 
   <td>同上一条</td> 
  </tr> 
 </tbody> 
</table>

#### 定义一个适配器 ####

每个适配器都定义两个构造函数:默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。例如，假定deq是一个deque<int>，我们可以用deq来初始化一个新的stack，如下所示：

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

默认情况下，stack和queue是基于deque实现的，priority\_queue是在vector之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

//在vector上实现的空栈
    stack<string,vector<string>> str_stk;
    // str_stk2在vector上实现，初始化时保存svec的拷贝
    stack<string,vector<string>> str_stk2(svec);

对于一个给定的适配器，可以使用哪些容器是有限制的。所有适配器都要求容器具有添加和删除元素的能力。因此，适配器不能构造在array 之上。类似的，我们也不能用forward\_list来构造适配器，因为所有适配器都要求容器具有添加、删除以及访问尾元素的能力。

*  stack只要求push\_back、pop\_back和back操作因此可以使用除array和forward\_list之外的任何容器类型来构造stack。
 *  queue适配器要求back、push\_back、front和push\_front，因此它可以构造于list或deque之上，但不能基于vector构造。
 *  priority\_queue除了front、push\_back和pop\_back操作之外还要求随机访问能力，因此它可以构造于vector或deque 之上，但不能基于list构造。

#### 栈适配器 ####

stack类型定义在stack头文件中。下表列出了stack所支持的操作。

栈默认基于deque实现，也可以在list或vector之上实现。

**栈特有操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s.pop()</td> 
   <td>删除栈顶元素，但不返回该元素值</td> 
  </tr> 
  <tr> 
   <td>s.push(item)</td> 
   <td>创建一个新元素压入栈顶，该元素通过拷贝或移动item而来，或者由args构造</td> 
  </tr> 
  <tr> 
   <td>s.emplace(args)</td> 
   <td>同上一条</td> 
  </tr> 
  <tr> 
   <td>s.top()</td> 
   <td>返回栈顶元素，但不将元素弹出栈</td> 
  </tr> 
 </tbody> 
</table>

下面的程序展示了如何使用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个元素添加到栈中，这些元素被初始化为从О开始连续的整数。while循环遍历整个stack，获取top值，将其从栈中弹出，直至栈空。

每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作。我们只可以使用适配器操作，而不能使用底层容器类型的操作。例如，

intstack.push(ix); //intstack保存0到9十个数

此语句试图在intstack的底层deque对象上调用push\_back。虽然stack是基于deque实现的，但我们不能直接使用deque操作。不能在一个stack上调用push\_back，而必须使用stack自己的操作——push。

#### 队列适配器 ####

queue和priority\_queue适配器定义在 queue头文件中。下表列出了它们所支持的操作。

queue默认基于deque实现，priority\_queue 默认基于vector实现;

queue也可以用list或vector实现，priority\_queue也可以用deque实现。

**队列特有的操作**

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>q.pop()</td> 
   <td>返回queue的首元素或priority_queue的最高优先级的元素,但不删除此元素</td> 
  </tr> 
  <tr> 
   <td>q.front()</td> 
   <td>（只适用于queue）返回首元素，但不删除此元素</td> 
  </tr> 
  <tr> 
   <td>q.back()</td> 
   <td>（只适用于queue）返回尾元素，但不删除此元素</td> 
  </tr> 
  <tr> 
   <td>q.top()</td> 
   <td>（只适用于priority_queue）返回首元素或尾元素，但不删除此元素</td> 
  </tr> 
  <tr> 
   <td>q.push(item)</td> 
   <td>在queue末尾或priority_queue 中恰当的位置创建一个元素，其值为item</td> 
  </tr> 
  <tr> 
   <td>q.emplace(args)</td> 
   <td>在queue末尾或priority_queue 中恰当的位置创建一个元素，或者由args构造</td> 
  </tr> 
 </tbody> 
</table>

标准库queue使用一种先进先出（first-in，first-out，FIFO）的存储和访问策略。进入队列的对象被放置到队尾，而离开队列的对象则从队首删除。正如饭店按客人到达的顺序来为他们安排座位，就是一个先进先出队列的例子。

priority\_queue允许我们为队列中的元素建立优先级。新加入的元素会排在所有优先级比它低的已有元素之前。正如饭店按照客人预定时间而不是到来时间的早晚来为他们安排座位，就是一个优先队列的例子。默认情况下，标准库在元素类型上使用 < 运算符来确定相对优先级。我们将在第11章学习如何重载这个默认设置。

## 小结 ##

本章顺序容器与Java神同形似的容器

<table> 
 <thead> 
  <tr> 
   <th>C++</th> 
   <th>Java</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>vector</td> 
   <td>Vector、ArrayList</td> 
  </tr> 
  <tr> 
   <td>deque</td> 
   <td>LinkedList、ArrayDeque</td> 
  </tr> 
  <tr> 
   <td>list</td> 
   <td>LinkedList</td> 
  </tr> 
  <tr> 
   <td>forward_list</td> 
   <td>-</td> 
  </tr> 
  <tr> 
   <td>array（容量固定，不能增删元素）</td> 
   <td>ArrayList（可动态扩容，能增删元素）</td> 
  </tr> 
  <tr> 
   <td>string</td> 
   <td>String（在Java，它不是容器，另外，<br>它一旦初始化，内容就不能改变）</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td>Stack、LinkedList</td> 
  </tr> 
  <tr> 
   <td>queue</td> 
   <td>LinkedList</td> 
  </tr> 
  <tr> 
   <td>priority_queue</td> 
   <td>PriorityQueue</td> 
  </tr> 
 </tbody> 
</table>

[2021051401423941.png_pic_center]: /images/20221021/4befd58c55c246c99fbe957bee92466e.png
[20210514014312443.png_pic_center]: /images/20221021/0b079cdd9d59458cbe69e2c4727c312e.png