关联式容器
我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义 :
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair()
: first(T1())
, second(T2())
{}
pair(const T1& a, const T2& b)
: first(a)
, second(b)
{}
};
树形结构的关联式容器
根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面介绍map和set
set
set的介绍
set文档介绍
翻译：
- set是按照一定次序存储元素的容器
- 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
- set在底层是用二叉搜索树(红黑树)实现的。
注意：
- 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
- set中插入元素时，只需要插入value即可，不需要构造键值对。
- set中的元素不可以重复(因此可以使用set进行去重)。
- 使用set的迭代器遍历set中的元素，可以得到有序序列
- set中的元素默认按照小于来比较
- set中查找某个元素，时间复杂度为：log2(N)
- set中的元素不允许修改
- set中的底层使用二叉搜索树(红黑树)来实现
set的使用
set的模板参数列表
- T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
- Compare：set中元素默认按照小于来比较
- Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
set的构造
函数声明 功能介绍 set (const Compare& comp = Compare(), const Allocator& = Allocator() ); 构造空的set set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); 用[first, last)区间 中的元素构造set set (const set& x); set的拷贝构造 set的迭代器
函数声明 功能介绍 iterator begin() 返回set中起始位置元素的迭代器 iterator end() 返回set中最后一个元素后面的迭代器 const_iterator cbegin() const 返回set中起始位置元素的const迭代器 const_iterator cend() const 返回set中最后一个元素后面的const迭代器 reverse_iterator rbegin() 返回set第一个元素的反向迭代器，即end reverse_iterator rend() 返回set最后一个元素下一个位置的反向迭代器，即 rbegin const_reverse_iterator crbegin() const 返回set第一个元素的反向const迭代器，即cend const_reverse_iterator crend() const 返回set最后一个元素下一个位置的反向const迭代器， 即crbegin set的容量
函数声明 功能介绍 bool empty ( ) const 检测set是否为空，空返回true，否则返回true size_type size() const 返回set中有效元素的个数 set修改操作
函数声明 功能介绍 pair<iterator,bool> insert ( const value_type& x ) 在set中插入元素x，实际插入的是<x, x>构成的键值对， 如果插入成功，返回<该元素在set中的位置，true>,如果 插入失败，说明x在set中已经存在，返回<x在set中的位 置，false> void erase ( iterator position ) 删除set中position位置上的元素 size_type erase ( const key_type& x ) 删除set中值为x的元素，返回删除的元素的个数 void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素 void swap ( set<Key,Compare,Allocator>& st ); 交换set中的元素 void clear ( ) 将set中的元素清空 iterator find ( const key_type& x ) const 返回set中值为x的元素的位置 size_type count ( const key_type& x ) const 返回set中值为x的元素的个数 erase与find的使用：
set本身是提供find的，如果找到了返回这个元素的迭代器，没找到就返回end位置，所以用find结合erase的方式来删除元素，要确保set中有该元素，否则，set会删除end位置，该位置是不属于set的，也就是非法删除了空间。
而直接用
erase(40);这种方法，set中有40就删除，没有就不删除任何元素算法库中的find和set提供的find的区别：效率不同。算法库中的find是遍历容器来查找，时间复杂度为O(N)，而set的find是按照搜索树的特点来查找，时间复杂度为O(logN)
set的使用举例
void test_set1() {std::set s;
s.insert(2);
s.insert(3);
s.insert(2);
s.insert(10);
s.insert(5);
s.insert(9);// set中值为3的元素出现了几次
std::cout << s.count(3) << std::endl;//迭代器的使用
std::set::iterator it = s.begin();
while (it != s.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;for (auto& e : s)
{
std::cout << e << " ";
}
std::cout << std::endl;//erase的使用
std::set::iterator pos = s.find(30);
if (pos != s.end())
{
s.erase(pos);
}for (auto& e : s)
{
std::cout << e << " ";
}
std::cout << std::endl;s.erase(40);
s.erase(10);for (auto& e : s)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
map
map的介绍
map的文档简介
翻译：
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
- map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))
map的使用
map的模板参数说明
- key: 键值对中key的类型
- T： 键值对中value的类型
- Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
- Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件
map的构造
函数声明 功能介绍 map() 构造一个空的map map的迭代器
函数声明 功能介绍 begin()和end() begin:首元素的位置，end最后一个元素的下一个位置 cbegin()和cend() 与begin和end意义相同，但cbegin和cend所指向的元素不能修改 rbegin()和rend() 反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与 begin和end操作移动相反 crbegin()和crend() 与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元 素不能修改 map的容量与元素访问
函数声明 功能简介 bool empty ( ) const 检测map中的元素是否为空，是返回true，否则 返回false size_type size() const 返回map中有效元素的个数 mapped_type& operator[] (const key_type& k) 返回key对应的value operator[]的底层是用insert实现的
insert的返回值是一个键值对pair<iterator, bool>，第一个是迭代器，第二个是bool值。
insert的返回值分两种情况：
- 当前树中不存在插入的元素，则进行插入，pair的第一个参数返回插入后指向新元素的迭代器，第二个参数返回true
- 当前树中已存在相同的key，pair的第一个参数返回已存在的元素的迭代器，第二个参数返回false
问题：当key不在map中时，通过operator[]获取对应value时会发生什么问题？
看看官方文档怎么说
- 如果传入的key已经存在，则返回key对应的value(引用)。
- 如果传入的key不存在，则会将该key进行插入，key的value通过默认的构造函数来创建。
operator[]的底层实现：
(*((this->insert(make_pair(k,mapped_type()))).first)).second解析：
所以，operator[]有三个作用：
- 插入
- 查找key对应的value
- 修改key对应的value，因为返回的是引用
一般不用operator[]进行查找，只用它进行插入和修改，查找可能改变树的结构
注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常
map中元素的修改
函数声明 功能简介 pair<iterator,bool> insert ( const value_type& x ) 在map中插入键值对x，注意x是一个键值对，返回值 也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功 void erase ( iterator position ) 删除position位置上的元素 size_type erase ( const key_type& x ) 删除键值为x的元素，返回删除的元素个数 void erase ( iterator first, iterator last ) 删除[first, last)区间中的元素 void swap ( map<Key,T,Compare,Allocator>& mp ) 交换两个map中的元素 void clear ( ) 将map中的元素清空 iterator find ( const key_type& x ) 在map中查找key为x的元素，找到返回该元素的位置 的迭代器，否则返回end const_iterator find ( const key_type& x ) const 在map中查找key为x的元素，找到返回该元素的位置 的const迭代器，否则返回cend size_type count ( const key_type& x ) const 返回key为x的键值在map中的个数，注意map中key 是唯一的，因此该函数的返回值要么为0，要么为1，因 此也可以用该函数来检测一个key是否在map中 拿insert的参数vlaue_type举例，value_type是通过typedef pair出来的，所以value_type是一个键值对。插入的语法是
insert(pair<T,T>)，同样迭代器表示的也是一个键值对，所以一个迭代器实际上是一个键值对的指针map的使用举例
void test_map1() {std::map<int, int> m;
m.insert(std::pair<int, int>(1,1));
m.insert(std::pair<int, int>(2,2));
m.insert(std::make_pair(3,3));//make_pair是pair的构造函数，构造的是一个匿名的pair，省去了模板类型的声明/ std::map<int, int>::iterator it = m.begin();while (it != m.end())
{
std::cout << it->first << “:” << it->second << std::endl;
++it;
}}
void test_map2()
{
std::string strs[] = {“张三”,“李四”, “张三”, “王五”, “张三”,“王五”,“张三”, “王五”, “赵六”, “张三”, “张三”, “赵六”, “李四”, “王五”, “张三”, “张三” };//统计名字出现的次数
std::map<std::string, int> count_map;for (std::string& sstr : strs)
{
auto pos = count_map.find(sstr);
if (pos != count_map.end())
{
pos->second++;
}
else
{
count_map.insert(std::make_pair(sstr, 1));
}
}std::map<std::string, int>::iterator it = count_map.begin();
while (it != count_map.end())
{
std::cout << it->first << “:” << it->second << std::endl;
++it;
}}
```cpp #include <string> #include <map>void TestMap()
{
map<string, string> m;
// 向map中插入元素的方式：
// 将键值对<“peach”,“桃子”>插入map中，用pair直接来构造键值对
m.insert(pair<string, string>(“peach”, “桃子”));// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对 m.insert(make_pair("banan", "香蕉")); // 借用operator[]向map中插入元素 /* operator[]的原理是： 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器 operator[]函数最后将insert返回值键值对中的value返回 */ // 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果， m["apple"] = "苹果"; // key不存在时抛异常 //m.at("waterme") = "水蜜桃"; cout << m.size() << endl; // 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列 for (auto& e : m) cout << e.first << "--->" << e.second << endl; cout << endl; // map中的键值对key一定是唯一的，如果key存在将插入失败 auto ret = m.insert(make_pair("peach", "桃色")); if (ret.second) cout << "<peach, 桃色>不在map中, 已经插入" << endl; else cout << "键值为peach的元素已经存在：" << ret.first->first << "--->" << ret.first->second <<" 插入失败"<< endl; // 删除key为"apple"的元素 m.erase("apple"); if (1 == m.count("apple")) cout << "apple还在" << endl; else cout << "apple被吃了" << endl;}
map的用法总结
- 增 insert + operator[]
- 删 erase
- 查 find
- 改 operator[]
- 遍历 iterator + 范围for
注：遍历出来的数据都是按key排序的，因为底层是搜索树， 遍历是按照树的中序来的
map中存的是pair<key, value>键值对，迭代器指向的是pair
multiset
multiset的介绍
multiset文档介绍
[翻译]：
- multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
- 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
- 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
- multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
- multiset底层结构为二叉搜索树(红黑树)
注意：
- multiset中在底层中存储的是<value, value>的键值对
- mtltiset的插入接口中只需要插入即可
- 与set的区别是，multiset中的元素可以重复，set中value是唯一的
- 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
- multiset中的元素不能修改
- 在multiset中找某个元素，时间复杂度为log2(N)
- multiset的find如果查找的元素有重复，则返回的是重复元素的第一个
- multiset的作用：可以对元素进行排序
multiset的使用
此处只简单演示set与multiset的不同，其他接口接口与set相同
#include <set>
void TestSet()
{
int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
// 注意：multiset在底层实际存储的是<int, int>的键值对
multiset<int> s(array, array + sizeof(array)/sizeof(array[0]));
for (auto& e : s)
cout << e << " ";
cout << endl;
return 0;
}
multimap
multimap的介绍
multimap文档介绍
翻译：
- Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
- 在multimap中，通常按照key排序和唯一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:
typedef pair<const Key, T> value_type;- 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
- multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历
multimap中的元素可以得到关于key有序的序列。- multimap在底层用二叉搜索树(红黑树)来实现。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的
multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：
- multimap中的key是可以重复的。
- multimap中的元素默认将key按照小于来比较
- multimap中没有重载operator[]操作。multimap中有多个相同的key时，不知道要返回哪个key对应的value
- 使用时与map包含的头文件相同
在OJ中的使用
两个思路：
- 先用map<string, int>统计出单词出现的次数，再将pair<string, int>键值对放到vector中，用sort排序，需要我们自己定义一个按int比较的仿函数排完后，还需要对次数相同的单词按字母排。因为sort是快排实现的，不稳定，排完了单词的相对顺序会改变。
- 用multimap排序。
同样先用map<string, int>统计出单词出现的次数，再用multimap<int, string>对出现次数进行排序(此时默认是升序的)，然后取出倒数的k个单词，可是怎么取呢，用反向迭代器的话会导致出现次数相同的单词不能按照字典序排列(map进行排序时，是按string来排的，string的排序就是按照字典序)，所以我们用multimap排序时，不按照升序排，按照降序排(multimap遍历相同key的顺序是按照插入顺序来的，而遍历map时，插入顺序就是字典序)，使用的就是multimap< int, string, greater >，然后取出前k个单词
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
map<string ,int> countMap;
for (auto& e : words)
{
countMap[e]++;//统计单词出现次数
}
//按单词出现次数排序
multimap<int, string, greater<int>> countSort;
for (auto& kv : countMap)
{
countSort.insert(make_pair(kv.second, kv.first));
}
vector<string> ret;
for (auto& kv : countSort)
{
if (k == 0)
break;
ret.push_back(kv.second);
--k;
}
return ret;
}
};