C++标准库 -- 顺序容器 (Primer C++ 第五版 · 阅读笔记)

r囧r小猫 2024-03-23 09:53 68阅读 0赞

#### C++标准库 -- 顺序容器(Primer C++ 第五版 · 阅读笔记） ####

*  第9章 顺序容器------(持续更新)
 *   *  9.1、顺序容器概述
     *  9.2、容器库概览
     *   *  9.2.1 、迭代器
         *  9.2.2 、容器类型成员
         *  9.2.3 、begin 和 end 成员
         *  9.2.4 、容器定义和初始化
         *  9.2.5 、赋值和 swap
         *  9.2.6 、容器大小操作
         *  9.2.7 、关系运算符
     *  9.3、顺序容器操作
     *   *  9.3.1 、向顺序容器添加元素
         *  9.3.2 、访问元素
         *  9.3.3 、删除元素
         *  9.3.4 、特殊的forward\_list操作
         *  9.3.5 、改变容器大小
         *  9.3.6 、容器操作可能使迭代器失效
     *  9.4、vector对象是如何增长的
     *  9.5、额外的string 操作
     *   *  9.5.1、构造string的其他方法
         *  9.5.2、改变string的其他方法
         *  9.5.3、string搜索操作
         *  9.5.4、compare函数
         *  9.5.5、数值转换
     *  9.6、容器适配器

## 第9章 顺序容器------(持续更新) ##

> 所有容器类都共享公共的接口，不同容器按不同方式对其进行扩展。  
> 这个公共接口使容器的学习更加容易—我们基于某种容器所学习的内容也都适用于其他容器。  
> 每种容器都提供了不同的性能和功能的权衡。

### 9.1、顺序容器概述 ###

![在这里插入图片描述][69bae1edb2a749e4a2ccda0b12253474.jpeg]

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

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

![在这里插入图片描述][d17a926e38d148c1b222c4b1617801a1.png]  
除了固定大小的 `array` 外，其他容器都提供高效、灵活的内存管理。

*  `list`和 `forward_list` 两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问:为了访问一个元素，我们只能遍历整个容器。而且，与 `vector`、`deque`和 `array`相比，这两个容器的额外内存开销也很大.
 *  `deque`是一个更为复杂的数据结构。与`string`和 `vector`类似，`deque` 支持**快速的随机访问**。与`string`和 `vector`一样，在 `deque` 的中间位置添加或删除元素的代价(可能）很高。但是，在 `deque` 的两端添加或删除元素都是很快的，与 `list`或`forward_list`添加删除元素的速度相当。
 *  `forward_list` 的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，`forward_lis`t没有`size`操作，因为保存或计算其大小就会比手写链表多出额外的开销。
 *  对其他容器而言`size`保证是一个快速的常量时间的操作。

### 9.2、容器库概览 ###

一般来说，每个容器都定义在一个头文件中，**文件名与类型名相同**。即，`deque`定义头文件 `deque`中，`list`定义在头文件`list`中，以此类推。

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

*  某些操作是**所有容器**类型都提供的。
 *  另外一些操作仅针对**顺序容器**、**关联容器** 或 **无序容器**。
 *  还有一些操作**只适用于一小部分容器**。

对**所有容器**都适用的操作:

![在这里插入图片描述][507bcb318a33490f85b7a063c98cbebe.png]  
![在这里插入图片描述][869f23167ebf4770952980c91d91ebbf.png]  
![在这里插入图片描述][ed064af242ff4cc098d731726e36dbee.png]

#### 9.2.1 、迭代器 ####

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

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

> \[begin, end)

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

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

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

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

#### 9.2.2 、容器类型成员 ####

为了使用这些类型，我们必须显式使用其类名，使用作用域运算符来说明我们希望使用`list<string>`类的`iterator`成员及`vector<int>`类定义的`difference_type`:

// iter是通过list<string>定义的一个迭代器类型
    list<string>::iterator iter;
    // count是通过vector<int>定义的一个difference_ type类型
    vector<int>::difference_type count;

#### 9.2.3 、begin 和 end 成员 ####

`begin`和`end`操作生成指向容器中第一个元素和尾元素之后位置的迭代器。

*  `begin`和 `end`有多个版本:带`r`的版本返回反向迭代器;
 *  以`c`开头的版本则返回`const`迭代器:
 *  不以`c`开头的函数都是被重载过的。也就是说，实际上有两个名为 `begin` 的成员。一个是`const`成员，返回容器的`const_iterator`类型。另一个是非常量成员，返回容器的`iterator`类型。`rbegin`、`end`和`rend`的情况类似。

list<string> a = {
        "Milton","Shakespeare", "Austen" };
    
    auto itl = 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

当我们对一个非常量对象调用这些成员时，得到的是返回 `iterator` 的版本。只有在对一个`const`对象调用这些函数时，才会得到一个`const`版本。

与`const`指针和引用类似，可以将一个普通的`iterator`转换为对应的`const_iterator`，但反之不行。

我们可以用以支持`auto`与`begin`和 `end` 函数结合使用。过去，没有其他选择，只能显式声明希望使用哪种类型的迭代器:

//是iterator还是const_ iterator依赖于a的类型
    auto it7 = a.begin();//仅当a是const时，it7是const_iterator
    auto it8 = a.cbegin();// it8是const_iterator,不管容器的类型是什么

> 当不需要写访问时,应使用 `cbegin`和 `cend`。

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

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

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

![在这里插入图片描述][e390d0165a874ebd8f7cf14e2dc355ce.png]

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

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

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

//每个容器有三个元素，用给定的初始化器进行初始化
    list<string> authors = ("Milton","Shakespeare", "Austen"};
    vector<const char*> articles = {
        "a", "an", "the"};
    
    list<string> list2(authors); 		//正确:类型匹配
    deque<string> authList(authors); 	//错误:容器类型不匹配
    vector<string> words(articles);		//错误:容器类型必须匹配
    //正确:可以将const char*元素转换为string
    forward_list<string> words(articles.begin(), articles.end());

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

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

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

vector<int> ivec (10, -1);			// 10个int元素，每个都初始化为-1
    list<string> svec(10,"hi !");		// 10个strings;每个都初始化为"hi! "
    forward_list<int> ivec(10);			// 10个元素，每个都初始化为0
    deque<string> svec(10);				// 10个元素，每个都是空string

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

**标准库 `array`具有固定大小**

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

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

由于大小是`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`类型的一部分。

#### 9.2.5 、赋值和 swap ####

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

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

![在这里插入图片描述][2d14df15371345cd8da535c6afeb6247.png]

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

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

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

**使用assign（仅顺序容器)**

赋值运算符要求左边和右边的运算对象具有相同的类型。它将右边运算对象中所有元素拷贝到左边运算对象中。

顺序容器(`array`除外）还定义了一个名为`assign`的成员，允许我们从一个 **不同但相容** 的类型赋值，或者从容器的一个子序列赋值。

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

例如，我们可以用`assgin`实现将一个`vector`中的一段`char*`值赋予一个`list`中的`string`:

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

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

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

//等价于slist1.clear ();
    //后跟slist1.insert(slist1.begin(), 10, "Hiya ! ");
    list<string> slist1(1);			// 1个元素，为空string
    slist1.assign(10，"Hiya! ");	//10个元素，每个都是“Hiya !”

**使用swap**

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

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

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

> 除`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`是一个好习惯。

#### 9.2.6 、容器大小操作 ####

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

*  成员函数`size`返回容器中元素的数目;
 *  `empty` 当`size`为0时返回布尔值 `true`，否则返回 `false`;
 *  `max_size`返回一个大于或等于该类型容器所能容纳的最大元素数的值。
 *  `forward_lis`t支持`max_size`和`empty`，但不支持`size`，原因我们将在下一节解释。

#### 9.2.7 、关系运算符 ####

每个容器类型都支持相等运算符（`==`和`!=`);除了无序关联容器外的所有容器都支持关系运算符(`>`、`>=`、`<`、`<=`)。

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

比较两个容器实际上是进行元素的逐对比较。这些运算符的工作方式与`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 };
    
    vl < v2 // true; v1和v2在元素[2]处不同:v1[2]小于等于v2[2]
    v1 < v3 // false;所有元素都相等，但v3中元素数目更少
    vl == v4 // true;每个元素都相等，且v1和v4大小相同
    vl == v2 // false;v2元素数目比v1少

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

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

容器的相等运算符实际上是使用元素的`==`运算符实现比较的，而其他关系运算符是使用元素的`<`运算符。

*  如果元素类型不支持所需运算符，那么保存这种元素的容器就不能使用相应的关系运算。

### 9.3、顺序容器操作 ###

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

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

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

![在这里插入图片描述][be75803e68684939a894212ae49da319.png]

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

*  **push\_back**：除`array`和`forward_list`之外，每个顺序容器（包括`string`类型）都支持`push_back`；
 *  **push\_front**：除了`push_back`，`list`、`forward_list`和 `deque`容器还支持名为`push_front`内类似操作。此操作将元素插入到容器头部；
 *  **insert**：`insert`成员提供了更一般的添加功能，它允许我们在容器中任意位置插入0个或多个元素。`vector`、`deque`、`list`和`string`都支持`insert`成员。`forward_list`提供了特殊版本的`insert`成员，我们将在后面介绍。

> 迭代器可以指向容器中任何位置，包括容器尾部之后的下一个位置，所以迭代器可能指向容器尾部之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以`insert`函数将元素插入到迭代器**所指定的位置之前**。

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

list<string> lst;
    auto iter = lst.begin();
    while (cin >> word)
    	iter = lst.insert(iter, word); //等价于调用push_front

*  **emplace**：
    
     *  新标准引入了三个新成员一`emplace_front`、`emplace`和 `emplace_back`，这  
        些操作构造而**不是拷贝元素**。这些操作分别对应`push_front`、`insert`和`push_back`,允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。
     *  当调用`push`或`insert`成员函数时，我们将元素类型的**对象**传递给它们，这些对象被**拷贝**到容器中。而当我们调用一个`emplace`成员函数时，则是将**参数**传递给元素类型的**构造函数**。`emplace`成员使用这些参数在容器管理的内存空间中**直接构造元素**。

> **例如:** 假定c保存`sales_data`元素:

//在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`函数在容器中直接构造元素。传递给`emplace`函数的参数必须与元素类型的构造函数相匹配。

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

#### 9.3.2 、访问元素 ####

包括`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`返回的迭代器来获得尾元素的引用。

![在这里插入图片描述][5ddf0f6bb6ee48f2ab46d5ba6e867095.png]

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

在容器中访问元素的成员函数（即，`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中的元素
    }

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

下标运算符并不检查下标是否在合法范围内。如果我们希望确保下标是合法的，可以使用`at`成员函数。`at`成员函数类似下标运算符，但如果下标越界，`a`t 会抛出一个`out_of_range`异常:

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

#### 9.3.3 、删除元素 ####

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

![在这里插入图片描述][1a69a72f651a4869bb95c9633b1795c9.png]

`pop_front`和`pop_back`返回`void`。如果你需要弹出的元素的值，就必须在执行弹出操作之前**保存**它:

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

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

当添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。为了添加或删除一个元素，我们需要访问其**前驱**，以便改变**前驱**的链接。

由于这些操作与其他容器上的操作的实现方式不同，`forward_list`并未定义`insert`、`emplace`和`erase`，而是定义了名为`insert_after`、`emplace after`和`erase_after`的操作。

`forward_list`也定义了`before_begin`，它返回一个首前( `off-the-beginning`)迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素(亦即在链表首元素之前添加删除元素)。

![在这里插入图片描述][146711b5461646ec969d74e86509e5fe.png]

#### 9.3.5 、改变容器大小 ####

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

![在这里插入图片描述][05fb9d4d75c0482bac1b6c6f489c7c29.png]

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

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

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

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

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

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

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

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

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

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

添加/删除 `vector`、`string`或`deque`元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。

*  程序必须保证每个循环步中都**更新迭代器、引用或指针**。

如果循环中调用的是`insert` 或`erase`，那么更新迭代器很容易。这些操作都返回迭代器,我们可以用来更新:

//傻瓜循环，删除偶数元素，复制每个奇数元素
    vector<int> vi = {
        0,1,2,3,4,5,6,7,8,9};
    auto iter = vi.begin(); // 调用begin而不是cbegin，因为我们要改变vi
    while (iter != vi.end()){
        
    	if(*iter % 2){
        
    		iter = vi.insert(iter, *iter); //复制当前元素
    		iter += 2; //向前移动迭代器，跳过当前元素以及插入到它之前的元素
    	}else
    		iter = vi.erase(iter);
    		//删除偶数元素
    		//不应向前移动迭代器，iter指向我们删除的元素之后的元素
    }

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

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

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

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

//安全的方法:在每个循环步添加/删除元素后都重新计算end
    while (begin != v.end(){
        
    	//做一些处理
    	++begin; //向前移动begin，因为我们想在此元素之后插入元素
    	begin = v.insert(begin, 42);//插入新值
    	++begin; //向前移动begin，跳过我们刚刚加入的元素
    }

### 9.4、vector对象是如何增长的 ###

`vector`在每次重新分配内存空间时都要移动所有元素，但使用此策略后，其扩张操作通常比`list`和 `deque`还要快。

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

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

![在这里插入图片描述][0bfd42e798ca42dbb34ef515979ae06a.png]

*  只有当需要的内存空间超过当前容量时，`reserve`调用才会改变`vector`的容量。如果需求大小大于当前容量，`reserve`至少分配与需求一样大的内存空间(可能更大)。
 *  在新标准库中，我们可以调用`shrink_to_fit`来要求`deque`、`vector`或`string`退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是，具体的实现可以选择忽略此请求。也就是说,调用`shrink_to_fit`也并不保证一定退回内存空间。
 *  容器的`size`是指它已经保存的元素的数目;
 *  `capacity`则是在不分配新的内存空间的前提下它最多可以保存多少元素。

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

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

### 9.5、额外的string 操作 ###

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

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

除了已经介绍过的构造函数，以及与其他顺序容器相同的构造函数外，`string`类型还支持另外三个构造函数，如下表：

![在这里插入图片描述][b2eadde86e7e4ffd9f018ad569f53f93.png]

*  通常当我们从一个 `const char*`创建`string`时，指针指向的数组必须以**空字符结尾**，拷贝操作遇到空字符时停止。
 *  如果我们还传递给构造函数一个**计数值**，数组就不必以空字符结尾。
 *  如果我们未传递计数值且数组也未以空字符结尾，或者给定计数值大于数组大小，则构造函数的行为是**未定义的**。

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 == "World"
    string s5(s1, 6, 5);			//从s1[6]开始拷贝5个字符;s5 == "World"
    string s6(s1, 6);				//从s1[6]开始拷贝，直至s1末尾;s6 == "World!!!"
    string s7(s1, 6, 20);			//正确，只拷贝到s1末尾;s7 == "World!!!"
    string s8(s1, 16);				//抛出一个out_of_range异常

**substr 操作**

![在这里插入图片描述][7abbae7e7b374f2781655db72aaadca2.png]

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

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

*  **接受下标的版本**：下标指出了开始删除的位置，或是`insert`到给定值之前的位置:

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

*  **接受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"

*  我们也可以指定将来自其他`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());

![在这里插入图片描述][fe33da6d81fa4a29aabf2765e7889781.png]  
![在这里插入图片描述][8248bd7c57ae42bb8c909eaed8e9effc.png]

**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

**改变string的多种重载函数**  
表9.13列出的`append`、`assign`、`insert`和 `replace`函数有多个重载版本，这些函数有共同的接口。

*  `assign`和 `append`函数无须指定要替换`string` 中哪个部分: `assign`总是替换`string`中的**所有内容**，`append`总是将新字符**追加**到`string`末尾。
 *  `replace`函数提供了两种指定删除元素范围的方式。可以通过一个位置和一个长度来指定范围，也可以通过一个迭代器范围来指定。
 *  `insert`函数允许我们用两种方式指定插入点:用一个下标或一个迭代器。在两种情况下，新元素都会插入到给定下标（或迭代器）之前的位置。

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

#### 9.5.3、string搜索操作 ####

`string`类提供了6个不同的搜索函数，每个函数都有4个重载版本。表9.14描述了这些搜索成员函数及其参数。

*  每个搜索操作都返回一个`string::size_type`值，表示匹配发生位置的下标。
 *  如果搜索失败，则返回一个名为`string::npos`的`static`成员。标准库将`npos`定义为一个`const stringsize_type`类型，并初始化为值-1。由于`npos`是一个`unsigned`类型，此初始值意味着`npos`等于任何string最大的可能大小。

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

//子字符串"Anna"在"AnnaBelle"中第一次出现的下标
    string name ("AnnaBelle");
    auto pos1 = name.find("Anna"); // pos1 == 0
    
    //搜索（以及其他string操作）是大小写敏感的
    string lowercase("annabelle");
    pos1 = lowercase.find("Anna"); // posl ==npos

一个更复杂一些的问题是查找与给定字符串中**任何一个字符匹配**的位置

//定位name 中的第一个数字;
    string numbers("0123456789"), name ( "r2d2");
    //返回1，即，name中第一个数字的下标
    auto pos = name.find_first_of(numbers);
    
    //搜索第一个不在参数中的字符
    string dept("03714p3");//返回5——字符'p'的下标
    auto pos = dept.find_first_not_of(numbers);

![在这里插入图片描述][ad3af2be2e82476385ec279689f95676.png]  
![在这里插入图片描述][bbf5bfbccb154a06982cf2e31ecfc94b.png]

#### 9.5.4、compare函数 ####

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

![在这里插入图片描述][92fa3924c0d145d9b722e33d568ce960.png]

#### 9.5.5、数值转换 ####

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

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

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

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

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

![在这里插入图片描述][dab6d3467593487db2be7696f25a3c66.png]

> 如果`string`不能转换为一个数值，这些函数抛出一个 `invalid_argument`异常。如果转换得到的数值无法用任何类型来表示,则抛出一个 `out_of_range`异常。

### 9.6、容器适配器 ###

除了顺序容器外，标准库还定义了三个顺序容器适配器:`stack`、`queue`和`priority_queue`。

*  适配器（ `adaptor`）是标准库中的一个通用概念。

![9a7dd75482744bb4a0b230b4a4bdf72d.jpeg][]

**容器**、**迭代器**和**函数**都有适配器。

![在这里插入图片描述][900a0ab3fcd74fbc89556eda9c4c2285.jpeg]

*  本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。
 *  一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。

> 例如，`stack`适配器接受一个顺序容器（除`array`或`forward_list`外)，并使其操作起来像一个`stack`一样。下表列出了所有容器适配器都支持的操作和类型。

![在这里插入图片描述][864a89c1ab73430cb0397807a05d89fc.png]

**定义一个适配器**

每个适配器都定义两个构造函数:

*  默认构造函数创建一个空对象；
 *  接受一个容器的构造函数铂贝该容器来初始化适配器。

例如，假定`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`所支持的操作。下面的程序展示了如何使用`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();					//弹出栈顶元素，继续循环, 返回值为void
    }

![在这里插入图片描述][6a0f07f901534fd082e50e25c9a24df7.png]

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

**队列适配器**

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

![在这里插入图片描述][08131c53d1814a59b9f92bd281ee72b8.png]  
![在这里插入图片描述][07d2eec5600846f8a84ad8e7641d11e0.png]  
`priority_queue` 允许我们为队列中的元素**建立优先级**。

*  新加入的元素会排在所有优先级比它低的已有元素之前。饭店按照客人预定时间而不是到来时间的早晚来为他们安排座位，就是一个优先队列的例子。
 *  默认情况下，标准库在元素类型上使用`<`运算符来确定相对优先级。

**注：仅供学习参考，如有不足，欢迎指正！！！**

[69bae1edb2a749e4a2ccda0b12253474.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/06bff303e0f14e53a6fb61e2645db528.png
[d17a926e38d148c1b222c4b1617801a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6dd8225f170f435ea9a2e4aa64a10566.png
[507bcb318a33490f85b7a063c98cbebe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6046e13b2a07407ba696d2ead1cc325e.png
[869f23167ebf4770952980c91d91ebbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b9479de9fcf94f6b88a823b3d743bf23.png
[ed064af242ff4cc098d731726e36dbee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/549f76c145244a38949af0eb8ed75a61.png
[e390d0165a874ebd8f7cf14e2dc355ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c781b721b8f843a8864a2a1d1fb97393.png
[2d14df15371345cd8da535c6afeb6247.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/41ae684cc8794127ab999ecde55603d1.png
[be75803e68684939a894212ae49da319.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/69a25d9163544e18b390fbcf3ce7c586.png
[5ddf0f6bb6ee48f2ab46d5ba6e867095.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/88d69a1d151d4bb4822073a3ed4af996.png
[1a69a72f651a4869bb95c9633b1795c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2e9fa182ea614358b36b4479d5874207.png
[146711b5461646ec969d74e86509e5fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ecea3aa24d9b44e49ecb0dfa942f73ff.png
[05fb9d4d75c0482bac1b6c6f489c7c29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e9de8711f0244ad1bab05c541f8d541b.png
[0bfd42e798ca42dbb34ef515979ae06a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/41734527c60040e2a4d71eb928ee8bdd.png
[b2eadde86e7e4ffd9f018ad569f53f93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/fccb3ab2a55f485797fa31b8b4b69068.png
[7abbae7e7b374f2781655db72aaadca2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1b71c7453ec24b8bb4e54a82aca97e17.png
[fe33da6d81fa4a29aabf2765e7889781.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8cda568932054103b6d5856c76d9c895.png
[8248bd7c57ae42bb8c909eaed8e9effc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/8381e7b152d747d0b5ec7eb65875c3ac.png
[ad3af2be2e82476385ec279689f95676.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/31a82c3e1e3e45a9ab9897290c9b23b9.png
[bbf5bfbccb154a06982cf2e31ecfc94b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/4241c96b0c7f40c59212220756504cbc.png
[92fa3924c0d145d9b722e33d568ce960.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/14935d307a0640a4993fe255ca35a76f.png
[dab6d3467593487db2be7696f25a3c66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/aa7ebd7f149447eaabbc37391c69d57f.png
[9a7dd75482744bb4a0b230b4a4bdf72d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/46338cedfdd04669afc5a12733d105b4.png
[900a0ab3fcd74fbc89556eda9c4c2285.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c9bc15e856474ab3b0e14af1ff829e25.png
[864a89c1ab73430cb0397807a05d89fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c42a3d35f14748ab8e644fa766fc669d.png
[6a0f07f901534fd082e50e25c9a24df7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6d3c10848ba347638f933e1d65bb9e43.png
[08131c53d1814a59b9f92bd281ee72b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/0f8bb4c2b185463db875618d513d59fe.png
[07d2eec5600846f8a84ad8e7641d11e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/07a0d54a0d4f4a98bfc352810129d2b8.png