目录
1、关联式容器
在之前，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是键值对，在数据检索时比序列式容器效率更高。
2、键值对
用来表示具有相对应关系的一种结构，该结构中一般只包含两个成员变量key和value，比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是相对应的关系，即通过该英文单词，在词典中就可以找到与其对应的中文含义。
2.1、pair
在C++的utility库中的pair模板，用来定义键值对类型。
template <class T1, class T2> struct pair;这两个模板参数分别为key和value。
2.2、构造函数
其构造函数为：
pair(); // 默认构造
template<class U, class V>
pair (const pair<U,V>& pr); // 既可以是构造，也可以是拷贝构造
pair (const first_type& a, const second_type& b); // 构造2.3、make_pair
构造一个键值对对象：
template <class T1, class T2>
pair<T1,T2> make_pair (T1 x, T2 y);该模板函数的行为与下面的定义类似：
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}2.4、大小比较
这个键值对的比较规则就是先比较T1，再比较T2。
template <class T1, class T2>
bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);
template <class T1, class T2>
bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);
template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);
template <class T1, class T2>
bool operator<= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);
template <class T1, class T2>
bool operator> (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);
template <class T1, class T2>
bool operator>= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs);上面的模板函数的行为与下面的定义类似：
template <class T1, class T2>
bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first==rhs.first && lhs.second==rhs.second; }
template <class T1, class T2>
bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(lhs==rhs); }
template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }
template <class T1, class T2>
bool operator<= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(rhs<lhs); }
template <class T1, class T2>
bool operator> (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return rhs<lhs; }
template <class T1, class T2>
bool operator>= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(lhs<rhs); }3、树形结构与哈希结构
根据应用场景的不桶，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(红黑树)作为其底层结构，下面一依次介绍每一个容器。
4、set与multiset
4.1、set
set是按照一定次序存储元素的容器，在set中，每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)。set在底层是用二叉搜索树(红黑树)实现的。
注意：
1、与map和multimap不同，map和multimap中存储的是键值对，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2、set中插入元素时，只需要插入value即可，不需要构造键值对。
3、set中的元素不可以重复(因此可以使用set进行去重)。
4、使用set的迭代器遍历set中的元素，可以得到有序序列（走的是中序遍历）。
5、set中的元素默认按照小于来比较。
6、set中查找某个元素，时间复杂度为：O(log(N))
7、set中的元素不允许修改(为了防止破坏set的底层结构)。
template < class T, class Compare = less<T>, class Alloc = allocator<T> >
class set;T：set中存放元素的类型，实际在底层存储的键值对。 Compare：set中元素默认按照小于来比较 Alloc：空间配置器（后面讲）。
4.1.1、构造与赋值重载
explicit set (const key_compare& comp = key_compare(), // 默认构造
const allocator_type& alloc = allocator_type());
set (const set& x); // 拷贝构造
set& operator= (const set& x); // 赋值重载4.1.2、迭代器
树形结构的迭代器设计相较于线性的结构较为复杂，可看第十六讲中set和map的模拟实现。
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;4.1.3、容量
bool empty() const; //判断是否为空
size_type size() const; // 返回元素个数
4.1.4、修改
pair<iterator,bool> insert (const value_type& val); // 插入
void erase (iterator position); // 删除set中position位置上的元素
size_type erase (const value_type& val); // 通过value删除
void swap (set& x); // 交换
void clear(); // 清空注意：
1、使用insert在set中插入元素value时，实际上插入的是<value, value>构成的键值对；如果插入成功，返回<该元素在set中的位置, true>该键值对，如果失败，则说明value在set中已经存在，返回<已存在的value的位置, false>。
2、erase (iterator position)，若删除的值存在，则删除；不存在则报错。第二个erase (const value_type& val)，若成功删除，返回删除了几个元素（因为在set中每个元素是唯一的，所以实际上成功删除只会返回1）；若不存在，则返回0。
4.1.5、操作
iterator find (const value_type& val) const; // 查找
size_type count (const value_type& val) const; // 返回set中值为val的元素的个数
iterator lower_bound (const value_type& val) const; // 返回大于等于val值位置的迭代器
iterator upper_bound (const value_type& val) const; // 返回大于val值位置的迭代器
pair<iterator,iterator> equal_range (const value_type& val) const; 注意：
1、因为set中每个元素都是唯一的，因此上面的count函数实际上只会返回1或者0，1表示有一个，0表示没有；所以该函数一般被用来判断某个值是否存在。
2、equal_range函数返回的键值对是<大于等于val的位置，大于val的位置>。
例如：
void test_set()
{
set<int> s;
s.insert(5);
s.insert(2);
s.insert(6);
s.insert(1);
s.insert(1);
s.insert(2);
set<int>::iterator it1 = s.begin();
while (it1 != s.end())
{
cout << *it1 << ' ';
++it1;
}
cout << endl;
pair<set<int>::iterator, bool> ret1 = s.insert(5);
cout << ret1.second << endl;
pair<set<int>::iterator, bool> ret2 = s.insert(3);
cout << ret2.second << endl;
for (auto e : s) // 只要能用迭代器，那就能使用范围for。
{
cout << e << ' ';
}
cout << endl;
set<int>::reverse_iterator it2 = s.rbegin();
while (it2 != s.rend())
{
cout << *it2 << ' ';
++it2;
}
cout << endl;
s.erase(2);
s.erase(10);
set<int>::iterator it3 = s.begin();
while (it3 != s.end())
{
cout << *it3 << ' ';
++it3;
}
cout << endl;
set<int>::iterator ret3 = s.find(5);
if (ret3 != s.end())
{
s.erase(5);
}
for (auto e : s)
{
cout << e << ' ';
}
cout << endl;
if (s.count(3))
{
cout << "3存在" << endl;
}
else
{
cout << "3不存在" << endl;
}
cout << s.size() << endl;
set<int> myset;
set<int>::iterator itlow, itup;
for (int i = 1; i < 10; i++)
{
myset.insert(i * 10);
}
itlow = myset.lower_bound(25);
itup = myset.upper_bound(70);
myset.erase(itlow, itup);
for (auto e : myset)
{
cout << e << ' ';
}
cout << endl;
set<int> my_set;
for (int i = 1; i < 10; i++)
{
my_set.insert(i * 10);
}
pair<set<int>::iterator, set<int>::iterator> ret4 = my_set.equal_range(35);
cout << *ret4.first << endl;
cout << *ret4.second << endl;
}
4.2、multiset
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的（这是与set最大的区别）。multiset元素的值不能在容器中进行修改(因为元素总是const的)， multiset底层结构为二叉搜索树(红黑树)。
注意：
1、multiset中在底层中存储的是<value, value>的键值对。
2、与set的区别是，multiset中的元素可以重复，set中value是唯一的。
3、使用迭代器对multiset中的元素进行遍历，可以得到有序的序列。
4、multiset中的元素不能修改。
5、在multiset中找某个元素，时间复杂度为O(log(N))
6、multiset的作用：可以对元素进行排序。
template < class T, class Compare = less<T>, class Alloc = allocator<T> >
class multiset; 4.2.1、构造与赋值重载
explicit multiset (const key_compare& comp = key_compare(), // 默认构造
const allocator_type& alloc = allocator_type());
multiset (const multiset& x); // 拷贝构造
multiset& operator= (const multiset& x); // 赋值重载4.2.2、迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;4.2.3、容量
bool empty() const; // 判断是否为空
size_type size() const; // 返回元素个数4.2.4、修改
iterator insert (const value_type& val); // 插入
void erase (iterator position); // 删除
size_type erase (const value_type& val); // 删除
void swap (multiset& x); // 交换
void clear(); // 清空注意：当有多个相同的元素时，erase (const value_type& val)删除所有的val，返回删除的个数。
4.2.5、操作
iterator find (const value_type& val) const; // 查找
size_type count (const value_type& val) const; // 返回值为val的元素个数
iterator lower_bound (const value_type& val) const;
iterator upper_bound (const value_type& val) const;
pair<iterator,iterator> equal_range (const value_type& val) const; 注意：当有多个相同的元素时，find查找该元素返回的是中序遍历序列中第一次出现该值的位置。
例如：
void test_multiset()
{
multiset<int> s;
s.insert(5);
s.insert(2);
s.insert(6);
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(1);
s.insert(5);
s.insert(2);
multiset<int>::iterator it1 = s.begin();
while (it1 != s.end())
{
cout << *it1 << ' ';
++it1;
}
cout << endl;
multiset<int>::iterator it2 = s.find(2);
while (it2 != s.end())
{
cout << *it2 << ' ';
++it2;
}
cout << endl;
cout << s.count(1) << endl;
size_t n = s.erase(5);
cout << n << endl;
for (auto e : s)
{
cout << e << ' ';
}
cout << endl;
}5、map与multimap
5.1、map
map是关联容器，它按照key来比较，存储由key和value组合而成的元素。 在map中，key通常用于排序和唯一地标识元素，而value中存储与此key相关联的内容。键值key和值value的类型可能不同，map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说是平衡二叉搜索树(即红黑树))。
注意：
1、map中的的元素是键值对。
2、map中的key是唯一的，并且不能修改；其中的value是可以被修改的。
3、默认按照小于的方式对key进行比较。
4、map中的元素如果用迭代器去遍历，可以得到一个有序的序列。
5、map的底层为平衡搜索树(红黑树)，查找效率比较高O(logN) 。
6、支持[]操作符，operator[]中实际进行插入查找。
template < class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T> >
class map;key：键值对中key的类型
T：键值对中value的类型
Compare：map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则。
Alloc：空间配置器，一般不需要用户传递，除非用户不想使用标准库提供的空间配置器。
5.1.1、构造与赋值重载
explicit map (const key_compare& comp = key_compare(), // 默认构造
const allocator_type& alloc = allocator_type());
map (const map& x); // 拷贝构造
map& operator= (const map& x); // 赋值重载
5.1.2、迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;5.1.3、容量
bool empty() const; // 判断是否为空
size_type size() const; // 返回元素个数5.1.4、访问
mapped_type& operator[] (const key_type& k);上面[]的重载的实现等价于：
(*((this->insert(make_pair(k,mapped_type()))).first)).second注意：在元素访问时，有一个与operator[]类似的操作at()函数(该函数不常用)，都是通过 key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认 value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。
5.1.5、修改
pair<iterator,bool> insert (const value_type& val); // 插入
void erase (iterator position); // 删除
size_type erase (const key_type& k); // 删除
void swap (map& x); // 交换
void clear(); // 清理5.1.6、操作
iterator find (const key_type& k); // 查找
const_iterator find (const key_type& k) const;
size_type count (const key_type& k) const;
例如：
void test_map()
{
map<string, string> dict;
dict.insert(pair<string, string>("sort", "排序"));
dict.insert(pair<string, string>("insert", "插入"));
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict["erase"];
cout << dict["erase"] << endl;
dict["erase"] = "删除";
cout << dict["erase"] << endl;
dict["test"] = "测试";
dict["left"] = "左边、剩余";
string s1("xxx"), s2("yyy");
dict.insert(make_pair(s1, s2));
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << (*it).first << ':' << (*it).second << endl;
cout << it->first << ':' << it->second << endl;
++it;
}
cout << endl;
for (auto& e : dict)
{
cout << e.first << ':' << e.second << endl;
}
cout << endl;
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
countMap[str]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ':' << kv.second << endl;
}
cout << endl;
}5.2、multimap
Multimap是关联式容器，它按照特定的顺序，存储由key和value组成的键值对，其中多个键值对之间的key是可以重复的。multimap在底层用二叉搜索树(红黑树)来实现。multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
注意：
1、multimap中的key是可以重复的；但key仍然不可以修改，能修改的只是value。
2、multimap中的元素默认将key按照小于来比较。
3、multimap中没有重载operator[]操作(因为key值不唯一)。
template < class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T> >
class multimap;5.2.1、构造与赋值重载
explicit multimap (const key_compare& comp = key_compare(), // 默认构造
const allocator_type& alloc = allocator_type());
multimap (const multimap& x); // 拷贝构造
multimap& operator= (const multimap& x); // 赋值重载5.2.2、迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;5.2.3、容量
bool empty() const; // 判断是否为空
size_type size() const; // 返回元素个数5.2.4、修改
iterator insert (const value_type& val); // 插入
void erase (iterator position); // 删除
size_type erase (const key_type& k); // 删除
void swap (multimap& x); // 交换
void clear(); // 清理5.2.5、操作
iterator find (const key_type& k); // 查找
const_iterator find (const key_type& k) const;
size_type count (const key_type& k) const;multimap的使用方法与map类似，不再演示具体的使用。
6、题目
6.1、第一题
参考：
6.2、第二题
参考：
