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 排序）。