C++ day 38 STL容器（15种！）

以你之姓@ 2023-02-18 09:53 21阅读 0赞

### 文章目录 ###

*  容器概念：通用类别，指定了所有容器类必须满足的要求
 *  容器：存储其他对象的对象
 *   *  复制构造，复制赋值 VS 移动构造， 移动赋值
 *  序列容器：对基本容器概念的重要改进（7种STL容器实际上都是序列容器）
 *   *  在基本容器的要求的基础上增加的要求
     *  7种序列容器类型
     *  vector:数组的一种类表示，有自动内存管理功能
     *  deque：双端队列
     *  list：双向链表，可以双向遍历
     *   *  示例
     *  forward\_list:单链表
     *  queue:一个适配器类，它的默认底层类是deque
     *  priority\_queue：优先队列，也是适配器类，但默认底层类是vector
     *  stack：适配器类，底层类为vector
     *  array
 *  关联容器：对容器概念的另一个改进，基于树数据结构，把值和键关联在一起
 *   *  优缺点
     *  4种关联容器：set, multiset, map, multimap
     *   *  set：最简单的关联容器（值就是键！）
         *   *  示例
             *  集合的交，并，差运算的STL方法
             *   *  示例：还是要靠敲
         *  multiset
         *  map
         *  multimap
         *   *  成员方法
             *   *  示例
 *  无序关联容器：对容器概念的另一种改进，C++11新增，基于哈希表数据结构
 *   *  4种无序关联容器
 *  容器类型：可创建具体容器对象的模板
 *  总结

# 容器概念：通用类别，指定了所有容器类必须满足的要求 #

如**容器，序列容器，关联容器**等。

用来指定STL的所有容器类必须满足的一系列要求。即所有容器类都通用的元素。很像是继承机制里的抽象基类，但是容器类并不真正的使用继承机制，所以换种说法，说他是概念。

> 前面说了，STL的术语“概念”表示一组要求，比较抽象，而概念的具体实现叫做概念的模型。  
> 容器，序列容器，关联容器都是容器概念，并不是具体的容器模型，他们只是一组要求而已。  
> vector， list等容器都是容器概念的一个模型。

# 容器：存储其他对象的对象 #

*  被存储的对象们必须是同一个类型。可以是内置类型，或者类的对象。

> 所以STL中也用了OOP理念的，因为容器里存的可以是对象。泛型编程并不是和OOP对立的编程理念，他们的侧重点不同，但是完全可以合作！

*  容器过期，则内部的内容也会过期。但是如果容器存储的是指针，则指针指向的内存中的内容并不过期。
 *  不是任何类型的对象都可以存在容器里。只有**可以复制构造的和可以赋值的**对象可以。C++11用术语可复制插入CopyInsertable和可移动插入MoveInsertable来描述。

> **基本数据类型一定满足这个要求**，所以一定可以放在容器里。  
> 类的对象要满足条件，则类定义不可以把**复制构造函数和赋值运算符**定义为私有或者保护的，必须是公有的。

*  基本容器**不保证元素按照特定顺序存储**，也不保证**元素的顺序不变**。
 *  基本的容器特征有（C++11之前的）：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

> 上图的复杂度描述执行操作需要的时间,从快到慢分别是：
> 
>  *  编译时间：代表操作在编译时进行，执行时间为0
>  *  固定时间：操作发生在运行阶段，但独立于对象中的元素数目。相当于大O表示法的O(1)。
>  *  线性时间：操作发生在运行阶段，但和对象中的元素数目成正比。相当于大O表示法的O(n)。  
>     比如`a==b`的复杂度是线性，因为`==`需要逐个对比容器里的每一个元素。

*  C++11新增的通用容器要求：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
    这里又提到了C++11新增的移动语义，看来移动语义真的是绕不过去的坎。

## 复制构造，复制赋值 VS 移动构造， 移动赋值 ##

*  复制操作**保留源对象**，移动操作可以**修改源对象**，还可以**转让所有权而不做任何复制**。
 *  如果**源对象是临时的，则移动操作的效率高于**常规复制。

# 序列容器：对基本容器概念的重要改进（7种STL容器实际上都是序列容器） #

sequence

序列是对容器很重要的一种改进。毕竟有7种STL容器类型实际上都是序列类型：

*  forward\_list
 *  list
 *  queue
 *  stack
 *  vector
 *  priority\_queue
 *  deque  
    除此之外，array类，它并不是STL容器，也被归类为序列容器。

## 在基本容器的要求的基础上增加的要求 ##

那么序列在基本容器的要求上，增加了什么呢？

*  **迭代器至少是正向迭代器**，这保证了元素按照特定顺序排列，两次迭代的元素顺序是固定的。
 *  要求元素按照严格的线性顺序排列。

> 数组，链表都是线性结构。但分支结构，比如树和图，不是线性结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]  
下面这个图可太牛逼了。。。这些方法都是固定时间复杂度的。如果是线性复杂度则没有实现。比如vector类就没有定义`push_front()`方法，但是定义了`push_back()`，这是因为如果把新元素插入到矢量容器最前面，则需要把已有元素全部往后移动一个位置，就像数组一样的，这是线性时间复杂度的，所以没实现。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]  
原来front()函数返回的是引用，而且实际上其实就是对`a.begin()`返回的迭代器解引用。

原来`push_front()`和`push_back()`方法实际上都是在底层调用`insert()`函数。而`pop_front()`和`pop_back()`方法实际上都是在底层调用`erase()`函数。

`a[n], a.at(n)`从这个表看起来没有任何区别，完全一样，都返回第n个元素（从0编号）的引用，但当然是有区别的。。。区别是：  
如果n无效，即落在容器的有效区间外，则后者会执行边界检查，应引发`out_of_range`异常，前者则不会。所以`a.at(n)`更加安全，对索引的内存越界问题有进行异常处理。

## 7种序列容器类型 ##

## vector:数组的一种类表示，有自动内存管理功能 ##

*  **最简单**的序列容器类型，如果不是必须用别的，则应该默认用vector。
 *  在尾部添加和删除元素为固定时间复杂度
 *  在头部添加和删除元素是线性时间复杂度
 *  vector其实还是可反转容器reversible container概念的模型，所以他有类方法`rbegin(),rend()`,这俩方法返回的都是反向迭代器reverse\_iterator  
    ![在这里插入图片描述][20200617200052475.png]

## deque：双端队列 ##

double-ended queue

*  `#Include <deque>`
 *  STL中的实现类似于vector，可以随机访问。
 *  和vector的区别：从deque对象的开始位置插入和删除元素的时间是固定的，而在vector中是线性时间的。

> 当然，为了实现在开头插入和删除也是固定时间，deque数据结构的设计也是更加复杂的。

*  deque比vector设计上更复杂，使得他在**随机访问**，和**从序列中间某位置的插入**这两个方法中的效率不如vector。

> deque并不是一定比vector好的，不要觉得它比vector高级。一方面的优势一定是拿什么别的东西换的。所以还是那句话，没有完美的，没有最好的，只有适合自己的。  
> 如果你需要频繁从头部插入新元素，则用deque更好，但是如果随机访问和从序列中部尾部插入，则vector更快。

## list：双向链表，可以双向遍历 ##

*  和vector一样，也是可反转容器
 *  和vector的区别之一：list不支持数组表示法和随机访问。
 *  **和vector的关键区别**：list在任何一个位置插入和删除的时间复杂度都是线性的。

> vector主打随机访问的快速。而list主打元素的快速插入和删除。就像两个企业，虽然都是数据结构，都是装数据的容器，但是主推的卖点不同，所以都有顾客，不存在竞争。顾客会自觉根据需要选择适合自己的。

*  和vector的区别第三点：从容器中删除或者插入元素之后，**链表迭代器指向的元素不变**，因为链表插入新元素并不会移动已有元素，只是修改链接信息。而矢量迭代器，在矢量数组中部插入一个元素，则必须移动后方的元素，所以被移动的每一个位置中存的元素都会变化，**矢量迭代器指向的位置没变，但是元素可能变了**（如果迭代器指向插入元素的前民，则元素不变）。
 *  list模板类中链表专用的方法：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]  
    ==splice()方法执行结束后，参数链表为空，是因为它是把**原链表**移动到了目标地址；而insert()==函数执行完毕，源链表还在，那是因为它只是把源链表的**副本**插入到目标地址了。

### 示例 ###

#include <iostream>
    #include <list>
    #include <iterator>
    #include <algorithm>
    void outint(int n){ std::cout << n << ' ';}
    
    int main()
    { 
    	using namespace std;
    	list<int> one(5, 2);//5个2
    	int stuff[5] = { 1, 2, 4, 8, 6};
    	list<int> two;
    	two.insert(two.begin(), stuff, stuff + 5);
    	int more[6] = { 6, 4, 2, 4, 6, 5};
    	list<int> three(two);//复制构造函数
    	three.insert(three.end(), more, more + 6);
    
    	cout << "List one: ";
    	for_each(one.begin(), one.end(), outint);
    	cout << endl << "List two: ";
    	for_each(two.begin(), two.end(), outint);
    	cout << endl << "List three: ";
    	for_each(three.begin(), three.end(), outint);
    
    	three.remove(2);
    	cout << endl << "List three minus 2s: ";
    	for_each(three.begin(), three.end(), outint);
    
    	three.splice(three.begin(), one);//把链表one的内容插入到three的前端，one会变空
    	cout << endl << "List three after splice: ";
    	for_each(three.begin(), three.end(), outint);
    	cout << endl << "List one: ";
    	for_each(one.begin(), one.end(), outint);
    
    	three.unique();	//去除连续的重复元素
    	cout << endl << "List three after unique: ";
    	for_each(three.begin(), three.end(), outint);
    
    	three.sort();//排序
    	cout << endl << "List three after sort: ";
    	for_each(three.begin(), three.end(), outint);
    
    	three.sort();
    	three.unique();
    	cout << endl << "List three after sort & unique: ";
    	for_each(three.begin(), three.end(), outint);
    
    
    	two.sort();
    	three.merge(two);
    	cout << endl << "Sorted two merged into three: ";
    	for_each(three.begin(), three.end(), outint);
    
    	return 0;
    }

List one: 2 2 2 2 2
    List two: 1 2 4 8 6
    List three: 1 2 4 8 6 6 4 2 4 6 5
    List three minus 2s: 1 4 8 6 6 4 4 6 5
    List three after splice: 2 2 2 2 2 1 4 8 6 6 4 4 6 5
    List one:
    List three after unique: 2 1 4 8 6 4 6 5
    List three after sort: 1 2 4 4 5 6 6 8
    List three after sort & unique: 1 2 4 5 6 8
    Sorted two merged into three: 1 1 2 2 4 4 5 6 6 8 8

我的问题：

*  我把outint函数的参数写成了`list<int>::iterator & it`。。。。看来for\_each函数的函数指针的参数是迭代器指向的容器内部存储的数据的类型，并不是迭代器的类型。
 *  我以为`unique()`函数可以去除所有重复元素，实际上只可以去除相邻的连续的重复元素。要想去除所有的重复元素，那就先排序，使得所有相同元素都聚到一起，再用unique函数，就可以得到一个没有重复元素的链表。
 *  我对for\_each函数和基于范围的for循环的使用还很生疏不熟练，总是想不到要用。  
    其实上面所有的for\_each函数都可以用基于范围的for循环替代，还不需要写outint函数了。

for_each(two.begin(), two.end(), outint);

for (auto x : one) cout << x << " ";

*  注意sort()函数不是成员函数哈，因为链表为了快速的插入和删除，放弃了随机访问，所以他的迭代器不是随机访问迭代器，而是双向迭代器，而sort()算法需要随机访问，所以没办法成为成员函数。

## forward\_list:单链表 ##

*  C++11新增

> 好奇怪哦，难道不应该先实现单链表在实现双向链表吗，，大概是最初觉得双向链表可以当做单链表用吧，后来又觉得简单的设计速度快，还是单独做了

*  由于是单链表，所以每个元素只链接到后一个元素结，所以只需要**正向迭代器**
 *  不可反转的容器
 *  总体来说，forward\_list更简单紧凑，功能更少

## queue:一个适配器类，它的默认底层类是deque ##

*  `#include <queue>`
 *  queue模板类让底层类deque展示出了典型的队列接口。所以它是一个适配器类。

> 还不是很清楚适配器的意思。ostream\_iterator类是一个适配器类，它让输出流可以使用迭代器接口。感觉像生活中的适配器，即接口，两端是不同的东西，它做中转，比如电源适配器让电脑可以使用家用交流电提供的接口——插座，因为它做了转换电压和电流的工作。

*  queue模板类的限制比deque要多：不允许随机访问队列元素；还不允许遍历队列！！！！

> 够狠。。。竟然不让遍历。。。后面看了栈，才明白原来就是不该随机访问和遍历。

*  queue类的方法：可以把元素添加到队尾，可以从队首删除元素，可以查看队首队尾的值，可以查看队列元素数目，可以测试队列是否为空。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]

> 都是作为队列最基本的操作。。

## priority\_queue：优先队列，也是适配器类，但默认底层类是vector ##

*  `#include <queue>`
 *  支持的操作和queue一样
 *  和queue的区别：最大的元素在队首，而最小的元素在队尾，即队列内部的元素是有序的。
 *  构造函数有一个可选参数，是一个函数对象，用于对队列内元素排序，决定谁在队首。  
    ![在这里插入图片描述][20200617212226206.png]

## stack：适配器类，底层类为vector ##

*  给默认的底层类vector提供了典型的栈接口
 *  限制比vector类多：不允许随机访问元素，不允许遍历栈！

> 想想也是，队列和栈都不应该提供遍历操作啊，也根本不应该提供随机访问，他们被称为队列和栈就是因为他们只能从一端进一端出或者一端进出的特殊特性的啊，就不能提供多一点的访问，这是他们自身的特点决定的，不是外界非要去限制他。

*  stack模板类的操作，都是栈数据结构需要的操作：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]

## array ##

*  `#include <array>`
 *  模板类array并不是STL容器，因为长度是固定的。它没有调整容器大小的操作，比如`push_back(), insert()`。
 *  它的操作：`operator[], at()`,对于它来说很有用
 *  很多STL标准算法都可以用到array模板类上，比如`copy(), for_each()`

# 关联容器：对容器概念的另一个改进，基于树数据结构，把值和键关联在一起 #

associative container

关联容器把值和键关联在一起，用键来查找值。

> 比如键是身份证号，值是性别，家庭地址，学号等  
> X::key\_type是键类型；X::value\_type是值类型

## 优缺点 ##

优点：

*  可以快速访问元素。

因为一般是用树结构实现的，比如二叉树，所以查找性能优于链表。同时还有链表的删除和插入数据的快速的优点，因为也是使用链接来存储。

> 只要设计不搞幺蛾子，树的查找速度比链表快

缺点：

*  不能指定插入新元素的位置。而序列容器可以指定。

因为关联容器一般有**确定数据放置位置的算法**，比如哈希算法，以便于查找时可以快速找到。

> 它的优点决定了它必然有这个缺点。果然什么都是平衡的，鱼和熊掌不可兼得，一方面见长就总有一方面见短，现在终于明白 舍得 二字的含义了，你选择得一样东西，就会舍一样东西。太哲学了，美啊。

## 4种关联容器：set, multiset, map, multimap ##

前两种是在set头文件定义，后两个在map头文件定义。

### set：最简单的关联容器（值就是键！） ###

集合

*  `#include <set>`
 *  **键和值的类型相同**。
 *  关联集合把键看做是**常量**。
 *  集合中**不会有多个相同的键**。键是唯一的。其实说白了，对于set，**值就是键**！所以无法存储多个相同的值。
 *  可反转
 *  可排序，set对象都是排好序的！！！

set<string> A;//第一个模板参数是存储的值的类型，第二个模板参数（这里省略了）是对键进行排序的函数指针

#### 示例 ####

#include <iostream>
    #include <list>
    #include <iterator>
    #include <string>
    #include <set>
    #include <algorithm>
    void outint(int n){ std::cout << n << ' ';}
    
    int main()
    { 
    	using namespace std;
    	string s[5] = { "buff", "thinkers", "for", "heavy", "van"};
    	set<string> a(s, s+5);//用迭代器区间作为参数的构造函数，这提供了把集合初始化为数组内容的简单方法，很多容器都有这种参数的构造函数
    	ostream_iterator<string, char> out(cout, " ");
    	copy(a.begin(), a.end(), out);
    	return 0;
    }

看来默认是按照升序排序的

buff for heavy thinkers van

#### 集合的交，并，差运算的STL方法 ####

*  数学上，集合有交并差运算。STL提供了**通用**方法，不是set类的成员方法，还可以用于其他类的对象。
 *  这些方法使用的先决条件：**容器是经过排序的**。set容器自动满足。

通用方法有：

*  `set_union()`:求并集，接受5个参数，1-2号参数指定第一个集合的区间；3-4号参数指定第二个集合的区间；最后一个参数是输出迭代器，指出把结果复制到什么位置。

set_union(a.begin(), a.end(), b.begin(), b.end(), ostream_iterator<string, char> out(cout, " "));

如果要把结果放在一个集合中，而不是显示，则：

set_union(a.begin(), a.end(), b.begin(), b.end(), insert_iterator<set<string>> (c, c.begin()));

注意千万不要把最后一个参数写为c.begin()：

*  因为c是空的，而这里相当于是copy()的那种**复制**（而不是插入），所以要求c必须有足够空间，可这里c是空的，所以不行；
 *  另一个原因是，**关联集合set的键是常量**，所以**c.begin()返回的迭代器是常量迭代器，而常量迭代器是不可以作为输出迭代器**的，毕竟你不能给常量赋值啊。所以这里只能用插入迭代器。

> 看出插入迭代器的作用来了吧。

*  `set_intersection()`:求交集,接口`set_union()`和一样
 *  `set_difference()`：求差集,接口`set_union()`和一样

set类的成员方法有：

*  `lower_bound()`: 参数是键，返回值是迭代器，指向集合中第一个小于键参数的成员
 *  `upper_bound()`：参数是键，返回值是迭代器，指向集合中第一个大于键参数的成员

##### 示例：还是要靠敲 #####

感觉现在对各种容器都在学概念，实际写代码不多，所以记忆不深刻，也不熟悉，其实没记住啥的感觉，留不下深刻印象。写了这个示例要好一些，还是要靠敲。

#include <iostream>
     #include <set>
     #include <string>
     #include <iterator>
     #include <algorithm>
    
     int main()
     { 
    	using namespace std;//使用了偷懒的方式处理名称空间问题
    	const int N = 6;
    	string s1[N] = { "buffoon", "thinkers", "for", "heavy", "can", "for"};//有重复值
    	string s2[N] = { "metal", "any", "food", "elegant", "deliver", "for"};
    
    	set<string> a(s1, s1+N);//set模板类的构造函数的参数是表示区间的迭代器
    	set<string> b(s2, s2+N);
    
    	//输出流迭代器
    	ostream_iterator<string, char> out(cout, " ");
    	//输出集合a，b
    	cout << "Set a:\n";
    	copy(a.begin(), a.end(), out);
    	cout << "\nSet b:\n";
    	copy(b.begin(), b.end(), out);
    
    	//并
    	cout << "\nunion of a and b:\n";
    	set_union(a.begin(), a.end(), b.begin(), b.end(), out);//前四个参数都是常量迭代器
    	//交
    	cout << "\nintersection of a and b:\n";
    	set_intersection(a.begin(), a.end(), b.begin(), b.end(), out);
    	//差
    	cout << "\ndifference of a and b:\n";
    	set_difference(a.begin(), a.end(), b.begin(), b.end(), out);
    
    	//输出到另一个集合
    	set<string> c;//空集合
    	set_union(a.begin(), a.end(), b.begin(), b.end(), insert_iterator<set<string>>(c, c.begin()));//使用匿名插入迭代器
    	cout << "\nSet c:\n";
    	copy(c.begin(), c.end(), out);
    
    	string s3("grungy");
    	c.insert(s3);//集合的insert方法
    	cout << "\nSet c after insertion:\n";
    	copy(c.begin(), c.end(), out);
    
    	cout << "\nShowing a range:\n";
    	copy(c.lower_bound("ghost"), c.upper_bound("spook"), out);
    	return 0;
     }

Set a:
    buffoon can for heavy thinkers
    Set b:
    any deliver elegant food for metal
    union of a and b:
    any buffoon can deliver elegant food for heavy metal thinkers
    intersection of a and b:
    for
    difference of a and b:
    buffoon can heavy thinkers
    Set c:
    any buffoon can deliver elegant food for heavy metal thinkers
    Set c after insertion:
    any buffoon can deliver elegant food for grungy heavy metal thinkers
    Showing a range:
    grungy heavy metal

学到的点：

*  插入迭代器的模板参数是集合的**具体类**，而输出流迭代器的模板参数有两个，一个是要输出的元素的数据类型，一个是输出流字符类型。我对输出流迭代器更熟悉一点点，因为用过几次了，但是对插入迭代器不太熟悉，连模板参数是什么都不知道。
 *  set果然是本身就有序的，用s1数组初始化以后，输出就是有序的，**且重复的for就只保留了一个**，说明**只要把一个无序的有重复值的字符串扔进set,就瞬间完成了排序和去除重复值的任务**，在力扣有刷到这种题，有一种方案就是一句代码set完成的。
 *  insert函数是set的成员函数，参数是set模板的具体化的类的对象，这里即string类对象。且插入会保证插入到正确的位置，保证插入后仍然有序。
 *  lower\_bound()返回大于参数的值的迭代器，而upper\_bound()返回小于参数的值的迭代器。很棒。
 *  只要把set\_union()等方法的租后一个参数设置为输出流迭代器，就可以完成输出到屏幕的功能，如果不这么做，则再用copy()函数也可以做到，很有意思。

### multiset ###

*  `#include <set>`
 *  集合中会有多个相同的键。键不是唯一的。

比如：1， 2， 3，2， 4， 2， 7， 7

*  其他和set一样

### map ###

*  `#include <map>`
 *  值和键的类型不同
 *  键唯一，每个键只对应一个值

### multimap ###

*  `#include <map>`
 *  键和值的类型不同
 *  键不是唯一的。一个键可以关联多个值。比如区号为718(键)的城市（值）可以有好几个。
 *  其他和map一样
 *  和set一样，可反转，已经过排序,数据项按键排序
 *  声明：

multimap<int, string> codes;//第一个模板参数是键类型，第二个模板参数是值类型，第三个模板参数是对键排序的函数对象，默认使用模板less<>，其模板参数是键类型

为了把键类型和值类型结合为一对，即把键和值存储到同一个对象中，即一条数据只用一个对象来存，这样才统一。STL使用了一个模板类：`pair<class T, class U>`。且每一个pair对象的实际类型是`pair<const keytype, datatype>`, 比如codes对象中的每一个值的类型实际上是`pair<const int, string>`。因为键的内容是不能改的，只有值可以修改。

比如要给codes对象插入一条数据（codes对象只是一个multimap容器，它里面可以装多条数据，每一个数据都是一个pair模板类的具体化类的对象）：

pair<const int, string> item(231, "Los Angeles");
    codes.insert(item);//插入到按键排序的正确位置

或者直接插入匿名的pair对象：

codes.insert(pair<const int, string> (231, "Los Angeles"));

#### 成员方法 ####

*  `count()`：参数为键，返回值是有这个键的元素的数目
 *  `lower_bound()`：参数是键，返回值是大于键的第一个迭代器
 *  `upper_bound()`：参数是键，返回值是小于键的第一个迭代器
 *  `equal_range()`：参数是键，返回两个迭代器，表示的区间和参数的键匹配。即返回参数键所在的区间。  
    返回的链各个迭代器被封装在一个pair对象中，这个pair的俩模板参数都是迭代器。  
    由于multimap对象的多条数据也是已经排序的，且是按键排序的，所以返回的范围包含的是同一个键的所有值。比如区号为718的所有城市：

pair<multimap<const int, string>::iterator, 
    multimap<const int, string>::iterator> range
    = codes.equal_range(718);
    
    cout << "Cities with area code 718:\n";
    multimap<const int, string>::iterator it;
    for (it = range.first;it!=range.second;++it)
    	cout << (*it).second << endl;

。。。。。

练打字速度还是练眼睛啊？？

auto 在哪？？？给我上！！！！

auto range = codes.equal_range(718);
    for (auto it = range.first;it!=range.second;++it)
    	cout << (*it).second << endl;

注意，pair对象的第一个参数是他的first公有成员变量，第二个参数存在second公有成员变量中。

##### 示例 #####

很简单。

#include <iostream>
    #include <map>
    #include <algorithm>
    #include <iterator>
    #include <string>
    typedef int keytype;
    typedef std::pair<const keytype, std::string> Pair;
    typedef std::multimap<keytype, std::string> MapCode;
    int main(){ 
    	using namespace std;
    	MapCode code;
    
    	code.insert(Pair(415, "San Francisco"));
    	code.insert(Pair(510, "Oakland"));
    	code.insert(Pair(718, "Brooklyn"));
    	code.insert(Pair(718, "Staten Island"));
    	code.insert(Pair(415, "San Rafael"));
    	code.insert(Pair(510, "Berkeley"));
    
    	cout << "Number of cities with area code 415: ";
    	cout << code.count(415) << endl;
    	cout << "Number of cities with area code 718: ";
    	cout << code.count(718) << endl;
    	cout << "Number of cities with area code 510: ";
    	cout << code.count(510) << endl;
    
    	cout << "Area Code\tCity\n";
    	for (auto it=code.begin();it!=code.end();++it)
    		cout << (*it).first << "\t\t" << (*it).second << endl;
    	auto range = code.equal_range(718);
    	cout << "Cities with area code 718:\n";
    	for (auto it = range.first;it!=range.second;++it)
    		cout << (*it).second << endl;
    	return 0;
    }

可以看到，只对键排序，同一个键下的值并没有排序哦。

Number of cities with area code 415: 2
    Number of cities with area code 718: 2
    Number of cities with area code 510: 2
    Area Code       City
    415             San Francisco
    415             San Rafael
    510             Oakland
    510             Berkeley
    718             Brooklyn
    718             Staten Island
    Cities with area code 718:
    Brooklyn
    Staten Island

# 无序关联容器：对容器概念的另一种改进，C++11新增，基于哈希表数据结构 #

基于哈希表主要是为了提高查找算法的效率，以及插入和删除元素的效率。

## 4种无序关联容器 ##

*  unordered\_set
 *  unordered\_multiset
 *  unordered\_map
 *  unordered\_multimap

# 容器类型：可创建具体容器对象的模板 #

C++11之前有11种容器：

*  deque：double-ended queue，双端队列，可以在两端添加和删除元素。
 *  list
 *  queue：队列，队尾加元素，队头删元素
 *  priority\_queue
 *  stack
 *  vector
 *  map
 *  multimap
 *  set
 *  multiset
 *  bitset：在比特级处理数据  
    C++11新增的5个容器：
 *  forward\_list
 *  unordered\_map
 *  unordered\_multimap
 *  unordered\_set
 *  unordered\_multiset

一共16种，但是C++11还把之前的bitset的容器身份取消了，把他当做一个普通的类，并不当做容器了，所以一共只有15种。

# 总结 #

*  感觉学习STL，容器，迭代器时理解能力变弱了一点，大概因为都是全新的知识和理念吧，都需要时间去接受和消化。
 *  我对基于范围的for循环很不熟悉，一定要加强，多用，感觉逼格很高。
 *  到现在，感觉C++里面面向对象只是一部分，也许在Java中只有oop吧，但是C++中泛型编程也占据了相当的领土，甚至GP的理念对C++的影响更大！OOP和GP没有任何冲突，在C++的世界里紧密合作，各自展示优势，用自己的办法尽量重用代码，写出更优雅紧凑安全的代码。
 *  终于明白auto的力量了。。。我猜先有模板后有auto。。。毕竟模板写起来太长了，又要写模板参数，还能要写迭代器啥的，很长很长。  
    对了，还有typedef,太有用了。。。
 *  queue, priority\_queue, stack都是**适配器类**模板，适配器类模板让底层容器类可以提供出适配器类模板名称所建议的特性接口。

> 适配器类或者适配器函数，总之“适配”二字，表示的就是一个**转换**的意思。底层的容器类就像家用220v交流电，而电源适配器让家用交流电提供电器真正可以用的低电压的直流电。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617191534130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061719222473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200617193631547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020061719373664.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200617200052475.png]: https://img-blog.csdnimg.cn/20200617200052475.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200617201928603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200617211916589.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200617212226206.png]: https://img-blog.csdnimg.cn/20200617212226206.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/202006172130191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70