【C++闯关笔记】map与set的使用

本文介绍了C++中关联式容器set和map的使用方法。首先区分了序列式容器和关联式容器，重点讲解了set和map的底层实现（红黑树）及其特性。对于set，详细说明了构造函数、迭代器、增删查操作以及lower_bound/upper_bound函数；对于map，则重点介绍了pair结构的应用、[]操作符原理及与set的差异。文章还对比了multiset/set和multimap/map的区别，强调前

贪婪的野指针

595人浏览 · 2025-10-25 22:28:20

贪婪的野指针 · 2025-10-25 22:28:20 发布

系列文章目录

上一篇笔记：【C++闯关笔记】详解多态-CSDN博客

阅读本文前，推荐先查看【C++闯关笔记】map与set底层：二叉搜索树-CSDN博客

文章目录

目录

系列文章目录

文章目录

前言

序列式容器和关联式容器

一、set的使用方法

1.set介绍

2.set的构造和迭代器

构造函数

迭代器

3.set的增删查

4.lower_bound与upper_bound

5.multiset和set的差异

二、map的使用方法

1.map介绍

pair介绍

make_pair

2.map的构造和迭代器

构造函数

迭代器

3.map的增删查

4.map的数据修改

为什么双向迭代器能使用operator[ ]

5.multimap和map的差异

总结

前言

序列式容器和关联式容器

什么是序列式容器？

逻辑结构为线性序列的数据结构，两个位置存储的值之间没有紧密的关联关系，比如交换一下，该数据结构依旧是序列式容器。

前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

什么是关联式容器？

关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。

常见的关联式容器有map/set系列和unordered_map/unordered_set系列。

本文将主要介绍set/map的使用方法。

一、set的使用方法

1.set介绍

set的声明如下图所示：

set底层是用红黑树实现，而红黑树又是以之前的一篇笔记中的k模型二叉搜索树加上一些算法实现的，set的增删查效率是O(logN)级，迭代器遍历是走的搜索树的中序，所以是有序的。

set中不允许出现值相等的元素，而multiset中允许。

一般情况下，我们使用set都不需要传后两个模版参数。set默认支持的小于比较，即set中默认升序，如果想按自己的需求走可以自行实现仿函数传给第二个模版参参数。

#include<set>
int main()
{
    set<int> s;
    return 0;
}

2.set的构造和迭代器

构造函数

set常用的默认构造函数包括如下几种：

①默认构造

set<int> s;

②花括号初始化构造（C++11 引入）

set<int>s1({ 1,2,3,4,5 });

花括号构造本质上调用的std::initializer_list在其他STL容器中也十分常用。如vector<int> v = {1, 2, 3, 4, 5};

③迭代器构造

//其他容器同理
vector<int> v= { 1, 2, 3, 4, 5 };
set<int>s(v.begin(), v.end());

④拷贝构造

set<int>s1={1,2,3,4,5};
set<int>s(s1);

迭代器

set的迭代器是双向迭代器，不支持随机访问。

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

set<int> s={1,2,3,4,5};
std::set<int>::iterator beg = s.begin();
std::set<int>::iterator end = s.end();

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

set<int> s={1,2,3,4,5};
auto rbeg = s.rbegin();
auto rend = s.rend();

3.set的增删查

首先声明set不支持修改存储值，因为set的底层是k模型的搜索二叉树，如果修改节点值会导致整课树结构的失效，所以set既不支持交换元素顺序也不支持修改元素数据。

insert函数

常用的insert的有三种重载：

①插入单个值，返回一个临时pair<iterator,bool>对象（下文有pair做介绍，可通过屏幕左侧目录跳转查看）

插入成功，返回的pair对象中包含“插入值的迭代器”与“true”;

插入失败，如插入已有值，那么返回的pair对象中包含“值的迭代器”与“false”;

	set<int> v = { 1,2,3 };
	auto it = v.insert(0);
	cout << *it.first << endl;
	for (auto x : v)cout << x << ' ';

②插入多个值

一般不会失败。

	set<int> v = { 1,2,3 };
	v.insert({7,6,5,5});
	for (auto x : v)cout << x << ' ';

③迭代器区间插入

这里的迭代器可以是其他容器的迭代器。

	set<int> v = { 1,2,3 };
	vector<int> vec= { 5,6,7 };
	v.insert(vec.begin(), vec.end());
	for (auto x : v)cout << x << ' ';

erase函数

常用的erase也有三个版本的重载。

①直接删除

常用的erase函数直接输入要删除的值即可，删除成功返回1，失败返回0.

	set<int> v = { 1,2,3 };
	for (auto x : v)cout << x << ' ';
	cout << endl;
	v.erase(3);
	for (auto x : v)cout << x << ' ';

②迭代器删除

删除迭代器指向的元素，并返回下一个迭代器。

	set<int> v = { 1,2,3 ,4,7,10,5 };
	for (auto x : v)cout << x << ' ';
	auto it = v.begin();
	while (it != v.end())
	{
		it = v.erase(it);
	}
	for (auto x : v)cout << x << ' ';

③迭代器区间删除

删除给定迭代器区间的所有数据。

	set<int> v = { 1,2,3 ,4,7,10,5 };
	for (auto x : v)cout << x << ' ';
	v.erase(v.begin(), v.end());
	for (auto x : v)cout << x << ' ';

find函数

中序遍历查找val，返回val所在的迭代器，没有找到返回end()。

	set<int> v = { 1,2,3 ,4,7,10,5 };
	auto ret = v.find(3);
	if (ret != v.end())
	{
		cout << *ret << endl;
	}

count函数

count会返回输入值在set的实际个数，这个函数主要在multiset 中经常使用，故在set中返回值一定为1.

	set<int> v = { 1,2,3 ,4,7,10,5 };
	cout << v.count(2);

4.lower_bound与upper_bound

lower_bound（val）函数作用：返回 >= val的迭代器

lower_bound（val）函数作用：返回 > val的迭代器

这两个函数常一起使用以达到查找到的 [itlow,itup) 区间。

5.multiset和set的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，随之带来的区别有：

①相比set，multiset虽然排序，但是不去重；

②find查找会返回第一个找到的值。

③erase时会删除所有容器中所有符合的值。

二、map的使用方法

1.map介绍

map在库中的声明如下。

map底层是用红黑树实现，而红黑树是基于k/v模型的搜索二叉树改进的，所以map的使用方法与set类似，增删查改效率也是O(logN)，迭代器遍历是走的也是中序，按key为关键字进行顺序遍历的。

一般情况下，我们使用map也都不需要传后两个模版参数。map默认支持的小于比较，即set中默认升序，如果想按自己的需求走可以自行实现仿函数传给第二个模版参参数。

与set不同的是，map底层存储数据的节点中使用了pair<Key,T>存储数据，其中key类型充当索引码，而T类型才是存储的数据；与set相同的是依据key值，map依旧不允许有两个及以上key相等的元素；比如，若map中已经有元素的key为“苹果”，那么之后就不能再插入key为“苹果”的数据。

map<string, int> mmo;

上面的string即充当key键，int为实际存储值。

pair介绍

pair 是 C++ 标准库中定义的一个模板类，它可以将两个值组合成一个单一的实体。简单来说，它就是一个有两个公开成员变量的模板类。pari中有两个成员：first 、second 。

template<class T1,class T2>
struct pair
{
    T1 first;
    T2 second; 
    //构造函数 
    pair():first(T1()),second(T2()){}
}

make_pair

有关pair最常用的函数就是make_pair函数。它的作用是接受两个任意类型的参数，返回一个通过这两个参数实例化的pair对象。

template<classT1,classT2>
inline pair<T1,T2>make_pair(T1x,T2y)
{
    return(pair<T1,T2>(x,y));
}

说回map，map底层使用pair的原因在于加强键值对key/val的联系，将键和值捆绑在一起，既体现了C++的封装性，又加强了安全性。

2.map的构造和迭代器

构造函数

map的构造函数类型与set类似，常用的依旧如下四种：

①默认构造

map<string, int> mmo;

②花括号初始化构造（C++11 引入）

map<string, int> mmo ({{"苹果",1},{"香蕉",1}});

③迭代器构造

map的迭代器构造函数可以用其他容器的迭代器构造，但要求其他容器中的元素类型是pair<const Key, Value>或可以转换为这种类型。

	vector<pair<string, int>> v = { {"苹果",1},{"香蕉",2} };
	map<string, int>m(v.begin(), v.end());

④拷贝构造函数

	map<string, int>m({ {"苹果",1},{"香蕉",2} });
	map<string, int>m1(m);

迭代器

map迭代器是一个双向迭代器，map可以使用[ ]是因为重载了operator[ ]，迭代器本质依旧是双向迭代器。

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

map<string, int>s({ {"苹果",1},{"香蕉",2} });
std::map<string, int>::iterator beg = s.begin();
std::map<string, int>::iterator end = s.end();

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

map<string, int>s({ {"苹果",1},{"香蕉",2} });
std::map<string, int>::iterator rbeg = s.rbegin();
std::map<string, int>::iterator rend = s.rend();

3.map的增删查

insert函数

①插入一个pair对象，返回一个pair<iterator,bool>

map<char, int>dict = { {'a',1},{'b',1},{'c',1} };
dict.insert(make_pair( 'a',3 ));

单个数据插入，如果已经key存在则插入失败，key存在相等value不相等也会插入失败。返回的pair<iterator,bool>，插入成功bool为true，反之为false。而iterator则是为[ ]铺垫。

②插入多个pair对象

	map<string, int>m({ {"苹果",1},{"香蕉",2} });
	m.insert({ {"菠萝",3},{"荔枝",4} });

③通过迭代器区间插入

迭代器区间插入，已经在容器中存在的值不会插入。

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	map<string, int>m1({ {"菠萝",3},{"荔枝",4} });
	m.insert(m1.begin(), m1.end());

erase函数

①通过迭代器删除

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	m.erase(m.begin());

②通过值删除

删除val，val存在返回0，存在返回1。

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	m.erase("苹果");

③删除一段迭代器区间的值

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	m.erase(m.begin(),m.end());

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	cout << m.count("苹果") << endl;

find函数

查找key，返回k所在的迭代器，没有找到返回end()

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	auto ret = m.find("苹果");
	cout << ret->first << ' ' << ret->second << endl;

count函数

查找k，返回k的个数。主要是在multimap中使用。

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	cout << m.count("苹果") << endl;

4.map的数据修改

map支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[ ]，但是operator[ ]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。

通过迭代器修改

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	auto it = m.find("苹果");
	it->second = 100;

通过operator[ ]

	map<string, int>m = { {"苹果",1},{"香蕉",2} };
	m["苹果"] = 2;

为什么双向迭代器能使用operator[ ]

还记得map的insert函数不管十分插入成功都会返回一个pair<iterator,bool>对象吗？也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器，那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[ ]。

// operator的内部实现
T& operator[] (const key_type& k)
{
    pair<iterator, bool> ret = insert({ k, T() });
    iterator it = ret.first;
    return it->second;
}