【C++进阶篇】C++容器完全指南：掌握set和map的使用，提升编码效率

在C++中，容器是存储和操作数据的核心工具。序列式容器（如vector、list）通过线性顺序存储数据，而关联式容器（如set、map）则通过键值对存储数据，允许更高效的查找、插入和删除。set是一个存储唯一元素的容器，内部自动排序，底层通常使用红黑树实现。它支持高效的查找和元素去重。map是存储键值对的容器，每个键都是唯一的，值可以重复，同样基于红黑树实现，提供快速的键值对查找。在需要快速检索、插入或删除元素时，set和map是非常实用的选择。

一. 序列式容器与关联式容器

1.1 序列式容器 (Sequential Containers)

序列式容器按照元素的插入顺序进行存储，它们提供了对元素的线性访问。序列式容器的元素是有顺序的，可以通过下标或迭代器来访问。常见的序列式容器包括：

• vector：动态数组，支持快速的随机访问。适用于频繁访问元素，但在中间插入或删除元素时性能较差。

• deque：双端队列，支持在两端快速插入和删除元素，但相比 vector，在访问和修改元素时稍慢。

• list：双向链表，支持在任意位置快速插入和删除元素，但不支持随机访问。

• array：固定大小的数组，支持快速随机访问，但在大小固定时使用。

• forward_list：单向链表，比 list 更节省内存，但只支持向前遍历。

1.2 关联式容器 (Associative Containers)

关联式容器是基于键值对的容器，每个元素由键和值组成，并且通过键进行访问。它们通常提供基于键的排序和查找功能，能够高效地查找、插入和删除元素。常见的关联式容器包括：

• set：存储唯一元素的集合，自动排序。可以高效地判断元素是否存在。

• map：存储键值对，其中每个键都是唯一的，值可以重复。自动按照键排序。

• multiset：与 set 类似，但允许存储重复的元素。

• multimap：与 map 类似，但允许存储重复的键。

声明：本篇文章重点介绍关联式容器中的set，map

二. set系列使用

set的底层是用红黑树实现的，增删查效率是 O(logN)，迭代器的遍历是中序，所以是有序的。

2.1 set的构造和迭代器

set的迭代器是双向迭代器，遍历默认是升序的，因为底层说到底还是二叉搜索树，所以迭代器（const和非const版本迭代器）都不支持修改数据，会破坏二叉搜索树的结构。

构造类型	原型	功能
无参默认构造	explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	构造一个指定类型T的对象
迭代器区间构造	template set(InputIterator first, InputIterator last,const key_compare & comp = key_compare(),const allocator_type & = allocator_type());	使用迭代器区间初始化对象
初始化列表构造	set(initializer_list<value_type> il,const key_compare & comp = key_compare(),const allocator_type & alloc = allocator_type());	使用初始化列表构造对象
拷贝构造	set (const set& x);	使用拷贝构造对象
迭代器	原型	功能
正向迭代器	iterator begin();iterator end()	正向遍历容器中的数据
反向迭代器	reverse_iterator rbegin();reverse_iterator rend();	反向遍历容器中的数据

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<set>
using namespace std;int main()
{//无参默认构造set<int> s1;cout << "修改前s1: ";for (auto ch : s1){cout <<"原:s1 " << ch;}cout << endl;//迭代器区间构造set<int> s2({ 1,2,3,4,5,6,7,8,9,10 });//initializer 列表构造//set<int> s1(s2.begin(), s2.end());错误写法，s1重定义//使用赋值,或者直接插入//s1.insert(s2.begin(),s2.end())s1 = set<int>(s2.begin(), s2.end());//创建临时对象，进行赋值cout << "修改后s1:";for (auto ch : s1){cout << ch << " ";}cout << endl;//拷贝构造set<int> s3(s1);cout << "s3: ";for (auto ch : s3){cout <<ch << " ";}cout << endl;// 正确的反向遍历cout << "Reverse traversal of s3: ";for (auto rit = s3.rbegin(); rit != s3.rend(); ++rit) {cout << *rit << " ";}cout << endl;return 0;
}

2.2 set的增删查

2.2.1 插入

类型	原型	功能
单个插入	pair<iterator,bool> insert (const value_type& val);	插入单个数据，插入已经存在插入失败
列表插入	insert (initializer_list<value_type> il);	使用初始化列表插入元素
迭代器区间插入	template void insert(InputIterator first, InputIterator last);	使用迭代器区间插入元素

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<set>
using namespace std;int main()
{int a = 10;set<int> s;s.insert(a);//插入单个数据for (auto ch : s){cout << ch;}cout << endl;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入for (auto ch : s){cout << ch<<" ";}cout << endl;set<int> s3({ 10,20,30,40,50,60,70,80,90,100 });s.insert(s3.begin(), s3.end());//迭代器区间插入数据for (auto ch : s){cout << ch << " ";}cout << endl;return 0;
}

2.2.2 查找

类型	原型	功能
查找单个元素	iterator find (const value_type& val);	查找val，返回val所在的迭代器，没有找到返回end()
查找每个元素的总出现个数	size_type count (const value_type& val) const;	查找val，返回Val的个数

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<set>
using namespace std;int main()
{set<int> s;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入for (auto ch : s){cout << ch<<" ";}cout << endl;auto it = s.find(6);//存在返回所在迭代器cout << *it << endl;it = s.find(10);//不存在不可进行解引用//cout << *it << endl;error程序会终止int ret = s.count(6);cout << ret << endl;//查找6出现的总个数return 0;
}

2.2.3 删除

类型	原型	功能
删除单个元素	size_type erase (const value_type& val);	删除val，val不存在返回0，存在返回1
删除迭代器位置	iterator erase (const_iterator position);	删除⼀个迭代器位置的值
删除迭代器区间	iterator erase (const_iterator first, const_iterator last)	删除⼀段迭代器区间的值

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<set>
using namespace std;int main()
{set<int> s;s.insert({ 1,2,3,4,5,6,7,8,9 });//初始化列表插入cout << "删除前: ";for (auto ch : s){cout << ch<<" ";}cout << endl;cout << "删除5后: ";s.erase(5);//删除单个值for (auto ch : s){cout << ch << " ";}cout << endl;cout << "删除8后: ";auto it = s.find(8);s.erase(it);//删除迭代器位置的值for (auto ch : s){cout << ch << " ";}cout << endl;cout << "全部删除后: ";s.erase(s.begin(), s.end());//删除迭代器区间区间的值,等效于s.clear()for (auto ch : s){cout << ch << " ";}cout << endl;return 0;
}

补充：

// 返回⼤于等val位置的迭代器

• iterator lower_bound (const value_type& val) const;

// 返回⼤于val位置的迭代器

• iterator upper_bound (const value_type& val) const；

2.3 multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，说白就是允许插入相同的值。
下面主要来看insert/find/count/erase都围绕着⽀持值冗余有所差异，示例代码：

```cpp
#include<iostream>
#include<set>
using namespace std;
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;// 相⽐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给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

三. map系列使用

map的底层是红黑树，key/value结构场景，也是有序的。

3.1 pair类

在C++中，pair 是标准模板库(STL)提供的一个模板类，用于将两个可能不同类型的对象组合成一个单一单元。

3.1.1 定义与创建

#include // 包含pair的头文件
// 创建pair的几种方式
std::pair<int, double> p1; // 默认构造，两个元素被值初始化
std::pair<int, double> p2(1, 3.14); // 直接初始化 std::pair<int,
double> p3 = {2, 2.718}; // 列表初始化（C++11起） auto p4 =
std::make_pair(3, 1.618); // 使用make_pair辅助函数

3.1.2 访问元素

int first_element = p2.first; // 访问第一个元素（int类型）
double second_element = p2.second; // 访问第二个元素（double类型）

结论：pair 是C++中处理简单二元组合的高效工具，在需要临时组合两个相关值时非常有用。对于更复杂的数据结构，建议使用 struct 或 class 来提高代码可读性。

3.2 map构造

map的迭代器是双向迭代器，遍历默认是升序的，因为底层说到底还是二叉搜索树，所以迭代器（const和非const版本迭代器）都不支持修改数据，会破坏二叉搜索树的结构。

构造类型	原型	功能
无参默认构造	explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	构造一个指定类型T的对象
迭代器区间构造	template map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type());	使用迭代器区间初始化对象
初始化列表构造	map(initializer_list<value_type> il,const key_compare & comp = key_compare(),const allocator_type & alloc = allocator_type());	使用初始化列表构造对象
拷贝构造	map (const map& x);	使用拷贝构造对象
迭代器	原型	功能
正向迭代器	iterator begin();iterator end();	正向遍历容器中的数据
反向迭代器	reverse_iterator rbegin();reverse_iterator rend();	反向遍历容器中的数据

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<map>
using namespace std;int main()
{//无参默认构造map<string, string> t1;for (auto entry : t1){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//初始化列表构造map<string, string> t2({{ "apple", "苹果" }, { "banana", "香蕉" }, { "orange", "橙子" } });for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//迭代器区间构造map<string, string> t3(t2.begin(), t2.end());for (auto entry : t3){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//拷贝构造map<string, string> t4(t2);for (auto entry : t4){cout << entry.first << " -> " << entry.second << endl;}cout << endl;//正向迭代器遍历auto it = t4.begin();while (it != t4.end()){cout << it->first << " " << it->second << endl;++it;}cout << endl;//反向迭代器遍历for (auto it = t4.rbegin(); it != t4.rend(); it++){cout << it->first << " " << it->second << endl;}return 0;
}

3.3 map增删查

3.3.1 插入

类型	原型	功能
单个插入	pair<iterator,bool> insert (const value_type& val);	单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
列表插入	void insert (initializer_list<value_type> il);	列表插⼊，已经在容器中存在的值不会插⼊
迭代器区间插入	template void insert(InputIterator first, InputIterator last);	使用迭代器区间插入元素

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<map>
using namespace std;int main()
{pair<string, string> s("insert", "插入");map<string, string> t1;t1.insert(s);//插入单个元素cout << "t1: ";for (auto entry : t1){cout << entry.first << " -> " << entry.second << endl;}cout << endl;map<string, string> t2;t2.insert({ { "apple", "苹果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;map<string, string> t3;t3.insert(t2.begin(), t2.end());//迭代器区间插入cout << "t3: ";for (auto entry : t3){cout << entry.first << " -> " << entry.second << endl;}cout << endl;return 0;
}

2.2.2 查找

类型	原型	功能
查找单个元素	iterator find (const value_type& val);	查找val，返回val所在的迭代器，没有找到返回end()
查找每个元素的总出现个数	size_type count (const value_type& val) const;	查找val，返回Val的个数

下面将给出一个整合代码演示上述的功能：

• 示例代码：

#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> t2;t2.insert({ { "apple", "苹果" },{ "apple", "苹果" },{ "apple", "苹果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}auto it = t2.find("apple");//返回apple位置所在的迭代器cout << it->first << " " << it->second << endl;int ret = t2.count("apple");//查找apple出现的总次数cout << ret << endl;return 0;
}

2.2.3 删除

类型	原型	功能
删除单个元素	size_type erase (const value_type& val);	删除val，val不存在返回0，存在返回1
删除迭代器位置	iterator erase (const_iterator position);	删除⼀个迭代器位置的值
删除迭代器区间	iterator erase (const_iterator first, const_iterator last)	删除⼀段迭代器区间的值

示例代码：

#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> t2;t2.insert({ { "apple", "苹果" },{ "apple", "苹果" },{ "apple", "苹果" }, { "banana", "香蕉" }, { "orange", "橙子" } });//初始化列表插入cout << "删除前t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;t2.erase("apple");//删除指定元素值cout << "前t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;auto it = t2.find("orange");t2.erase(it);//删除迭代器位置的值cout << "中t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}cout << endl;t2.erase(t2.begin(), t2.end());//删除迭代器区间的值cout << "后t2: ";for (auto entry : t2){cout << entry.first << " -> " << entry.second << endl;}return 0;
}

3.4 map[]功能(重点)

3.4.1 基本功能

1. 访问元素：如果键存在于map中，operator[]会返回该键对应的值的引用。
2. 修改元素：通过返回的引用，可以直接修改该键对应的值。
3. 插入元素：如果键不存在于map中，operator[]会插入一个新的键值对，其中键是给定的键，值是值类型的默认构造值（对于内置类型如int、string等，默认构造值通常是0或空字符串；对于自定义类型，则是其默认构造函数创建的对象）。

3.4.2 返回值类型

operator[]返回的是值的引用（value_type&），这允许对值进行直接修改。

3.4.3 自动插入特性

当使用operator[]访问一个不存在的键时，map会自动插入一个新的键值对。
新插入的键的值部分是其值类型的默认构造值。

• 使用实例：

#include<iostream>
#include<map>
#include<string>
using namespace std;int main() {map<string, int> wordCount;// 访问并修改现有元素wordCount["apple"] = 10; // 插入或修改键为"apple"的元素cout << "apple: " << wordCount["apple"] << endl; // 输出: apple: 10// 访问不存在的键，自动插入新元素cout << "banana: " << wordCount["banana"] << endl; // 输出: banana: 0（因为int的默认构造值是0）// 修改自动插入的元素wordCount["banana"] += 5;cout << "banana: " << wordCount["banana"] << endl; // 输出: banana: 5// 使用at()方法访问元素（需要确保键存在）try {cout << "orange: " << wordCount.at("orange") << endl;} catch (const out_of_range& e) {cout << "orange: " << e.what() << endl; // 输出: orange: map::at: key not found}return 0;
}

3.5 multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，

• 示例代码：

#include <iostream>
#include <map>
#include <string>using namespace std;int main() {// 创建multimap并插入数据multimap<string, int> scores = {{"Alice", 90},{"Bob", 85},{"Alice", 95},  // 允许重复的key{"Charlie", 88}};// 1. 查找操作（返回第一个匹配项）auto it = scores.find("Alice");if (it != scores.end()) {cout << "找到Alice的第一个分数: " << it->second << endl; // 输出90}// 2. 计数操作（统计重复key的数量）int count = scores.count("Alice");cout << "Alice出现的次数: " << count << endl; // 输出2// 3. 范围查找（获取所有匹配项）cout << "所有Alice的分数: ";auto range = scores.equal_range("Alice");for (auto itr = range.first; itr != range.second; ++itr) {cout << itr->second << " "; // 输出90 95}cout << endl;// 4. 删除操作（删除所有匹配项）scores.erase("Alice");cout << "删除Alice后剩余元素数量: " << scores.size() << endl; // 输出2（Bob和Charlie）// 5. 尝试使用[]操作符（会编译失败）// scores["David"] = 78; // 错误：multimap不支持[]操作符return 0;
}

通过这个示例可以看出，multimap在处理需要多个相同key的场景时比map更灵活，但相应地也失去了一些特性（如[]操作符的直接访问能力）。在实际开发中，应根据是否需要key唯一性来选择合适的数据结构。

四. 最后

本文详述了C++中关联式容器set、multiset、map、multimap的用法，涵盖构造、迭代器、增删查等操作。set自动排序去重，multiset允许重复；map存储键值对，multimap支持键冗余。重点解析了map的[]操作符自动插入特性及multimap的范围查找。通过代码示例展示了各容器的核心功能与应用场景，是学习C++标准库关联容器的实用指南。