当前位置: 首页 > article >正文

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


http://www.kler.cn/a/590410.html

相关文章:

  • 《论分布式系统架构设计及其应用》架构师论文
  • Qt-QChart实现折线图
  • [贪心算法]-最大数(lambda 表达式的补充)
  • Java 集合框架(Collection)
  • QT:动态属性和对象树
  • Compose笔记(九)--Checkbox
  • [数据结构]排序之 快速排序详解(递归版非递归版)
  • 游戏引擎学习第162天
  • 2025年高职大数据可视化实训室建设及实训平台整体解决方案
  • Vue秘籍:如何动态修改页面 Title(浏览器页签名称)?
  • idea cpu干到100%的解决方法?
  • HarmonyOS NEXT开发实战——HUAWEI DevEco Studio 开发指南
  • 车载以太网测试-13【网络层-IGMP协议】
  • 【Godot】Viewpoint
  • mapbox基础,使用线类型geojson加载symbol符号图层,用于标注文字
  • 解锁智慧养老新可能,全面提升养老生活质量
  • Go语言中的错误处理与异常恢复:性能对比与实践思考
  • 【leetcode】51.N皇后
  • 如何检查CMS建站系统的插件是否安全?
  • 《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(60)五火七禽扇灭火 - 接雨水(双指针与动态规划)