C++STL——map和set的使用

目录

1.容器

1.1 序列容器

1.2 容器适配器

1.3 关联容器

1.4 无序关联容器

1.5 键值对到底是个什么东西？

2.set系列的使用

2.1 set类的介绍

2.2 set的构造以及迭代器

2.3 set的增，删，查

2.3.1 插入

2.3.2 删除

2.3.3 查找

2.3.4 lower_bound 以及 upper_bound

2.4 multiset与set的差异

3.map系列的使用

3.1 map类的介绍

3.2 pair类型的介绍

3.3 map的构造

3.3 map的增，删，查

3.4 map数据的修改

3.5 multimap与map的差异

---

1.容器

在C++标准库中，容器是用于存储和管理数据集合的模板类，根据数据组织方式和功能特性，它们可以分为以下几类：

1.1 序列容器

就是按照线性顺序存储元素，元素的顺序由插入顺序决定。常用的容器就是以上那几个，咱们应该多少都讲过。这里前三个都是随机迭代器，迭代器支持的功能最多，第四个是单向迭代器，迭代器支持的功能最少，第五个是双向迭代器，位于单向迭代器与随机迭代器的中间位置。 

特点：vector：动态数组，支持快速随机访问（O（1））；尾部插入/删除高效（O（1）），但是中间插入/删除较慢（O（n））。

list：双向链表，任意位置插入/删除高效（O（1）），但随机访问慢（O（n））

deque：双端队列，支持头尾高效插入/删除（O（1）），随机访问较快（O（1））

array：固定大小的数组，编译时确定大小，无法动态扩容

forward_list：单向链表，内存占用更小，但仅支持单向遍历

所以说如果要频繁的在中间插入或者删除，就用list或者forward_list。需要随机访问就用vector或者deque。只能说没有完全好的容器，各有各的好处。

1.2 容器适配器

基于其他容器实现的接口，提供特定数据结构的抽象（如栈，队列）。

特点：stack：后进先出，底层是基于deque实现

queue：先进先出，底层基于deque实现

priority_queue：元素按优先级排序，默认基于vector实现堆结构。

并且容器适配器是没有迭代器的。

1.3 关联容器

这个是咱们今天要讲的重点 

 基于键（key）有序存储元素，通常用红黑树实现，支持高效的查找。这个可以理解为，有关联的容器。

特点：set：唯一键集合，元素即键

map：键值对集合，键唯一

multiset/multimap:允许重复键（允许冗余）

并且他们的迭代器都是双向迭代器。

1.4 无序关联容器

这个是基于哈希表实现的，元素无序但是查找更快（平均O（1）），这个毕竟还没学，暂时不讲。

1.5 键值对到底是个什么东西？

那么既然讲到键值对了，就来说一下，键值对是个什么东西？ 

在C++的std::map中，key（键）和value（值）是键值对（Key-Value Pair)的两个核心组成部分，它们共同构成了一种关联关系，这也是为什么叫它关联容器。

key（键）：

定义：用于唯一标识元素的“标识符”，类似于词典中的“词条”。

特点：

唯一性：在map中，所有的key必须唯一（若需要允许重复的键，需用std:multimap)。

不可变性：key一旦插入到map中，就不能直接修改，（但可以删除后重新插入）

排序性：map默认按key的升序排序（可通过仿函数修改）

value（值）：

定义：与key关联的数据，类似于字典中词条对应的“解释”。

特点：1.相同的key可以对应不同的value

2.可以通过key直接修改value的值。

那么来看他们的实际应用场景：

1.字典/数据库索引：

key：单词（如apple）

value：单词的释义（如一种水果）

2.学生信息管理系统

key：学号（唯一标识学生，如“s001”）

value：学生详细信息（如Alice，18，CS）.

这也是对上一章最后的补充。OK，让咱们进入主题吧

本章节讲解的map和set底层是红黑树，红黑树是⼀颗平衡二叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。

2.set系列的使用

2.1 set类的介绍

set的声明如下，T就是set底层关键字的类型

• set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模 版参数

• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参 数。

• ⼀般情况下，我们都不需要传后两个模版参数。

• set底层是用红黑树实现，增删查效率是 的。 

前⾯部分我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，在这里我只挑选几个比较重要的接口来将。

2.2 set的构造以及迭代器

大家只需要知道这四个构造即可：无参默认构造， 迭代器区间构造，拷贝构造，列表构造。

 迭代器是⼀个双向迭代器：-> a bidirectional iterator to const value_type

正向迭代器  iterator begin(); iterator end();

 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中 序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改 关键字数据，破坏了底层搜索树的结构。

2.3 set的增，删，查

需要说明的是key_type与value_type均为T，即key。 

2.3.1 插入

1.单个数据插入，如果已经存在则插入失败 pair <iterator,bool>insert (const value_type& val);

2. 列表插入，已经在容器中存在的值不会插入 void insert (initializer_list<value_type> il);

 3.迭代器区间插入，已经在容器中存在的值不会插⼊ template <Class InputIterator>

void insert (InputIterator first, InputIterator last);

来看一段测试代码：

int main()
{// 去重+升序排序set<int> s;// 去重+降序排序（给一个大于的仿函数）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout << *it << " ";++it;}cout << endl;// 插入一段initializer_list列表值，已经存在的值插入失败s.insert({ 2,8,3,9 });for (auto e : s){cout << e << " ";}cout << endl;set<string> strset = { "sort", "insert", "add" };// 遍历string比较ascll码大小顺序遍历的for (auto& e : strset){cout << e << " ";}cout << endl;return 0;
}

 

上面的为运行结果。

注意插入单个元素返回的是pair，pair是一个自定义类型，第一个成员是iterator，第二个成员是bool，第一个元素是指向插入元素的迭代器，第二个表示是否插入成功。如果插入成功，iterator指向插入的元素，bool为true。如果元素已存在，iterator指向已经存在的元素，bool为false。

2.3.2 删除

  1.删除⼀个迭代器位置的值 iterator erase (const_iterator position);

2. 删除 val ， val 不存在返回 0 ，存在返回 1 size_type erase (const value_type& val);

 3.删除⼀段迭代器区间的值 iterator erase (const_iterator first, const_iterator last);

这儿为什么不用bool判断是否删除成功了呢？其实也是因为后面会讲到multiset，所以这儿先知道一下，后面会讲。且这儿只能返回0或1，因为set是去重过的。

set<int> s = { 4,2,7,2,8,5,9 };
for (auto e : s)
{cout << e << " ";
}
cout << endl;s.erase(s.begin());for (auto e : s)
{cout << e << " ";
}
cout << endl;// 直接删除x
int x;
cin >> x;
int num = s.erase(x);
if (num == 0)
{cout << x << "不存在！" << endl;
}for (auto e : s)
{cout << e << " ";
}
cout << endl;// 直接查找再利用迭代器删除x
int x;
cin >> x;
auto pos = s.find(x);
if (pos != s.end())
{s.erase(pos);
}
else
{cout << x << "不存在！" << endl;
}for (auto e : s)
{cout << e << " ";
}
cout << endl;

删除对应的代码。

2.3.3 查找

find找到了返回当前元素的迭代器，否则返回end位置的迭代器。

1. 查找 val ，返回 val 所在的迭代器，没有找到返回 end() iterator find (const value_type& val);

 2.查找 val ，返回 Val 的个数 size_type count (const value_type& val) const; 

还有一种查找，即count，返回的是key的个数有几个，就返回几个，但是set中只有0或1个，而后面讲的multiset会有多个。

// O(N)
auto pos1 = find(s.begin(), s.end(), x);
// O(logN)
auto pos2 = s.find(x);cin >> x;
/*auto pos = s.find(x);
if (pos != s.end())*/
if(s.count(x))
{cout << x << "存在！" << endl;
}
else
{cout << x << "不存在！" << endl;
}

这儿的find如果是算法库中的find，那么其实本质是暴力查找，时间复杂度为O（N），是为了vector准备的，其实远不如使用自带的find成员函数。

2.3.4 lower_bound 以及 upper_bound

1.返回大于等 val 位置的迭代器 iterator lower_bound (const value_type& val) const;

有这个值，就返回val位置的iterator。无这个值，就返回比val大的位置的iterator。

2.返回大于 val 位置的迭代器 iterator upper_bound (const value_type& val) const; 

有这个值，就返回比val值大的位置的iterator。无val这个值，也返回大于val值的迭代器的位置。

咱们知道迭代器的区间都是左闭右开的，那么这个就是为了寻找迭代器的区间而存在的。

lower_bound是为了找闭区间，而另一个是为了找开区间。

int main()
{std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";}cout << endl;/* 实现查找到的[itlow,itup)包含[30, 60]区间返回 >= 30*/auto itlow = myset.lower_bound(30);// 返回 > 60auto itup = myset.upper_bound(60);myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;// 实现查找到的[itlow,itup)包含[35, 65]区间// 返回 >= 35auto itlow = myset.lower_bound(35);// 返回 > 65auto itup = myset.upper_bound(65);myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;// 实现查找到的[itlow,itup)包含[30, 90]区间auto itlow = myset.lower_bound(30);auto itup = myset.upper_bound(90);myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

以上是一段删除代码，请大家仔细观摩。

2.4 multiset与set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset支持值冗余，那么 insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下⾯的样例代码理解。 

int main()
{// 相比set不同的是，multiset是排序，但是不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// find返回中序的第一个4auto pos = s.find(4);while (*pos == 4){cout << *pos << " ";++pos;}cout << endl;cout << s.count(4) << endl;cout << s.count(5) << endl;cout << s.count(6) << endl;//若是erase参数只给一个要删除的数字，那么会删除所有的这个数字，且返回删除的数字的个数// 若是erase的参数是迭代器，那么只会删除该位置的数字// 删除所有的4//cout << s.erase(4) << endl;// 删除中序第一个4pos = s.find(4);if(pos != s.end())s.erase(pos);it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

 

所以这里知道为什么erase的返回值要是size_type的了吧，就是为了与multiset区分开。那么这儿的count自然也是发挥了很大的作用。 

3.map系列的使用

3.1 map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持 小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的 内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红黑树实 现，增删查改效率是 O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

那么我们来思考一个东西，在set中，只有一个key，所以你要是想访问数据，直接就可以访问了，但是对于key_value的呢？一个里面有两个值啊，好，那么这个之后，咱们可以用pair去存储，你可以把pair理解为一个结构体。两个成员，即key，value即为结构体的成员变量。咱们访问的时候，直接访问结构体中的成员变量即可。

3.2 pair类型的介绍

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

 

3.3 map的构造

也是只需要掌握4个即可：无参数构造，迭代器区间构造，拷贝构造，参数列表构造。

迭代器是⼀个双向迭代器 iterator -> a bidirectional iterator to const value_type

 正向迭代器 iterator begin(); iterator end();

 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend(); 

map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走 的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键 字数据，破坏了底层搜索树的结构。

3.3 map的增，删，查

这儿的key就是key，这儿的T其实就是value，这儿的pair<Key,Value>其实就是value_type。

map的增删查关注以下几个接⼝即可： map增接口，插⼊的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全 类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代 还可以修改value 。

int main()
{map<string, string> dict;pair<string, string> kv1("sort", "排序");dict.insert(kv1);dict.insert(pair<string, string>("left", "左边"));dict.insert(make_pair("left", "左边"));dict.insert({ "right", "右边" });//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//因为咱们知道，*的返回值是引用类型，所以可以直接用.访问结构体里的成员// 但是，->的返回值是&（取地址），指针类型，所以，这儿其实是it->->first,// 为了可读性，就省去一个->。//cout << (*it).first <<":" << (*it).second <<endl;//(*it).second = "左边1";说明map中的value是可以修改的cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "无此单词，请重新输入" << endl;}}return 0;
}

大家有什么疑问，请看上面的代码。

 

插入，不管什么，都是插入成功。删除的接口与set的删除接口一样的，就不演示了。

即erase传Key，会将Key对应的Value全删了，count的返回值为Key的Value有几个，就返回几。

3.4 map数据的修改

咱们先来看一段代码：

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& str : arr){/*auto pos = countMap.find(str);if (pos != countMap.end()){pos->second++;}else{countMap.insert({ str, 1 });}*///以上的代码可以等价于下面的一个代码countMap[str]++;}for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

OK，咱们来讲解一下这个[],

这个【】，返回值是Value，而方括号里面写的是Key。

这个【】，也可以用来访问Key中的Value，以及修改Value，但是上面代码有点问题，就是对于已有的数据，直接++没问题，但是对于没有的数据怎么办呢？其实，【】会先插入Key，之后Value为second的默认构造（一般往0那边去靠），这儿int的默认构造是0.所以会先插入Key，之后0+1=1. 

int main()
{map<string, string> dict;dict.insert({ "sort", "排序" });// 增加dict["left"] = "左边";// 增加dict["right"]="右边";// 修改dict["right"] = "右边1";// 查找，你得确定值在其中，否则就变成插入了cout << dict["left"] << endl;cout << dict["kkk"] << endl;//不可以，因为map是去重的dict.insert({ "sort", "xxxx" });for (auto& e : dict){cout << e.first << e.second << endl;}return 0;
}

 

以上就是方括号的用法。 

那么方括号的底层呢，其实是运用了insert。

需要注意的是这个ret.first，指的是访问的是指向节点的指针。第二个->访问的才是节点里面的成员变量。

insert 插⼊⼀个 pair 对象

 1 、如果 key 已经在 map 中，插⼊失败，则返回⼀个 pair 对象，返回 pair 对象 first 是 key 所在结点的迭代器， second 是 false

 2 、如果 key 不在在 map 中，插入成功，则返回⼀个 pair 对象，返回 pair 对象 first 是新插⼊ key 所在结点的迭代器， second 是 true

3.也就是说无论插入成功还是失败，返回 pair 对象的 first 都会指向 key 所在的迭 代器

4. 那么也就意味着 insert 插入失败时充当了查找的功能，正是因为这⼀点， insert 可以用来实现 operator[]

5. 需要注意的是这里有两个 pair ，不要混淆了，⼀个是 map 底层红黑树节点中存的 pair ，另 ⼀个是 insert 返回值 pair  。

3.5 multimap与map的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么 insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全⼀样，比如 find时，有多个key，返回中序第⼀个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

OK，本篇只讲了map与set系列的使用，还有一点就是map与multimap包的是同一个头文件。set与multiset也是的。