【C++100问】深度总结STL基本容器的使用

Myth丶恋晨 2023-07-07 08:29 65阅读 0赞

## [专栏C++学习笔记][C] ##

## 声明 ##

1）本文仅供学术交流，非商用。  
2）博主才疏学浅，文中如有不当之处，请各位指出，共同进步，谢谢。  
3）此属于第一版本，若有错误，还需继续修正与增删，还望大家多多指点。  
4）大家都共享一点点，一起为祖国科研的推进添砖加瓦。

### 文章目录 ###

*   *  专栏C++学习笔记
     *  声明
     *   *  〇、前言
         *  一、C++库引用（Import C++ Library）
         *  二、STL（Standard Template Library）
         *  三、容器（Containers）
         *  四、顺序容器（Sequence containers）
         *   *  4.1）常用操作（共同点）
             *   *  1\_添加元素
                 *  2\_访问元素
                 *  3\_删除元素
                 *  4\_改变容器大小
                 *  5\_容器操作可能使迭代器失效
             *  4.2）向量（vector）
             *   *  1\_定义和初始化：
                 *  2\_简单vector操作
                 *  3\_关键概念: vector对象能高效增长
                 *  4\_实例
             *  4.3）双端队列（deque）
             *   *  1\_实例
             *  4.4）列表（list）
             *   *  1\_实例
             *  4.5）字符串（string）
             *   *  1\_定义和初始化：
                 *  2\_简单vector操作
                 *  3\_处理字符
                 *  4\_额外操作
                 *  5\_实例
             *  4.6）容器选择
         *  五、关联容器（Associative containers）
         *   *  5.1）常用操作（共同点）
             *   *  1\_类型别名
                 *  2\_添加元素
                 *  3\_删除元素
                 *  4\_访问元素
             *  5.2）集合（set）和多重集合（multiset）
             *   *  1\_实例
             *  5.3）映射（map）和多重映射（multimap）
             *   *  1\_实例
         *  六、适配器（Adaptor）
         *   *  6.1）常用操作（共同点）
             *  6.2）栈（stack）
             *   *  1\_基本操作
                 *  2\_实例
             *  6.3）队列（queue）和优先级队列（priority\_queue）
             *   *  1\_基本操作
         *  七、无序容器（Unordered associative container）
         *   *  7.1）unordered\_map/unordered\_multimap
             *  7.2）unordered\_set/unordered\_multiset
             *   *  1\_常用操作（共同点）
         *  八、sizeof、size和capacity
         *  九、总结
     *  参考文章

### 〇、前言 ###

近期终于粗略地学习完了C++的STL容器，决心总结一波，以便复习和记录。

因为是初学者，如果有写的不对的地方，还请各位不吝赐教。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]  
以下是学习笔记总目录（更新中ing），和关于容器的章节习题。

*  [《C++ Primer》学习笔记/习题答案 总目录][C_ Primer_]

--------------------

*  [《C++ Primer》学习笔记（三）：字符串、向量和数组][C_ Primer]
 *  [《C++ Primer》习题参考答案：第3章 - 字符串、向量和数组][C_ Primer_3_ -]
 *  [《C++ Primer》学习笔记（九）：顺序容器][C_ Primer 1]
 *  [《C++ Primer》习题参考答案：第9章 - 顺序容器][C_ Primer_9_ -]
 *  [《C++ Primer》学习笔记（十一）：关联容器][C_ Primer 2]
 *  [《C++ Primer》习题参考答案：第11章 - 关联容器][C_ Primer_11_ -]

--------------------

### 一、C++库引用（Import C++ Library） ###

众所周知，常用的库引用如下：

#include <iostream> 
    #include <cstdio> 
    #include <fstream> 
    #include <algorithm> 
    #include <cmath> 
    #include <deque> 
    #include <vector> 
    #include <queue> 
    #include <string> 
    #include <cstring> 
    #include <map> 
    #include <stack> 
    #include <set>

有些太多，所以有了一个新奇的方法：

#include <bits/stdc++.h>

一行代码解决一系列代码，方便！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]  
其中 `bits/stdc++.h` 源码如下：

// C++ includes used for precompiling -*- C++ -*-
    
    // Copyright (C) 2003-2014 Free Software Foundation, Inc.
    //
    // This file is part of the GNU ISO C++ Library. This library is free
    // software; you can redistribute it and/or modify it under the
    // terms of the GNU General Public License as published by the
    // Free Software Foundation; either version 3, or (at your option)
    // any later version.
    
    // This library is distributed in the hope that it will be useful,
    // but WITHOUT ANY WARRANTY; without even the implied warranty of
    // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    // GNU General Public License for more details.
    
    // Under Section 7 of GPL version 3, you are granted additional
    // permissions described in the GCC Runtime Library Exception, version
    // 3.1, as published by the Free Software Foundation.
    
    // You should have received a copy of the GNU General Public License and
    // a copy of the GCC Runtime Library Exception along with this program;
    // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
    // <http://www.gnu.org/licenses/>.
    
    /** @file stdc++.h * This is an implementation file for a precompiled header. */
    
    // 17.4.1.2 Headers
    
    // C
    #ifndef _GLIBCXX_NO_ASSERT
    #include <cassert>
    #endif
    #include <cctype>
    #include <cerrno>
    #include <cfloat>
    #include <ciso646>
    #include <climits>
    #include <clocale>
    #include <cmath>
    #include <csetjmp>
    #include <csignal>
    #include <cstdarg>
    #include <cstddef>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    
    #if __cplusplus >= 201103L
    #include <ccomplex>
    #include <cfenv>
    #include <cinttypes>
    #include <cstdalign>
    #include <cstdbool>
    #include <cstdint>
    #include <ctgmath>
    #include <cwchar>
    #include <cwctype>
    #endif
    
    // C++
    #include <algorithm>
    #include <bitset>
    #include <complex>
    #include <deque>
    #include <exception>
    #include <fstream>
    #include <functional>
    #include <iomanip>
    #include <ios>
    #include <iosfwd>
    #include <iostream>
    #include <istream>
    #include <iterator>
    #include <limits>
    #include <list>
    #include <locale>
    #include <map>
    #include <memory>
    #include <new>
    #include <numeric>
    #include <ostream>
    #include <queue>
    #include <set>
    #include <sstream>
    #include <stack>
    #include <stdexcept>
    #include <streambuf>
    #include <string>
    #include <typeinfo>
    #include <utility>
    #include <valarray>
    #include <vector>
    
    #if __cplusplus >= 201103L
    #include <array>
    #include <atomic>
    #include <chrono>
    #include <condition_variable>
    #include <forward_list>
    #include <future>
    #include <initializer_list>
    #include <mutex>
    #include <random>
    #include <ratio>
    #include <regex>
    #include <scoped_allocator>
    #include <system_error>
    #include <thread>
    #include <tuple>
    #include <typeindex>
    #include <type_traits>
    #include <unordered_map>
    #include <unordered_set>
    #endif

不过 `VS` 会报错，网上解决办法一大堆，这里就不过多赘述了。

--------------------

### 二、STL（Standard Template Library） ###

1.  **STL（Standard Template Library）**，中文名 **标准模板库**，是一个高效的C++程序库，包含很多常用的 **基本数据结构** 和 **基本算法**，为C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
2.  从逻辑层次来看，在STL中体现了 **泛型编程思想（generic programming）**。
3.  从实现层次看，整个STL是以一种 **类型参数化（type parameterized）** 的方式实现的。

STL有六大组件（`容器(containers)`、`迭代器(iterators)`、`空间配置器(allocator)`、`配接器(adapters)`、`算法(algorithms)`、`仿函数(functors)`）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 2]  
但主要是容器、迭代器和算法三个部分：

*  **容器（Containers）**：用来管理某类对象的集合。对最常用的数据结构提供了支持，每一种容器都有其优点和缺点，为了应付程序中的不同需求。
 *  **迭代器（Iterators）**：用来在一个对象集合的元素上进行遍历动作。这个对象集合或许是个容器，或许是容器的一部分，每种容器都提供了了解该种容器内部结构的迭代器。
 *  **算法（Algorithms）**：用来处理对象集合中的元素。通过所有容器的迭代器提供一致的接口，可以多次复用算法于任意容器之上。

**STL** 的基本观念就是将数据和操作分离。

*  数据由 **容器** 进行管理;
 *  操作由 **算法**进行;
 *  而 **迭代器** 在两者之间充当粘合剂，使任何 **算法** 都可以和任何 **容器** 交互运作。

--------------------

### 三、容器（Containers） ###

一个容器就是一些特定类型对象的集合，是用来管理某类对象的，从C++11标准以来，C++中STL定义的几种容器的效率非常高，优化的非常好，完全没有必要自己去定义类似的数据结构，了解使用它们，可以满足90%的日常编程需要！本文是 **基于C++11标准，基于《C++primer》参考** 完成的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
常用的STL基本容器类型分为四类：

*  **顺序容器（Sequence containers）**，为程序员提供了控制元素存储和访问顺序的能力。顺序性容器中的每个元素均有固定的位置，取决于插入时机和地点，和元素值无关，除非用删除或插入的操作改变这个位置。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]
 *  **关联容器（Associative containers）**，支持高效的关键字查找和访问操作。关联容器中各元素间没有严格的物理顺序，取决于特定的排序准则以及元素值，和插入次序无关，元素是有序的集合。默认情况下，标准库使用关键字类型的 `<` 运算符来进行比较操作。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]
 *  **无序容器（Unordered associative container）**，使用 **哈希函数** 和关键字类型的 `==` 运算符组织元素。在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。使用无序容器通常更为简单(通常也会有更好的性能) 。
 *  **容器适配器（Adaptor）**，是标准库中的一个通用概念，容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样的一种机制。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作"它保存一个容器，这个容器再保存所有元素"。

其中，**STL** 提供的 **最常用的**：

*  四个 **顺序容器**： 
    
     *  **向量（vector）**；
     *  **双端队列（deque）**；
     *  **列表（list）**；
     *  **字符串（string）**；
 *  四个 **关联容器**： 
    
     *  **集合（set）**；**多重集合（multiset）**；
     *  **映射（map）**；**多重映射（multimap）**；
 *  三种 **适配器**： 
    
     *  **栈（stack）**；
     *  **队列（queue）**；
     *  **优先级队列（priority\_queue）**；
 *  四种 **无序容器**： 
    
     *  **unordered\_map**；
     *  **unordered\_multimap**；
     *  **unordered\_set**；
     *  **unordered\_multiset**；

容器类自动申请和释放内存，因此无需new和delete操作。

--------------------

### 四、顺序容器（Sequence containers） ###

#### 4.1）常用操作（共同点） ####

##### 1\_添加元素 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]

##### 2\_访问元素 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]

##### 3\_删除元素 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]

##### 4\_改变容器大小 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]

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

**向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重的程序设计错误。**

*  向容器中添加元素后： 
    
     *  如果容器是 `vector` 或 `string` 类型，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效。
     *  如果容器是 `deque` 类型，添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效。
     *  如果容器是 `list` 或 `forward_list` 类型，指向容器的迭代器、指针和引用仍然有效。
 *  从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效： 
    
     *  如果容器是 `list` 或 `forward_list` 类型，指向容器其他位置的迭代器、指针和引用仍然有效。
     *  如果容器是 `deque` 类型，删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响。
     *  如果容器是 `vector` 或 `string` 类型，指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。

#### 4.2）向量（vector） ####

**vector（向量）**：事实上和数组差不多，但比数组更优越，一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界，而 `vector` 正好弥补了这个缺陷，它的特征是相当于可变大小的数组（动态数组）。由于元素是连续存储的，随机访问快，在末端插入和删除快，但在中间插入和删除慢。

**优缺点：**

> 优点：支持随机访问，即 `[]` 操作和 `.at()`，查询效率高。  
>    
> 缺点：当向头部或中部，插入或删除元素，插入效率低。

需要导入头文件 `#include <vector>`。

##### 1\_定义和初始化： #####

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

##### 2\_简单vector操作 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]

##### 3\_关键概念: vector对象能高效增长 #####

C++标准要求 `vector` 应该能在运行时高效快速地添加元素，因此定义 `vector` 对象的大小没有必要，事实上性能可能更差，只有一种例外情况，就是所有元素的值都一样！一旦元素的值有所不同，更有效的办法是先定义一个空的 `vector` 对象，再在运行时向其中添加具体值。

开始的时候创建空的 `vector` 对象，在运行时再动态添加元素，这一做法与C语言及其他大多数语言中内置数组类型的用法不同，特别是如果用惯了C或者Java，可以预计在创建 `vector` 对象时顺便指定其容量是最好的，然而事实上，通常的情况是恰恰相反。

##### 4\_实例 #####

#include <iostream>
    #include <vector>
    using namespace std;
    int main()
    { 
    	vector<int> ivec1;
    	for (int i = 0; i<9; i++)
    		ivec1.push_back(i);
    	cout << ivec1.size() << endl;
    	for (int i = 0; i<ivec1.size(); i++)
    		cout << ivec1[i] << " ";
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

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

#### 4.3）双端队列（deque） ####

**deque（双端队列）**：是一个更为复杂的数据结构，最大任务就是在这些分段的连续空间上，维护其整体连续的假象，并提供随机存取的接口。与 `vector` 类似，随机访问快，不过是在两端插入和删除快，但在中间插入和删除慢。

**优缺点：**

> 优点：支持随机访问，即 `[]` 操作和 `.at()`，查询效率高；当向两端，插入或删除元素，插入效率高。  
>    
> 缺点：当向中部，插入或删除元素，插入效率低。

需要导入头文件 `#include <deque>`

##### 1\_实例 #####

#include <iostream>
    #include <deque>
    using namespace std;
    int main()
    { 
    	deque<int> ideq1;
    	for (int i = 0; i<9; i++)
    		ideq1.push_back(i);
    	cout << ideq1.size() << endl;
    	for (int i = 0; i<ideq1.size(); i++)
    		cout << ideq1[i] << " ";
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

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

#### 4.4）列表（list） ####

**list（列表）**：由 `deque` 实现而成，元素也存放在堆中。设计目的是令容器任何位置的添加和删除操作都很快速，作为代价不支持元素的随机访问——为了访问一个元素，只能遍历整个容器。

**优缺点：**

> 优点：内存不连续，动态操作，可在任意位置插入或删除且效率高。  
>    
> 缺点：不支持随机访问。

需要导入头文件 `#include <list>`

##### 1\_实例 #####

#include <iostream>
    #include <list>
    using namespace std;
    int main(int argc, char* argv[])
    { 
    	list<char> ilist;
    	for (char c = 'a'; c <= 'z'; ++c)
    		ilist.push_back(c);
    	cout << ilist.size() << endl;
    	while (!ilist.empty())
    	{ 
    		cout << ilist.front() << " ";
    		ilist.pop_front();
    	}
    	system("pause");
    	return 0;
    }

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

#### 4.5）字符串（string） ####

**string（字符串）**：表示可变长的字符序列，事实上和 `vector` 差不多。由于元素是连续存储的，随机访问快，在末端插入和删除快，但在中间插入和删除慢。

**优缺点：**

> 优点：支持随机访问，即 `[]` 操作和 `.at()`，查询效率高。  
>    
> 缺点：当向头部或中部，插入或删除元素，插入效率低。

需要导入头文件 `#include <string>`。

##### 1\_定义和初始化： #####

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

##### 2\_简单vector操作 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 8]

##### 3\_处理字符 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 9]

##### 4\_额外操作 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][20200222195911444.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 12]

##### 5\_实例 #####

#include <iostream>
    #include <string>
    using namespace std;
    int main()
    { 
    	string ivec1;
    	for (int i = 0; i<9; i++)
    		ivec1.push_back('i');
    	cout << ivec1.size() << endl;
    	for (int i = 0; i<ivec1.size(); i++)
    		cout << ivec1[i] << " ";
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

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

#### 4.6）容器选择 ####

**容器选择原则：**

*  除非有合适的理由选择其他容器，否则应该使用 `vector`。
 *  如果程序有很多小的元素，且空间的额外开销很重要，则不要使用 `list` 或 `forward_list`。
 *  如果程序要求随机访问容器元素，则应该使用 `vector` 或 `deque`。
 *  如果程序需要在容器头尾位置插入/删除元素，但不会在中间位置操作，则应该使用 `deque`。
 *  如果程序只有在读取输入时才需要在容器中间位置插入元素，之后需要随机访问元素。则： 
    
     *  先确定是否真的需要在容器中间位置插入元素。当处理输入数据时，可以先向 `vector` 追加数据，再调用标准库的 `sort` 函数重排元素，从而避免在中间位置添加元素。
     *  如果必须在中间位置插入元素，可以在输入阶段使用 `list`。输入完成后将 `list` 中的内容拷贝到 `vector` 中。
 *  不确定应该使用哪种容器时，可以先只使用 `vector` 和 `list` 的公共操作：使用迭代器，不使用下标操作，避免随机访问。这样在必要时选择 `vector` 或 `list` 都很方便。

--------------------

### 五、关联容器（Associative containers） ###

#### 5.1）常用操作（共同点） ####

##### 1\_类型别名 #####

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

##### 2\_添加元素 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 13]

##### 3\_删除元素 #####

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

##### 4\_访问元素 #####

![在这里插入图片描述][20200222202645502.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 14]

#### 5.2）集合（set）和多重集合（multiset） ####

**set（集合）**：由红黑树实现，其中每个元素只包含一个关键字并依据其值自动排序，支持高效的关键字查询操作，每个元素值只能出现一次，不允许重复。插入和删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。

**multiset（多重集合）**：唯一的区别是插入的元素可以相同。

**优缺点：**

> 优点：关键字查询高效，且元素唯一，以及能自动排序。  
>    
> 缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。

需要导入头文件 `#include <set>`。

##### 1\_实例 #####

#include <iostream>
    #include <set>
    using namespace std;
    int main(int argc, char* argv[])
    { 
    	set<int> iset;
    	iset.insert(3);
    	iset.insert(1);
    	iset.insert(2);
    	iset.insert(1);
    	set<int>::iterator it;
    	cout << iset.size() << endl;
    	for (it = iset.begin(); it != iset.end(); it++)
    	{ 
    		cout << *it << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }

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

#### 5.3）映射（map）和多重映射（multimap） ####

**map（映射）**：由红黑树实现，其中每个元素都是一些 **键值对（key-value）**：关键字起索引作用，值表示与索引相关联的数据。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。插入和删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。

**multimap（多重映射）**：唯一的区别是插入的元素（值）可以相同，即同一个键可以对应多个值。

**优缺点：**

> 优点：关键字查询高效，且元素唯一，以及能自动排序。把一个值映射成另一个值，可以创建字典。  
>    
> 缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。

需要导入头文件 `#include <map>`。

##### 1\_实例 #####

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    int main(int argc, char* argv[])
    { 
    	map<int, string> imap;
    	imap.insert({  3, "张三" });
    	imap.insert({  4, "李四" });
    	imap.insert({  1, "王二麻子" });
    	imap.insert({  2, "小淘气" });
    	map<int, string>::iterator it;
    	for (it = imap.begin(); it != imap.end(); it++)
    	{ 
    		printf("学号：%d 姓名：%s\n", (*it).first, (*it).second.c_str());
    	}
    	system("pause");
    	return 0;
    }

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

--------------------

### 六、适配器（Adaptor） ###

#### 6.1）常用操作（共同点） ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 15]

#### 6.2）栈（stack） ####

**stack（栈）**：LIFO（后进先出）。

需要导入头文件 `#include <stack>`。

##### 1\_基本操作 #####

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

##### 2\_实例 #####

[《C++ Primer》习题参考答案：第9章 - 顺序容器][C_ Primer_9_ - 1] 最后一题。

#### 6.3）队列（queue）和优先级队列（priority\_queue） ####

**queue（队列）**：FIFO（先进先出），即普通的缓冲区（buffer）。

**priority\_queue（优先级队列）**：基于程序员提供的排序准则定义不同的优先权。

需要导入头文件 `#include <queue>`。

##### 1\_基本操作 #####

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

--------------------

### 七、无序容器（Unordered associative container） ###

#### 7.1）unordered\_map/unordered\_multimap ####

#### 7.2）unordered\_set/unordered\_multiset ####

**无序容器**：在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。事实上使用无序容器通常更为简单(通常也会有更好的性能) 。如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。

##### 1\_常用操作（共同点） #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 16]  
通常可以用一个无序容器替换对应的有序容器，反之亦然。但是输出（通常）会不同。

--------------------

### 八、sizeof、size和capacity ###

*  `sizeof` 操作符统计的是容器 `vector<int>` 的大小；
 *  `size()` 操作符统计的是容器（vector）内元素的大小；
 *  `capacity` 操作符统计的是容器（vector）能存储的容量大小。

#include <iostream>
    #include <vector>
    using namespace std;
    int main(int argc, char* argv[])
    { 
    	vector<int> ivec;
    	cout << sizeof(ivec) << endl;
    	cout << ivec.size() << endl;
    	cout << ivec.capacity() << endl;
    	for (int i = 0; i<10; i++)
    		ivec.push_back(1);
    	cout << sizeof(ivec) << endl;
    	cout << ivec.size() << endl;
    	cout << ivec.capacity() << endl;
    	system("pause");
    	return 0;
    }

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

另外：

*  `reserve()` 操作符统计的是指定容器内能存储元素的数量；
 *  `resize()` 操作符统计的是重新指定容器内有效元素的数量；

### 九、总结 ###

![在这里插入图片描述][20200222215912815.png_pic_center]  
最后送你两张图：

*  第一张：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 17]
 *  第二张：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 18]

***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

***回复【福利】即可获取我为你准备的大礼，包括C++，编程四大件，NLP，深度学习等等的资料。***

***想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~***

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 3]

## 参考文章 ##

*  《C++primer》第五版
 *  [《C++ Primer》学习笔记（十一）：关联容器][C_ Primer 3]
 *  [《C++ Primer》学习笔记（九）：顺序容器][C_ Primer 1]
 *  [《C++ Primer》习题参考答案：第9章 - 顺序容器][C_ Primer_9_ -]
 *  [《C++ Primer》学习笔记（三）：字符串、向量和数组][C_ Primer]
 *  https://en.cppreference.com/w/cpp/container

[C]: https://blog.csdn.net/tefuirnever/article/category/9342309
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200222091734813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70#pic_center
[C_ Primer_]: https://blog.csdn.net/TeFuirnever/article/details/100700212
[C_ Primer]: https://blog.csdn.net/TeFuirnever/article/details/101671578
[C_ Primer_3_ -]: https://blog.csdn.net/TeFuirnever/article/details/101976043
[C_ Primer 1]: https://tefuirnever.blog.csdn.net/article/details/103731653
[C_ Primer_9_ -]: https://blog.csdn.net/TeFuirnever/article/details/103731673
[C_ Primer 2]: https://blog.csdn.net/TeFuirnever/article/details/103731739
[C_ Primer_11_ -]: https://blog.csdn.net/TeFuirnever/article/details/103731753
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200222092549140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200222095229954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222105640800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200222104906710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200222104927554.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200222170028963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020022217034768.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200222170508409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200222170535899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222164214693.png]: https://img-blog.csdnimg.cn/20200222164214693.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200222164604618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222190028978.png]: https://img-blog.csdnimg.cn/20200222190028978.png
[20200222185817577.png]: https://img-blog.csdnimg.cn/20200222185817577.png
[20200222190555505.png]: https://img-blog.csdnimg.cn/20200222190555505.png
[20200222195551695.png]: https://img-blog.csdnimg.cn/20200222195551695.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200222195601817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200222195632345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200222195847653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200222200039932.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222195911444.png]: https://img-blog.csdnimg.cn/20200222195911444.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200222195936282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222200318384.png]: https://img-blog.csdnimg.cn/20200222200318384.png
[20200222202243493.png]: https://img-blog.csdnimg.cn/20200222202243493.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200222202534442.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222202552652.png]: https://img-blog.csdnimg.cn/20200222202552652.png
[20200222202645502.png]: https://img-blog.csdnimg.cn/20200222202645502.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200222202650871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222202939785.png]: https://img-blog.csdnimg.cn/20200222202939785.png
[20200222204211643.png]: https://img-blog.csdnimg.cn/20200222204211643.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200222204850229.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222205049978.png]: https://img-blog.csdnimg.cn/20200222205049978.png
[C_ Primer_9_ - 1]: https://tefuirnever.blog.csdn.net/article/details/103731673
[20200222205954333.png]: https://img-blog.csdnimg.cn/20200222205954333.png
[20200222210000534.png]: https://img-blog.csdnimg.cn/20200222210000534.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200222210559940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[20200222211905485.png]: https://img-blog.csdnimg.cn/20200222211905485.png
[20200222215912815.png_pic_center]: https://img-blog.csdnimg.cn/20200222215912815.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200222215356951.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 18]: https://img-blog.csdnimg.cn/20200222215538754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200331201850310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy,size_16,color_FFFFFF,t_70#pic_center
[C_ Primer 3]: https://tefuirnever.blog.csdn.net/article/details/103731739