【1++的数据结构】之map与set（一）

👍作者主页：进击的1++
🤩 专栏链接：【1++的数据结构】

---

一，关联式容器与键值对

像list vector dequeue等这样的容器我们称为序列式容器，原因是由于其底层是线性的数据结构，存储的是元素本身。关联式容器与序列式容器的区别在于：关联式容器中存储的是键值对，其数据检索时效率更高。

---

那么什么是键值对呢？
用来表示具有一 一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，value表示与key对应的信息。

STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

二，set

set中只放value，但在底层实际存放的是由<value, value>构成的键值对。在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定排序准则进行排序。set在底层是用二叉搜索树(红黑树)实现的

set的使用

---

构造

void Test1()
{set<int> s1;int arr[] = { 2,1,4,7,3,8 };set<int> s2(arr, arr + sizeof(arr) / sizeof(arr[0]));set<int> s3(s2);for (auto x : s2){cout << x << " " ;}cout << endl;for (auto x : s3){cout << x << " ";}cout << endl;}

---

插入

int arr[] = { 2,1,4,7,3,8 };set<int> s2(arr, arr + sizeof(arr) / sizeof(arr[0]));for (auto x : s2){cout << x << " ";}cout << endl;std::pair<set<int>::iterator,bool> p1=s2.insert(5);cout << "p1 first:" << *p1.first << " p1.second:" << p1.second;std::pair<set<int>::iterator, bool> p2 = s2.insert(4);cout << endl;cout << "p2 first:" << *p2.first << " p2.second:" << p2.second;cout << endl;for (auto x : s2){cout << x << " ";}cout << endl;

对于返回值pair，当插入的元素set中没有时，则进行插入，并且pair中的first_value中存储插入元素的位置，second_value存储true； 当插入的元素已经存在时，first_value中存储已经存在元素的位置，second_value存储false。

---

删除

int arr[] = { 2,1,4,7,3,8 };set<int> s1(arr, arr + sizeof(arr) / sizeof(arr[0]));for (auto x : s1){cout << x << " ";}cout << endl;int ret1 = s1.erase(4);int ret2 = s1.erase(10);s1.erase(s1.begin());for (auto x : s1){cout << x << " ";}cout << endl;cout << ret1 << endl;cout << ret2 << endl;

在第二种按元素删除的方式中，其返回值为返回被删除元素的个数。

三，map

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair。

map的使用

构造

---

map<int,char> m1;m1[1] = 'a';m1[2] = 'b';m1[3] = 'c';m1[4] = 'd';map<int, char> m2(m1.begin(), m1.end());for (auto x : m2){cout << x.first << x.second<<" ";}cout << endl;

在上述中，我们提到了operator[ ]，下面我们对这个操作进行讲解。

此操作具有查找，修改，插入，三种功能。
当map中有key时，则其返回key对应的value的引用，就可以进行对value的修改了。
当map中没有key时，则在map中插入 一个新的键值对，返回value的引用。

插入

---

m2.insert(pair<int, char>(5, 'e'));m2.insert(make_pair(6, 'f'));for (auto x : m2){cout << x.first << x.second << " ";}cout << endl;

删除

---

map的删除与set相似，这里就不过多进行讲解。

四，multiset与multimap

multiset与set的区别是，multiset中的元素可以重复，set是中value是唯一的。

---

multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
multimap中的接口可以参考map，功能都是类似的。
multimap中没有重载operator[]。