关联式容器
C++STL包含了序列式容器和关联式容器：
序列式容器： 序列式容器里面储存的式元素本身 其底层为线性序列的数据结构 比如说：vector list deque等
关联式容器： 关联式容器里面储存的是<key , value>结构的键值对 一般在数据检索时 比序列式容器的效率更高 比如说 set map等
小Tip： C++STL中的queue和stack并不属于容器 而是容器适配器 本质是由容器封装而成的 默认封装容器是deque
树形结构与哈希结构
根据应用场景的不同 C++STL总共实现了两种不同结构的关联式容器： 树形结构和哈希结构
关联式容器 容器结构 底层实现
set、map、multiset、multimap 树型结构 平衡搜索树（红黑树）
unordered_set、unordered_map、
unordered_multiset、unordered_multimap 哈希结构 哈希表
其中 树形结构容器中的序列是一个有序的序列
而哈希结构容器中的序列是一个无序的序列
键值对
键值对是用来表示一种具有一一对应关系的一种结构 该结构中一般只包含两个成员变量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) {} };
set
set的介绍
set是按照一定次序来存储数据的容器 因此使用set的迭代器去遍历之 我们就能得到有序的序列
set当中存储的value值是唯一的 不可以重复 因此可以使用set进行去重
与map不同的是 map的底层存放的是真正的 k v键值对 set当中只存放 value 但是其实set的底层存放的是 v v键值对 因此在向set容器里面插入元素的时候 只需要插入value值就好
set中的元素不能被修改 因为set的底层是用二叉搜索树来实现的 如果我们修改了二叉搜索树某个节点的值的话 那么这棵树就不再是二叉搜索树了
在内部 set中的元素总是按照其内部比较对象所指示的特定严格弱排序来进行排序 当不传入内部比较对象时 set中的元素默认用小于来比较
set容器通过key访问单个元素的效率比unordered_set慢 但是set容器允许根据顺序对元素进行直接迭代
set底层是用红黑树来实现的 所以说它查找的复杂度为LogN
set的定义方式
方式一： 构造一个某类型的空容器
set<int> s1; // 构造int类型的空容器
方式二： 拷贝构造某类型set容器的复制品
set<int> s2(s1) // 拷贝构造与s1相同的容器
方式三： 使用迭代器拷贝构造某一段内容
string str("hello world"); set<char> s3(str.begin(), str.end()); // 使用string的迭代器拷贝构造
方式四： 构造一个某类型的空容器 比较方式指定为大于
set<int, greater<int>> s4; // 构造int类型的空容器 比较大小为greater
set的使用
常用接口函数
迭代器相关函数
使用代码如下
展示去重和范围for遍历
set<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); for (auto x : s1) { cout << x << endl; }
我们使用set容器 并且插入多组重复数据 之后使用范围for遍历 达到一个去重排序的效果
展示直接删除
set<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); for (auto x : s1) { cout << x << " "; } cout << endl; s1.erase(3); for (auto x : s1) { cout << x << " "; } cout << endl;
我们在使用erase括号后面跟上了要删除的值 之后遍历整个set容器
我们可以发现 3被删除了
那么如果我们连续两次删除3会有什么发生呢？
我们可以发现 还是和上面一样 只是删除了3而已
展示迭代器遍历（正反向遍历）
set<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); set<int>::iterator it = s1.begin(); while (it != s1.end()) { cout << *it << " "; it++; } cout << endl; set<int>::reverse_iterator it1 = s1.rbegin(); while (it1 != s1.rend()) { cout << *it1 << " "; it1++; }
我们还是采用了上面的几组数据 并且使用正向反向迭代器来遍历数据 结果如下
展示查找计数交换等
set<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); cout << s1.count(3) << endl; cout << s1.count(2) << endl; cout << s1.size() << endl; s1.clear(); cout << s1.size() << endl; cout << s1.empty() << endl;
我们可以发现查找 3 2 出现的次数
s1的大小 清空后的大小 以及s1是否为空
展示交换容器
set<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); set<int> s2; cout << s2.size() << endl; cout << s1.size() << endl; s2.swap(s1); cout << s2.size() << endl; cout << s1.size() << endl;
我们可以发现 交换完之后它们的大小发生了改变
multiset
multiset和set的底层实现都是相同的 接口函数也十分类似
它们之间最大的区别就是 multiset中允许键值对冗余
multiset<int> s1; s1.insert(1); s1.insert(3); s1.insert(5); s1.insert(3); s1.insert(4); s1.insert(9); s1.insert(7); s1.insert(4); for (auto x : s1) { cout << x << " "; }
我们可以发现 相比于set 这里多出来了很多冗余的数据
由于multiset容器允许键值冗余，因此两个容器中成员函数find和count的意义也有所不同
成员函数find 功能
set对象 返回值为val的元素的迭代器
multiset对象 返回底层搜索树中序的第一个值为val的元素的迭代器
成员函数count 功能
set对象 值为val的元素存在则返回1，不存在则返回0（find成员函数可代替）
multiset对象 返回值为val的元素个数（find成员函数不可代替）
map
map的介绍
map是关联式容器 它按照特定的次序来存储 < key value >数据 当我们遍历map中的数据的时候 我们可以得到一组有序的数据
在map中 键值key用于排序和唯一的标识元素 而值value则储存与key相关的内容 它们的类型可能不同 并且在map的内部 它们通过成员类型value_type绑定在一起 并取别名pair
map容器中的key值是不可以被改变的 但是value值可以被修改 这是因为map底层的二叉搜索是根据key建立的
在map内部 它的元素是按照key值来进行比较的 一般是默认小于
map容器通过键值key访问单个元素的效率比unordered_map容器慢 但是map容器允许根据顺序对元素进行迭代
map容器支持下标访问 即在【】中放入key 便可以找到对应的value
map底层是用红黑树实现的 查找某个元素的效率为 logN
map的定义方式
方式一： 指定构造key value类型的空容器
map<int, char> m1; // 创造一个key为int value为char的空容器
方式二： 拷贝构造某类型容器
map<int, char> m2(m1) // 拷贝构造一个m1的复制品m2
方式三： 使用迭代器拷贝构造某一段内容
map<int, char> m3(m2.begin(),m2.end()); // 使用m2的迭代器拷贝构造m3
方式四： 指定key和value的类型构造一个空容器 key比较方式指定为大于
map<int, char, greater<int>> m4;// 创造一个key为int value为char 比较方式为greater的空容器
map的插入
map插入函数的原型如下
pair<iterator,bool> insert (const value_type& val);
insert函数的参数
insert函数的参数是value_type类型的 实际上就是pair类型的别名
typedef pair<const Key, T> value_type;
因此 我们向map容器插入元素的时候 我们需要用key和value构造一个pair对象 然后再将pair对象作为参数传入insert函数
方式一： 构造匿名对象插入
map<string, string> dict; // 调用pair的构造函数 构造一个匿名对象 dict.insert(pair<string, string>("left", "左边")); dict.insert(pair<string, string>("right", "右边")); dict.insert(pair<string, string>("hello", "你好")); for (auto x : dict) { cout << x.first << " : " << x.second << endl; }
运行结果如下
但是这种插入方式会导致代码变得很长 所以我们不经常使用它 更多的是使用方式二
方式二： 使用模板插入
在库当中提供了以下的模板
template<class T1, class T2> pair<T1, T2> make_pair(T1 x, T2 y) { return (pair<T1, T2>(x, y)); }
因此我们只需要向函数传递key和value 该函数模板就会根据类型自动推导 最终返回一个pair对象
比如说我们上面的代码可以改写成这样子
map<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); for (auto x : dict) { cout << x.first << " : " << x.second << endl; }
是不是感觉代码整体简洁了不少呢
insert的返回值
我们首先来看官网的原文
The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
The versions with a hint (2) return an iterator pointing to either the newly inserted element or to the element that already had an equivalent key in the map.
Member type iterator is a bidirectional iterator type that points to elements.
pair is a class template declared in (see pair).
我们从上面可以知道
insert函数的返回值是一个pair对象 该对象中的第一个成员是map的迭代器类型 第二个成员是一个bool类型具体含义如下
若待插入元素的键值key在map当中不存在 则insert标识插入成功 并返回插入后元素的迭代器和true
若待插入元素的键值key在map当中存在 则insert插入失败 并返回map中键值为key的迭代器和false
map的查找
map查找函数的原型如下
iterator find (const key_type& k);
map查找函数是根据key值在map当中查找
如果找到了 则返回对应的迭代器 如果找不到 则返回end迭代器 map<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); // 查找right并且打印right的中文意思 auto it = dict.find("right"); if (it != dict.end()) { cout << it->second << endl; } }
map的删除
map删除的函数原型如下：
删除指定k值
size_type erase (const key_type& k);
删除迭代器位置
void erase(iterator position);
这里和set是一样的
我们使用两种方式删除
map<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); auto it = dict.find("right"); dict.erase(it); // 删除right的迭代器 dict.erase("left"); // 删除key值为left的数据 for (auto x : dict) { cout << x.first << " : " << x.second << endl; }
我们可以发现 最后dict被删除的只剩下了 hello
map的[ ]运算符重载
map的【】运算符重载的函数原型如下：
mapped_type& operator[] (const key_type& k);
【】运算符重载函数的参数就是一个key值 而这个函数的返回值如下
(*((this->insert(make_pair(k, mapped_type()))).first)).second
看上去可能有点难理解 但是我们分成三个步骤就好理解多了
使用insert插入键值对
获取insert函数的返回值迭代器
返回该迭代器元素的值value
对应的分解代码如下
mapped_type& operator[] (const key_type& k) { //1、调用insert函数插入键值对 pair<iterator, bool> ret = insert(make_pair(k, mapped_type())); //2、拿出从insert函数获取到的迭代器 iterator it = ret.first; //3、返回该迭代器位置元素的值value return it->second; }
那么这个重载【】有什么意义呢 我们看下面的这段代码
map<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); dict["right"] = "正确"; dict["go"] = "出发"; for (auto x : dict) { cout << x.first << " : " << x.second << endl; }
以这两行代码为例
dict["right"] = "正确"; dict["go"] = "出发";
通过了【】的三个步骤之后 不管原来的dict里面有没有我们的key值
都会通过insert函数来返回一个迭代器的value的引用
从而会发生下面的情况
我们修改了right的含义 并且增加了go的含义 于是我们可以总结一下
如果key不在map中 则使用【】会插入键值对 然后返回该键值对中value的引用
如果key在map中 则会返回键值为K的元素的value的引用
map的其他成员函数
其他成员函数的用法基本上和set一样
这里就不过多介绍了 代码和运行结果如下
map<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); map<string, string> dict1; // 调用make_pair函数 dict1.insert(make_pair("left", "左边")); dict1.insert(make_pair("right", "右边")); dict1.insert(make_pair("hello", "你好")); cout << dict.size() << endl; cout << dict.empty() << endl; cout << dict.count("left") << endl; dict.clear(); cout << dict.empty() << endl; dict.swap(dict1); cout << dict.size() << endl;
multimap
multimap和map的底层一样 都是由红黑树构造的
它们的接口函数也类似
它允许键值冗余
代码和演示结果如下
multimap<string, string> dict; // 调用make_pair函数 dict.insert(make_pair("right", "对的")); dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict.insert(make_pair("hello", "你好")); for (auto x : dict) { cout << x.first << " : " << x.second << endl; }
由于multimap容器允许键值冗余 因此两个容器中成员函数find和count的意义也有所不同
成员函数find 功能
map对象 返回值为键值为key的元素的迭代器
multimap对象 返回底层搜索树中序的第一个键值为key的元素的迭代器
成员函数count 功能
map对象 键值为key的元素存在则返回1，不存在则返回0（find成员函数可代替）
multimap对象 返回键值为key的元素个数（find成员函数不可代替）
由于multimap允许键值冗余 所以说调用【】时 返回值存在歧义 所以在muitimap中没有重载【】
