当前位置:首页 » 《资源分享》 » 正文

【C++进阶学习】第六弹——set和map——体会用C++来构建二叉搜索树

27 人参与  2024年09月16日 10:02  分类 : 《资源分享》  评论

点击全文阅读


set和map基础:【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

前言:

在上篇的学习中,我们已经学习了如何使用C语言来实现二叉搜索树,在C++中,我们是有现成的封装好的类模板来实现二叉搜索树的——set和map,这也是我们今天要讲的重点

目录

一、容器

二、set和multiset

一、set与multiset概述

二、set与multiset的基本操作

三、高级特性

四、set与multiset的选择

三、map和multimap

1. map与multimap的区别

2. map与multimap的使用场景

3. 基本操作

4. 注意事项

5. 示例代码

四、总结


一、容器

在前面,我们经常提到容器这个东西,比如stack、queue等许多类模板都称之为容器,其实今天要讲的set和map也是容器的一种,容器这个东西我会在下一章进行单独讲解,有兴趣的可以关注一下

二、set和multiset

在C++标准模板库(STL)中,setmultiset是两种关联容器,它们在处理有序集合数据时非常有用。

一、set与multiset概述

set 是一种关联容器,它存储唯一(不重复)的元素,并且这些元素会根据特定的排序规则自动排序。set内部通常采用红黑树实现,保证了元素的对数时间复杂度的插入、删除和查找操作。

multiset 与set类似,但它允许存储重复的元素。multiset同样基于红黑树实现,其操作的时间复杂度特性与set相同。

二、set与multiset的基本操作

在使用set或multiset之前,需要包含相应的头文件:

#include <set>#include <multiset>

以下是一些基本操作:

构造函数
set<T> s; // 默认构造函数multiset<T> ms; // 默认构造函数// 可以通过比较函数和分配器进行自定义构造
插入元素
s.insert(key); // set插入元素ms.insert(key); // multiset插入元素
insert 方法用于向set或multiset中添加元素,如果插入成功,set 的insert方法返回pair<iterator, bool>(这个东西后面会讲),其中bool指示是否插入成功。multiset 的insert方法返回指向插入元素的迭代器。 删除元素
s.erase(key); // 删除特定元素(set)ms.erase(key); // 删除特定元素(multiset)// 删除操作在multiset中会删除所有匹配的元素
查找元素
auto it = s.find(key); // 查找元素(set)auto it = ms.find(key); // 查找元素(multiset)// find返回指向元素的迭代器,如果未找到则返回end()
统计元素个数
s.count(key); // set中元素个数(总是1或0)ms.count(key); // multiset中元素个数(可能是大于0的整数)
大小和容量
s.size(); // 返回元素数量ms.size(); // 返回元素数量s.empty(); // 判断是否为空ms.empty(); // 判断是否为空

三、高级特性

迭代器

set和multiset都提供迭代器,支持前向和后向遍历。

for (auto it = s.begin(); it != s.end(); ++it) {    // 遍历set中的元素}
排序规则

默认情况下,set和multiset使用小于操作符<进行排序,但可以通过自定义比较函数来改变排序规则。

struct CustomCompare {    bool operator()(const T& a, const T& b) const {        // 自定义比较逻辑    }};set<T, CustomCompare> s; // 使用自定义比较函数multiset<T, CustomCompare> ms; // 使用自定义比较函数
性能考虑

由于set和multiset基于二叉搜索树实现,它们的插入、删除和查找操作通常具有O(log n)的时间复杂度。

四、set与multiset的选择

选择使用set还是multiset取决于是否需要存储重复元素。如果需要存储唯一的元素集合,则应该使用set。如果允许集合中存在重复元素,那么应该选择multiset。

三、map和multimap

在C++的STL(标准模板库)中,mapmultimap是两种关联容器,它们用于存储键值对。这些容器使用红黑树作为底层数据结构,以确保高效的插入、查找和删除操作。

1. mapmultimap的区别

唯一性map存储的是唯一键值对,即每个键只能对应一个值。而multimap允许相同的键对应多个值,提供了一种更灵活的数据存储方式。排序:两者都按照键的自然顺序进行排序,通常为升序。可以通过自定义比较函数来改变排序规则。

2. mapmultimap的使用场景

map通常用于需要确保键的唯一性且需要对键进行排序的场景。例如,统计不同类别的数据数量、实现字典等。multimap则适用于需要处理多个值与相同键关联的场景,如记录用户在不同时间段的登录记录。

3. 基本操作

下面这些操作与上面set和multiset的操作基本一致,就不再写了

构造与初始化:可以通过构造函数直接初始化mapmultimap,也可以使用std::make_mapstd::make_multimap辅助函数。自定义排序可以通过传递比较函数来实现。插入与删除:使用insert方法插入键值对,erase方法删除键值对。erase方法还可以用于删除指定范围内的元素。查找find方法用于查找键值对,返回指向匹配元素的迭代器;lower_boundupper_bound方法用于查找键的范围,适用于处理多个相同键的值。

4. 注意事项

迭代器的失效:删除元素后,所有指向被删除元素的迭代器都会失效。在迭代时,需要确保迭代器的有效性。键的类型:键的类型必须支持比较操作,通常需要有定义的比较运算符或提供一个比较函数。性能:插入、查找和删除操作的时间复杂度为O(log n),基于红黑树的高效性。值类型:值的类型可以是任何类型,但通常选择有意义的数据类型,如整型、浮点型或字符串等。

5. 示例代码

#include <iostream>#include <map>#include <string>using namespace std;int main() {    // 使用map存储唯一键值对   map<string, int> fruitCounts = {        {"apple", 10},        {"banana", 15},        {"cherry", 5}    };    // 使用multimap存储多个值与相同键关联    multimap<string, int> logins =     {        {"Alice", 1001},        {"Bob", 2001},        {"Alice", 1003}    };    // 查找和打印map中的元素    auto it = fruitCounts.find("banana");    if (it != fruitCounts.end()) {        cout << "Found banana: " << it->second << endl;    }    // 查找和打印multimap中的元素    auto range = logins.equal_range("Alice");    for (auto it = range.first; it != range.second; ++it) {        cout << "Login for Alice: " << it->second << endl;    }    return 0;}

运行结果:

四、总结

以上就是C++中set和map的全部内容,其实底层逻辑就是二叉搜索树或者准确来说叫红黑树,其中有一些小的知识点会在下一节再提一下

感谢各位大佬观看,创作不易,还请各位大佬点赞支持一下!!!


点击全文阅读


本文链接:http://zhangshiyu.com/post/160607.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1