【C++】set 和 map

目录

0. 序列式容器和关联式容器

一、set

1. set 的介绍

2. set 的增删查

3. multiset

二、map

类型别名：

1. map介绍

2. pair

3. map的增删查

4. map的 [ ] 操作

5. multimap

三、map和set的区别

0. 序列式容器和关联式容器

• 序列式容器

  • 本质：元素按照插入的顺序或指定的位置线性排列。

  • 特点：每个元素都有固定的物理位置（索引），你可以通过位置（下标）直接访问它；两个位置存储的值之间一般没有紧密的关联关系。

  • 代表：vector（动态数组）、list（双向链表）、deque（双端队列）、array（静态数组）、forward_list（单向链表）。

• 关联式容器

  • 本质：元素按照Key（键）自动排序，或者通过哈希函数映射。

  • 特点：没有所谓的“物理位置”概念（不能用下标访问），你想找元素，只能通过它的 Key 去查找；它是非线性结构，两个位置有紧密的关联关系，交换一下，它的存储结构就被破坏了。

  • 代表：map/set（底层红黑树，有序）、unordered_map/unordered_set（底层哈希表，无序）。

一、set

1. set 的介绍

是一个"用平衡二叉搜索树实现的、自动去重、自动排序的集合容器"。

#include <set> std::set<int> s = {5, 1, 3, 3, 2}; // s 里实际是：{1, 2, 3, 5} // 自动排序 ↑ 自动去重 ↑

set比较重要的两个特性：

• 只支持增删查；
• 时间复杂度是 O(logn)。
• 不允许修改key

std::set<int>::iterator it = s1.begin(); while (it != s1.end()) { // *it += 1; // 不支持修改key ++it; } cout << endl;

2. set 的增删查

set - C++ Reference

（1）insert、erase、find、count...

int main(){ std::set<int> s; s.insert(10); // 插入，重复则忽略 s.insert({ 3, 7, 3 }); // 批量插入，3 只留一个 s.count(10); // 1 存在 / 0 不存在（set 里 count 非 0 即 1） s.find(10); // 返回迭代器，找不到返回 s.end() s.erase(10); // 按值删，返回删除个数 s.erase(s.find(7)); // 按迭代器删 s.empty(); // 是否为空 s.size(); // 元素个数 s.clear(); // 清空 return 0; }

（2）lower_bound、upper_bound

• lower_bound(k)：下界（闭区间）， 返回第一个 >= k 的元素。
• upper_bound(k)：上界（开区间），返回第一个 >k 的元素。

std::set<int> s1; s1.insert({ 3,4,2,4,2,1,6,7,8,9,10 }); for (auto e : s1) { cout << e << " "; } cout << endl; // 删除[3,5] // >=3，左闭区间位置 auto it1 = s1.lower_bound(3); // > 5 右开区间位置 auto it2 = s1.upper_bound(5); s1.erase(it1, it2); for (auto e : s1) { cout << e << " "; // 1 2 6 7 8 9 10 } cout << endl;

（3）find的时间复杂度

（ find返回的是中序的第一个。）

• 算法库里的 find 用的是暴力算法，时间复杂度为 O(N)。
• set 底层是搜索二叉树，find的时间复杂度是O(logN)。

3. multiset

multiset =允许 key 重复的set 。

multiset 和 set 的区别：

void test_set() { // 相比set不同的是，multiset是排序，但是不去重 multiset<int> s = { 1，2，3，2，4，4，5，6，2，2}; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // 相比set不同的是，x可能会存在多个，find查找中序的第一个 int x; cin >> x; auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // 相比set不同的是，count会返回x的实际个数 cout << s.count(x) << endl; // 相比set不同的是，erase给值时会删除所有的x s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; }

二、map

类型别名：

1. key_type（键的类型）
第一个模板参数。就是在声明 map 时传入的第一个类型，如果是 map<string, int> m;，那么 key_type 就是 string。

2. mapped_type（值的类型）
第二个模板参数。就是在声明 map 时传入的第二个类型，如果是 map<string, int> m;，那么 mapped_type 就是 int。

3. value_type（底层真正存储的元素类型）- 即pair<const key_type, mapped_type>。

1. map介绍

std::map 的功能和 set 类似，会自动排序，主要用于快速查找，去重等；它的底层实现是红黑树。

与 set 不同的是，map 里存储的不是单独的key，而是键值对( key-value )，

key用于排序和标识，value用于存储与key关联的内容。

• map中key不允许重复，value可以重复
• key不允许修改，value可以修改

• map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it->first << ":" << it->second << endl; //it->first = "x"; // 不能修改key it->second = "x"; // 可以修改value ++it; } cout << endl;

map的定义：

2. pair

map底层的红黑树节点中的数据，使用pair存储键值对数据。

template<class K, class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; pair<const K，V>_kv; //map里是这样存的 // ... }； /////// pair /////// typedef pair<const Key, T> value_type; template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; // key T2 second; // value //... };

注意：pair未支持流插入、流提取操作。

3. map的增删查

（1）插入

void test_map1() { map<string, string> dict; dict.insert(pair<string, string>("sort", "排序")); dict.insert(pair<string, string>("insert", "插入")); dict.insert({ "string", "字符串" }); // 隐式类型转换 pair<string, string> kv1 = { "string", "字符串" }; for (auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; } cout << endl; return 0； }

insert插入的是一个pair对象，插入的方式有以下几种：

map<string, string> dict = { {"hello","你好"},{"insert","插入"} }; // insert 插入的4种方式 pair<string, string> kv1 = { "left","左边" }; dict.insert(kv1); dict.insert(pair<string, string>("right", "右边")); dict.insert(make_pair("erase", "删除"); dict.insert({ "world","世界" });

make_pair 是c++11前的一种写法，它是一个函数模板，返回pair类型的对象，了解即可。

（2）查找

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& str : arr) { auto it = countMap.find(str); if (it == countMap.end()) countMap.insert({ str,1 }); else it->second++; } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl;

注意：map类支持 [ ] ，所以上述代码也可以改为：

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (auto& str : arr) { countMap[str]++; // 重载了[] } for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl;

（3）删除的方式和set类似，不做赘述。

4. map的 [ ] 操作

若 key 不在 map 中，插入 value_type(key, T()) 并返回其 value 的引用；否则返回已存在元素的 value 引用。

map的[ ] 支持查询，修改，插入的功能。

map<string, string> dict; dict["hello"] = "你好"; // 可以插入 cout << dict["hello"] << endl; // 可以查找 dict["hello"] = "您好"; // 可以修改 cout << dict["hello"] << endl;

原理：

std::map::operator[ ]的定义：

mapped_type& operator[] (const key_type& k) { return (*((this->insert(make_pair(k, mapped_type()))).first)).second; }

1. 第一层：this->insert(...)

• 调用 map 的 insert 函数。
• （插入key，并调用第二个模板参数（即T）的默认构造，生成一个默认值mapped_type()。例如 map<string, int>，这就相当于生成了一个 int(0)）。
• 重点来了：insert 的返回值是一个pair<iterator, bool>。
• .first是一个迭代器，指向 map 中键为 k 的那个元素（不管这个元素是刚刚新插入的，还是原本就已经存在的）。
• .second 是一个布尔值，表示是否真的插入了（true 表示原来没有，新插了；false 表示原来就有，没插）。

4. 第二层：(...).first

• 我们取出了 insert 返回的 pair 中的 .first，也就是那个迭代器。
• 此时我们手里拿着一个指向 pair<const Key, T> 的迭代器。
• 注：因为我们不关心到底插没插进去（布尔值），只关心能不能拿到那个位置的数据，所以这里直接忽略了 .second。

5. 第三层：*(...)

• 对迭代器进行解引用（*），拿到 map 中真正存储的那个元素本身。

• 这个元素的类型是 pair<const Key, T>。

6. 第四层：(...).second 和 return

• 取出该元素的 .second，也就是我们真正要操作的 value（T类型）。

• 因为迭代器解引用拿到的是引用，所以这里的 .second 也是引用，return 直接把它作为一个 T& 返回出去。

• 返回引用就可以支持直接赋值等对value的修改操作。

map<string, string> dict; dict["hello"] = "你好"; // 可以插入 cout << dict["hello"] << endl; // 可以查找 dict["hello"] = "您好"; // 可以修改 cout << dict["hello"] << endl;

一句话总结：
它尝试把 (k, T()) 插入 map，如果 k 已经存在则不插入；不管插没插进去，insert 都会返回一个指向该 k 对应元素的迭代器，然后把这个元素的 second（也就是 value）以引用的形式返回。

5. multimap

和map类似，multimap支持值冗余，不支持operator[ ]。

multimap允许重复插入，map的第二次插入无效，value不会被覆盖成新的值。

三、map和set的区别