容器-Map&Set

type

status

summary

date

slug

1.Set

1.Set的底层其实就是红黑树，而红黑树其实就是一种特殊的搜索二叉树，既能快速查找也能快速的插入删除有着较强的性能

其实去重的原理就是如果在插入的时候被发现重复就不插入

💡

关于迭代器

在C++中，反向迭代器（reverse iterators）和普通迭代器（normal iterators）主要有以下几方面的区别：

迭代方向：

普通迭代器：按照容器元素的顺序进行遍历，从容器的前端向后端移动。

反向迭代器：按照与容器元素顺序相反的方向进行遍历，从容器的后端向前端移动。

自增自减操作：

当使用普通迭代器时，自增操作（++）会使迭代器向前移动到下一个元素，而自减操作（-）使迭代器移动到前一个元素。

对于反向迭代器，自增操作（++）实际上会使迭代器向后移动到前一个元素，而自减操作（-）会使迭代器向前移动到下一个元素。

解引用操作：

当对普通迭代器进行解引用操作（）时，得到的是迭代器指向的元素的引用。

对于反向迭代器，解引用操作得到的是它所“反向指向”的元素的引用。

比较操作：

普通迭代器的比较操作是直观的，即如果迭代器a在迭代器b之前，则a < b。

反向迭代器的比较操作则相反，如果反向迭代器ra在rb之前，则ra实际上指向的是容器中rb之后的位置，因此ra > rb。

与容器的关联：

反向迭代器通常通过容器的rbegin()和rend()成员函数获取，分别对应于普通迭代器的begin()和end()函数。rbegin()返回指向容器最后一个元素的迭代器，而rend()返回指向容器第一个元素之前位置的迭代器。

使用场景：

普通迭代器适用于需要正向遍历容器元素的场景。

反向迭代器适用于需要反向遍历容器元素的场景，如逆序处理元素。

在C++中，反向迭代器（reverse iterators）和普通迭代器（normal iterators）主要有以下几方面的区别：

💡

迭代器中的end（）指的是只想容器最后一个元素的最后一个位置

通用性：对于大多数标准库容器（如 vector、list、deque、set、map 等），end() 返回的迭代器并不等同于 nullptr。它是一个有效的迭代器，但是不允许对其进行解引用操作，因为解引用一个超出末尾的迭代器是未定义行为。

空容器的 end()：对于空容器，begin() 和 end() 返回相同的迭代器，表示容器中没有元素。这个迭代器也是有效的，但同样不允许解引用。

指针迭代器：对于像 std::array 或 std::vector 这样的容器，其迭代器实际上是 T* 类型的指针。在这种情况下，end() 返回的迭代器指向的是数组或缓冲区的末尾之后的第一个位置。这个位置通常不对应于实际的内存地址 nullptr。

自定义容器：对于自定义容器，end() 迭代器的实现可以不同，但通常也会遵循上述规则，返回一个特殊的迭代器，而不是 nullptr。

2.set的常用方法

在 C++ 中，std::set 是一种关联容器，它存储了唯一的元素，并且元素是有序的。以下是一些 std::set的常用用法：

初始化

#include <set>

std::set<int> mySet = {1, 2, 3, 4, 5};

// 使用初始化列表


std::set<int> anotherSet;

// 空集合

插入元素

mySet.insert(6); // 插入单个元素


mySet.insert({7, 8, 9});

// 插入多个元素

查找元素

auto it = mySet.find(3); // 查找元素3

if (it != mySet.end()) {
    std::cout << "Element found: " << *it << std::endl;
} else {
    std::cout << "Element not found." << std::endl;
}

删除元素

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


mySet.erase(it);

// 删除迭代器it指向的元素

访问元素

由于 std::set 是有序的，你可以使用迭代器访问元素：

for (const auto& element : mySet) {
    std::cout << element << " ";
}
std::cout << std::endl;

检查元素是否存在

if (mySet.count(3) > 0) {
    std::cout << "Element 3 exists." << std::endl;
} else {
    std::cout << "Element 3 does not exist." << std::endl;
}

获取集合的大小

size_t setSize = mySet.size();

检查集合是否为空

if (mySet.empty()) {
    std::cout << "The set is empty." << std::endl;
} else {
    std::cout << "The set is not empty." << std::endl;
}

获取集合的上下界

auto lowerBound = mySet.lower_bound(3); // 返回指向第一个不小于3的元素的迭代器auto upperBound = mySet.upper_bound(3); // 返回指向第一个大于3的元素的迭代器

清空集合

mySet.clear(); // 移除所有元素

使用自定义比较函数

#include <set>#include <functional>

std::set<int, std::greater<int>> mySet = {1, 2, 3, 4, 5};

// 使用自定义比较函数，降序排列

这些是 std::set 的基本用法。根据具体需求，你可能会使用更多高级特性，例如自定义比较函数或结合其他容器进行更复杂的数据操作。

cplusplus.com

https://cplusplus.com/reference/set/

3.multiset

（1）包含在set头文件下的一种特殊的set容器，与set不同的是，set是排序加去重复，但是multiset只有排序允许冗余，其他特性（迭代器，常用基础函数等）都与set相同，其中有一个count其实也不同了，不再是在set中的0或者1了，而是可以告诉我，这些数据里面有几个相同key

（2）还有就是其中的find（）函数找到的key不一定是第一个key（有相同key的情况下）是中序遍历下的第一个key

2.Map

在 C++ 中，std::map 是一种关联容器，它存储了键值对（key-value 对），其中每个键都是唯一的。std::map 内部使用红黑树实现，这意味着它能够自动根据键对元素进行排序。

以下是 std::map 的一些基本特性和基本用法

特点

键是唯一的，每个键只能对应一个值。

键和值可以是任意类型，但键类型必须支持比较操作（即必须定义了 < 运算符）。

元素根据键自动排序。

通常，插入和查找操作的时间复杂度为 O(log n)，其中 n 是元素的数量。

用法

💡

这里需要注意的还是find函数在找到指定的元素后返回的是该元素的迭代器

中的来说std::map 提供了一种高效的方式来管理键值对数据，特别是当你需要频繁地根据键来查找值时。由于它的元素是有序的，所以在需要有序数据集时也非常有用。

💡

1.这里查找[]使用operator[]能通过key来访问map中的元素

2.map中的迭代器存在两个it（代指迭代器变量），it→first,it→second分别指的是

key和value

3.Map在实际运用中的常用用法和用处

用法

键值存储：最基本的用法，用于存储键值对，其中键是唯一的，而值可以是重复的。

快速查找：由于 std::map 是基于红黑树实现的，它提供了对数时间复杂度的查找性能，非常适合需要频繁查找的场景。

有序集合：std::map 自动根据键对元素进行排序，适用于需要有序数据结构的场景。

范围查找：使用 std::map 的 lower_bound 和 upper_bound 方法可以快速找到指定键的范围。

自定义比较函数：通过传递自定义比较函数给 std::map，可以自定义元素的排序方式。

用途

字典：实现一个简单的字典，存储单词及其定义。

计数器：统计各种元素的频率，例如，统计一个文本中每个单词出现的次数。

索引构建：在数据库或搜索引擎中，用于构建索引，快速定位数据。

缓存：实现简单的缓存机制，使用键来快速访问缓存的数据。

配置管理：存储程序的配置项，键可以是配置的名称，值可以是配置的值。

映射关系：将一种类型的数据映射到另一种类型，例如，将用户ID映射到用户详细信息。

📎

作者留言和思考

暂无