当前位置： 首页 > news >正文

C++-setmap详解

news 2025/8/15 6:43:55

C++set&map

1. 序列式容器和关联式容器

1.1 序列式容器

序列式容器按照线性顺序存储元素，元素的位置取决于插入的时间和位置，与元素的值无关。

主要特点：

  • 元素按插入顺序存储

  • 可以通过位置（索引）直接访问元素

  • 不自动排序

  • 允许重复元素

常见的序列式容器：

  1. array（C++11）

    • 固定大小的数组

    • 内存连续分配

    • 大小在编译时确定

    • 快速随机访问

  2. vector

    • 动态数组

    • 内存连续分配

    • 可动态扩展

    • 在尾部插入/删除高效

    • 支持快速随机访问

  3. deque（双端队列）

    • 双端可扩展

    • 内存分段连续

    • 在头尾插入/删除高效

    • 支持快速随机访问（比vector稍慢）

  4. list

    • 双向链表

    • 内存非连续分配

    • 在任何位置插入/删除高效

    • 不支持随机访问

  5. forward_list（C++11）

    • 单向链表

    • 内存非连续分配

    • 更节省空间

    • 只支持单向遍历

1.2 关联式容器

关联式容器按照特定顺序存储元素，元素的顺序取决于元素的键（key），而不是插入的顺序。

主要特点：

  • 元素按特定顺序（平衡二叉搜索树或哈希）存储

  • 通过键（key）快速查找元素

  • 通常实现为平衡二叉搜索树或哈希表

  • 有些版本不允许重复元素

常见的关联式容器：

  1. 有序关联容器（基于红黑树实现）

    • set：唯一键的集合，按键排序

    • map：键值对集合，按键排序，键唯一

    • multiset：键可重复的set

    • multimap：键可重复的map

  2. 无序关联容器（C++11引入，基于哈希表实现）

    • unordered_set：唯一键的集合，基于哈希

    • unordered_map：键值对集合，基于哈希，键唯一

    • unordered_multiset：键可重复的unordered_set

    • unordered_multimap：键可重复的unordered_map

2. 认识pair类型

2.1 概念

pair是C++标准模板库（STL）中的一个实用模板类，用于将两个值组合成一个单一对象，可以存储两个不同类型的元素，称为first和second。这两个值可以是相同类型，也可以是不同类型。它定义在<utility>头文件中，是许多STL容器(如map)的基础构建块。

2.2 pair实现

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;first_type first;second_type second;pair(): first(T1()), second(T2()) {}    // 默认构造pair(const T1& a, const T2& b): first(a), second(b) {}template<class U, class V>pair (const pair<U,V>& pr): first(pr.first), second(pr.second) {}    // 拷贝构造
};

为什么拷贝构造需要使用类中内嵌模板？

template <typename U1, typename U2> pair(const pair<U1, U2>& p); 这个构造函数的存在是为了支持跨类型的拷贝构造，而不仅仅是同类型的拷贝构造。这是 C++ 模板类设计中的一个重要特性，称为转换构造函数。

  1. 类型转换支持：

    • 允许从 pair<U1, U2> 构造 pair<T1, T2>

    • 只要 U1 可以转换为 T1，U2 可以转换为 T2

  2. 场景：

    std::pair<int, double> p1(42, 3.14);
std::pair<long, float> p2(p1);  // 需要这个模板构造函数

  3. 与普通拷贝构造的区别：

    • 普通拷贝构造：pair(const pair<T1, T2>& p)

    • 模板拷贝构造：template <typename U1, typename U2> pair(const pair<U1, U2>& p)

  4. 如果没有这个模板拷贝构造函数会怎么样？

    std::pair<int, std::string> p1(1, "hello");
std::pair<double, const char*> p2(p1);  // 编译错误
// 因为没有从 pair<int,string> 到 pair<double,const char*> 的转换路径

2.3 创建和初始化pair

2.3.1 构造函数
std::pair<int, std::string> p1(1, "apple");
2.3.2 使用make_pair函数（自动推导类型）

make_pair函数模板原型：

template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

auto p2 = std::make_pair(2, "banana");
2.3.3 C++11-initializer_list初始化
std::pair<int, std::string> p3 = {3, "cherry"};

2.4 访问pair成员

通过 first 和 second 访问成员。

2.4.1 普通访问
std::pair<int, std::string> p(1, "apple");std::cout << "First: " << p.first << std::endl;    // 输出: First: 1
std::cout << "Second: " << p.second << std::endl;  // 输出: Second: apple
2.4.2 结构化绑定（C++17）
auto p = std::make_pair(3.14, "pi");
auto [value, name] = p;  // value=3.14, name="pi"

3. set

set是C++ STL中的关联式容器，它存储唯一元素（key）并自动排序去重。

set原型

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

  • T就是set底层关键字（key）的类型

  • set默认要求T⽀持⼩于⽐较（仿函数less支持搜索树大于往右走，小于往左走，greater则相反），若比较的类型和方式比较复杂，可以自己实现仿函数

  • set底层是⽤红⿊树实现，增删查效率是O(logN) ，迭代器遍历是⾛的搜索树的中序，根据搜索树的性质，遍历是有序的

3.1 成员函数

3.1.1 成员类型
成员类型解释
key_type第一个模板参数T
value_type第一个模板参数T
key_compare第二个模板参数（less仿函数）
allocator_type第三个模板参数，STL空间配置器（内存池）
3.1.2 构造函数
序号函数原型说明
1️⃣explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())默认构造
2️⃣set (const set& x)拷贝构造
3️⃣set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())使用 initializer_list 初始化
4️⃣template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type())使用一段迭代器区间初始化
3.1.3 赋值重载
序号函数原型说明
1️⃣set& operator= (const set& x)两个已存在的 set 对象的赋值
2️⃣set& operator= (initializer_list<value_type> il)使用 initializer_list 赋值
3.1.4 迭代器
序号函数原型说明
1️⃣iterator begin()返回指向 set 对象中第一个元素的迭代器
2️⃣const_iterator begin() const返回指向 set 对象中第一个元素的 const 迭代器
3️⃣iterator end()返回指向 set 对象末尾元素之后位置的迭代器
4️⃣const_iterator end() const返回指向 set 对象末尾元素之后位置的 const 迭代器
5️⃣reverse_iterator rbegin()返回指向 set 对象末尾元素的反向迭代器
6️⃣const_reverse_iterator rbegin() const返回指向 set 对象末尾元素的 const 反向迭代器
7️⃣reverse_iterator() rend()返回指向 set 对象起始元素之前位置的反向迭代器
8️⃣const_reverse_iterator() rend() const返回指向 set 对象起始元素之前位置的 const 反向迭代器

注意：set迭代器是按中序的方式遍历的。

3.1.5 容量相关的接口
序号函数原型说明
1️⃣bool empty() const判断 set 对象是否为空
2️⃣size_type size() const返回 set 对象中元素的数量
3.1.6 修改相关的接口
序号函数原型说明
1️⃣pair<iterator,bool> insert (const value_type& val)向 set 对象中插入 val 元素
2️⃣iterator erase (const_iterator position)删除 set 对象中 position 迭代器位置元素，返回删除元素的下一个有效迭代器
3️⃣size_type erase (const value_type& val)删除 set 对象中 val 元素，返回值返回为删除的 val 元素（0或1）
4️⃣void clear()清空 set 对象

pair<iterator,bool> insert (const value_type& val) 返回值解析

返回值是一个 std::pair，包含两个部分：

  1. iterator：指向插入元素的迭代器

    • 如果插入成功：指向新插入的元素

    • 如果插入失败（元素已存在）：指向已存在的元素

  2. bool：表示插入是否成功

    • true：元素被成功插入

    • false：元素已存在，未插入新元素

3.1.7 其他
序号函数原型说明
1️⃣iterator find (const value_type& val)在 set 对象中查找 val 元素，成功返回该位置迭代器，失败返回迭代器end()
2️⃣size_type count (const value_type& val) const返回 set 对象中 val 元素的数量（0或1）

3.2 set与multiset的区别

set和multiset都是C++ STL中的关联容器，它们的主要区别在于元素的唯一性。

主要区别

  1. 元素唯一性

    • set：存储唯一元素，不允许重复

    • multiset：允许存储重复元素

  2. 插入操作

    • 向set插入已存在元素时，插入操作会失败

    • 向multiset可以重复插入相同元素

  • set与multiset接口一致。

  • 对于包含重复元素的multiset，find接口会返回按照容器排序顺序（默认是中序遍历顺序）出现的第一个与key相等的元素的迭代器。

4. map

map 是C++标准模板库（STL）中的一个关联容器，它存储的元素是pair类型，并且根据键（key）自动排序去重。

map原型

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

map中存储的pair类型

typedef pair<const Key, T> value_type;

  • Key就是map底层关键字的类型，T是map底层value的类型

  • map默认要求Key⽀持⼩于⽐较（仿函数less支持搜索树大于往右走，小于往左走，greater则相反），若比较的类型和方式比较复杂，可以自己实现仿函数

  • map底层是⽤红⿊树实现，增删查效率是O(logN) ，迭代器遍历是⾛的搜索树的中序，根据搜索树的性质，遍历是有序的

4.1 成员函数

4.1.1 成员类型
成员类型解释
key_type第一个模板参数Key
mapped_type第二个模板参数T
value_typemap 中实际存储的元素 pair<const key_type,mapped_type>
key_compare第三个模板参数（less仿函数）
allocator_type第死个模板参数，STL空间配置器（内存池）
4.1.2 构造函数
序号函数原型说明
1️⃣explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())默认构造
2️⃣map(const map& x)拷贝构造
3️⃣map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())使用 initializer_list 初始化
4️⃣template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type())使用一段迭代器区间初始化
4.1.3 赋值重载
序号函数原型说明
1️⃣map& operator= (const map& x)两个已存在的 map 对象的赋值
2️⃣map& operator= (initializer_list<value_type> il)使用 initializer_list 赋值
4.1.4 迭代器
序号函数原型说明
1️⃣iterator begin()返回指向 map 对象中第一个元素的迭代器
2️⃣const_iterator begin() const返回指向 map 对象中第一个元素的 const 迭代器
3️⃣iterator end()返回指向 map 对象末尾元素之后位置的迭代器
4️⃣const_iterator end() const返回指向 map 对象末尾元素之后位置的 const 迭代器
5️⃣reverse_iterator rbegin()返回指向 map 对象末尾元素的反向迭代器
6️⃣const_reverse_iterator rbegin() const返回指向 map 对象末尾元素的 const 反向迭代器
7️⃣reverse_iterator() rend()返回指向 map 对象起始元素之前位置的反向迭代器
8️⃣const_reverse_iterator() rend() const返回指向 map 对象起始元素之前位置的 const 反向迭代器

注意：map迭代器是按中序的方式遍历的。

4.1.5 容量相关的接口
序号函数原型说明
1️⃣bool empty() const判断 map 对象是否为空
2️⃣size_type size() const返回 map 对象中元素的数量
4.1.6 元素的访问
序号函数原型
1️⃣mapped_type& operator[] (const key_type& k)

map 的 operator[] 是一个非常有用的成员函数，它提供了对映射值的快速访问和修改能力。

功能说明

  1. 查找与修改：如果键 k 存在于 map 中，返回对应的映射值（value）的引用

  2. 插入与修改：如果键 k 不存在，会自动插入一个新的键值对，键为 k，值为 mapped_type 的默认构造值，然后返回这个新值（value）的引用

operator[]实现

(*( (insert(make_pair(k,mapped_type()))).first).second)

解析

mapped_type& operator[] (const key_type& k) {pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}
4.1.7 修改相关的接口
序号函数原型说明
1️⃣pair<iterator,bool> insert (const value_type& val)向 map 对象中插入 val 元素
2️⃣iterator erase (const_iterator position)删除 map 对象中 position 迭代器位置元素，返回删除元素的下一个有效迭代器
3️⃣size_type erase (const key_type& val)删除 map 对象中 val 元素，返回值返回为删除的 val 元素（0或1）
4️⃣void clear()清空 map 对象

pair<iterator,bool> insert (const value_type& val) 返回值解析

返回值是一个 std::pair，包含两个部分：

  1. iterator：指向插入元素的迭代器

    • 如果插入成功：指向新插入的元素

    • 如果插入失败（元素已存在）：指向已存在的元素

  2. bool：表示插入是否成功

    • true：元素被成功插入

    • false：元素已存在，未插入新元素

4.1.8 其他
序号函数原型说明
1️⃣iterator find (const value_type& val)在 map 对象中查找 val 元素，成功返回该位置迭代器，失败返回迭代器end()
2️⃣size_type count (const value_type& val) const返回 map 对象中 val 元素的数量（0或1）

4.2 map与multimap的区别

map和multimap都是C++ STL中的关联容器，它们的主要区别在于元素的唯一性。

主要区别

  1. 元素唯一性

    • map：存储唯一元素，不允许重复

    • multimap：允许存储重复元素

  2. 插入操作

    • 向map插入已存在元素时，插入操作会失败

    • 向multimap可以重复插入相同元素

  3. operator[]

    • map：支持 operator[] 访问

    • multimap：不支持 operator[]，因为键不唯一

  • map与multimap接口一致。

  • 对于包含重复元素的multimap，find接口会返回按照容器排序顺序（默认是中序遍历顺序）出现的第一个与key相等的元素的迭代器。

5. set与map迭代器失效问题

  • 只有指向被删除元素的迭代器会失效

循环中删除元素

std::set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); ) {if (*it % 2 == 0) {it = s.erase(it);  // erase返回下一个有效迭代器} else {++it;}
}

今天的看不懂，会成为明天的太简单。

http://www.lryc.cn/news/620556.html

相关文章：

  • 图灵测试：人工智能的“行为主义判据”与哲学争议
  • Elastic 获得 2025 年 Google Cloud DORA “以 AI 构建未来架构” 奖
  • 认知系统的架构： 认知残余三角形、认知主体意识 和认知演进金字塔(腾讯元宝）
  • Vue Vant应用-数据懒加载
  • Linux入门指南：基础开发工具---yum/apt
  • 分享一个基于Hadoop+spark的超市销售数据分析与可视化系统，超市顾客消费行为分析系统的设计与实现
  • 2025年大模型安全岗的面试汇总（题目+回答）
  • 使用Applications Manager进行 Apache Solr 监控
  • LeetCode 37.解数独：回溯法在二维网格中的应用与剪枝策略
  • 考公VS考研，拼哪个性价比高？
  • 考研408《计算机组成原理》复习笔记，第四章(1)——指令系统概念（指令字长、N地址指令、定长和变长操作码）
  • 微软发布五大AI Agent设计模式 推动企业自动化革新
  • 使用 Rust 进行 Web 自动化入门
  • Playwright初学指南 (3)：深入解析交互操作
  • Notepad++插件开发实战：从零打造效率工具
  • Inconsistent vendoring detected. Please re-run “go mod vendor“.
  • 【120页PPT】人工智能与数字化转型的业财融合（附下载方式）
  • Uniapp 条件编译详解
  • Transformers库中的 Trainer 类 的详细解析
  • 数据产品经理 | GenAI时代数据质量评估原则：FAV-QIRC 框架（一）
  • 【MATLAB代码】滑动窗口均值滤波、中值滤波、最小值/最大值滤波对比。订阅专栏后可查看完整代码
  • Spring 事务详解：从基础到传播机制的实践指南
  • 【机器人-开发工具】ROS 2 （4）Jetson Nano 系统Ubuntu22.04安装ROS 2 Humble版本
  • Claude Code 国内直接使用，原生支持 Windows 免WSL安装教程
  • CVPR 2025 | 即插即用，动态场景深度感知新SOTA！单目视频精准SLAM+深度估计
  • Linux系统Namespace隔离实战：dd/mkfs/mount/unshare命令组合应用
  • 【iOS】KVC原理及自定义
  • 【KALI】第一篇 安装Kali Linux虚拟机之详细操作步骤讲解
  • Redis 从入门到生产：数据结构、持久化、集群、工程实践与避坑（含 Node.js/Python 示例）
  • Windows 安装 Claude Code 并将 Claude Code 的大模型替换为 Kimi 的完整步骤