C++ STL：set和map的结构及接口使用

news/2024/10/19 6:17:11/

目录

一. set和map的简介

1.1 set的简介

1.2 map的简介 

二. set的主要接口函数及使用方法

2.1 构造及赋值相关接口函数

2.2 通过迭代器遍历set

2.3 结构修改相关接口函数

2.4 其他主要接口函数

三. map的主要接口函数及使用方法 

3.1 构造和赋值相关接口函数

3.2 通过迭代器遍历map

3.3 结构修改相关接口函数

3.3 查找和访问相关接口函数

一. set和map的简介

1.1 set的简介

  • set是按照一定的次序顺序存储数据的容器。
  • set的底层是通过二叉搜索树（红黑树）来实现的。
  • 在默认情况下，set底层的二叉树遵循左子节点小于根节点、右子节点大于根节点且不能有相同节点的结构要求。
  • 每个节点的值key具有const属性，不能被修改。
  • 在set中查找某个特定数据的时间复杂度是O(NlogN)。
  • 默认情况下，使用正向迭代器遍历set，是按照中序遍历进行的，也就是说会得到一组升序的数据。
  • set不可以存储相同的节点，但是multiset可以，multiset与set唯一的不同就是可以存储相同值的节点。
图1.1 set和multiset的声明

1.2 map的简介 

  • map是关联式容器。其结构与set类似，底层都是通过红黑树来实现的。
  • map和set的不同在于，map存储的数据类型是以Key和Value组成的键值对<Key, Value>，通过比较Key的值来使map满足搜索树的结构要求，而Value只是与Key进行配对的数据，不参数比较。
  • map中不允许存储两个Key相同的节点，但是multimap允许。
图1.2 map和multimap的声明

二. set的主要接口函数及使用方法

2.1 构造及赋值相关接口函数

接口函数功能
set(const compare& comp = compare)默认构造，创建空树
set(InputIterator first, InputIterator last, ...)使用迭代器区间初始化
set(const set& x)拷贝构造
set& operator=(const set& x)赋值运算符重载函数

代码2.1：（构造和赋值） 

int main()
{int arr[5] = { 5,2,3,4,1 };std::set<int> st1;   //默认构造std::set<int> st2(arr, arr + 5);   //迭代器区间构造std::set<int> st3(st2);  //拷贝构造std::set<int, std::greater<int>> st4;   //创建右子节点大于根节点左子节点小于根节点的setst1 = st3;  //赋值return 0;
}

2.2 通过迭代器遍历set

默认情况下，使用正向迭代器遍历set是进行中序遍历，得到一组升序的数据。

代码2.2：（set遍历的直接实现） 

int main()
{int arr[5] = { 5,2,3,4,1 };std::set<int> st1(arr, arr + 5);std::set<int, std::greater<int>> st2(arr, arr + 5);//给定迭代器std::set<int>::iterator it1 = st1.begin();std::set<int, std::greater<int>>::iterator it2 = st2.begin();//正向迭代器遍历st1，得到一组升序数据while (it1 != st1.end()){std::cout << *it1++ << " ";}std::cout << std::endl;//正向迭代器遍历st2，得到一组降序数据while (it2 != st2.end()){std::cout << *it2++ << " ";}std::cout << std::endl;return 0;
}
图2.1 对set前序遍历的运行结果

代码2.3：（set遍历的函数模板实现）

template<class T, class Compare = std::less<T>>
void SetPrint(const std::set<T, Compare>& st)
{typename std::set<T, Compare>::const_iterator it = st.begin();while (it != st.end()){std::cout << *it++ << " ";}std::cout << std::endl;
}

2.3 结构修改相关接口函数

接口函数功能
pair<iterator,bool> insert(const Type& x)在插入值为x的节点
void insert(InputIterator first, InputIterator last)插入位于一段迭代器区间的数据集
size_t erase(const Type& x)删除指定值
void erase(iterator pos)通过给定迭代器位置删除特定节点
void clear()清空所有节点
  • 这里需要注意insert函数的返回值：insert函数返回一键值对，pair中的first数据为iterator类型，如果成功插入节点（set中没有x），则返回新插入节点的位置的迭代器，如果插入节点失败，则返回与x值相同的节点的迭代器。pair中的second数据类型为bool，插入成功返回true，失败返回false。
  • erase返回被删除的节点的个数，因为set不允许有相同的节点，因此erase返回值只能是1或0，而multiset中erase的返回值则可以大于1，因为multiset中允许相同节点的存在。
  • 当调用erase函数给定值不存在或迭代器位置不合法时：如果使用给定值x的方法删除set的节点且x不存在，那么函数不进行任何工作，直接返回。如果给定不合法的迭代器位置调用erase，那么程序会崩溃。

代码2.4：（插入、删除和清空操作） 

int main()
{std::set<int> st;st.insert(7);st.insert(1);st.insert(0);st.insert(4);st.insert(5);   //插入数据SetPrint(st);   //set正向遍历打印函数st.erase(7);st.erase(10);st.erase(0);SetPrint(st);st.clear();   //清空元素SetPrint(st);return 0;
}
图2.2 代码2.4的运行结果

2.4 其他主要接口函数

接口函数功能
iterator find(const Type& x) const查找特定数据x函数
size_t  count(const Type& x) const统计set中x出现的次数
iterator lower_bound (const Type& x) const返回大于或等于x的最小节点
iterator upper_bound (const Type& x) const返回大于x的最小节点
pair<iterator,iterator> equal_range (const Type& x) const返回包含x的区间
  • find函数如果没有找到值为x的节点，就返回end()的迭代器位置，如果要使用find函数的返回值，保险起见，应当检查 st.find(x) != st.end() 是否成立。
  • 由于set中不允许有相同的节点，count的返回值只能是0或1。
  • equal返回的区间只包含一个数：[first, second) -- 左开右闭区间，*first = x。

代码2.5：

int main()
{std::set<int> st = { 10,10,20,30,40,40,50,60,70,80,90 };//查找数据20 -- 找得到std::set<int>::iterator pos1 = st.find(20);  if (pos1 != st.end()){std::cout << "找到了" << std::endl;}else{std::cout << "没找到" << std::endl;}//查找数据100 -- 找不到std::set<int>::iterator pos2 = st.find(100);if (pos2 != st.end()){std::cout << "找到了" << std::endl;}else{std::cout << "没找到" << std::endl;}std::set<int>::iterator it1 = st.lower_bound(30);std::set<int>::iterator it2 = st.lower_bound(40);std::set<int>::iterator it3 = st.upper_bound(40);std::set<int>::iterator it4 = st.upper_bound(45);std::cout << "*it1 = " << *it1 << std::endl;std::cout << "*it2 = " << *it2 << std::endl;std::cout << "*it3 = " << *it3 << std::endl;std::cout << "*it4 = " << *it4 << std::endl;std::pair<std::set<int>::iterator, std::set<int>::iterator> pa = st.equal_range(50);std::cout << "first=" << *pa.first << ", " << "second=" << *pa.second << std::endl;return 0;
}
图2.3 代码2.5的运行结果

三. map的主要接口函数及使用方法 

3.1 构造和赋值相关接口函数

接口函数功能
map(const compare& comp = compare)默认构造，创建空树
map(InputIterator first, InputIterator last, ...)使用迭代器区间初始化
map(const map& x)拷贝构造
map& operator=(const map& x)赋值运算符重载函数

代码3.1：（构造和赋值）

int main()
{std::map<int, int> mp1;  //默认构造std::map<int, int> rmp;rmp[1] = 1;rmp[3] = 3;rmp[2] = 2;std::map<int, int> mp2(rmp.begin(), rmp.end());  //通过迭代器区间构造std::map<int, int> mp3(mp2);  //拷贝构造mp1 = mp2;  //赋值return 0;
}

3.2 通过迭代器遍历map

注意：由于map存储的是键值对，对于map的迭代器it，不能直接对it解引用，*it会报错。如果想获取键值对中的数据，应当使用(*it).first/second 或it->first/second。

代码3.1：（迭代器遍历map）

int main()
{std::map<int, int> mp;mp[1] = 1;mp[3] = 3;mp[2] = 2;std::map<int, int>::iterator it = mp.begin();while (it != mp.end()){//std::cout << (*it).first << "=>" << (*it).second << " ";std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;return 0;
}
图3.2 代码3.1的运行结果

3.3 结构修改相关接口函数

接口函数功能
pair<iterator,bool> insert(const pair<T1,T2>& x)数据插入函数
void insert(InputIterator first, InputIterator second)插入某段迭代器区间的数据
size_t erase(const Type_Key& x)删除键值对中Key为x的数据
void erase(iterator pos)删除特定迭代器位置的节点
void erase(iterator first, iterator second)删除特定迭代器区间的节点
void clear()清空元素
  • make_pair(const Type1& key, const Type2& value) -- 键值对创建函数，给定参数为键值对的key和value，返回键值对pair<Type1,Type2>

代码3.2：（结构修改）

int main()
{std::map<int, int> mp;mp.insert(std::make_pair(5, 5));mp.insert(std::make_pair(7, 7));mp.insert(std::make_pair(3, 3));mp.insert(std::make_pair(1, 1));mp.insert(std::make_pair(9, 9));   //插入数据std::map<int, int>::iterator it = mp.begin();while (it != mp.end()){std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;mp.erase(1);mp.erase(9);  //给定值删除mp.erase(mp.begin());  //给定迭代器位置删除it = mp.begin();while (it != mp.end()){std::cout << it->first << "=>" << it->second << " ";++it;}std::cout << std::endl;mp.clear();  //清空元素return 0;
}
图3.3 代码3.2的运行结果

3.3 查找和访问相关接口函数

接口函数功能
iterator find(const Key_Type x)查找键值对Key为x的节点
Value_Type& operator[](const Key_Type x)

通过指定的Key的值x访问与之配对的Value值

/ 创建Key值为x的新节点

  • operator[]函数：如果在二叉map中找到了x，那么就直接返回与之配对的Value值的引用。如果没有找到x，那么就会以x为Key插入新的节点，但是Value的值就只能调用的类型的默认构造来给初值，无法保证新插入的节点的Value初值是需要的。

代码3.3：（查找和访问）

int main()
{std::map<int, int> mp;mp.insert(std::make_pair(5, 5));mp.insert(std::make_pair(7, 7));mp.insert(std::make_pair(3, 3));mp.insert(std::make_pair(1, 1));mp.insert(std::make_pair(9, 9));   std::map<int, int>::iterator it = mp.find(3);std::cout << it->first << "=>" << it->second << std::endl;mp[3] = 5;  //3存在std::cout << "mp[3] = " << mp[3] << std::endl;mp[10] = 10;   //10不存在std::cout << "mp[10] = " << mp[10] << std::endl;return 0;
}
图3.4 代码3.3的运行结果

http://www.ppmy.cn/news/64512.html

相关文章

(免费分享)springboot，vue物业管理系统

(免费分享)springboot，vue物业管理系统

一、项目技术 后端框架&#xff1a;springboot 前端框架&#xff1a;elementUIvue 主要实现了用户登录、社区信息展示、物业公告、社区设施、物业人员信息。 进入物业系统管理后端。实现了社区的管理&#xff0c;包括基本信息管理、周边设施管理、物业公告管理。楼盘管理包括楼…
阅读更多...
C++ | 结构体及大小计算

C++ | 结构体及大小计算

C结构体及大小计算 文章目录 C结构体及大小计算struct 和 class 区别字节对齐默认对齐方式 位域使用#pragma pack(n)结构体中有结构体Reference struct 和 class 区别 结构体&#xff08;struct&#xff09;和类&#xff08;class&#xff09;有点像&#xff0c;均是定义一个数…
阅读更多...
什么是应用交付网络（ADN）

什么是应用交付网络（ADN）

从CDN到ADN CDN&#xff08;内容分发网络&#xff09;在90年代末受到麻省理工学院的启发并完成发明&#xff0c;00年代初成立第一家成功的CDN商业企业Akamai。CDN的目标是相对于最终用户在空间上分配服务&#xff0c;以提供高可用性和高性能。随着互联网的发展&#xff0c;CDN…
阅读更多...
设计模式（二）：依赖倒转原则（详解）

设计模式（二）：依赖倒转原则（详解）

依赖倒转原则 前言一、依赖倒转原则1、基本介绍2、依赖关系传递的三种方式3、注意事项 二、代码演示1、版本一2、版本二3、版本三 前言 本博主将用CSDN记录软件开发求学之路上亲身所得与所学的心得与知识&#xff0c;有兴趣的小伙伴可以关注博主&#xff01;也许一个人独行&am…
阅读更多...
Http 响应头 Transfer-Encoding ： chunked 导致 浏览器客户端请求错误问题

Http 响应头 Transfer-Encoding ： chunked 导致 浏览器客户端请求错误问题

生产环境服务器规划如下 服务器类型网络环境cal.comnginx外网192.168.7.15:9200tomcat内网192.168.7.16:9200tomcat内网sdd.comnginx内网192.168.7.15:9100tomcat内网192.168.7.16:9100tomcat内网 192.168.7.15和192.168.7.16是做个负载均衡。目前的需求是用户访问外网的cal.…
阅读更多...
【存储数据恢复】NetApp存储WAFL文件系统数据恢复案例

【存储数据恢复】NetApp存储WAFL文件系统数据恢复案例

存储数据恢复环境&#xff1a; NetApp存储设备&#xff0c;WAFL文件系统&#xff0c;底层是由多块硬盘组建的raid磁盘阵列。 存储故障&#xff1a; 工作人员误操作导致NetApp存储内部分重要数据被删除。 存储数据恢复过程&#xff1a; 1、将存储设备的所有磁盘编号后取出&…
阅读更多...
springboot + vue 部署 阿里云云服务器 ECS

springboot + vue 部署 阿里云云服务器 ECS

安装所需文件 安装mysql5.7 下载MySQL的yum源配置 wget http://dev.mysql.com/get/mysql57-community-release-el7-11.noarch.rpm安装MySQL的yum源 yum -y install mysql57-community-release-el7-11.noarch.rpm使用yum方式安装MySQL5.7&#xff08;下载需要点时间&#xf…
阅读更多...
面试官：一千万的数据，你是怎么查询的

面试官：一千万的数据，你是怎么查询的

很多小伙伴一看到一些千万级数据之类的面试题就不知道怎么去回答。 也许有些人没遇过上千万数据量的表&#xff0c;也不清楚查询上千万数据量的时候会发生什么。 今天就来带大家实操一下&#xff0c;这次是基于MySQL 5.7.26做测试 准备数据 没有一千万的数据怎么办&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023