【C++】set与map的使用

一、set：

1、set介绍：

2、常用构造：

3、常用修改操作：

（1）insert：

（2）find

（3）erase：

4、其他操作：

（1）count：

（2）lower_bound、upper_bound：

multiset：

二、map：

1、map介绍：

2、常用构造：

3、常用修改操作：

（1）insert、emplace：

（2）find：

（3）erase：

4、其他操作：

（1）count：

（2）lower_bound、upper_bound：

multimap：

一、set：

1、set介绍：

set是按照一定次序存储元素的容器，它用于存储唯一的元素（即在容器中没有重复的元素）通常用于需要快速查找、插入和删除元素的场景，底层通常是用红黑树来实现这些操作的快速性。

特点：

在set中的元素都具有唯一性，也就是set会自动排序＋去重，默认按照升序排序。
往set中插入元素时，只需要插入value即可，不需要构造键值对。
可以使用set的迭代器遍历set中的元素，即可得到升序的有序序列。
set的查找效率是非常高效的：O(logN)，底层由红黑树实现（高度次查找）。

2、常用构造：

void Test1()
{vector<int> v = { 4,5,8,3,2,5,6,9,4,3 };set<int> s1(v.begin(), v.end()); // 区间构造set<int> s2(s1); // 拷贝构造set<int> s3;  s3 = s2; // 赋值重载// 遍历可得升序的去重序列for (auto e : s1){cout << e << " ";}cout << endl;
}

3、常用修改操作：

（1）insert：

set的插入操作就只用insert就可以了，因为无论从哪个位置插入，最终都会被排序好。至于去重的功能，就是在树中（set的底层就是红黑树）如果已存在要插入的值，则取消插入操作。

void Test2()
{set<int> s;s.insert(6);s.insert(3);s.insert(8);s.insert(7);s.insert(6);s.insert(9);s.insert(0);s.insert(3);s.insert(7);s.insert(5);for (auto e : s){cout << e << " ";}cout << endl;
}

（2）find

find查找找到了返回指定值位置的迭代器，找不到返回end();

void Test4()
{vector<int> v = { 4,5,8,3,2,5,6,9,4,3 };set<int> s(v.begin(), v.end());auto it = s.find(3);cout << *it << endl; // 输出3auto it2 = s.find(20);if (it2 == s.end()) cout << "it2 == s.end()" << endl;}

（3）erase：

erase 的三种删除:

指定位置删除：s.erase(iterator)

指定区间删除：s.erase(first,second)

指定值删除：s.erase(val)；

void Test3()
{vector<int> v = { 4,5,8,3,2,5,6,9,4,3 };set<int> s(v.begin(), v.end());cout << "s:";for (auto e : s){cout << e << " ";}cout << endl << endl;// s.erase(iterator)cout << "s.erase(iterator): erase(begin()): ";s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl << endl;// s.erase(val)cout << "s.erase(val): val = 6: ";s.erase(6);for (auto e : s){cout << e << " ";}cout << endl << endl;// s.erase(first, second),cout << "s.erase(first,second): erase(s.begin(),s.end()) : ";s.erase(s.begin(),s.end());for (auto e : s){cout << e << " ";}cout << endl; cout << "因为区间删除全删了，所以set中没有元素";
}

4、其他操作：

（1）count：

count(val) 的操作就是在容器中查找是否有值val，如果有返回1，没有返回0。

（2）lower_bound、upper_bound：

lower_bound(key_value)返回第一个大于等于key_value的定位器

upper_bound(key_value)返回第一个大于key_value的定位器

失败都返回end( ); 可以理解为两者分别是一个开、闭区间【）

void Test6()
{vector<int> v = { 1,2,3,4,5,6,7,8,9,10,11,12 };set<int> s(v.begin(), v.end());cout << "s: ";for (auto e : s){cout << e << " ";}cout << endl << endl;// 可以配合erase实现区间删除的功能s.erase(s.lower_bound(3), s.upper_bound(9));cout << "删除区间3 ~ 9:  ";for (auto e : s){cout << e << " ";}cout << endl;
}

multiset：

前面说到set会自动去重，但是如果不想让其去重的话可以使用multiset，从用法上来讲和set差别不大，但是不会去重，在插入时可以默认相同值往右插入，但是也可能会旋转到左分支去，在查找并返回时，为了配合删除但不影响整棵树的原则，默认是找中序遍历的第一个值，也就是说找到该值后你还不能停，还要去你的左子树看看还有没有相同值，因为中序遍历就是左中右形式。

二、map：

1、map介绍：

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。它包含可以重复的键值对（key-value pairs），但每个键（key）在map中是唯一的。map提供了一种从键（key）映射到值（value）的方式，其中键用于唯一标识元素，而值是与该键相关联的数据。

特点：

map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
map和set一样会通过键值key去重操作。

2、常用构造：

void map1()
{map<string, int> m1; // 无参构造// 传入键值对构造map<string, int> m2 = { {"zhangsan",1 }, { "lisi",2 }, { "wangwu",3 } }; // 迭代器区间构造:vector<pair<string, int>> p = { {"zhangsan",1 }, { "lisi",2 }, { "wangwu",3 } };map<string, int> m3(p.begin(), p.end());map<string, int> m4(m3); // 拷贝构造map<string, int> m5 = m4; // 赋值重载// 遍历:for (auto e : m5){cout << e.first << " : " << e.second << endl;}
}

可以看到map默认以key值升序排序(也就是按照e.first升序排序)

3、常用修改操作：

（1）insert、emplace：

map的插入主要通过insert插入和emplace插入:

insert方法接受一个 pair<const Key, T>的值（或可以隐式转换为该值的对象），其中Key是键的类型,T是值的类型。

emplace方法则是直接在 map 中构造元素，而不是首先创建一个临时的pair对象。这通常可以减少不必要的拷贝或移动操作，从而提高效率。特别是当构造pair对象本身需要执行大量工作时（例如，当值类型涉及大量计算或内存分配时），使用emplace可以显著提高性能。

void map2()
{map<string, int> m1;m1["zhangsan"] = 1; m1["lisi"] = 2; m1["wangwu"] = 3; // 也可以通过此方法插入，底层的[]是重载了的map<string, int> m2;m2.insert(pair<string, int>("zhangsan", 1));m2.insert(make_pair("lisi", 2));// 上面的两种插入比较繁杂，所以一般使用以下简洁的写法m2.insert({ "wangwu",3 });m2.emplace("zhaoliu", 4);for (auto e : m2){cout << e.first << " : " << e.second << endl;}
}

（2）find：

find查找找到了返回指定key值位置的迭代器，找不到返回end();

（3）erase：

erase 的三种删除:

指定位置删除：m.erase(iterator)

指定区间删除：m.erase(first,second)

指定key值删除：m.erase(key)；

void map4()
{map<string, int> m;m["liuyi"] = 1; m["chener"] = 2; m["zhangsan"] = 3; m["lisi"] = 4; m["wangwu"] = 5; m["zhaoliu"] = 6;for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << endl;m.erase(m.begin());cout << "m.erase(iterator): erase(begin())" << endl;for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << endl;cout << "m.erase(key): key = zhangsan" << endl;;m.erase("zhangsan");for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << endl;cout << "erase(first,second): erase(begin(), end())" << endl;m.erase(m.begin(), m.end());for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << "因为进行begin() ~ end()的删除，所以map中已经没有元素" << endl;
}

4、其他操作：

（1）count：

count(key) 的操作就是在容器中查找是否有键值key，如果有返回1，没有返回0。

（2）lower_bound、upper_bound：

lower_bound(key_value)返回第一个大于等于key_value的定位器

upper_bound(key_value)返回第一个大于key_value的定位器

失败都返回end( ); 可以理解为两者分别是一个开、闭区间【）

void map7()
{map<string, int> m;m["liuyi"] = 1; m["chener"] = 2; m["zhangsan"] = 3;m["lisi"] = 4; m["wangwu"] = 5; m["zhaoliu"] = 6;for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << endl;// 同样可以配合erase达到删除区间的目的:m.erase(m.lower_bound("lisi"), m.upper_bound("zhansan"));for (auto& e : m){cout << e.first << " : " << e.second << endl;}cout << endl;
}