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)中的一个实用模板类,用于将两个值组合成一个单一对象,可以存储两个不同类型的元素,称为firstsecond。这两个值可以是相同类型,也可以是不同类型。它定义在<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 可以转换为 T1U2 可以转换为 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成员

通过 firstsecond 访问成员。

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.pswp.cn/pingmian/93040.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/93040.shtml
英文地址,请注明出处:http://en.pswp.cn/pingmian/93040.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解决程序连不上RabbitMQ:Attempting to connect to/access to vhost虚拟主机挂了的排错与恢复

前言&#xff1a;在分布式系统里&#xff0c;RabbitMQ作为消息中间件&#xff0c;是服务间通信的关键纽带。但实际使用中&#xff0c;程序连接RabbitMQ失败的情况时有发生。本文结合真实报错&#xff0c;细致呈现从问题发现到解决的完整排错思路&#xff0c;还会深入讲解Rabbit…

K8S中如何配置PDB(Pod Disruption Budget)

1. PDB 核心概念作用&#xff1a;控制自愿中断&#xff08;如节点升级、缩容&#xff09;期间&#xff0c;应用的最小可用副本数或最大不可用比例。关键参数&#xff1a;minAvailable&#xff1a;必须保持运行的 Pod 数量&#xff08;如 2 或 50%&#xff09;。maxUnavailable&…

从 0 到 1:用 MyCat 打造可水平扩展的 MySQL 分库分表架构

一、为什么要分库分表&#xff1f; 单机 MySQL 的极限大致在&#xff1a;维度经验值单表行数≤ 1 000 万行&#xff08;B 树三层&#xff09;单库磁盘≤ 2 TB&#xff08;SSD&#xff09;单机 QPS≤ 1 万&#xff08;InnoDB&#xff09;当业务继续增长&#xff0c;数据量和并发…

电池模组奇异值分解降阶模型

了解如何将奇异值分解 (SVD) 降阶模型 (ROM) 应用于电池模块热模拟。挑战随着电池模块在电动汽车和储能系统中的重要性日益提升&#xff0c;其热性能管理也成为一项重大的工程挑战。高功率密度会产生大量热量&#xff0c;如果散热不当&#xff0c;可能导致电池性能下降、性能下…

《Python函数:从入门到精通,一文掌握函数编程精髓》

坚持用 清晰易懂的图解 代码语言&#xff0c;让每个知识点变得简单&#xff01; &#x1f680;呆头个人主页详情 &#x1f331; 呆头个人Gitee代码仓库 &#x1f4cc; 呆头详细专栏系列 座右铭&#xff1a; “不患无位&#xff0c;患所以立。” Python函数&#xff1a;从入门到…

【记录贴】STM32 I2C 控制 OLED 卡死?根源在 SR1 与 SR2 的读取操作

问题描述最近在复用以前STM32F407控制OLED的代码&#xff0c;移植到STM32F103 上&#xff0c;使用硬件 I2C 通信方式。按照常规流程&#xff0c;先发送 OLED 的从机地址&#xff0c;OLED 有正常应答&#xff0c;但当发送第一个控制命令&#xff08;0xAE&#xff09;前的控制字节…

【AI驱动的语义通信:突破比特传输的下一代通信范式】

文章目录1 语义通信简介1.1 基本概念&#xff1a;什么是语义通信&#xff1f;语义通信的核心目标1.2 基本结构&#xff1a;语义通信系统结构语义通信系统的通用结构组成语义通信系统的结构关键模块1.3 基于大模型的语义通信关键技术&#x1f9e0;语义通信系统中AI大模型的设计建…

网络原理-HTTP

应用层自定义协议自定义协议是指根据特定需求设计的通信规则&#xff0c;用于设备或系统间的数据交换。其核心在于定义数据结构、传输方式及处理逻辑。协议结构示例典型的自定义协议包含以下部分&#xff1a;头部&#xff08;Header&#xff09;&#xff1a;标识协议版本、数据…

ROS配置debug指南

一. 安装插件 下面的这一个插件过期了需要用下面的这一个插件来替换:二. 设置CMakeLists.txt的编译模式 set(CMAKE_BUILD_TYPE "Debug") set(CMAKE_CXX_FLAGS_DEBUG "$ENV{CXXFLAGS} -O0 -Wall -g -ggdb") set(CMAKE_CXX_FLAGS_RELEASE "$ENV{CXXFLAG…

微软正式将GPT-5接入Microsoft Copilot Studio(国际版)

微软宣布正式在Microsoft Copilot Studio&#xff08;国际版&#xff09;中集成GPT-5&#xff0c;推动智能体构建能力实现突破性升级。此次更新不仅为企业用户带来更高效的响应速度、更精准的语境理解能力&#xff0c;还通过增强的逻辑推理功能&#xff0c;显著提升了AI交互的深…

微算法科技(NASDAQ:MLGO)通过蚁群算法求解资源分配的全局最优解,实现低能耗的区块链资源分配

随着区块链网络规模的不断扩大和业务需求的日益复杂&#xff0c;资源分配问题逐渐成为制约其发展的关键因素之一。传统的区块链资源分配方法往往存在效率低下、能耗过高、难以达到全局最优解等问题。高能耗不仅增加了运营成本&#xff0c;还对环境造成了较大的压力。因此&#…

深入浅出JVM:Java虚拟机的探秘之旅

深入浅出JVM&#xff1a;Java虚拟机的探秘之旅一、JVM 初相识&#xff1a;揭开神秘面纱 在 Java 的世界里&#xff0c;JVM&#xff08;Java Virtual Machine&#xff0c;Java 虚拟机&#xff09;就像是一个神秘的幕后大 boss&#xff0c;掌控着 Java 程序运行的方方面面。你可以…

Nginx学习笔记(八)—— Nginx缓存集成

&#x1f5c4;&#x1f5c4; Nginx缓存集成 &#x1f4cc;&#x1f4cc; 一、缓存核心价值 #mermaid-svg-CNji1KUDOsF8MwoY {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-CNji1KUDOsF8MwoY .error-icon{fill:#5522…

httpx 设置速率控制 limit 时需要注意 timeout 包含 pool 中等待时间

假设通过 httpx.Client 设置 limit 速率控制后&#xff0c;同时发起多个请求访问 youtube。并且由于科学原因一直连接不上 假设一共 4 个连接&#xff0c;max_connection2&#xff0c;timeout5s。 默认会发生的情况不是前两个连接 tcp 握手 timeout&#xff0c;后两个连接再发起…

【网络】TCP/UDP总结复盘

1.UDP的格式2.TCP的格式3.TCP是来解决什么问题的&#xff1f;答&#xff1a;解决IP层的不可靠传输问题&#xff0c;可能数据包丢失、损坏、重复等为上层应用层提高可靠有序的数据传输服务通过校验和、确认应答机制、序列号来解决不可靠传输和无序性问题通过流量控制--->>…

Nginx 配置中,root 和 alias 区别

在 Nginx 配置中&#xff0c;root 和 alias 都用于定义文件路径&#xff0c;但它们的行为有重要区别&#xff0c;特别是 路径拼接方式 和 末尾斜杠 (/) 的影响。1. root 和 alias 的区别 (1) root 指令 作用&#xff1a;root 会将 location 的 URI 拼接到 root 路径后面&#x…

基于vue.js的无缝滚动

方法一&#xff1a;基于requestAnimationFrame demo <template><h-page-container class"hoem-page"><h1>无缝滚动</h1><h2>垂直方向</h2><div class"container1"><AutoScroll :data"list" :item-…

【Linux学习|黑马笔记|Day4】IP地址、主机名、网络请求、下载、端口、进程管理、主机状态监控、环境变量、文件的上传和下载、压缩和解压

【DAY4】 今天看的是Linux第四章剩余部分 至此Linux暂时学到这&#xff0c;第五章还包含很多软件的安装&#xff0c;但是等我要用的时候再装吧 我现在只装了MySQL8.0&#xff0c;具体教程请看笔记安装教程 内容包含更换镜像源和安装配置步骤 文章目录【DAY4】6&#xff09;IP地…

【合新通信】射频光纤传输模块详解

射频光纤传输模块是一种将射频(RF)信号通过光纤进行传输的关键设备&#xff0c;广泛应用于通信、军事、广播电视等领域。以下是关于射频光纤传输模块的全面介绍&#xff1a;基本原理与组成射频光纤传输模块主要由以下几部分组成&#xff1a;电光转换单元&#xff1a;将输入的射…

【信息收集】从GET到POST:破解登录表单的全流程

目标&#xff1a;将浏览器数据代理至BP的proxy模块。将个人PHP的留言板项目首页登录数据包代理至BP&#xff0c;并转发至intrder模块&#xff0c;进行暴力破解。免责声明&#xff1a;本文章内容仅用于个人网络安全知识学习与研究&#xff0c;严禁用于任何未经授权的攻击或非法活…