目录

• 1. 容器概述
  • 1.1. 顺序容器、关联容器 ----区分
  • 1.2. 特点分析
• 2. 顺序容器
  • 2.1. 概述
  • 2.2. Vector 容器
  • 2.3. string 容器
  • 2.4. List 容器
• 3. 关联容器
  • 3.1. 概述
  • 3.2. 有序关联–map
• 4. 容器适配器

参考：

1. Containers library
2. C++中常用的std标准容器
   ----转载
3. C++ 容器详解
   // 侧重比较
4. C/C++STL常用容器用法总结
   // 侧重用法

C语言：

1. C语言实现类似C++的容器vector

---

1. 容器概述

1.1. 顺序容器、关联容器 ----区分

1. 可以用下标访问的容器有（既可以插入也可以赋值）：vector、deque、map；
   特别要注意一下，vector和deque如果没有预先指定大小，是不能用下标法插入元素的！、

2. 序列式容器才可以在容器初始化的时候 指定大小，关联式容器不行；

3. 注意，关联容器的迭代器不支持it+n操作，仅支持it++操作。

1.2. 特点分析

1. 特点

   标准容器适配器	特点
   顺序性容器
   vector	从后面快速的插入与删除，直接访问任何元素
   deque	从前面或后面快速的插入与删除，直接访问任何元素
   list	双链表，从任何地方快速插入与删除
   关联容器
   set	快速查找，不允许重复值
   multiset	快速查找，允许重复值
   map	一对多映射，基于关键字快速查找，不允许重复值
   multimap	一对多映射，基于关键字快速查找，允许重复值
   容器适配器
   stack	后进先出
   queue	先进先出
   priority_queue	最高优先级元素总是第一个出列

---

2. 顺序容器

2.1. 概述

1. 分类
   1. vector
   2. string (它不是类模板）
   3. list (双向链表)
   4. forward_list (单向链表)
   5. deque (double-end queue,双端队列)
   6. queue
   7. priority_queue
   8. stack

---

2.2. Vector 容器

1. 常用操作

   1. 属性操作v1.size()　　　　　//v1内已经存放的元素的数目v1.capacity()　　　// v1现有的在存储容量（不再一次进行扩张内存空间的前提下）v1.empty()　　　　 // 判断v1是否为空v1.max_size()　　　// 返回vector可以存放的最大元素个数，一般这个数很大，//因为vector可以不断调整容量大小。v1.shrink_to_fit()　　// 该函数会把v1的capacity()的大小压缩到size()大小，即释放多余的内存空间。2. 访问操作：访问操作都会返回引用，通过它，我们可以修改vector中的值。v1[n]　　　　　　// 通过下标进行访问vector中的元素的引用//（下标一定要存在 ，否则未定义，软件直接崩了）v1.at(n)　　　　// 与上面类似，返回下标为n的元素的引用，不同的是，如果下标不存在，//它会抛出out_of_range的异常。它是安全的，建议使用它。v1.front()　　　// 返回vector中头部的元素的引用（使用时，一定要进行非空判断）v1.back()　　　 // 返回vector中尾部的元素 引用（使用时，一定要进行非空判断）3. 添加操作：v1.push_back(a)　　　　　　 //在迭代器的尾部添加一个元素v1.push_front(a)　　　　　　// vector不支持这个操作--------------------v1.insert(iter, a)　　　　　// 将元素a 插入到迭代器指定的位置的前面，//返回新插入元素的迭代器（在c++11标准之前的版本，返回void)v1.insert(iter, iter1, iter2)　　　//把迭代器[iterator1, iterator2]范围内的元素插入到迭代器iterator之前的位置，//返回新插入的第一个元素的迭代器（在c++11标准之前的版本， 返回空）。标准与效率 问题：在c++11标准中，引入了emplac_front()、 emplace()、emplace_back(),它们分别与push_front()、insert()、 push_back()相对应，用法与完成的动作作完全相同，但是实现不一样。push_front()、insert()各push_back()是对元素使用copy操作来完成的，而emplac_front()、 emplace()和emplace_back()是对元素使用构造来完成的，后者的效率更高，避免了不必要的操作。因此，在以后更后推荐使用它们。4. 删除操作：v1.erase(iterator)　　　　// 删除人人迭代器指定的元素，//返回被删除元素之后的元素的迭代器。（效率很低，最好别用）v1.pop_front() 　　　　　　//vector不支持这个操作-------------v1.pop_back()　　　　　　  //删除vector尾部的元素 ， 返回void类型 (使用前，一定要记得非空判断）v1.clear()　　　　　　　　 //清空所有元素5. 替换操作：v1.assign({初始化列表})　　// 它相当于赋值操作，v1.assign(n, T)　　　　　　// 此操作与初始化时的操作类似，用n个 T类型的元素对v1进行赋值v1.assign(iter1, iter2)　　　// 使用迭代器[iter1, iter2]区间内的元素进行赋值（该迭代器别指向自身就可以），//另外，只要迭代器指的元素类型相同即可（存放元素的容器不同，//例如：可以用list容器内的值对vector容器进行assign操作，而用 "=" 绝对做不到的。v1.swap(v2)　　　　　　// 交换v1与v2中的元素;//swap操作速度很快，因为它是通过改变v1与v2两个容器内的数据结构//（可能是类似指针之类的与v1和v2的绑定）完成的，不会对容器内的每一个元素进行交换。//这样做，不仅速度快，并且指向原容器的迭代器、引用以及指针等仍然有效，//因为原始的数据没有变。在c++ primer 中建议大家使用==非成员版本的swap()函数==，它在范型编程中很重要。
   ----注释写在后面；
   

---

2.3. string 容器

1. 概述

string与vector类似，但是string不是一种类模板，而就是一种类型，因为它专门用于存放字符的（存放的元素类型已经明确），所以没有设计为类模板。它的所有特性与vector相同，包括存储在连续的空间／快速随机访问／高效在尾部插入与删除／低效在中间插入与删除等， string的迭代器也支持算术运算。 实际上，就可以把string类型看作为vector类型， vector的所有特性都适合与string类型。当然，因为string类型比vector模板更特例化一些，因此它肯定具有一些自己特有而vector没有的特性，下面总结一下。

在陈述之前，首先说明：

1. 在string中(有一些也适用于C风格的字符串），我们可以使用一组迭代器／单个迭代器（从此迭代器开始到字符串末）／位置＋长度表示范围／单个位置（从此位置到字符串末）来表示字符串中的范围， 这样的参数记作range.

2. 可以使用列表初始化的字符串／使用字符串＋range的组合形式表示的子字符串 / 字面值常量（如“china”）来表示字符串。 这里的字符串包括string类型的字符串和C风格的char* 字符串。 字符串使用字符args 表示。

正因为pos和args的样式可以随意组合，所以string的操作函数的参数是多种的，因此它的重载函数数目很多，由于对于insert(pos, args)／append(args)／erase(pos,args)／replace(pos, args)等操作。

a. string的初始化
相对于vector类型来说， string 增加一个使用字面值类型进行初始化，即：

string a("xiaoming")
string a = "xiaoming"

b. string中包含的专有的操作（相对于vector来说）

1. string的添加与替换

在string中，增加了append(）与 replace()函数

str.append(args)　　　　// 在尾部添加一个字符或一个字符

str.replace(pos, args)　　　　// 在尾部添加一个字符或一个字符 ,它的重载函数很多,共16个。

2. string的访问子字符串：

str.substr(_pos, n)　　//该函数可以获得原字符串中的部分字符, 从pos开始的n个字符，当_pos超过范围时，会抛出out_of_range的异常。

3. str的搜索操作：

str.find(args)　　//查找args 第一次出现的位置

str.rfind(args)　　//查找args最后一次出现的位置

str.find_first_of(args)　　　//搜索的是字符， 第一个是args里的字符的位置

str.find_last_of(args)　　　// 搜索的是字符， 最后一个是args里的字符的位置

str.find_first_not_of()　　// 搜索的是字符，第一个不是args里的字符的位置

str.find_last_not_of()　　// 搜索的是字符， 最后一个不是args里的字符的位置

4. str的大小操作：

str.length()　　　// 该函数与str.size()函数完成一样，只是名字不同而已罢了。只所以这样搞的原因，可能开发人员感觉length更适合字串符，size更适合容器吧。

c字符串的转换函数

1. 由数值转换为字符串：

to_string(val):

2. 由字符串转换为数值：（要转换的string的第一个非空白符必须是数值中可能出现的字符，处理直到不可能转换为数值的字符为止，以下内容来自：c++primer）

stoi(str, pos, base) 　　// 字符串转换为整型，其中str表示字符串， pos用于表示第一个非数值字符的下标(意思就是我给函数传入一个地址，它会对它进行赋第一个非数值字符的位置）, base表数值的基数，默认为10，即10进制数。
stol(str, pos, base)　　　　// 转换为long
stoul(str, pos, base)　　　　// 转换为 unsigned long
stoll(str, pos, base)　　　　// 转换为 long long
stoull(str, pos, base)　　　// 转换为unsigned long long
stof(str, pos)　　　　　　// 转换为float
stod(str, pos,)　　　　　// 转换为double
stold(str, pos,)　　　　　// 转换为long double

d 对字符的操作（在cctype头文件中，并不属于string头文件的范围，但是关系很紧密的）
以下内容来自:c++ primer 第五版p82, 只写出部分常用来的(字母：alpha, 数字：number或digit)

isalnum©　　// 当为字母或数字时为真

isalpha©　　// 当为字母时为真

isdigit©　　// 当为数字时真

islower©　　// 当为小写字母时为真

issupper©　　// 当为大写字母时为真

isspace©　　// 当为空格时为真

tolower©　　// 转换为小写字母， 当本身为小写字母时，原样输出

toupper©　　// 转换为大写字母， 当本身为大写字母时，原样输出

---

2.4. List 容器

1. 概述

   1. 与vector和string相比，list内部的实现为一个双向链表，元素存储在非连续的内存空间，
   2. 这就决定了它不能在常量时间内完成对元素的随机访问，只能从头到尾的遍历一遍。
   3. 因为是用双向链表实现的，所以，它的一大特性就是它的迭代器永远不会变为无效；
      （除非这段空间不存在了），即无论增加、删除操作，都不会破坏迭代器。

   大多数对vector的操作也适合于list，由于底层实现不同，有也差异：

2. list与vector的差别：

   1. list支持push_front()、pop_front()操作；

   2. list不支持vector中的随机访问操作，即使用v1.at( )和v1[ ] 操作。

   3. list的删除与增加元素的操作不会破坏迭代器，而 vector与string 会使迭代器失效。

   4. list 内部增加了一个sort()的方法，用于实现排序，不过呢，反正我感觉基本不用它，直接用里的范型sort(）更好啊啊。

   5. list增加了一个类似insert()的函数，为splice( ) ：该函数可以实现在常数时间内把一个list 插入到另一个list内，与insert()的区别在于insert是进行copy, 而splice()直接操作的链表的指针指向。它有好几个重载函数。

   6. list的去重复函数： unique()； 该函数的作用是去除连续重复的元素，参数即可以为空，也可以传入一个二元谓词，用于确定相等的比较算法。 因为unique()函数可能去除连续重复的元素，因此，很依赖配合上sort()函数使用啊。

   7. list的合并函数merge(): 该函数就是合并两个list， 它在合并过程中会在两个链表之间进行来回的比较，如果原来的两个list是有顺序的，合并之后的结果也是有序的，如果合并之前是无序的，合并之后也是无序的。反正吧，这个比较就这样。

3. 关联容器

3.1. 概述

1. 分类

   1. 有序关联容器
      1. map
      2. multimap
      3. set
      4. multiset
   2. 无序关联容器
      1. unordered_map
      2. unordered_multimap
      3. unordered_set
      4. unordered_multiset

2. 关联容器与顺序容器最大的区别：

   1. 在于关联容器没有下标，都过键值或 值本身进行索引。
   2. 有序关联容器内部通过红黑树实现的，当搜索一个元素时，具有O(logn）的平均复杂度，
   3. 而无序的关联容器在底层是通过散列表（哈希函数映射）实现的，当搜索一个元素时，通常O(1)的平均复杂度，最坏为O(logn)。

3.2. 有序关联–map

1. map 容器
   在介绍map之前，必须先介绍pair 类型。

pair类型：

1. pair类型定义在头文件utility中。
2. pair类型为一个结构体类型的模板，（在c++中结构体与类，除了默认的访问符不同，没有其它任何区别）
3. pair 有两个public的数据成员，分别为first与second.
4. pair的初始化与大多数结构体或类的初始化相同：

pair<int, string> sb //初始化一个默认值的pair对象sb, 它的first是默认初始化的（0,内置类型默认初始化大多数应该是未定义的啊，它这是为0）， second也是采用默认初始化（空字符串）
pair<int, string> sb(1, “japan”); //很常见的初始化方法
pair<int, string> sb = (1, “japan”);
pair<int, string> sb{1,“japan”} //c++11中的列表初始化方法
pair<int, string> sb = {1, “japan”}
可以调用make_pair()模板函数，返回一个pair对象：

1. map是用于存放键-值对的容器，它使用pair的first数据成员表示键（key)，second数据成员表示对应的值(value),所以呢，map是存放pair类型对象的容器。在map中，key都是固定的，一旦使用就不可以改变，而value是可以改变的， 因此会把pair类型的first数据成员的类型声明为const。2. map的特性之一是：按value的大小进行有序存放（unordered_map是无序的）， 因此，构造mqp容器时，要求它的key类型必须能够比较大小，当使用自定义的类类型时，

应该把重载的 operator< 运算符传递给map, 例如：

1 // 添加相关代码
2
3
4
5 …
3.在map中:

::value_type表示"键-值 对"类型
::key_type表示键类型,vlue类型
::mapped_type 表示值的类型
例如： map<int, string>, 则 map<int, string>::value_type 与pair<int, string>等价， map<int, string>::key_type与int等价， map<int, string>::mapped_type与string等价;

4. map的访问操作：

map同样支持使用迭代器，它会返回指向 pair类型的对象 的迭代器
map 使用[]运算符 通过key来访问对应的 value ，如果访问的key不存在，则会自动添加一个对应的pair 对象，其中它的value采用默认值。因此，当通过key来访问map时，
map不能是const类型。
map 使用at()成员函数 通过key来访问对应的value, 如果访问的key不存在，则会抛出一个out_of_range的异常;
5. map的添加与删除操作:

insert()或emplace()操作： 当向map中插入不存在的元素（指key值不同）时,可以插入成功，当插入一个已经存在key值的pair对象时，ma不会作任何改变。因此，当对map进行插入操作时，需要知道有没有插入成功。insert()与emplace()函数的 返回值也是一个pair类型，first为一个迭代器，指向插入时的键值对应的pair对象(可能是新插入的，也可能是已经存在的), second是一个bool类型，它表示是否插入成功(例如：当map中已经存在待插入的值时，为false)
erase()操作：它有三个版本，前两个版本与顺序容器相同，使用迭代器指定一个位置或一对迭代器指定一个范围，这时返回值为一个迭代器，指向删除之后的下一个元素；第三个版本的erase()很不错，我很喜欢，它的参数为key值，删除对应key值的pair()对象, 返回值为成功删除的个数（可能为0或1，在multimap中可能为n)
6.查找操作

find(key): 查找一个特定key值的pair对象，如果找到就返回对应的迭代器，如果找不到，就返回.end()迭代器。
count(key)：统计在map容器中特征key值的pair对象的个数.(在multimap与multiset中很有用的）
equal_range(key) // 返回一个pair类型，first表示low_bound, second表示upper_bound;
lower_bound(key) //返回迭代器，对应第一个大于等于key的元素
upper_bound(key) //返回迭代器，对应第一个大于key的元素 （说明：其实，最后这四个函数，在multimap与multiset中是非常有用的）

4. 容器适配器

ll