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

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（标准模板库）中，map和multimap是两种关联容器，它们用于存储键值对。这些容器使用红黑树作为底层数据结构，以确保高效的插入、查找和删除操作。

1. `map`与`multimap`的区别

唯一性：map存储的是唯一键值对，即每个键只能对应一个值。而multimap允许相同的键对应多个值，提供了一种更灵活的数据存储方式。

排序：两者都按照键的自然顺序进行排序，通常为升序。可以通过自定义比较函数来改变排序规则。

2. `map`与`multimap`的使用场景

map通常用于需要确保键的唯一性且需要对键进行排序的场景。例如，统计不同类别的数据数量、实现字典等。

multimap则适用于需要处理多个值与相同键关联的场景，如记录用户在不同时间段的登录记录。

3. 基本操作

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

构造与初始化：可以通过构造函数直接初始化map或multimap，也可以使用std::make_map或std::make_multimap辅助函数。自定义排序可以通过传递比较函数来实现。

插入与删除：使用insert方法插入键值对，erase方法删除键值对。erase方法还可以用于删除指定范围内的元素。

查找：find方法用于查找键值对，返回指向匹配元素的迭代器；lower_bound和upper_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的全部内容，其实底层逻辑就是二叉搜索树或者准确来说叫红黑树，其中有一些小的知识点会在下一节再提一下

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

原文地址:https://blog.csdn.net/2301_80220607/article/details/140389387 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1811867143407538176.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部