[C++随想录] map和set的使用

set — — key模拟
map — — key_value模型

set

初始化

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);cout << "s-> ";for (auto e : s){cout << e << " ";}cout << endl;set<int>s1(s.begin(), s.end());cout << "s1-> ";set<int>::iterator it = s1.begin();while (it != s1.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{set_test1();return 0;
}

运行结果:

s-> 5 9 10 12 13
s1-> 5 9 10 12 13

1. set默认 去重 + 排序
2. 支持 遍历, 但不支持 随机访问, 即[], 迭代器是 双向迭代器👇👇👇
   

find

void set_test2()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);auto it = s.find(10);if(it != s.end())cout << *it << endl;auto tem = s.find(5);if(tem != s.end())cout << *tem << endl;
}int main()
{set_test2();return 0;
}

运行结果:

5

• 算法库里面的 find — — 暴力搜索, O(N)
  set自带的 find — — 利用二叉搜索树的特性 O(logN)

void set_test2()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);// set自带的find函数auto it = s.find(5);if(it != s.end())cout << *it << endl;// 算法库里面的 find函数auto tem = find(s.begin(), s.end(), 5);if(tem != s.end())cout << *tem << endl;
}int main()
{set_test2();return 0;
}

运行结果:

5
5

erase

1. 先找后删
   🗨️思考: 下面的代码正确不?

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);auto it = s.begin();s.erase(it);s.erase(it + 3);
}int main()
{set_test1();return 0;
}

• 上面的代码是错误的:
  1. set没有重载 +
  2. 即使重载了 +, 我们也要 判断 我们要删除的地址是否在s中

我们应该这样写👇👇👇

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);cout << "s-> ";for (auto e : s){cout << e << " ";}cout << endl;auto it = s.find(10);// 判断 s 中是否有此元素if (it != s.end()){s.erase(it);}cout << "删除后-> ";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test1();return 0;
}

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 12 13

2. 传值直接删

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);cout << "s-> ";for (auto e : s){cout << e << " ";}cout << endl;// 传值直接删除s.erase(10);cout << "删除后-> ";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test1();return 0;
}

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 12 13

🗨️传值直接删除, 不用判断元素在不在set对象中?

• 不用!
  如果在对象中, 就删除; 如果不在对象中, 啥事不干👇👇👇

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);cout << "s-> ";for (auto e : s){cout << e << " ";}cout << endl;// 传值直接删除s.erase(15);cout << "删除后-> ";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test1();return 0;
}

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 10 12 13

3. 删除一段区间

void set_test1()
{set<int>s;s.insert(10);s.insert(12);s.insert(13);s.insert(9);s.insert(10);s.insert(5);cout << "s-> ";for (auto e : s){cout << e << " ";}cout << endl;// 删除 [5, 10)区间内的值auto i = s.find(5);auto j = s.find(10);s.erase(i, j);cout << "删除后-> ";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test1();return 0;
}

运行结果:

s-> 5 9 10 12 13
删除后-> 10 12 13

• 这个我感觉很 鸡肋:
  1. set不支持 +
  2. 找到了还要判断是否存在

从而导致, 用这个方法删除一段区间有点麻烦.
不过, 后面有两个函数: lower_bound 和 upper_bound, 可以配合使用找寻 一段区间, 可以配合这个方法使用~~

count

在 set中, 判断一个元素存不存在:

1. find
2. count

count函数返回 该元素的个数, 由于set 去重 ⇒ 所以, 返回 1 或 0
count函数 在 multiset 里面可以体现出 统计元素个数的功能

1. 判段元素在不在

void set_test3()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);// count 和 find 来判断元素是否存在int tem = s.count(5);if (tem > 0){cout << "5元素存在" << endl;}else{cout << "5元素不存在" << endl;}auto it = s.find(11);if (it != s.end()){cout << "11元素存在" << endl;}else{cout << "11元素不存在" << endl;}
}int main()
{set_test3();return 0;
}

运行结果:

5元素存在
11元素不存在

2. 统计元素个数

void set_test3()
{multiset<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);s.insert(15);s.insert(15);int n = s.count(15);cout << "15的个数: " << n << endl;}int main()
{set_test3();return 0;
}

运行结果:

15的个数: 3

• multiset 和 set
  1. set中的 key是唯一的, 而multiset中的 key 允许是多个的
  2. set 和 multiset 都是包含在 <set>的头文件中的

lower_bound && upper_bound

void set_test3()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);s.insert(10);s.insert(11);// lower_bound && upper_boundauto itlow = s.lower_bound(5);cout << *itlow << endl;auto itup = s.upper_bound(15);cout << *itup << endl;}int main()
{set_test3();return 0;
}

运行结果:

5
18

itlow 和 itup构成的区间是 [itlow, itup) ⇒ 这样我们就可以 删除特定区间的内容👇👇👇

void set_test3()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);s.insert(10);s.insert(11);cout << "s ->";for (auto e : s){cout << e << " ";}cout << endl;// 删除 5~15 这段区间的内容auto itlow = s.lower_bound(5);auto itup = s.upper_bound(15);s.erase(itlow, itup);cout << "删除 5~15 ->";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test3();return 0;
}

运行结果:

s ->1 5 10 11 12 15 18
删除 5~15 ->1 18

equal_ range

• pair :
  在C++中，std::pair是一个模板类，用于保存两个元素的有序对。std::pair的成员变量 first和second分别表示有序对中的第一个和第二个元素。你可以使用 点号（.）操作符来访问这些成员

如果对象里面 存在val, 那么正常返回; 如果对象里面 不存在val, 那么就 返回一个不存在的区间

void set_test3()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(1);s.insert(10);s.insert(11);cout << "s ->";for (auto e : s){cout << e << " ";}cout << endl;cout << "equal_range(5) val存在的情况" << endl;auto eit1 = s.equal_range(5);cout << "first element-> " << *eit1.first << endl;cout << "second element-> " << *eit1.second << endl;cout << "equal_range(6) val不存在的情况" << endl;auto eit2 = s.equal_range(6);cout << "first element-> " << *eit2.first << endl;cout << "second element-> " << *eit2.second << endl;}int main()
{set_test3();return 0;
}

运行结果:

equal_range(5) val存在的情况
first element-> 5
second element-> 10
equal_range(6) val不存在的情况
first element-> 10
second element-> 10

假设: set中, 值等于value的下标为i;
其实, set 使用 equal_range 最多只能返回 [i, i+1)
multiset 使用 equal_range 可以返回 [i, i+1, i+2, ... ... j)

set

void set_test3()
{set<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(5);s.insert(5);s.insert(5);s.insert(1);s.insert(10);s.insert(11);cout << "s ->";for (auto e : s){cout << e << " ";}cout << endl;// set 删除所有等于5的值auto eit = s.equal_range(5);s.erase(eit.first, eit.second);cout << "set删除所有等于5的值 ->";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test3();return 0;
}

运行结果:

s ->1 5 10 11 12 15 18
set删除所有等于5的值 ->1 10 11 12 15 18

multiset

void set_test3()
{multiset<int> s;s.insert(15);s.insert(18);s.insert(12);s.insert(5);s.insert(5);s.insert(5);s.insert(5);s.insert(1);s.insert(10);s.insert(11);cout << "s ->";for (auto e : s){cout << e << " ";}cout << endl;// set 删除所有等于5的值auto eit = s.equal_range(5);s.erase(eit.first, eit.second);cout << "multiset删除所有等于5的值 ->";for (auto e : s){cout << e << " ";}cout << endl;
}int main()
{set_test3();return 0;
}

运行结果:

s ->1 5 5 5 5 10 11 12 15 18
multiset删除所有等于5的值 ->1 10 11 12 15 18

map

insert

void map_test1()
{map<string, string> m1;// C++98// 1. 传一个pair对象pair<string, string> kv1("insert", "插入");m1.insert(kv1);// 2. 传一个pair的匿名对象m1.insert(pair < string, string>("sort", "排序"));// 3. make_pairm1.insert(make_pair("love", "爱情"));// C++11// 4. 多参数的构造函数支持隐式类型转换, 用{}m1.insert({ "insert", "xxx" });for (auto e : m1){cout << e.first  << "-> " << e.second << endl;}cout << endl;// 区间初始化map<string, string> m2(m1.begin(), m1.end());map<string, string>::iterator it = m2.begin();while (it != m2.end()){// cout << (*it).first << "-> "(*it).second << endl;cout << it->first << "-> " << it->second << endl;++it;}cout << endl;}int main()
{map_test1();return 0;
}

运行结果:

insert-> 插入
love-> 爱情
sort-> 排序insert-> 插入
love-> 爱情
sort-> 排序

1. map的 insert, 传的是一个 pair结构, 返回的也是一个 pair结构.
   

2. map的 insert, 是根据 key来进行判断的: 如果 key形同, value不同, 就 不会覆盖

3. map的 insert, 几种传参方式:

   1. C++98
      1. 传一个pair对象
      2. 传一个pair的匿名对象
      3. 用 make_pair来创建一个pair对象
   2. C++11
      4. 支持多参数的隐式类型转换, 用 {}

4. map的迭代器也是 双向迭代器, 而不是随机迭代器. map虽然重载了[ ], 但跟我们平常的不大一样, 下面会讲的
   

[ ]运算符

一般的[ ] 是返回 存储对象的, 比如: vector 就返回 int, list 就返回 string;
但是 map中的 [ ], 不是返回 pair结构, 而是返回 pair结构中的 第二个元素的.

我们细看一下 [ ] 的不同:

[ ]的本质是 调用 insert, 通过 key 来返回 value:

1. 当key不存在时, 会插入该键的新元素, 并返回value的引用
2. 当key存在时, 会返回value的引用

⇒ [ ]有两大功能 插入 + 修改

[ ] 的本质是调用 insert, 但是有所不同

1. insert中, key相同, value不同的键值对是 不会覆盖的
2. [ ]中, 会返回value的引用, 所以能对value就行修改 ⇒ key相同, value不同的键值对是可以 覆盖的

void map_test1()
{map<string, string> m1;// C++98// 1. 传一个pair对象pair<string, string> kv1("insert", "插入");m1.insert(kv1);// 2. 传一个pair的匿名对象m1.insert(pair < string, string>("sort", "排序"));// 3. make_pairm1.insert(make_pair("love", "爱情"));// C++11// 4. 多参数的构造函数支持隐式类型转换, 用{}m1.insert({ "insert", "xxx" });for (auto e : m1){cout << e.first  << "-> " << e.second << endl;}cout << endl;// 插入m1["muyu"];cout << "[]: 插入(muyu)" << endl;for (auto e : m1){cout << e.first << "-> " << e.second << endl;}cout << endl;// 修改(覆盖)m1["insert"] = "xxx";cout << "[]: 修改(insert)" << endl;for (auto e : m1){cout << e.first << "-> " << e.second << endl;}cout << endl;// 插入 + 修改m1["mutong"] = "沐潼";cout << "[]: 插入 + 修改(<mutong, 沐潼>)" << endl;for (auto e : m1){cout << e.first << "-> " << e.second << endl;}cout << endl;
}int main()
{map_test1();return 0;
}

运行结果:

insert-> 插入
love-> 爱情
sort-> 排序[]: 插入(muyu)
insert-> 插入
love-> 爱情
muyu->
sort-> 排序[]: 修改(insert)
insert-> xxx
love-> 爱情
muyu->
sort-> 排序[]: 插入 + 修改(<mutong, 沐潼>)
insert-> xxx
love-> 爱情
mutong-> 沐潼
muyu->
sort-> 排序

在这里, 我们可以 简化之前写的统计次数👇👇👇

int main()
{map<string, int> count;string arr[] = {"苹果", "桃子", "土豆", "苹果", "栗子", "桃子"};for (auto e : arr){// 直接改变 e 所对应的value值count[e]++;}for (auto e : count){cout << e.first << "-> " << e.second << endl;}cout << endl;return 0;
}

运行结果:

栗子-> 3
苹果-> 1
苹果-> 2
土豆-> 4

map的其他迭代器诸如 find, erase, count, lower_bound, upper_bound, equal_range ; 用法都和 set的用法都差不多的, 在这里, 我们就不过多介绍了!

multiset && multimap

multiset 和 multimap都允许 key冗余

void multi_test()
{multiset<int> ms;ms.insert(1);ms.insert(1);ms.insert(5);ms.insert(2);cout << "multiset " << endl;for (auto e : ms){cout << e << " ";}cout << endl << endl;multimap<string, int> mm;mm.insert({ "苹果", 1 });mm.insert({ "苹果", 2 });mm.insert({ "栗子", 3 });mm.insert({ "土豆", 4 });cout << "multimap " << endl;for (auto e : mm){cout << e.first << "-> " << e.second << endl;}cout << endl;}int main()
{multi_test();return 0;
}

运行结果:

multiset
1 1 2 5multimap
栗子-> 3
苹果-> 1
苹果-> 2
土豆-> 4

multiset 和 multimap 的其它接口的用法 都是和 set 和 map 都是大致一样的

---

望门投止思张俭，忍死须臾待杜根；
我自横刀向天笑，去留肝胆两昆仑。
— — 谭嗣同《狱中题壁》