• •  是一种按照元素插入顺序存储数据的容器。元素存储在连续或逻辑上连续的空间中，通过索引或迭代器可以顺序访问每个元素。
  • 常见的序列式容器包括数组、向量（vector）、列表（list）、双端队列（deque）等。
  • 元素按照插入顺序依次存储。例如，在 vector 中，元素存储在连续的内存空间中；在 list 中，元素通过指针或引用连接在一起。
  • 存储结构相对简单，主要关注元素的顺序和连续性。
• 关联式容器：
  • 是一种基于键值对存储数据的容器。每个元素由键（Key）和值（Value）组成，键是唯一的，通过键可以快速定位到对应的值。
  • 常见的关联式容器包括哈希表（unordered_map）、平衡二叉树（map）、集合（set）等。
  • 元素存储方式取决于具体的实现。例如：
    • map 和 set 通常基于平衡二叉树（如红黑树）实现，元素按照键的顺序存储。
    • unordered_map 和 unordered_set 基于哈希表实现，元素存储在哈希桶中，通过哈希函数快速定位。
  • 存储结构更复杂，但能通过键快速访问元素。

二.set

在这里插入图片描述

2.1set基本介绍

set的声明如下，T就是set底层关键字的类型

代码语言：javascript

AI代码解释

template < class T, // set::key_type/value_type

 class Compare = less<T>, // set::key_compare/value_compare

 class Alloc = allocator<T> // set::allocator_type

 > class set;

• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数

• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参 数。

• ⼀般情况下，我们都不需要传后两个模版参数。

• set底层是⽤红⿊树实现，增删查效率是O（logN） ，迭代器遍历是⾛的搜索树的中序，所以是有序的。

2.2set的构造和迭代器

在这里插入图片描述

代码语言：javascript

AI代码解释

// empty (1) ⽆参默认构造 

explicit set (const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造 

template <class InputIterator>
 set (InputIterator first, InputIterator last,
 const key_compare& comp = key_compare(),
 const allocator_type& = allocator_type());
 

// copy (3) 拷⻉构造 

set (const set& x);

// initializer list (5) initializer 列表构造 

set (initializer_list<value_type> il,
 const key_compare& comp = key_compare(),
 const allocator_type& alloc = allocator_type());

一、set 的构造函数

set 的构造函数有多种重载形式，用于创建不同类型的 set 容器。以下是常见的构造方式：

1. 默认构造

代码语言：javascript

AI代码解释

std::set<int> mySet;

• 创建一个空的 set，默认使用小于操作符（<）对元素进行排序。

2. 指定比较函数

代码语言：javascript

AI代码解释

std::set<int, std::greater<int>> mySet; // 使用大于操作符排序

• 可以通过自定义比较函数来改变元素的排序方式。例如，使用 std::greater 可以让元素按降序排列。

3. 从另一个容器初始化

代码语言：javascript

AI代码解释

std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::set<int> mySet(vec.begin(), vec.end());

• 使用一个范围（如另一个容器的迭代器范围）来初始化 set。重复的元素会被自动去除。

4. 使用初始化列表

代码语言：javascript

AI代码解释

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

• 使用花括号 {} 包裹的初始化列表来创建 set。同样，重复的元素会被自动去除。

5. 拷贝构造和移动构造

代码语言：javascript

AI代码解释

std::set<int> original = {1, 2, 3};
std::set<int> copy(original); // 拷贝构造
std::set<int> moved(std::move(original)); // 移动构造

• 拷贝构造会创建一个与原 set 完全相同的副本。
• 移动构造会将原 set 的内容移动到新 set 中，原 set 会变成空。

二、set 的迭代器

set 的迭代器用于遍历容器中的元素。由于 set 是基于平衡二叉树实现的，迭代器会按照元素的排序顺序访问元素。

代码语言：javascript

AI代码解释

// 迭代器是⼀个双向迭代器 
iterator -> a bidirectional iterator to const value_type

// 正向迭代器 
iterator begin();
iterator end();

// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

1. 获取迭代器

begin() 和 end()：分别返回指向第一个元素和最后一个元素之后位置的迭代器。

代码语言：javascript

AI代码解释

auto it = mySet.begin(); // 指向第一个元素
auto it_end = mySet.end(); // 指向最后一个元素之后的位置

2. 遍历 set

代码语言：javascript

AI代码解释

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

// 使用迭代器遍历
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

// 使用范围 for 循环
for (const auto& elem : mySet) {
    std::cout << elem << " ";
}
std::cout << std::endl;

• 迭代器支持递增操作（++），可以依次访问每个元素。
• 范围 for 循环是 C++11 引入的简化，语法可以直接遍历容器中的元素。