C++STL之map与set使用详解

头发还没掉光光

938人浏览 · 2025-10-09 17:49:07

头发还没掉光光 · 2025-10-09 17:49:07 发布

C++STL之map与set

1. 关联式容器

基本概念

序列式容器：vector、list、deque等，存储元素本身，底层为线性数据结构，存储的数据和数据之间没有关联
关联式容器：map、set等，不仅仅是存储数据，一般还可以查找数据，数据检索效率更高，存储的数据和数据之间很强关联性

2. 树形结构的关联式容器

树形结构的关联式容器包括：

树型结构：map、set、multimap、multiset
哈希结构：unordered系列容器

共同点：使用平衡搜索树（红黑树）作为底层结构，元素有序

2.1 set容器

特性

按次序存储元素，value即key，必须唯一
元素不可修改，可插入删除
内部按严格弱排序准则排序
访问速度比unordered_set慢，但支持顺序迭代
底层用二叉搜索树（红黑树）实现

注意事项

实际存储<value, value>键值对
插入只需value，无需构造键值对
set中的元素是唯一的，重复插入会被忽略。（可用于去重）
迭代遍历得到有序序列
默认按小于比较
查找时间复杂度：O(log₂n)
set中的元素不能直接修改，因为元素的值同时也是键，修改可能会破坏排序。如果需要修改，应先删除再插入。

使用方式

template <class T, class Compare = less<T>, class Alloc = allocator<T>>
class set;

// 构造方式
set<int> s1;                   // 空set
set<int> s2(begin, end);       // 迭代器区间构造
set<int> s3(s2);               // 拷贝构造
set<int, greater<int> > s4(begin, end);       // 使用greater作为比较函数，使用迭代器区间构造

// 基本操作
s.insert(value);               // 插入
s.erase(iterator);             // 删除指定位置
s.erase(value);                // 删除指定值
s.find(value);                 // 查找
s.count(value);                // 计数（0或1）

构造函数

set(): 默认构造函数，创建一个空的set。

set(initializer_list< T > init): 使用初始化列表构造set。

set(InputIterator first, InputIterator last): 使用迭代器范围构造set。

set(const set& other): 拷贝构造函数。

set(set&& other): 移动构造函数（C++11）。

示例：

#include <set>
using namespace std;

set<int> s1; // 空set
set<int> s2 = {1, 2, 3}; // 初始化列表
set<int> s3(s2); // 拷贝构造
set<int> s4(move(s2)); // 移动构造（C++11）
set<int, greater<int>> s2 = {1, 2, 3}; // 使用greater作为比较函数生成set

析构函数

~set(): 释放set所有元素占用的内存。

赋值运算符

set& operator=(const set& other): 拷贝赋值。

set& operator=(set&& other): 移动赋值（C++11）。

set& operator=(initializer_list< T > ilist): 用初始化列表赋值（C++11）。

示例：

s1 = s3; // 拷贝赋值
s1 = move(s3); // 移动赋值
s1 = {4, 5, 6}; // 初始化列表赋值

迭代器

begin(), cbegin(): 返回指向第一个元素的迭代器（const版本返回const_iterator）。

end(), cend(): 返回指向最后一个元素之后位置的迭代器。

rbegin(), crbegin(): 返回指向最后一个元素的反向迭代器。

rend(), crend(): 返回指向第一个元素之前位置的反向迭代器。

示例：

set<int> s = {1, 2, 3};
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}
// 输出：1 2 3

for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
    cout << *rit << " ";
}
// 输出：3 2 1

容量

empty(): 检查set是否为空。

size(): 返回set中元素的个数。

max_size(): 返回set可容纳的最大元素数。

示例：

set<int> s;
cout << s.empty() << endl; // 1 (true)
s.insert(1);
cout << s.size() << endl; // 1

修改操作

insert(const T& value): 插入一个元素，返回一个pair，第一个元素是指向插入元素的迭代器，第二个元素是是否插入成功（bool）。

insert(T&& value): 插入一个右值元素（C++11）。

insert(iterator hint, const T& value): 在hint位置附近插入，可能提高插入效率。

insert(InputIterator first, InputIterator last): 插入一个迭代器范围。

insert(initializer_list< T > ilist): 插入一个初始化列表（C++11）。

erase(iterator pos): 删除指定位置的元素。

erase(const T& key): 删除键为key的元素，返回删除的元素个数（对于set，只能是0或1）。

erase(iterator first, iterator last): 删除一个迭代器范围。

clear(): 清空set。

swap(set& other): 交换两个set的内容。

示例：

set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(2); // 重复，插入失败
cout << s.size() << endl; // 3

s.erase(2); // 删除键为2的元素
cout << s.size() << endl; // 2

s.clear();
cout << s.size() << endl; // 0

查找

find(const T& key): 查找键为key的元素，返回迭代器，若没找到则返回end()。

count(const T& key): 返回键为key的元素个数，对于set，只能是0或1。

lower_bound(const T& key): 返回第一个不小于key的元素的迭代器。

upper_bound(const T& key): 返回第一个大于key的元素的迭代器。

equal_range(const T& key): 返回一个pair，表示键等于key的元素范围（由于set元素唯一，所以范围最多一个元素）。

示例：

set<int> s = {1, 2, 3, 4, 5};
auto it = s.find(3);
if (it != s.end()) {
    cout << "Found: " << *it << endl;
}

cout << s.count(3) << endl; // 1
cout << s.count(6) << endl; // 0

auto lit = s.lower_bound(2); // 指向2
auto uit = s.upper_bound(3); // 指向4
s.erase(lit, uit);           // 删除[2, 3]（即[2, 4)）区间内的所有值

for(auto e : s)
{
    cout<< e << " ";        // 1, 4, 5
}

观察器

key_comp(): 返回用于比较键的函数对象（默认是less< T >）。

value_comp(): 对于set，同样返回用于比较键的函数对象，因为set中value就是key。

示例：

set<int> s;
auto comp = s.key_comp();
cout << comp(1, 2) << endl; // 1 (true, 1<2)

非成员函数

operator==, operator!=, operator<, operator<=, operator>, operator>=: 比较两个set的大小关系（C++20中引入了三路比较）。

swap(set& lhs, set& rhs): 交换两个set。

示例：

set<int> s1 = {1, 2, 3};
set<int> s2 = {1, 2, 3};
cout << (s1 == s2) << endl; // 1 (true)

综合使用：排序去重

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string>

using namespace std;
int main()
{
	vector<string> data = { "string", "vector", "map", "set", "stack", "list",
                           "queue", "vector", "map", "set", "stack", "list", };
	set<string> se;
	for (const string& e : data)
	{
		se.insert(e);
	}

	for (const string& e : se)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

在这里插入图片描述

可以看到，set既可以实现去重，还可以实现排序，在其他方面，set也有更为广泛的应用场景，比如，在用户权限管理系统中，set被用于存储和管理用户的唯一权限标识。系统将每个用户的权限代码自动去重并排序存储，当用户尝试访问某个功能时，系统只需在权限set中快速查找对应的权限码是否存在，既保证了权限的唯一性，又实现了高效的权限验证，避免了线性搜索带来的性能损耗。

2.2 map容器

map容器与set结构相似，不同的点是map是key-value模型的关联式容器，可以通过key进行查找访问修改所对应的value。

在成员属性设置上，map除了一些数据结构相关的指针外，其数据存储所用类型为键值对pair。这样就可以根据其第一个元素进行查找，找到后返回键值对可以拿到第二个元素。

需要注意的是，第一个元素key不允许被修改，因为key用来进行排序的唯一标识，修改后不符合搜索树的规则，无法进行排序查找。

键值对(pair)

定义与作用

表示一一对应关系的结构
包含两个成员变量：key（键值）和value（对应信息）

SGI-STL中的实现

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    
    T1 first;
    T2 second;
    
    pair(): first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b): first(a), second(b) {}
};

与set不同的特性

按key次序存储键值对
key用于排序和唯一标识，value存储关联内容
支持下标访问符operator[]

使用方式

template <class Key, class T, class Compare = less<Key>, 
          class Alloc = allocator<pair<const Key, T>>>
class map;

// 元素访问
map<string, string> m;
m["apple"] = "苹果";           // 插入或修改
m.at("key");                   // 访问，key不存在时抛异常

// 插入方式
m.insert(pair<string, string>("peach", "桃子"));
m.insert(make_pair("banana", "香蕉"));

构造函数

map(): 默认构造函数，创建一个空的map。

map(initializer_list<pair<const Key, T>> init): 使用初始化列表构造map。

map(InputIterator first, InputIterator last): 使用迭代器范围构造map。

map(const map& other): 拷贝构造函数。

map(map&& other): 移动构造函数（C++11）。

示例：

#include <map>
#include <string>
using namespace std;

map<int, string> m1; // 空map
map<int, string> m2 = {{1, "one"}, {2, "two"}, {3, "three"}}; // 初始化列表
map<int, string> m3(m2); // 拷贝构造
map<int, string> m4(move(m2)); // 移动构造（C++11）
map<int, string, greater<int>> m5 = {{1, "one"}, {2, "two"}}; // 使用greater作为比较函数

析构函数

~map(): 释放map所有元素占用的内存。

赋值运算符

map& operator=(const map& other): 拷贝赋值。

map& operator=(map&& other): 移动赋值（C++11）。

map& operator=(initializer_list<pair<const Key, T>> ilist): 用初始化列表赋值（C++11）。

示例：

m1 = m3; // 拷贝赋值
m1 = move(m3); // 移动赋值
m1 = {{4, "four"}, {5, "five"}, {6, "six"}}; // 初始化列表赋值

迭代器

begin(), cbegin(): 返回指向第一个元素的迭代器（const版本返回const_iterator）。

end(), cend(): 返回指向最后一个元素之后位置的迭代器。

rbegin(), crbegin(): 返回指向最后一个元素的反向迭代器。

rend(), crend(): 返回指向第一个元素之前位置的反向迭代器。

示例：

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

// 正向遍历
for (auto it = m.begin(); it != m.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}
// 输出：
// 1: one
// 2: two
// 3: three

// 反向遍历
for (auto rit = m.rbegin(); rit != m.rend(); ++rit) {
    cout << rit->first << ": " << rit->second << endl;
}
// 输出：
// 3: three
// 2: two
// 1: one

容量

empty(): 检查map是否为空。

size(): 返回map中元素的个数。

max_size(): 返回map可容纳的最大元素数。

示例：

map<int, string> m;
cout << m.empty() << endl; // 1 (true)
m.insert({1, "one"});
cout << m.size() << endl; // 1
cout << m.max_size() << endl; // 返回最大可能大小

元素访问

operator[]: 访问或插入指定键的元素。

at(): 访问指定键的元素，键不存在时抛出异常（C++11）。

示例：

map<string, int> m;
m["apple"] = 5; // 插入键值对
cout << m["apple"] << endl; // 输出: 5
cout << m["banana"] << endl; // 输出: 0（自动插入默认值）

try {
    cout << m.at("cherry") << endl; // 抛出std::out_of_range异常
} catch (const out_of_range& e) {
    cout << "Key not found!" << endl;
}

修改器

insert(const value_type& value): 插入元素。

insert(const_iterator hint, const value_type& value): 在指定位置提示下插入元素。

insert(InputIt first, InputIt last): 插入迭代器范围内的元素。

insert(initializer_list<value_type> ilist): 插入初始化列表中的元素。

emplace(Args&&… args): 原地构造元素。

emplace_hint(const_iterator hint, Args&&… args): 带提示的原地构造。

erase(const_iterator pos): 删除指定位置的元素。

erase(const_iterator first, const_iterator last): 删除指定范围的元素。

erase(const key_type& key): 删除指定键的元素。

clear(): 清空所有元素。

swap(map& other): 交换两个map的内容。

示例：

map<int, string> m;

// insert 
m.insert({1, "one"}); //隐式类型转换，相当于 m.insert(pair<int,string>(1,"one"));
m.insert(m.begin(), {2, "two"});

vector<pair<int, string>> vec = {{3, "three"}, {4, "four"}};
m.insert(vec.begin(), vec.end());

m.insert({{5, "five"}, {6, "six"}});

// emplace 原地构造
m.emplace(7, "seven");

// erase 
m.erase(1);
auto it = m.find(2);
if (it != m.end()) {
    m.erase(it);
}

m.erase(m.find(3), m.end());

map<int, string> m2 = {{8, "eight"}};
m.swap(m2);
m.clear();

查找

find(const key_type& key): 查找指定键的元素。

find(const key_type& key) const: const版本查找。

count(const key_type& key) const: 返回匹配特定键的元素数量。

lower_bound(const key_type& key): 返回指向首个不小于给定键的元素的迭代器。

lower_bound(const key_type& key) const: const版本。

upper_bound(const key_type& key): 返回指向首个大于给定键的元素的迭代器。

upper_bound(const key_type& key) const: const版本。

equal_range(const key_type& key): 返回匹配特定键的元素范围。

equal_range(const key_type& key) const: const版本。

示例：

map<int, string> m = {{1, "one"}, {2, "two"}, {4, "four"}};

// find
auto it = m.find(2);
if (it != m.end()) {
    cout << "Found: " << it->second << endl;
}

// count - 检查键是否存在
if (m.count(3) == 0) {
    cout << "Key 3 not found" << endl;
}

// 范围查找
auto lb = m.lower_bound(2);
auto ub = m.upper_bound(2);

// equal_range - 获取键的范围
auto range = m.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << ": " << it->second << endl;
}

观察器

key_comp() const: 返回键比较函数对象。

value_comp() const: 返回值比较函数对象。

示例：

map<int, string> m;

// 获取比较器
auto key_comp = m.key_comp();
bool result1 = key_comp(1, 2);

auto value_comp = m.value_comp();
bool result2 = value_comp({1, "a"}, {2, "b"});

operator[]特性

map中部分内置类型：

key_type	键的类型 Key
mapped_type	值的类型 T
value_type	std::pair<const Key, T>

operator函数实现的时候调用的是第一个insert，原型如下：

在这里插入图片描述

该函数插入一个键值对(我们map中使用的value_type键值对)，会返回一个键值对。返回的键值对类型为：pair<iterator, bool> 。

当我们插入键值对时，如果map中不存在该键值对的key，那么我们就插入该键值对，并且将新插入位置的迭代器和true作为键值对返回。

如果插入键值对中的key已经在map对象中存在，那么将key所在位置的迭代器和false作为键值对返回。

因此在官方文档中也有这样的解释：

在这里插入图片描述

operator[]相当于这样一行代码：*((this->insert(make_pair(k,mapped_type()))).first)).second；

其中，make_pair(k, mapped_type()) 返回k和mapped_type()创建的键值对。mapped_type() 相当于 T()，

则相当于：

value_type k = make_pair(k, T());

insert(k);

insert返回值为键值对，我们用ret接受后，获取其中第一个元素，就是我们所插入数据位置的迭代器。有了迭代器通过解引用（*it）就可以访问到我们存放的键值对数据（value_type k）,k.second就是我们所要访问的value

则该函数实现相当于：

mapped_type& operator[] (const key_type& k)
{
	pair<iterator, bool> ret = insert(k);
	iterator it = ret.first;
	return (*it).second;
}

其中，k 对应 make_pair(k, mapped_type())

ret对应insert(make_pair(k, mapped_type()))

it 对应 insert(make_pair(k, mapped_type())).first

(*it).second对应 *( insert(make_pair(k, mapped_type())).first).second

综合使用：统计计数

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
int main()
{
	vector<string> data = { "string", "vector", "map", "set", "stack", "list", "queue", "vector", "map", "set", "stack", "list", };
	map<string, int> ma;
	for (const string& e : data)
	{
		ma[e]++; //不存在就插入，并且计数器++，也就是1。存在直接返回value++，自增1
	}

	for (const pair<string, int>& e : ma)
	{
		cout << e.first << ": " << e.second << endl;
	}
	return 0;
}

在这里插入图片描述

可以看到，使用map，可以实现排序➕计数，这只是最基础的map使用，其有更多的应用场景，在电商平台的商品库存管理中，map构成了核心的数据结构。系统以商品ID作为键，对应的库存信息对象作为值，建立起高效的键值映射关系。通过商品ID可以直接O(log n)时间复杂度获取库存详情，支持实时库存查询、库存扣减和补货操作，同时自动按商品ID排序的特性便于生成有序的商品列表。