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

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）中，set和multiset是两种关联容器，它们在处理有序集合数据时非常有用。

一、set与multiset概述

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

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

二、set与multiset的基本操作

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

#include 
#include 

以下是一些基本操作：

1. 构造函数：

set s; // 默认构造函数
multiset ms; // 默认构造函数
// 可以通过比较函数和分配器进行自定义构造

1. 插入元素：

s.insert(key); // set插入元素
ms.insert(key); // multiset插入元素

• insert 方法用于向set或multiset中添加元素，如果插入成功，set 的insert方法返回pair（这个东西后面会讲），其中bool指示是否插入成功。
• multiset 的insert方法返回指向插入元素的迭代器。
  1. 删除元素：

  s.erase(key); // 删除特定元素（set）
  ms.erase(key); // 删除特定元素（multiset）
  // 删除操作在multiset中会删除所有匹配的元素

  1. 查找元素：

  auto it = s.find(key); // 查找元素（set）
  auto it = ms.find(key); // 查找元素（multiset）
  // find返回指向元素的迭代器，如果未找到则返回end()

  1. 统计元素个数：

  s.count(key); // set中元素个数（总是1或0）
  ms.count(key); // multiset中元素个数（可能是大于0的整数）

  1. 大小和容量：

  s.size(); // 返回元素数量
  ms.size(); // 返回元素数量
  s.empty(); // 判断是否为空
  ms.empty(); // 判断是否为空

  三、高级特性

  1. 迭代器：

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

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

  1. 排序规则：

  默认情况下，set和multiset使用小于操作符