C++ map set pair
一、std::set
1. 基本概念
- 定义:
std::set
是关联容器,存储唯一键(不允许重复),按键自动排序(默认升序)。 - 头文件:
#include <set>
- 底层实现:通常为红黑树(平衡二叉搜索树)。
- 特性:
- 元素唯一且有序。
- 插入、删除和查找的时间复杂度为 O(log n)。
- 支持双向迭代器。
2. 构造函数
(1) 默认构造函数
std::set<int> s1; // 空集合,默认按less<int>排序
(2) 指定比较函数
struct CustomCompare {
bool operator()(int a, int b) { return a > b; } // 降序排序
};
std::set<int, CustomCompare> s2; // 自定义排序规则
(3) 通过迭代器范围构造
int arr[] = {3, 1, 4};
std::set<int> s3(arr, arr + 3); // 元素:1, 3, 4
(4) 拷贝构造函数
std::set<int> s4(s3); // 深拷贝s3的内容
3. 修改操作
(1) insert()
插入元素,支持以下重载:
- 插入单个值:
std::pair<std::set<int>::iterator, bool> result = s1.insert(5); // 返回pair,second为true表示插入成功 s1.insert(6);//或者直接插入
- 插入带有位置提示的值:
std::set<int>::iterator it = s1.begin(); s1.insert(it, 2); // 提示插入位置
- 插入迭代器范围:
int arr[] = {5, 6}; s1.insert(arr, arr + 2); // 插入数组内容
(2) erase()
删除元素,支持以下重载:
- 通过键删除:
size_t count = s1.erase(3); // 删除键为3的元素,返回删除数量(0或1)
- 通过迭代器删除:
std::set<int>::iterator it = s1.find(4); if (it != s1.end()) { s1.erase(it); // 删除迭代器指向的元素 }
- 通过迭代器范围删除:
s1.erase(s1.begin(), s1.find(3)); // 删除[begin, 3)之间的元素
(3) clear()
清空所有元素:
s1.clear(); // size=0
4. 查找操作
(1) find()
查找键对应的迭代器:
std::set<int>::iterator it = s1.find(3);
if (it != s1.end()) { /* 找到元素 */ }
(2) count()
统计键的数量(对于 set
只能是 0 或 1):
size_t c = s1.count(5); // 返回0或1
(3) lower_bound()
和 upper_bound()
返回键的边界迭代器:
std::set<int>::iterator lower = s1.lower_bound(3); // 第一个>=3的元素
std::set<int>::iterator upper = s1.upper_bound(3); // 第一个>3的元素
(4) equal_range()
返回键的区间(返回值为 pair<iterator, iterator>
)
一个包含两个迭代器的 pair 对象。
first:指向第一个不小于 key 的元素。
second:指向第一个大于 key 的元素。
若元素存在,则 first 指向该元素,second 指向下一个元素。
若元素不存在,first 和 second 均指向插入该元素时应处的位置(保持有序性)。
2. 在 set 中的行为
由于 set 中的元素是唯一的,equal_range 的返回值有两种可能:
元素存在:返回的 pair 中,first 指向该元素,second 指向其后一个元素。
元素不存在:first 和 second 指向相同位置,即该元素应插入的位置。
std::pair<std::set<int>::iterator, std::set<int::iterator> range = s1.equal_range(3);
// range.first是lower_bound(3), range.second是upper_bound(3)
5. 容量与迭代器
(1) size()
和 empty()
size_t s = s1.size();
if (s1.empty()) { /* 处理空集合 */ }
(2) 迭代器操作
for (std::set<int>::iterator it = s1.begin(); it != s1.end(); ++it) {
cout << *it << " "; // 升序遍历
}
for (std::set<int>::reverse_iterator rit = s1.rbegin(); rit != s1.rend(); ++rit) {
cout << *rit << " "; // 降序遍历
}
二、std::multiset
1. 基本概念
- 定义:
std::multiset
允许存储重复键,其他特性与std::set
相同。 - 头文件:
#include <set>
- 与
set
的区别:- 插入操作总是成功(返回迭代器,不返回
bool
)。 count()
可能返回大于1的值。erase(key)
删除所有匹配的键。- 如果有多个值,find返回的是中序的第一个。
- 插入操作总是成功(返回迭代器,不返回
用法与set类似,这里不在赘述了。
三、std::map
1. 基本概念
- 定义:
std::map
是关联容器,存储键值对(pair<const Key, Value>
),键唯一且按顺序排列(默认升序)。 - 头文件:
#include <map>
- 底层实现:红黑树(平衡二叉搜索树)。
- 特性:
- 键唯一,值可重复。
- 插入、删除和查找的时间复杂度为 O(log n)。
- 支持双向迭代器。
2. 构造函数
(1) 默认构造函数
std::map<int, std::string> m1; // 空map,默认按less<int>排序键
(2) 指定比较函数
struct CustomCompare {
bool operator()(int a, int b) { return a > b; } // 降序排序
};
std::map<int, std::string, CustomCompare> m2; // 自定义键排序规则
(3) 通过迭代器范围构造
typedef std::pair<const int, std::string> Entry;
Entry arr[] = {Entry(3, "A"), Entry(1, "B")};
std::map<int, std::string> m3(arr, arr + 2); // 元素:{1:"B", 3:"A"}
(4) 拷贝构造函数
std::map<int, std::string> m4(m3); // 深拷贝m3的内容
3. 修改操作
(1) insert()
插入键值对,支持以下重载:
- 插入单个键值对:
std::pair<std::map<int, std::string>::iterator, bool> result = m1.insert(std::make_pair(5, "C")); // 返回pair,second为true表示插入成功
- 插入带有位置提示的键值对:
std::map<int, std::string>::iterator it = m1.begin(); m1.insert(it, std::make_pair(2, "D")); // 提示插入位置(不一定加速)
- 插入迭代器范围:
Entry arr[] = {Entry(5, "E"), Entry(6, "F")}; m1.insert(arr, arr + 2); // 插入数组内容
(2) operator[]
通过键访问或插入值(若键不存在则默认构造值):
m1[3] = "G"; // 插入或修改键3对应的值
std::string val = m1[3]; // 获取键3的值(若不存在则插入默认值)
4. 删除操作
(1) erase()
删除元素,支持以下重载:
- 通过键删除:
size_t count = m1.erase(3); // 删除键为3的元素,返回删除数量(0或1)
- 通过迭代器删除:
std::map<int, std::string>::iterator it = m1.find(4); if (it != m1.end()) { m1.erase(it); // 删除迭代器指向的元素 }
- 通过迭代器范围删除:
m1.erase(m1.begin(), m1.find(3)); // 删除[begin, 3)之间的元素
(2) clear()
清空所有元素:
m1.clear(); // size=0
5. 查找与访问
(1) find()
查找键对应的迭代器:
std::map<int, std::string>::iterator it = m1.find(3);
if (it != m1.end()) {
std::cout << "Value: " << it->second; // 输出键3的值
}
(2) count()
统计键是否存在(对于 map
只能是 0 或 1):
size_t c = m1.count(5); // 返回0或1
(3) lower_bound()
和 upper_bound()
返回键的边界迭代器:
std::map<int, std::string>::iterator lower = m1.lower_bound(3); // 第一个>=3的键
std::map<int, std::string>::iterator upper = m1.upper_bound(3); // 第一个>3的键
(4) equal_range()
返回键的区间(pair<iterator, iterator>
):
std::pair<std::map<int, std::string>::iterator, std::map<int, std::string>::iterator> range =
m1.equal_range(3);
// range.first是lower_bound(3), range.second是upper_bound(3)
四、std::multimap
1. 基本概念
- 定义:
std::multimap
允许重复键,其他特性与std::map
相同。 - 头文件:
#include <map>
- 与
map
的区别:- 允许重复键。
- 没有
operator[]
(因为多个键可能对应不同值)。 insert()
总是成功,返回迭代器。erase(key)
删除所有匹配的键。
五、Pair
1. 基本定义
std::pair
可以存储两个不同类型的值,分别通过成员 first
和 second
访问:
#include <utility> // pair 的头文件
std::pair<int, std::string> p1; // 默认初始化,first=0,second=空字符串
std::pair<int, std::string> p2(3, "A"); // first=3,second="A"
2. 在 map
中的核心作用
在 std::map<Key, Value>
中,每个元素都是一个 pair<const Key, Value>
,其中:
first
是键(const Key
,不可修改)。second
是对应的值(Value
,可以修改)。
示例:
#include <map>
#include <string>
std::map<int, std::string> m;
m.insert(std::make_pair(1, "Apple")); // 插入一个 pair
m[2] = "Banana"; // operator[] 隐式创建 pair
// 遍历 map 时,迭代器指向的是 pair
for (std::map<int, std::string>::iterator it = m.begin(); it != m.end(); ++it) {
int key = it->first; // 获取键
std::string value = it->second; // 获取值
}
3. 在 set
中的潜在使用
虽然 std::set<T>
通常存储单个值,但如果你需要存储键值对,可以定义一个 set
存储 pair
:
#include <set>
#include <utility>
std::set<std::pair<int, std::string>> s;
s.insert(std::make_pair(3, "Cat")); // 插入 pair
此时,pair
的 first
和 second
共同作为元素的唯一标识(需定义比较规则)。
4. 常用操作
(1) 创建 pair
- 直接初始化:
std::pair<int, std::string> p(1, "Dog");
- 使用
make_pair
(自动推断类型):auto p = std::make_pair(2, "Cat"); // p 的类型是 pair<int, const char*>
(2) 访问成员
int key = p.first;
std::string value = p.second;
(3) 比较操作
pair
支持比较运算符(先比较 first
,若相等再比较 second
):
std::pair<int, int> p1(1, 2);
std::pair<int, int> p2(1, 3);
bool is_less = (p1 < p2); // true,因为 p1.second < p2.second
5. 为什么 pair
重要?
-
map
的底层实现:map
的元素是pair
,它通过first
(键)排序,保证键唯一。 - 多值关联:当需要将两个值作为一个整体处理时(例如函数返回多个值),
pair
提供轻量级封装。 - 与其他容器结合:例如
vector<pair<int, string>>
可以存储键值对列表。
总结
std::pair
用于将两个值捆绑在一起。- 在
map
中:它是元素的底层结构,first
是键,second
是值。 - 在
set
中:可以存储pair
,但需要自定义比较规则(默认按first
和second
排序)。