C++—— set、map、multiset、multimap的介绍及使用

目录

关联式容器

关联式容器的特点和使用场景

树形结构与哈希结构 

树形结构

哈希结构

键值对 

set

 set的介绍

set的定义方式

 set的使用

multiset

map 

map的介绍

map的定义方式

map的使用

multimap 


关联式容器

C++标准模板库(STL)中的关联式容器(Associative Containers)是一类根据键值对元素进行存储和操作的数据结构。它们允许快速查找、插入和删除操作,并且通常是基于树或哈希表实现的。C++ STL中的关联式容器包括四种主要类型:

  1. std::setstd::multiset

    • std::set 是一种集合,其中每个元素是唯一的,按特定顺序排序。
    • std::multisetstd::set 类似,但允许重复元素。
    • 这两种容器通常使用红黑树等平衡二叉搜索树实现,因此其查找、插入和删除操作的时间复杂度为 O(log n)。
  2. std::mapstd::multimap

    • std::map 是一种关联数组,其中每个元素都是一个键-值对,键是唯一的,按特定顺序排序。
    • std::multimapstd::map 类似,但允许键重复。
    • 这两种容器也通常使用平衡二叉搜索树实现,其查找、插入和删除操作的时间复杂度同样为 O(log n)。
  3. std::unordered_setstd::unordered_multiset

    • std::unordered_set 是一种无序集合,其中每个元素是唯一的,元素无特定顺序。
    • std::unordered_multisetstd::unordered_set 类似,但允许重复元素。
    • 这两种容器使用哈希表实现,因此其平均情况下的查找、插入和删除操作时间复杂度为 O(1)。
  4. std::unordered_mapstd::unordered_multimap

    • std::unordered_map 是一种无序关联数组,其中每个元素是一个键-值对,键是唯一的,元素无特定顺序。
    • std::unordered_multimapstd::unordered_map 类似,但允许键重复。
    • 这两种容器也使用哈希表实现,其平均情况下的查找、插入和删除操作时间复杂度为 O(1)。

关联式容器的特点和使用场景

  1. 有序关联容器(setmultisetmapmultimap

    • 排序:元素按照键的顺序排列,可以方便地进行范围查询。
    • 使用场景:需要按顺序访问元素或进行范围查询时,例如实现有序字典或集合。
  2. 无序关联容器(unordered_setunordered_multisetunordered_mapunordered_multimap

    • 无序:元素无特定顺序,通过哈希值快速访问。
    • 使用场景:关注查找、插入和删除的平均时间效率,而不在乎元素顺序时,例如实现哈希表或快速查找的数据结构。

树形结构与哈希结构 

树形结构

树形结构常用于实现有序关联容器,如 std::setstd::multisetstd::mapstd::multimap。具体来说,这些容器通常采用平衡二叉搜索树(如红黑树)来实现。以下是树形结构的一些关键点:

  1. 自动排序:元素按键值自动排序,支持有序遍历。
  2. 平衡性:红黑树等平衡二叉树保证了树的高度在O(log n)范围内,从而确保查找、插入和删除操作的时间复杂度为O(log n)。
  3. 复杂性:相对于哈希表实现,树形结构的插入和删除操作更为复杂,需要维护树的平衡。

适用场景

  • 需要按顺序访问或处理数据,例如范围查询。
  • 需要查找键的前驱或后继等顺序关系操作。

哈希结构

哈希结构用于实现无序关联容器,如 std::unordered_setstd::unordered_multisetstd::unordered_mapstd::unordered_multimap。这些容器基于哈希表来实现。以下是哈希结构的一些关键点:

  1. 无序存储:元素无特定顺序,基于哈希值进行存储。
  2. 快速访问:平均情况下,查找、插入和删除操作的时间复杂度为O(1)。
  3. 哈希冲突:需要处理哈希冲突,一般采用链地址法或开放地址法等策略。

适用场景

  • 更关注操作的平均时间效率,而不在乎元素的顺序。
  • 大量频繁的查找、插入和删除操作,例如实现哈希表或集合。

 

键值对 

  键值对是用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。

  比如我们若是要建立一个英译汉的字典,那么该字典中的英文单词与其对应的中文含义就是一一对应的关系,即通过单词可以找到与其对应的中文含义。

在SGI-STL中关于键值对的定义如下:

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

set

 set的介绍

1.set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列。

2.set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重。

3.与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对,因此在set容器中插入元素时,只需要插入value即可,不需要构造键值对。

4.set中的元素不能被修改,因为set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树。

5.在内部,set中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。当不传入内部比较对象时,set中的元素默认按照小于来比较。

6.set容器通过key访问单个元素的速度通常比unordered_set容器慢,但set容器允许根据顺序对元素进行直接迭代。

7.set在底层是用平衡搜索树(红黑树)实现的,所以在set当中查找某个元素的时间复杂度为logN。

set的定义方式

方式一: 构造一个某类型的空容器。

set<int> s1; //构造int类型的空容器

方式二: 拷贝构造某类型set容器的复制品。 

set<int> s2(s1); //拷贝构造int类型s1容器的复制品

 方式三: 使用迭代器拷贝构造某一段内容。

string str("abcdef");
set<char> s3(str.begin(), str.end()); //构造string对象某段区间的复制品

方式四: 构造一个某类型的空容器,比较方式指定为大于。

set < int, greater<int>> s4; //构造int类型的空容器,比较方式指定为大于

 set的使用

set当中常用的成员函数如下:

set当中迭代器相关函数如下:

 

使用示例: 

#include <iostream>
#include <set>

int main() {
    // 创建一个整数类型的set容器
    std::set<int> mySet;

    // 插入一些元素到set中
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(8);
    mySet.insert(2);

    // 使用迭代器遍历容器并输出元素(正向遍历)
    std::cout << "使用迭代器正向遍历容器:" << std::endl;
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除一个元素
    mySet.erase(3);

    // 使用范围 for 循环遍历容器并输出元素
    std::cout << "使用范围 for 循环正向遍历容器:" << std::endl;
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 检查集合中是否包含特定元素
    int target = 8;
    if (mySet.count(target)) {
        std::cout << "集合包含 " << target << std::endl;
    } else {
        std::cout << "集合不包含 " << target << std::endl;
    }

    // 获取集合的大小
    std::cout << "集合的大小:" << mySet.size() << std::endl;

    // 清空集合
    mySet.clear();

    // 检查集合是否为空
    if (mySet.empty()) {
        std::cout << "集合为空" << std::endl;
    } else {
        std::cout << "集合不为空" << std::endl;
    }

    // 向空集合中插入一些元素
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);

    // 使用反向迭代器遍历容器并输出元素(反向遍历)
    std::cout << "使用反向迭代器反向遍历容器:" << std::endl;
    for (auto rit = mySet.rbegin(); rit != mySet.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

multiset

    multiset容器与set容器的底层实现一样,都是平衡搜索树(红黑树),其次,multiset容器和set容器所提供的成员函数的接口都是基本一致的,这里就不再列举了,multiset容器和set容器的唯一区别就是,multiset允许键值冗余,即multiset容器当中存储的元素是可以重复的。

#include <iostream>
#include <set>

int main() {
    // 创建一个允许重复元素的 multiset 容器
    std::multiset<int> ms;

    // 插入一些元素到 multiset 中
    ms.insert(1);
    ms.insert(4);
    ms.insert(3);
    ms.insert(3);
    ms.insert(2);
    ms.insert(2);
    ms.insert(3);

    // 使用范围 for 循环遍历容器并输出元素
    for (auto e : ms) {
        std::cout << e << " ";
    }
    std::cout << std::endl; // 输出:1 2 2 3 3 3 4

    return 0;
}

由于multiset容器允许键值冗余,因此两个容器中成员函数find和count的意义也有所不同:

 

map 

map的介绍

1.map是关联式容器,它按照特定的次序(按照key来比较)存储键值key和值value组成的元素,使用map的迭代器遍历map中的元素,可以得到有序序列。

2.在map中,键值key通常用于排序和唯一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,并取别名为pair。

3.map容器中元素的键值key不能被修改,但是元素的值value可以被修改,因为map底层的二叉搜索树是根据每个元素的键值key进行构建的,而不是值value。

4.在内部,map中的元素总是按照键值key进行比较排序的。当不传入内部比较对象时,map中元素的键值key默认按照小于来比较。

5.map容器通过键值key访问单个元素的速度通常比unordered_map容器慢,但map容器允许根据顺序对元素进行直接迭代。

6.map容器支持下标访问符,即在[]中放入key,就可以找到与key对应的value。

7.map在底层是用平衡搜索树(红黑树)实现的,所以在map当中查找某个元素的时间复杂度为logN。

map的定义方式

方式一: 指定key和value的类型构造一个空容器。

map<int, double> m1; //构造一个key为int类型,value为double类型的空容器

方式二: 拷贝构造某同类型容器的复制品。 

map<int, double> m2(m1); //拷贝构造key为int类型,value为double类型的m1容器的复制品

方式三: 使用迭代器拷贝构造某一段内容。

map<int, double> m3(m2.begin(), m2.end()); //使用迭代器拷贝构造m2容器某段区间的复制品

方式四: 指定key和value的类型构造一个空容器,key比较方式指定为大于。

map<int, double, greater<int>> m4; //构造一个key为int类型,value为double类型的空容器,key比较方式指定为大于

map的使用

map的插入 map的查找 map的删除 map的[ ]运算符重载 map的迭代器 

#include <iostream>
#include <map>

int main() {
    // 创建一个键为整数,值为字符串的 map 容器
    std::map<int, std::string> myMap;

    // 插入元素到 map 中
    myMap.insert(std::make_pair(1, "One"));
    myMap.insert(std::make_pair(2, "Two"));
    myMap.insert(std::make_pair(3, "Three"));

    // 查找 map 中的元素
    int keyToFind = 2;
    auto it = myMap.find(keyToFind);
    if (it != myMap.end()) {
        std::cout << "键为 " << keyToFind << " 的值为:" << it->second << std::endl;
    } else {
        std::cout << "键为 " << keyToFind << " 的元素未找到" << std::endl;
    }

    // 删除 map 中的元素
    int keyToDelete = 1;
    myMap.erase(keyToDelete);

    // 使用 [] 运算符向 map 中插入或访问元素
    myMap[4] = "Four";

    // 使用迭代器遍历 map 并输出键值对
    std::cout << "遍历 map:" << std::endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "键:" << it->first << " 值:" << it->second << std::endl;
    }

    return 0;
}

map的其他成员函数

除了上述成员函数外,map当中还有如下几个常用的成员函数:

#include <iostream>
#include <string>
#include <map>

int main() {
    // 创建一个 map 容器,键为整数,值为字符串
    std::map<int, std::string> myMap;

    // 插入一些键值对到 map 中
    myMap.insert(std::make_pair(2, "two"));
    myMap.insert(std::make_pair(1, "one"));
    myMap.insert(std::make_pair(3, "three"));

    // 获取容器中元素的个数
    std::cout << "容器中元素的个数:" << myMap.size() << std::endl; // 输出:3

    // 容器中 key 值为 2 的元素个数
    std::cout << "容器中 key 值为 2 的元素个数:" << myMap.count(2) << std::endl; // 输出:1

    // 清空容器
    myMap.clear();

    // 容器判空
    std::cout << "容器是否为空:" << myMap.empty() << std::endl; // 输出:1

    // 创建一个临时的 map 容器,并交换数据
    std::map<int, std::string> tmpMap;
    myMap.swap(tmpMap);

    return 0;
}

multimap 

    multimap容器与map容器的底层实现一样,也都是平衡搜索树(红黑树),其次,multimap容器和map容器所提供的成员函数的接口都是基本一致的,这里也就不再列举了,multimap容器和map容器的区别与multiset容器和set容器的区别一样,multimap允许键值冗余,即multimap容器当中存储的元素是可以重复的。

#include <iostream>
#include <string>
#include <map>

int main() {
    // 创建一个 multimap 容器,键为整数,值为字符串
    std::multimap<int, std::string> mm;

    // 插入一些键值对到 multimap 中(允许重复键)
    mm.insert(std::make_pair(2, "two"));
    mm.insert(std::make_pair(2, "double"));
    mm.insert(std::make_pair(1, "one"));
    mm.insert(std::make_pair(3, "three"));

    // 使用范围 for 循环遍历 multimap 并输出键值对
    for (const auto& e : mm) {
        std::cout << "<" << e.first << "," << e.second << "> ";
    }
    std::cout << std::endl; // 输出:<1,one> <2,two> <2,double> <3,three>

    return 0;
}

 由于multimap容器允许键值冗余,因此两个容器中成员函数find和count的意义也有所不同:

其次,由于multimap容器允许键值冗余,调用[ ]运算符重载函数时,应该返回键值为key的哪一个元素的value的引用存在歧义,因此在multimap容器当中没有实现[ ]运算符重载函数。 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/642639.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【2024最新华为OD-C卷试题汇总】传递悄悄话的最长时间(100分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; 文章目录 前…

Mysql插入中文内容报错解决及其Mysql常用的存储引擎说明

一、问题描述 我们在Mysql数据库的表中插入带有中文内容时报错,提示【1366 - Incorrect string value: \xE5\x8C\x97\xE4\xBA\xAC... for column UserDealer at row 1】,如下图所示: 二、问题分析 一般来说插入中文内容有问题我们首先想到的就是编码问题;我们可以查看该表使…

C语言之指针进阶(3),函数指针

目录 前言&#xff1a; 一、函数指针变量的概念 二、函数指针变量的创建 三、函数指针变量的使用 四、两段特殊代码的理解 五、typedef 六、函数指针数组 总结&#xff1a; 前言&#xff1a; 本文主要讲述C语言指针中的函数指针&#xff0c;包括函数指针变量的概念、创建…

git分支策略(github-flow VS git flow,如何选择)

一. 结论 Github flow&#xff1a;最简单 小型项目&#xff0c;持续部署&#xff0c;自动化测试程度高&#xff0c;发布流程简单 Git flow&#xff1a;复杂但最常用 大型项目&#xff0c;发布周期长&#xff0c;需要同时维护多个版本&#xff0c;发布流程复杂 表格提供了不…

【算法设计与分析】基于Go语言实现动态规划法解决TSP问题

本文针对于最近正在学习的Go语言&#xff0c;以及算法课实验所需内容进行Coding&#xff0c;一举两得&#xff01; 一、前言 由于这个实验不要求向之前的实验一样做到那种连线的可视化&#xff0c;故可以用图形界面不那么好实现的语言进行编写&#xff0c;考虑到Go语言的…

2、xss-labs之level2

1、打开页面 2、传入xss代码 payload&#xff1a;<script>alert(xss)</script>&#xff0c;发现返回<script>alert(xss)</script> 3、分析原因 打开f12&#xff0c;没什么发现 看后端源码&#xff0c;在这form表单通过get获取keyword的值赋给$str&am…

下雨!大水蚁引发的水文!看比赛咯,曼联VS曼城——早读(逆天打工人爬取热门微信文章解读)

唠唠嗑 水一水 引言Python 代码结尾 引言 今天星期六 大小周 一个等了很久的双休 昨天晚上真的是吓到我了 漫天的小飞虫 我一开始还以为是一两只 没想到那些小飞虫 从阳台不断飞进来 在山卡拉下面租房子 也是太恐怖了 来个特写 他们也就一个晚上的时间 成虫 天气合适 长翅…

使用docker commit创建新镜像

前言 我们知道&#xff0c;从docker-hub上拉取的镜像所创建的容器是最小版本的&#xff0c;比如ubuntu内部是没有vim编辑器的&#xff0c;我们需要自己手动安装&#xff0c;但是当我们安装后假如有人把我们的容器误删了&#xff0c;那么我们再次根据原始镜像创建的容器就没有了…

优先级队列(堆)的实现

1.什么是优先级队列 队列是一种先进先出(FIFO)的数据结构&#xff0c;但有些情况下&#xff0c;操作的数据可能带有优先级&#xff0c;一般出队 列时&#xff0c;可能需要优先级高的元素先出队列&#xff0c;该中场景下&#xff0c;使用队列显然不合适&#xff0c;比如&#x…

Drone+Gitee自动执行构建、测试和发布工作流

拉取Drone:(至于版本&#xff0c;你可以下载最新的) sudo docker pull drone/drone:2 拉取runner&#xff1a; sudo docker pull drone/drone-runner-docker 在Gitee中添加第三方应用&#xff1a; 进入个人主页&#xff0c;点击设置&#xff1a; 往下翻&#xff0c;找到数…

2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针

import java.util.Scanner;public class Main {static Scanner scnew Scanner(System.in);public static void main(String[] args) {int nsc.nextInt();//数组长度int tsc.nextInt();//操作次数int arr[]new int[n];char arr1[] new char[t];int arr2[] new int[t];int vis…

输入一串字符,输入想要字符串前*的个数n,判断字符串前*的个数是大于n还是小于n,如果大于n则删除多余的*其它保持不变,如果小于n,则字符串也保持不变

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> void fun(char* a, int n) {int i 0, j 0, m 0,b0,c0;char* p;p a;//第一步&#xff0c;判断字母前面有多少个*while (p[i] *){j;}printf("字母前*的个数%d\n",j);//求总的字符串长度while (a[m] !…

基于.net开发的博客系统

基于.net开发可以批量上传md文件生成文章的博客系统 .NET 个人博客 基于.net开发的博客系统 个人博客系统&#xff0c;采用.net core微服务技术搭建&#xff0c;采用传统的MVC模式&#xff0c;使用EF core来对mysql数据库(sqlite数据库)进行CRUD操作项目 为什么要自己开发博客…

csdn的insCode怎么用IDE和linux终端

1.进入insCode&#xff0c;选择工作台 找到我的项目&#xff0c;没有项目的话可以新建一个。 选择在IDE中编辑&#xff0c;界面如下&#xff1a; 右边有个终端&#xff0c;点击即可出现linux的xterm终端。

依赖的各种java库(工具类) :fastjson,lombok,jedis,druid,mybatis等

lombok 功能&#xff1a; Lombok 是一个实用的Java类库&#xff0c;可以通过简单的注解来简化和消除一些必须有但显得很臃肿的Java代码。 导入包&#xff1a;使用Lombok首先要将其作为依赖添加到项目中&#xff0c;在pom.xml文件中手动添加 <dependency><groupId&g…

别对我动心短视频:成都鼎茂宏升文化传媒公司

别对我动心短视频&#xff1a;时代的爱情哲学与心理探索 在短视频的海洋里&#xff0c;"别对我动心"这样的标题&#xff0c;如同一颗石子投入平静的湖面&#xff0c;激起了层层涟漪。它不仅仅是对一段情感的拒绝&#xff0c;更是一种现代人情感态度的表达&#xff0…

AIGC-常见图像质量评估MSE、PSNR、SSIM、LPIPS、FID、CSFD,余弦相似度----理论+代码

持续更新和补充中…多多交流&#xff01; 参考: 图像评价指标PNSR和SSIM 函数 structural_similarity 图片相似度计算方法总结 MSE和PSNR MSE: M S E 1 m n ∑ i 0 m − 1 ∑ j 0 n − 1 [ I ( i , j ) − K ( i , j ) ] 2 MSE\frac{1}{mn}\sum_{i0}^{m-1}\sum_{j0}^{n-1}[…

TECHNIUM INTERNATIONAL: 利用 AI 和 TECHNIUM 矩阵协议引领区块链创新

在充满活力的加密货币和区块链技术领域&#xff0c;Technium International 以领军者的姿态迅速崛起&#xff0c;跻身科技巨头的顶尖行列。Technium International 成立于 2018 年&#xff0c;总部设于塞席尔&#xff0c;透过人工智慧&#xff08;AI&#xff09;和区块链技术的…

代码随想录算法训练营第三十七天|435. 无重叠区间、763.划分字母区间、56. 合并区间、738.单调递增的数字、968.监控二叉树

435. 无重叠区间 文档讲解&#xff1a;代码随想录 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 本道题与上个题目相似&#xff0c;都是求重叠区间 统计重叠区间的个数&#xff0c;减去重叠区间的个数就是无重叠区间了 主要就是为了让区间尽可能的重叠。&a…

Python_文件操作_学习

目录 一、关于文件的打开和关闭 1. 文件的打开 2.文件的关闭 二、文件的读取 1. 文件的读_r 2. 使用readline 3.使用readlines 三、文件的写入 1. 文本的新建写入 2.文本的追加写入 四、文件的删除和重命名 1.文件的重命名 2.文件的删除 五、文件的定位读写 1.t…