map与set介绍及使用
关联式容器
之前我们学的list，vector等等是序列式容器，这里的set和map和之后的哈希表都是关联式容器，比如说搜索二叉树我们想插入一个值，不能随意的插入，因为每个数都是有关联的，需要找到准确位置才能进行插入。
健值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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) {} };
https://legacy.cplusplus.com/reference/utility/pair/?kw=pair
set
set文档介绍：https://cplusplus.com/reference/set/set/
这是一颗平衡搜索二叉树，也就是说不会出现那种只出现一边倾斜的情况，时间复杂度是稳定的 O(logN).
template < class T, // set::key_type/value_type
class Compare = less< T >, // set::key_compare/value_compare
class Alloc = allocator< T > // set::allocator_type
> class set;
#include<iostream> #include<set> using namespace std; int main() { set<int>tree; tree.insert(1); tree.insert(3); tree.insert(9); tree.insert(4); tree.insert(1); tree.insert(7); tree.insert(1); tree.insert(3); for (auto& e : tree)//这里的e尽量用引用 { cout << e << ' '; } cout << endl; return 0; }
首先我们看这段代码，了解到set的功能就是排序+去重的功能。
第一个参数是插入一个值。第二个是在某个位置插入一个值，但是这个接口要慎用，因为有可能破坏树的结构。第三个是迭代器的区间。
第一个参数是迭代器位置。第二个是值，这里如果删除的值不存在会返回0，存在返回1。第三个是迭代器区间。
这里是查找一个值，返回的是迭代器的位置，如果没有找到就返回end的位置。
这个接口的作用是统计这棵树中有多少个这个值的结点。
这个接口是为了multiset存在的。
multiset
multiset文档介绍https://cplusplus.com/reference/set/multiset/
template < class T, // multiset::key_type/value_type
class Compare = less, // multiset::key_compare/value_compare
class Alloc = allocator > // multiset::allocator_type
> class multiset;
multiset是允许值冗余：
#include<iostream> #include<set> using namespace std; int main() { multiset<int>tree; tree.insert(1); tree.insert(3); tree.insert(9); tree.insert(4); tree.insert(1); tree.insert(7); tree.insert(1); tree.insert(3); for (auto& e : tree)//这里的e尽量用引用 { cout << e << ' '; } cout << endl; return 0; }
这就是为什么set要设计要设计一个count接口了：
那么在查找这棵树的1的时候，先找到的就是中序遍历的第一个1。
#include<iostream> #include<set> using namespace std; int main() { multiset<int>tree; tree.insert(1); tree.insert(3); tree.insert(9); tree.insert(4); tree.insert(1); tree.insert(7); tree.insert(1); tree.insert(3); auto it = tree.find(1); while (it != tree.end()) { cout << *it << ' '; it++; } cout << endl; return 0; }
迭代器所有的区间基本都符合左闭右开的特性:
upper_bound是>
lower_bound是>=
map
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;
map也是一个平衡二叉搜索树，是一个KV模型。
上面的键值对，是数中结点值的类型。
#include<iostream> #include<map> using namespace std; int main() { map<string, string>dict; dict.insert(pair<string, string>("一", "one")); dict.insert(pair<string, string>("二", "two")); dict.insert(pair<string, string>("三", "three")); dict.insert(make_pair("四", "four"));//这里和上面三个是等价的写法 return 0; }
#include<iostream> #include<map> using namespace std; int main() { map<string, string>dict; dict.insert(pair<string, string>("一", "one")); dict.insert(pair<string, string>("二", "two")); dict.insert(pair<string, string>("三", "three")); dict.insert(make_pair("四", "four"));//这里和上面三个是等价的写法 for (const auto& e : dict)//如果不改变加const，e前面不加引用就是这个类型的拷贝构造，代价有些大 { cout << e.first << ":" << e.second << endl;//e不能直接访问，因为<<没有对pair类型进行重载 } return 0; }
map当中最重要的是：
(*((this->insert(make_pair(k,mapped_type()))).first)).second
返回值很长，逐步分析：
首先看一下insert的返回值
pair<iterator,bool> insert (const value_type& val);
这里如果插入（没有一个与他相同的key）成功就返回true，插入失败失败返回false。
注意：无论成功与否都会返回一个迭代器。
那么operator[]中返回值插入的是什么？
make_pair(k,mapped_type())
插入的是k， value类型的匿名对象，在这里匿名对象会仅有默认值，比如int类型就是0，指针类型就是空指针等等。
也就是说，插入接口调用完之后返回的迭代器的位置就是pair对应的位置，然后去调用first，也就是插入返回的iterator值，就是k对应的结点，然后再去找second，也就是k对应的结点的value。
也就是说，这个operator[]可以插入，修改，查找。（要小心，如果一个值没有，会进行插入的操作）
#include<iostream> #include<map> using namespace std; int main() { map<string, string>dict; dict.insert(pair<string, string>("一", "one")); dict.insert(pair<string, string>("二", "two")); dict.insert(pair<string, string>("三", "three")); dict.insert(make_pair("四", "four"));//这里和上面三个是等价的写法 dict["五"] = "five";//插入+修改 dict["六"]; dict.insert(make_pair("六", "six"));//不能修改，因为这个key值存在 for (auto& e : dict) { cout << e.first << ":" << e.second << " "; } cout << endl; dict["六"] = "six"; for (auto& e : dict) { cout << e.first << ":" << e.second << " "; } return 0; }
这里和operator[]的区别就是，如果不存在会抛出一个异常。
这里第二个参数只需要一个key，不需要pair。
multimap
这里和map最大的区别就是不提供operator[]，因为一棵树当中会有多个相同的key，所以没必要存在operator[]。还有就是find会中序遍历查找，找到的第一个就是。
