Container in Standard Libraries

阅读文章前，您需要了解入门的 C++ 语法规则，并最好拥有简单的数据结构知识

目录

---

Vector

功能

vector 是 C++ 标准库中最常用的动态数组容器，它提供了随机访问、自动扩展的能力。vector 能够在末尾插入和删除元素，并支持通过索引访问元素，因此非常适合需要高效随机访问和动态增加/删除元素的场景。

内部实现

• 内部数据结构：vector 通常使用一个动态数组（数组大小可以改变）来存储数据。数组的大小在初始化时会有一个默认值，通常是小的容量，当存储的元素超过当前容量时，vector 会自动分配一个更大的内存块，将原有元素复制到新的内存地址，然后继续插入新的元素。通常新的容量会是当前容量的两倍。

• 自动扩展机制：当 vector 容器的容量不足时，它会重新分配内存来适应更多的元素。这个过程是自动的，但是由于内存重新分配可能会导致性能上的开销，因此在有预期元素数量时，使用 reserve() 可以手动调整 vector 的容量，避免多次扩展。

• 内存分配：vector 内部的内存分配是连续的，允许高效的随机访问。但是由于内存的连续性，扩展时可能需要大量的内存复制操作，尤其在元素较多时。因此，频繁地插入/删除大量元素可能影响性能。

性能

• 时间复杂度：
  • push_back()：平均时间复杂度是 O(1)，但在需要扩展容量时，可能是 O(n)。
  • 随机访问（operator[] 和 at()）：O(1)。
  • 插入/删除（insert() 和 erase()）：平均 O(n)。
  • reserve()：平均 O(n)，当扩展容量时，可能需要 O(n) 时间。
• 内存：由于 vector 需要确保数据的连续性，所以扩展时可能需要重新分配内存，并将旧数据拷贝到新位置，这可能会产生性能开销。

声明

要使用 vector，你需要包含 <vector> 头文件。常见的声明方式如下：

#include <vector>

std::vector<int> vec1;           // 默认构造，创建一个空的 vector
std::vector<int> vec2(10);       // 创建一个包含 10 个默认值的 vector
std::vector<int> vec3(10, 5);    // 创建一个包含 10 个元素，值都为 5 的 vector
std::vector<int> vec4 = {1, 2, 3};  // 使用初始化列表创建

常用方法

构造函数

• vector(): 默认构造函数，创建一个空的 vector。
• vector(n): 创建一个包含 n 个元素的 vector，元素的初始值为默认值。
• vector(n, value): 创建一个包含 n 个元素的 vector，所有元素的值为 value。
• vector(begin, end): 使用一个区间来初始化 vector，区间由两个迭代器（begin 和 end）指定。

插入与删除

• push_back(value): 在 vector 的末尾插入一个元素。
• pop_back(): 删除 vector 末尾的元素。
• insert(position, value): 在指定位置插入一个元素。
• erase(position): 删除指定位置的元素，后面的元素会自动向前移动来填补删除的空缺，相应地，size 减小 1，但是 capacity 不变化。
• clear(): 清空所有元素，但不释放内存。

访问元素

• operator[]: 使用索引访问元素，不做边界检查。

• at(index): 使用索引访问元素，提供边界检查（如果索引越界会抛出 std::out_of_range 异常）。

• front(): 返回 vector 中第一个元素。
• back(): 返回 vector 中最后一个元素。

[!TIP]

vector 类通过重载 [] 操作符来实现通过索引访问元素的功能。重载后的 operator[] 允许用户像访问普通数组一样，通过索引直接访问 vector 中的元素。

vector 的索引范围是从 0 到 size() - 1 即有效索引范围是 [0,n−1]，与普通数组一致

容量与大小

• size(): 返回 vector 中当前元素的数量。
• capacity(): 返回 vector 当前的容量，即它可以容纳的最大元素数量。
• empty(): 判断 vector 是否为空（size() == 0），返回一个布尔值，在容器为空时返回 true。
• reserve(n): 设置 vector 的容量为 n，如果当前容量小于 n，则分配更多的内存。注意，reserve() 只改变容量，而不改变 vector 的大小。
• shrink_to_fit(): 请求将 vector 的容量调整为它当前大小，以减少内存使用。

迭代器

• begin(): 返回指向第一个元素的迭代器。
• end(): 返回指向最后一个元素后面位置的迭代器。
• rbegin(): 返回指向最后一个元素的反向迭代器。
• rend(): 返回指向第一个元素之前位置的反向迭代器。

[!NOTE]

迭代器（Iterator）是什么？

迭代器（Iterator）通常是由容器（如 vector、list、map 等）定义的一个嵌套类，或者是一个在容器类外部定义的类型（通常是模板类）。它实现了指向容器元素的访问方法，并支持诸如前进、后退、解引用等操作。用于遍历容器（如 vector、list、map 等）中的元素。它提供了一种通用的方式来访问容器中的元素，而无需关心容器的具体实现（如数组、链表等）。

迭代器通常支持以下基本操作：

• 访问元素：通过迭代器可以访问容器中的元素。
• 前进/后退：通过迭代器可以在容器中进行遍历（前进和后退）。
• 比较操作：可以比较两个迭代器，判断它们是否指向相同的元素或容器的开始/结束位置。

迭代器的基本操作

常见的迭代器操作包括：

• begin()：返回指向容器第一个元素的迭代器。
• end()：返回指向容器最后一个元素后一个位置的迭代器（即“尾后”迭代器）。
• ++：使迭代器指向下一个元素。
• --：使迭代器指向前一个元素（双向迭代器及随机访问迭代器支持）。
• *：解引用迭代器，返回迭代器当前指向的元素。
• !=：比较两个迭代器是否指向不同的位置。
• ==：比较两个迭代器是否指向相同的位置。

迭代器的类型

C++ 标准库中定义了多种类型的迭代器，不同类型的容器可能支持不同类型的迭代器。常见的迭代器类型有：

• 输入迭代器（Input Iterator）：只允许读取数据，支持前进操作。

  #include <iostream>
  #include <vector>
  
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      
      // 输入迭代器声明
      std::vector<int>::iterator it = vec.begin();  // 可以读取数据
      std::vector<int>::const_iterator cit = vec.begin();  // 只能读取，不可修改
      
      // 使用输入迭代器遍历
      while (it != vec.end()) {
          std::cout << *it << " ";  // 读取数据
          ++it;  // 前进操作
      }
  
      std::cout << std::endl;
  
      return 0;
  }

• 输出迭代器（Output Iterator）：只允许写入数据，支持前进操作。

  #include <iostream>
  #include <vector>
  
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      
      // 输出迭代器声明（可写入数据）
      std::vector<int>::iterator it = vec.begin();
      
      // 使用输出迭代器写入数据
      while (it != vec.end()) {
          *it = *it * 2;  // 修改数据
          ++it;  // 前进操作
      }
  
      // 输出修改后的数据
      for (const auto& elem : vec) {
          std::cout << elem << " ";
      }
  
      std::cout << std::endl;
  
      return 0;
  }

• 前向迭代器（Forward Iterator）：支持读取和写入数据，可以前进多次（即可以 it + n 直接跳跃）。

  #include <iostream>
  #include <vector>
  
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      
      // 前向迭代器声明
      std::vector<int>::iterator it = vec.begin();
      
      // 使用前向迭代器读取和修改数据
      while (it != vec.end()) {
          *it = *it + 1;  // 修改数据
          ++it;  // 前进操作
      }
  
      // 输出修改后的数据
      for (const auto& elem : vec) {
          std::cout << elem << " ";
      }
  
      std::cout << std::endl;
  
      return 0;
  }

• 双向迭代器（Bidirectional Iterator）：支持前进和后退操作。

  #include <iostream>
  #include <vector>
  
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      
      // 双向迭代器声明
      std::vector<int>::iterator it = vec.begin();
      
      // 正向遍历
      while (it != vec.end()) {
          std::cout << *it << " ";  // 读取数据
          ++it;  // 前进操作
      }
  
      std::cout << std::endl;
  
      // 反向遍历
      std::vector<int>::reverse_iterator rit = vec.rbegin();
      while (rit != vec.rend()) {
          std::cout << *rit << " ";  // 读取数据
          ++rit;  // 前进操作
      }
  
      std::cout << std::endl;
  
      return 0;
  }

• 随机访问迭代器（Random Access Iterator）：支持前进、后退、跳跃等任意位置的访问（如 vector、deque 等支持的迭代器）。

  #include <iostream>
  #include <vector>
            
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
                
      // 随机访问迭代器声明
      std::vector<int>::iterator it = vec.begin();
                
      // 使用随机访问迭代器进行跳跃访问
      it += 2;  // 跳到第 3 个元素
      std::cout << *it << std::endl;  // 输出：3
            
      // 前进操作
      it++;  // 指向第 4 个元素
      std::cout << *it << std::endl;  // 输出：4
                
      // 后退操作
      it--;  // 指向第 3 个元素
      std::cout << *it << std::endl;  // 输出：3
                
      return 0;
  }

示例

#include <iostream>
#include <vector>

int main() {
    // 创建一个空的 vector
    std::vector<int> vec;

    // 在末尾添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 输出所有元素
    for (int i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";  // 使用 operator[] 访问元素
    }
    std::cout << std::endl;
  
    // 使用基于范围的 for 循环遍历 vector
    for (int value : myVector) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

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

    // 删除末尾元素
    vec.pop_back();

    // 使用 at() 方法访问元素并检查边界
    try {
        std::cout << "Element at index 2: " << vec.at(2) << std::endl;  // 如果越界，会抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "Out of range: " << e.what() << std::endl;
    }

    return 0;
}

[!NOTE]

这段代码中使用了基于范围的 for 循环（range-based for loop）

// 使用基于范围的 for 循环遍历 vector
for (int value : myVector) {
    std::cout << value << " ";
}
std::cout << std::endl;

// 还可以更简单
for (auto value : myVector) {
    std::cout << value << " ";
}
std::cout << std::endl;

表示对容器 myVector 中的每一个元素进行迭代。value 会依次被赋予 myVector 中的每个元素的值。

对 vector, list, deque 等容器均支持此用法。

---

List

功能

list 是 C++ 标准库中的一个双向链表容器，它提供了快速的插入和删除操作（尤其是在容器的任意位置）。list 的元素不是连续存储的，因此不支持随机访问，但是它在频繁的插入和删除操作上比 vector 更加高效。

内部实现

• 内部数据结构：list 使用双向链表作为内部数据结构。每个节点包含两个部分：

  • 一个数据部分（存储实际的元素值）

  • 两个指针，分别指向前一个节点和后一个节点

    通过这些指针，list 能够在 O(1) 时间复杂度内在任意位置插入和删除元素。

• 内存分配：由于每个元素存储在独立的节点中，list 的元素不是存储在连续的内存块中，因此相比于 vector 来说，它的内存访问效率较低。每次访问元素时，都需要通过指针跳转。

• 访问性能：list 不支持通过索引直接访问元素，因此无法像 vector 一样使用 operator[] 进行随机访问。只能通过迭代器遍历。

• 优点：在频繁进行插入和删除操作时，list 的效率要远高于 vector，特别是在容器两端和中间位置的插入/删除操作。

性能

• 时间复杂度：

  • push_back() 和 push_front()：O(1)
  • pop_back() 和 pop_front()：O(1)
  • 插入/删除操作（insert() 和 erase()）：O(1)（如果已经获得了目标位置的迭代器）
  • 排序（sort()）：O(nlogn)
  • 合并（merge()）：O(n+m)，其中 n 是当前 list 的元素数量，m 是合并的 list 的元素数量

[!NOTE]

merge 方法要求两个 list 容器已经是 有序的，并将它们合并成一个新的有序链表。这种操作本质上是对两个有序链表的 归并（merge）过程，也就是每次从两个有序链表中选择较小的元素，插入到合并后的链表中，这就需要遍历两个链表一遍。

不过 list 并不会像堆一样在插入元素时自动保持顺序，除非显式地调用一些操作来保持顺序。

显式调用 sort 时，默认按照升序排序。

所以在调用 merge 之前需要先两个 list 进行排序。当然，如果不排序，它不会报错，只是仍然按照上述操作归并之后无法得到正确的升序结果。

• 内存：由于 list 的元素是存储在单独的节点中，并且每个节点都有两个指针，所以每个元素都会占用比 vector 更多的内存空间。每次插入和删除操作的开销相对较小，因为不需要移动其他元素。

• 适用场景：

  • list 特别适合需要频繁在容器两端或中间位置进行插入和删除操作的场景。比如实现队列、双端队列等数据结构时，list 是一个非常高效的选择。
  • 但是，list 不适合需要高效随机访问的场景，因为它不支持索引访问元素，且访问某个元素需要遍历链表。

声明

要使用 list，你需要包含 <list> 头文件。常见的声明方式如下：

#include <list>

std::list<int> list1;               // 默认构造，创建一个空的 list
std::list<int> list2(10);           // 创建一个包含 10 个默认值的 list
std::list<int> list3(10, 5);        // 创建一个包含 10 个元素，值为 5 的 list
std::list<int> list4 = {1, 2, 3};   // 使用初始化列表创建

常用方法

构造函数

• list(): 默认构造函数，创建一个空的 list。
• list(n): 创建一个包含 n 个元素的 list，元素的初始值为默认值。
• list(n, value): 创建一个包含 n 个元素的 list，所有元素的值为 value。
• list(begin, end): 使用一个区间来初始化 list，区间由两个迭代器（begin 和 end）指定。

插入与删除

• push_back(value): 在 list 的末尾插入一个元素。

• push_front(value): 在 list 的前面插入一个元素。

• pop_back(): 删除 list 末尾的元素。

• pop_front(): 删除 list 开头的元素。

• insert(position, value): 在指定位置的前面插入一个元素，position 是一个迭代器。

  std::list<int> mylist = {10, 20, 30, 40};
  auto it = mylist.begin();  // 获取第一个元素的位置
  std::advance(it, 2);        // 将迭代器移动到指向第三个元素（30）
  mylist.insert(it, 15);     // 结果变为 {10, 20, 15, 30, 40}

• erase(position): 删除指定位置的元素。

• erase(first, last): 删除从 first 到 last 之间的所有元素。

  first 和 last 都是指向容器内元素的迭代器。

  删除操作包括 first 位置的元素，但 不包括 last 位置的元素。

• clear(): 清空所有元素。

访问元素

• front(): 返回 list 中第一个元素。
• back(): 返回 list 中最后一个元素。

容量与大小

• size(): 返回 list 中当前元素的数量。
• empty(): 判断 list 是否为空（size() == 0）。
• resize(n): 调整 list 的大小，若 n 小于当前大小，则删去尾部多余元素；若 n 大于当前大小，则在尾部插入元素，默认值为元素类型的默认值。

迭代器

• begin(): 返回指向第一个元素的迭代器。
• end(): 返回指向最后一个元素后面位置的迭代器。
• rbegin(): 返回指向最后一个元素的反向迭代器。
• rend(): 返回指向第一个元素之前位置的反向迭代器。

合并与排序

• merge(other): 合并另一个 list 到当前 list，需要两个 list 已经是有序的。
• sort(): 对 list 中的元素进行排序。
• reverse(): 反转 list 中的元素顺序。

示例

#include <iostream>
#include <list>

int main() {
    // 创建一个包含 5 个元素的 list
    std::list<int> mylist = {1, 2, 3, 4, 5};

    // 插入元素
    mylist.push_back(6);  // 末尾插入
    mylist.push_front(0); // 头部插入

    // 输出所有元素
    std::cout << "List contents: ";
    for (int value : mylist) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 删除元素
    mylist.pop_back();    // 删除末尾元素
    mylist.pop_front();   // 删除头部元素

    std::cout << "After pop operations: ";
    for (int value : mylist) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 使用迭代器访问
    std::cout << "Using iterator: ";
    for (auto it = mylist.begin(); it != mylist.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 排序
    mylist.sort();
    std::cout << "After sort: ";
    for (int value : mylist) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 反转
    mylist.reverse();
    std::cout << "After reverse: ";
    for (int value : mylist) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

---

Deque

功能

deque 是 C++ 标准库中的一个双端队列容器，提供了在两端进行快速插入和删除操作。与 vector 相比，deque 具有更灵活的操作方式，支持在队列的两端（前端和后端）高效地进行插入和删除。

内部实现

• 内部数据结构：deque 的内部实现通常采用多个固定大小的数组块来存储元素。它不像 vector 那样使用单一的连续内存块，而是将数据分散在多个内存块中。这些内存块通过指针连接，形成一个二维结构。

• 内存管理：这种分散的内存块使得 deque 可以高效地在两端进行扩展，不会像 vector 一样在扩展时需要移动大量元素。相对于 list，deque 也支持快速的随机访问，但它的内存管理要复杂一些。

• 插入与删除：deque 提供常数时间复杂度 O(1) 的操作来在两端插入或删除元素（前端和后端），但是对于中间的插入和删除，其时间复杂度仍然是 O(n)，与 vector 类似。

• 访问性能：与 vector 类似，deque 支持随机访问，能够通过索引快速访问任意元素，且时间复杂度是 O(1)。

性能

• 时间复杂度：

  • push_back() 和 push_front()：O(1)
  • pop_back() 和 pop_front()：O(1)
  • 随机访问（operator[] 和 at()）：O(1)
  • 插入/删除操作（insert() 和 erase()）：O(n)，在插入/删除时，如果位置在两端，复杂度为 O(1)，但如果在中间，复杂度为 O(n)。

• 内存管理：deque 使用分散的内存块，具有比 vector 更灵活的内存扩展机制，但仍然能提供较快的访问和高效的两端操作。

• 适用场景：

  • deque 非常适合用在需要频繁在两端进行插入和删除操作的场景。例如实现队列、双端队列等数据结构。
  • 它比 vector 更适用于两端的插入/删除操作，但相较于 vector，其随机访问速度略慢。

声明

要使用 deque，你需要包含 <deque> 头文件。常见的声明方式如下：

#include <deque>

std::deque<int> deque1;               // 默认构造，创建一个空的 deque
std::deque<int> deque2(10);           // 创建一个包含 10 个默认值的 deque
std::deque<int> deque3(10, 5);        // 创建一个包含 10 个元素，值为 5 的 deque
std::deque<int> deque4 = {1, 2, 3};   // 使用初始化列表创建

常用方法

构造函数

• deque(): 默认构造函数，创建一个空的 deque。
• deque(n): 创建一个包含 n 个元素的 deque，元素的初始值为默认值。
• deque(n, value): 创建一个包含 n 个元素的 deque，所有元素的值为 value。
• deque(begin, end): 使用一个区间来初始化 deque，区间由两个迭代器（begin 和 end）指定。

插入与删除

• push_back(value): 在 deque 的末尾插入一个元素。
• push_front(value): 在 deque 的前面插入一个元素。
• pop_back(): 删除 deque 末尾的元素。
• pop_front(): 删除 deque 开头的元素。
• insert(position, value): 在指定位置插入一个元素。
• erase(position): 删除指定位置的元素。
• erase(first, last): 删除从 first 到 last 之间的所有元素。
• clear(): 清空所有元素。

[!NOTE]

这里的用法和上面相同

访问元素

• operator[]: 使用索引访问元素，不做边界检查。
• at(index): 使用索引访问元素，提供边界检查（如果索引越界会抛出 std::out_of_range 异常）。
• front(): 返回 deque 中第一个元素。
• back(): 返回 deque 中最后一个元素。

容量与大小

• size(): 返回 deque 中当前元素的数量。
• empty(): 判断 deque 是否为空（size() == 0）。
• resize(n): 调整 deque 的大小，若 n 小于当前大小，则删去尾部多余元素；若 n 大于当前大小，则在尾部插入元素，默认值为元素类型的默认值。
• reserve(n): deque 不支持 reserve()，它的容量管理是自动的。

迭代器

• begin(): 返回指向第一个元素的迭代器。
• end(): 返回指向最后一个元素后面位置的迭代器。
• rbegin(): 返回指向最后一个元素的反向迭代器。
• rend(): 返回指向第一个元素之前位置的反向迭代器。

示例

#include <iostream>
#include <deque>

int main() {
    // 创建一个包含 5 个元素的 deque
    std::deque<int> mydeque = {1, 2, 3, 4, 5};

    // 插入元素
    mydeque.push_back(6);    // 末尾插入
    mydeque.push_front(0);   // 头部插入

    // 输出所有元素
    std::cout << "Deque contents: ";
    for (int value : mydeque) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 删除元素
    mydeque.pop_back();      // 删除末尾元素
    mydeque.pop_front();     // 删除头部元素

    std::cout << "After pop operations: ";
    for (int value : mydeque) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 使用迭代器访问
    std::cout << "Using iterator: ";
    for (auto it = mydeque.begin(); it != mydeque.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用 at() 方法进行访问
    try {
        std::cout << "Element at index 2: " << mydeque.at(2) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Out of range: " << e.what() << std::endl;
    }

    return 0;
}

---

Stack

功能

stack 是 C++ 标准库中的一个容器适配器，它实现了一个后进先出（LIFO，Last In First Out）数据结构。stack 是基于其他容器（如 deque 或 list）实现的，但它只提供了有限的操作。stack 类非常适合用于处理需要倒序处理数据的场景，例如括号匹配、深度优先搜索等。

主要特点：

• 后进先出（LIFO）：即最后插入的元素最先被访问或删除。
• 封装：stack 不允许用户直接访问底层元素，只能通过提供的接口进行操作。

注意：

• stack 并不提供随机访问功能，因此无法直接访问栈中的任意元素。如果你需要访问栈中的非栈顶元素，可能需要在栈内部分离出一个副本或使用底层容器提供的操作。

• 栈的主要用途是遵循 LIFO 原则，在编程中非常适合做一些递归算法的迭代模拟（如深度优先搜索）或是括号匹配等问题。

内部实现

stack 是一个容器适配器，意味着它是基于某个底层容器实现的。标准库中的 stack 默认使用 deque 作为底层容器，但也可以选择使用其他容器，如 vector 或 list。

• 底层容器：stack 类的底层容器（如 deque）负责实际存储数据。对于 stack 类而言，用户并不直接与底层容器交互，而是通过栈的接口进行操作。
• 栈的操作：stack 只允许在栈顶进行插入和删除操作，因此其内部并不暴露底层容器的随机访问能力。这样可以确保数据只能从栈顶操作，遵循后进先出的原则。

性能

• 时间复杂度：

  • push() 和 pop()：平均时间复杂度是 O(1)，即操作在栈顶进行，不需要遍历所有元素。
  • top()：O(1)，直接访问栈顶元素。
  • empty() 和 size()：O(1)，直接返回栈的状态或大小。
• 内存：由于 stack 是容器适配器，它不负责内存分配和释放，内存管理是由底层容器（如 deque）来负责的。因此，栈的内存管理性能与底层容器的实现有关。如果不指定，stack 默认会使用 std::deque 作为底层容器。

声明

要使用 stack，你需要包含 <stack> 头文件。常见的声明方式如下：

#include <stack>

std::stack<int> s1;          // 默认构造，创建一个空的栈
std::stack<int> s2({1, 2, 3});  // 使用初始化列表创建

[!NOTE]

对于 {1, 2, 3}，假设这些元素是按顺序依次被 插入 的（即 push(1), push(2), push(3)），那么：

栈底 -> [1] [2] [2] <- 栈顶

也就是一个列表被用来初始化 stack 的时候，默认索引 0 为栈底？

你也可以通过指定底层容器来构造 stack：

#include <stack>
#include <deque>

std::stack<int, std::deque<int>> s1;   // 指定底层容器为 deque
std::stack<int, std::vector<int>> s2;  // 指定底层容器为 vector

常用方法

构造函数

• stack(): 默认构造函数，创建一个空的 stack。
• stack(container): 使用指定的底层容器来初始化栈。

插入与删除

• push(value): 向栈顶插入元素 value。
• pop(): 删除栈顶元素，但不会返回该元素，通常在调用 pop() 后会访问栈顶的元素（通常会使用 top() 来查看）。

访问元素

• top(): 返回栈顶元素的引用，允许访问栈顶元素。若栈为空，调用此方法会导致未定义行为。

容量与大小

• empty(): 判断栈是否为空，若栈为空返回 true，否则返回 false。
• size(): 返回栈中元素的数量。

示例

#include <iostream>
#include <stack>

int main() {
    // 创建一个空栈
    std::stack<int> s;

    // 向栈中添加元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 输出栈顶元素
    std::cout << "Top element: " << s.top() << std::endl;  // 输出 30

    // 删除栈顶元素
    s.pop();

    // 再次输出栈顶元素
    std::cout << "Top element after pop: " << s.top() << std::endl;  // 输出 20

    // 判断栈是否为空
    if (!s.empty()) {
        std::cout << "The stack is not empty." << std::endl;
    }

    // 输出栈的大小
    std::cout << "Stack size: " << s.size() << std::endl;

    return 0;
}

---

Queue

功能

queue 是 C++ 标准库中的一个容器适配器，它实现了一个先进先出（FIFO，First In First Out）数据结构。queue 提供了在队列的两端进行插入和删除操作，符合队列的基本特性：第一个插入的元素最先被访问或删除。

• 先进先出（FIFO）：即最早插入的元素会最早被移除。
• 容器适配器：queue 本身并不直接存储数据，它是基于其他容器（如 deque 或 list）实现的，只提供队列相关的操作接口。
• 队列的操作：queue 只允许在队列的两端进行插入和删除操作。具体来说，数据总是从队列尾部插入，从队列头部删除。

注意：

• 和 stack 一样，queue 类并不提供随机访问功能，因此无法直接访问队列中的任意元素。如果你需要访问队列中的非队头元素，可能需要在队列内部分离出一个副本或使用底层容器提供的操作。

内部实现

queue 是一个容器适配器，和 stack 一样，它是基于某个底层容器实现的。标准库中的 queue 默认使用 deque 作为底层容器，但你也可以指定使用其他容器（如 list）。

性能

• 时间复杂度：

  • push() 和 pop()：平均时间复杂度是 O(1)，即操作在队列的两端进行，不需要遍历所有元素。
  • front() 和 back()：O(1)，直接访问队列头尾元素。
  • empty() 和 size()：O(1)，直接返回队列的状态或大小。
• 内存：由于 queue 是容器适配器，它不负责内存分配和释放，内存管理是由底层容器（如 deque）来负责的。因此，队列的内存管理性能与底层容器的实现有关。

声明

要使用 queue，你需要包含 <queue> 头文件。常见的声明方式如下：

#include <queue>

std::queue<int> q1;             // 默认构造，创建一个空的队列
std::queue<int> q2({1, 2, 3});  // 使用初始化列表创建

[!NOTE]

列表被传入用于初始化 queue 时，默认索引 0 处为队头

#include <iostream>
#include <queue>

int main() {
    // 初始化队列，队列元素为 {1, 2, 3}
    std::queue<int> q({1, 2, 3});

    // 输出队头和队尾元素
    std::cout << "Front: " << q.front() << std::endl; // 输出 1
    std::cout << "Back: " << q.back() << std::endl;   // 输出 3

    return 0;
}

你也可以通过指定底层容器来构造 queue：

#include <queue>
#include <deque>

std::queue<int, std::deque<int>> q1;   // 指定底层容器为 deque
std::queue<int, std::list<int>> q2;    // 指定底层容器为 list

常用方法

构造函数

• queue(): 默认构造函数，创建一个空的 queue。
• queue(container): 使用指定的底层容器来初始化队列。

插入与删除

• push(value): 向队列尾部插入元素 value。
• pop(): 删除队列头部的元素，但不会返回该元素。

访问元素

• front(): 返回队列头部元素的引用，允许访问队列的第一个元素。
• back(): 返回队列尾部元素的引用，允许访问队列的最后一个元素。

容量与大小

• empty(): 判断队列是否为空，若队列为空返回 true，否则返回 false。
• size(): 返回队列中元素的数量。

示例

#include <iostream>
#include <queue>

int main() {
    // 创建一个空的队列
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 输出队列头部元素
    std::cout << "Front element: " << q.front() << std::endl;  // 输出 10

    // 输出队列尾部元素
    std::cout << "Back element: " << q.back() << std::endl;  // 输出 30

    // 删除队列头部元素
    q.pop();

    // 输出新的队列头部元素
    std::cout << "Front element after pop: " << q.front() << std::endl;  // 输出 20

    // 判断队列是否为空
    if (!q.empty()) {
        std::cout << "The queue is not empty." << std::endl;
    }

    // 输出队列的大小
    std::cout << "Queue size: " << q.size() << std::endl;

    return 0;
}

---

Priority Queue

功能

priority_queue 是 C++ 标准库中的一个容器适配器，用于实现优先队列。与 queue 不同，priority_queue 中的元素总是按照优先级排序，优先级高的元素总是被优先取出。它并不是一个简单的队列，而是根据元素的优先级自动进行排序，确保每次取出的元素是优先级最高的。

主要特点：

• 优先级：priority_queue 中的元素按照优先级自动排序，默认情况下是大根堆（最大优先级最先被取出）。
• 容器适配器：priority_queue 是一个容器适配器，底层实现可以使用其他容器（如 vector 或 deque），但默认使用堆（heap）结构。
• 堆排序：priority_queue 使用堆来维护元素的顺序，从而实现优先级的快速访问。

注意：

• priority_queue 只能访问堆顶元素，无法直接访问其他元素。它不提供遍历整个优先队列的功能。如果需要访问所有元素，通常需要将元素取出并暂时存储在其他容器中。

• priority_queue 的元素默认是按照优先级排序的，默认情况下使用大根堆（最大值优先）。如果你想改变排序方式（例如使用小根堆），可以使用自定义的比较器（如 std::greater）。

内部实现

priority_queue 类默认使用堆（heap）来存储数据，基于二叉树实现，分为两种类型：

• 大根堆（Max Heap）：父节点的值大于或等于子节点的值。
• 小根堆（Min Heap）：父节点的值小于或等于子节点的值。

C++ 标准库中的 priority_queue 默认实现的是大根堆，这意味着优先级队列中，值最大的元素会最先被取出。

• 底层容器：priority_queue 默认使用 vector 作为底层容器，也可以指定其他容器（如 deque）。
• 堆结构：priority_queue 实现了一个堆结构，通过堆的性质来保证插入和删除操作的效率。插入和删除操作的时间复杂度是 O(log n)，其中 n 是当前元素的数量。

性能

• 时间复杂度：

  • push()：O(log n)，将新元素插入堆中，堆需要调整结构保持顺序。
  • pop()：O(log n)，删除堆顶元素后，堆需要重新调整结构。
  • top()：O(1)，直接访问堆顶元素。
  • size() 和 empty()：O(1)，直接返回队列的大小或判断是否为空。
• 内存：priority_queue 使用堆来存储元素，底层容器（如 vector）会负责内存管理。由于堆是完全二叉树，因此内存结构较为紧凑，不会有浪费。

声明

要使用 priority_queue，你需要包含 <queue> 头文件。常见的声明方式如下：

#include <queue>

std::priority_queue<int> pq1;  // 默认使用大根堆（Max Heap）
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;  // 小根堆（Min Heap）

• 第一个模板参数：表示存储在队列中的元素类型。
• 第二个模板参数：表示底层容器，默认是 std::vector。
• 第三个模板参数：表示排序方式，默认使用 std::less<T>（大根堆）。如果想使用小根堆，可以使用 std::greater<T>。

常用方法

构造函数

• priority_queue()：默认构造函数，创建一个空的优先队列，使用大根堆（Max Heap）。
• priority_queue(container)：使用指定的容器来初始化队列，通常容器是 vector 或 deque。
• priority_queue(container, comparator)：使用指定的容器和排序规则（如 std::greater）来初始化队列。

插入与删除

• push(value)：将元素 value 插入到队列中，插入后会自动根据优先级进行排序。
• pop()：删除优先队列中优先级最高的元素，即队列头部的元素。

访问元素

• top()：返回优先队列中优先级最高的元素的引用，允许访问优先队列的头部元素。

容量与大小

• empty()：判断优先队列是否为空，若为空返回 true，否则返回 false。
• size()：返回优先队列中元素的数量。

示例

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 创建一个大根堆（默认 priority_queue）
    std::priority_queue<int> pq;

    // 向优先队列中添加元素
    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(15);

    // 输出并删除优先队列中的元素
    while (!pq.empty()) {
        std::cout << "Top element: " << pq.top() << std::endl;  // 输出当前最大元素
        pq.pop();  // 删除优先级最高的元素
    }

    // 创建一个小根堆（Min Heap）
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

    // 向小根堆中添加元素
    min_pq.push(10);
    min_pq.push(20);
    min_pq.push(5);
    min_pq.push(15);

    // 输出并删除小根堆中的元素
    while (!min_pq.empty()) {
        std::cout << "Top element (Min Heap): " << min_pq.top() << std::endl;  // 输出当前最小元素
        min_pq.pop();  // 删除优先级最低的元素
    }

    return 0;
}

---

Set

功能

set 是 C++ 标准库中的一个关联容器，它存储一组唯一的元素，并且这些元素是按照特定的顺序排列的。set 内部使用红黑树（red-black tree）实现，因此可以提供高效的查找、插入和删除操作。

• 唯一性：set 中的元素是唯一的，不能有重复元素。尝试插入重复的元素时，插入操作会被忽略。
• 自动排序：set 会自动对元素进行排序，默认情况下是按升序排列，也可以通过自定义比较函数来改变排序方式。

内部实现

set 是基于红黑树实现的。红黑树是一种自平衡的二叉查找树，它保证了树的高度在最坏情况下始终是对数级别的，从而确保了插入、删除和查找操作的 O(logn) 时间复杂度。

• 排序顺序：set 会根据元素的值来排序，默认使用 < 运算符。你可以自定义排序规则，使用自定义的比较函数（例如 std::greater<T>）。

性能

• 时间复杂度：

  • insert()、erase()、find()：O(logn)，其中 n 是当前 set 中的元素数量。
  • lower_bound() 和 upper_bound()：O(logn)，通过红黑树的性质，查找操作的时间复杂度都是对数级别的。
• 内存：set 的内存使用与红黑树结构的大小相关。红黑树的高度为 O(logn)，因此其内存结构是比较紧凑的。

声明

要使用 set，你需要包含 <set> 头文件。常见的声明方式如下：

#include <set>

std::set<int> s1;  // 默认构造一个空的 set，按升序排列
std::set<int, std::greater<int>> s2;  // 使用降序排列的 set

你也可以使用初始化列表来创建 set：

std::set<int> s = {10, 20, 30};

常用方法

构造函数

• set()：默认构造函数，创建一个空的 set，默认按升序排列。
• set(begin, end)：使用给定范围的元素来初始化 set，并按照默认排序规则进行排序。
• set(container)：使用指定容器中的元素来初始化 set，并按照默认排序规则进行排序。

插入与删除

• insert(value)：插入一个元素 value，如果元素已存在，则插入失败（不插入重复元素）。
• erase(value)：删除指定的元素 value，如果元素不存在，什么也不做。
• erase(iterator)：删除指定迭代器指向的元素。
• clear()：清空 set 中的所有元素。

查找操作

• find(value)：返回指向元素 value 的迭代器，如果元素不存在，则返回 end() 迭代器。
• count(value)：返回元素 value 在 set 中的个数（由于 set 中不允许重复元素，所以返回值只能是 0 或 1）。
• lower_bound(value)：返回一个指向第一个不小于 value 的元素的迭代器。
• upper_bound(value)：返回一个指向第一个大于 value 的元素的迭代器。

容量与大小

• empty()：判断 set 是否为空，若为空返回 true，否则返回 false。
• size()：返回 set 中元素的数量。

遍历操作

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

示例

#include <iostream>
#include <set>

int main() {
    // 创建一个空的 set，按升序排列
    std::set<int> s;

    // 插入元素
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(20);  // 重复元素不会被插入

    // 输出 set 中的元素
    std::cout << "Elements in the set: ";
    for (const int& num : s) {
        std::cout << num << " ";  // 输出 10 20 30
    }
    std::cout << std::endl;

    // 查找元素
    if (s.find(20) != s.end()) {
        std::cout << "Found 20 in the set." << std::endl;
    } else {
        std::cout << "20 not found." << std::endl;
    }

    // 删除元素
    s.erase(20);
    std::cout << "After erasing 20, elements: ";
    for (const int& num : s) {
        std::cout << num << " ";  // 输出 10 30
    }
    std::cout << std::endl;

    // 使用 lower_bound 和 upper_bound
    auto it = s.lower_bound(15);
    if (it != s.end()) {
        std::cout << "The first element >= 15 is: " << *it << std::endl;  // 输出 20
    }

    return 0;
}

---

Map

功能

map 是 C++ 标准库中的一种关联容器，它存储的是键值对（key-value pairs）。与 set 类似，map 中的元素是有序的，但与 set 不同的是，map 中的每个元素包含一个键和一个值，并且键是唯一的。

map 内部会根据键的值来排序，默认情况下，map 按照升序排列键，值可以是任意类型，可以是基础数据类型、结构体、类等。

主要特点：

• 键的唯一性：与 set 类似，map 中的键是唯一的，如果你尝试插入一个已经存在的键，它的值会被更新或插入失败（取决于操作）。
• 自动排序：map 会按照键值的顺序（默认是升序）排列元素。
• 排序：map 根据键的大小进行排序，默认是升序。如果你希望按照降序排列，可以通过提供自定义比较函数（例如 std::greater<T>）来实现。

内部实现

map 的底层实现通常使用红黑树（red-black tree）

性能

• 时间复杂度：

  • insert()、erase()、find()：O(logn)，其中 n 是当前 map 中的元素数量。
  • operator[]：如果键存在，时间复杂度是 O(logn)，如果键不存在，operator[] 会插入一个默认值，并且时间复杂度为 O(logn)。
• 内存：map 使用红黑树作为底层数据结构，内存消耗相对较高，但能保证高效的查找、插入和删除。

声明

要使用 map，你需要包含 <map> 头文件。常见的声明方式如下：

#include <map>

std::map<int, std::string> m1;  // 默认按升序排列键，值为 string
std::map<int, std::string, std::greater<int>> m2;  // 按降序排列键

• 第一个模板参数：表示存储在 map 中的键的类型。
• 第二个模板参数：表示存储在 map 中的值的类型。
• 第三个模板参数：表示比较键的方式，默认使用 std::less<T>（升序排序）。如果需要按降序排列，可以使用 std::greater<T>。

常用方法

构造函数

• map()：默认构造函数，创建一个空的 map，默认按升序排列键。

• map(begin, end)：用指定范围的元素初始化 map。

  // 创建一个 vector，包含键值对
  std::vector<std::pair<int, std::string>> vec = {{1, "One"}, {2, "Two"}, {3, "Three"}};
  
  // 使用 vector 的范围初始化 map
  std::map<int, std::string> m(vec.begin(), vec.end());

• map(container)：使用指定容器中的元素初始化 map。

  // 创建一个 vector，包含键值对
  std::vector<std::pair<int, std::string>> vec = {{3, "Three"}, {1, "One"}, {2, "Two"}};
  
  // 使用 vector 容器直接初始化 map
  std::map<int, std::string> m(vec);

[!NOTE]

std::pair 是一个包含两个成员的结构体（first 和 second），它可以存储任何类型的两个数据项。first 和 second 可以是任意类型，它们的类型是通过模板参数指定的。其定义可以理解为：

template <class T1, class T2>
struct pair {
    T1 first;   // 第一个元素
    T2 second;  // 第二个元素

    pair(); // 默认构造函数
    pair(const T1& a, const T2& b); // 构造函数
};

直接使用：

#include <iostream>
#include <utility>  // 如果没有通过其他库间接引入，可以通过这个库引入 std::pair 和 std::make_pair

int main() {
    // 创建一个 pair 类型，first 为 int 类型，second 为 std::string 类型
    std::pair<int, std::string> p1(1, "Hello");
  
      // 使用 make_pair 创建 pair，它会自动推导类型
    std::pair<int, std::string> p2 = std::make_pair(2, "World");

    // 访问 pair 的成员
    std::cout << "First: " << p1.first << ", Second: " << p1.second << std::endl;

    return 0;
}

比较：

std::pair 的比较是基于 first 和 second 元素的 lexicographical（字典序）比较：先比较 first，如果 first 相等，再比较 second。

std::pair<int, std::string> p1(1, "One");
std::pair<int, std::string> p2(2, "Two");

if (p1 < p2) {
    std::cout << "p1 is less than p2" << std::endl;
}

// Result: p1 is less than p2

[!NOTE]

可以把 std::map 看作是存储了一些 pair 元素的容器，不过它不允许这些 pair 的 first （也就是 key）重复

插入与删除

• insert(pair)：插入一个 key-value 键值对。如果键已经存在，插入会失败。
• insert_or_assign(key, value)：如果键存在，则更新值；如果键不存在，则插入新的键值对。
• erase(key)：删除指定键的元素。
• erase(iterator)：删除迭代器指向的元素。
• clear()：清空 map 中的所有元素。

查找操作

• find(key)：返回一个指向指定键 key 的迭代器，如果键不存在，则返回 end()。
• count(key)：返回键 key 在 map 中的个数（对于 map 来说，这个值要么是 0，要么是 1）。
• at(key)：返回键 key 对应的值的引用，如果键不存在，抛出 std::out_of_range 异常。
• operator[]：通过键访问对应的值，如果键不存在，会插入一个默认值。

容量与大小

• empty()：判断 map 是否为空，若为空返回 true，否则返回 false。
• size()：返回 map 中元素的数量。

遍历操作

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

示例

#include <iostream>
#include <map>

int main() {
    // 创建一个空的 map，按升序排列键
    std::map<int, std::string> m;

    // 插入元素
    m.insert({1, "One"});
    m.insert({2, "Two"});
    m.insert({3, "Three"});
    m[4] = "Four";  // 使用 operator[] 插入元素

    // 查找元素
    if (m.find(3) != m.end()) {
        std::cout << "Found key 3: " << m[3] << std::endl;
    }

    // 使用 at() 方法访问
    try {
        std::cout << "Key 2 maps to value: " << m.at(2) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << e.what() << std::endl;
    }

    // 删除元素
    m.erase(1);  // 删除键为 1 的元素

    // 遍历并输出 map
    std::cout << "Map contains:\n";
    for (const auto& pair : m) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 使用 operator[] 访问并修改元素
    m[2] = "Updated Two";  // 更新键为 2 的值
    std::cout << "After update:\n";
    for (const auto& pair : m) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

---

Unordered Set

功能

unordered_set 是 C++ 标准库中的一个关联容器，它用于存储唯一的元素并提供常数时间复杂度的查找、插入和删除操作。与 set 不同，unordered_set 并不按照元素的排序顺序存储，而是基于哈希表（Hash Table）实现的，因此它提供的是无序存储。

主要特点：

• 无序：元素的顺序是由哈希函数决定的，而不是元素的值大小。
• 唯一性：容器中存储的元素是唯一的，任何元素只能出现一次。

内部实现

unordered_set 是基于哈希表实现的，哈希表是一种可以通过哈希函数将元素映射到一个数组位置的数据结构。它的核心思想是：

• 哈希函数：unordered_set 使用哈希函数将每个元素映射到一个桶（bucket）中，哈希函数的目的是将元素均匀分布到不同的桶中，避免冲突。
• 元素要求：unordered_set 中的元素必须能够被哈希。C++ 标准库为常见类型（如 int, std::string 等）提供了默认的哈希函数。如果使用自定义类型作为元素类型，用户需要提供一个自定义的哈希函数，以便在哈希表中计算该元素的哈希值。
• 相等比较：unordered_set 中的元素必须支持相等比较操作符 ==，这是因为哈希表在存储元素时，会检查元素是否已经存在（通过比较元素的哈希值和相等性）。如果没有提供合适的相等比较函数，unordered_set 将无法判断元素是否重复。
• 冲突解决：当多个元素的哈希值相同（即哈希冲突）时，这些元素会被存储在同一个桶中。常见的冲突解决方法有链式法（用链表存储冲突元素）和开放寻址法等。C++ 标准库实现通常使用链式法。

扩容机制：

• unordered_set 会在元素数量超过当前负载因子（load factor，定义为元素数与桶数的比值）时自动扩容。扩容后，哈希表的大小通常会翻倍。
• 负载因子过高会导致更多的哈希冲突，从而影响查找性能，因此在知道大致元素个数时，可以通过 reserve() 函数提前指定桶的数量来避免频繁扩容。

[!NOTE]

在哈希表中，bucket 是存储哈希值映射的一个“桶”，每个桶是一个容器（通常是一个链表或其他数据结构）。当我们向哈希表中插入元素时，首先会通过哈希函数计算出元素的哈希值，然后根据哈希值将元素存放到对应的桶中。例如，假设桶的数量为 N，哈希值为 H，则该元素会被放入 H % N 位置的桶中。

在实际应用中，哈希函数可能会将多个元素映射到同一个桶（即发生哈希冲突），这时候按照上述方法处理哈希冲突。

性能

• 时间复杂度：

  • 查找、插入和删除：平均时间复杂度为 O(1)，但在最坏情况下可能退化为 O(n)，这通常发生在哈希冲突较多时。
  • 遍历：遍历 unordered_set 的时间复杂度为 O(n)，即必须访问每个元素。
• 空间复杂度：unordered_set 需要额外的空间来存储哈希表和桶。它的空间复杂度通常是 O(n)，但还受到负载因子的影响。

声明

要使用 unordered_set，你需要包含 <unordered_set> 头文件。常见的声明方式如下：

#include <unordered_set>

std::unordered_set<int> us1;           // 默认构造，创建一个空的 unordered_set
std::unordered_set<int> us2 = {1, 2, 3};  // 使用初始化列表创建

你还可以通过自定义哈希函数来创建 unordered_set，如下所示：

#include <unordered_set>
#include <iostream>

struct MyHash {
    size_t operator()(const std::string& s) const {
        size_t hash = 0;
        for (char c : s) {
            hash = hash * 31 + c;
        }
        return hash;
    }
};

int main() {
    std::unordered_set<std::string, MyHash> us;
    us.insert("apple");
    us.insert("banana");
    us.insert("orange");

    for (const auto& elem : us) {
        std::cout << elem << std::endl;
    }
}

常用方法

插入与删除

• insert(value): 向 unordered_set 插入一个元素。如果元素已经存在，则不会插入新的元素，且返回一个指向该元素的迭代器。
• erase(value): 删除 unordered_set 中的指定元素。
• erase(position): 删除指定位置的元素。
• clear(): 清空 unordered_set 中的所有元素。

查找

• find(value): 查找指定元素，如果存在则返回指向该元素的迭代器，否则返回 end()。
• count(value): 查找指定元素，返回元素出现的次数（由于 unordered_set 中的元素是唯一的，返回值要么是 0，要么是 1）。
• contains(value) (C++20 引入)：检查是否包含某个元素，返回 true 或 false。

容量与大小

• size(): 返回 unordered_set 中元素的数量。
• empty(): 判断 unordered_set 是否为空。
• bucket_count(): 返回当前哈希表中桶的数量。
• load_factor(): 返回当前负载因子，即元素数与桶数的比值。

[!NOTE]

负载因子是元素数量与桶数量的比值，通常用 load_factor = size / bucket_count() 来表示。负载因子越高，哈希表中元素分布不均匀的可能性越大。

C++ 中的 unordered_set 默认的负载因子上限为 1.0，这意味着如果负载因子超过 1.0，哈希表会自动扩容（增加桶的数量）。

迭代器

• begin(): 返回指向容器第一个元素的迭代器。
• end(): 返回指向容器最后一个元素之后的迭代器。
• cbegin(), cend(): 常量迭代器，不能修改元素。

负载因子和扩容

• reserve(n): 保证 unordered_set 至少有 n 个桶。如果当前桶数少于 n，则会进行扩容。
• rehash(n): 将 unordered_set 的桶数量调整为 n，通常用来控制负载因子。

示例代码

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个 unordered_set
    std::unordered_set<int> us;

    // 插入元素
    us.insert(10);
    us.insert(20);
    us.insert(30);
    us.insert(20);  // 重复元素不会插入

    // 输出所有元素
    for (const auto& elem : us) {
        std::cout << elem << " ";  // 输出的顺序是无序的
    }
    std::cout << std::endl;

    // 查找元素
    if (us.find(20) != us.end()) {
        std::cout << "Found 20" << std::endl;
    } else {
        std::cout << "20 not found" << std::endl;
    }

    // 删除元素
    us.erase(10);

    // 检查容器是否为空
    if (us.empty()) {
        std::cout << "unordered_set is empty" << std::endl;
    } else {
        std::cout << "unordered_set is not empty" << std::endl;
    }

    return 0;
}

---

Unordered Map

功能

unordered_map 是 C++ 标准库中的一种关联容器（关联数组），它存储键值对（key-value）。与 map 不同，unordered_map 中的元素并不按键的顺序排列，而是根据哈希值来组织和访问。它提供了快速的查找、插入和删除操作，平均时间复杂度为 O(1)。

主要特点：

• 无序：元素不会按键的顺序排列，而是根据哈希函数决定元素的存储位置。
• 键唯一：unordered_map 的每个键必须是唯一的。如果插入一个已经存在的键，那么新插入的值会覆盖旧值。

内部实现

unordered_map 同样使用哈希表作为其底层数据结构。

unordered_map 中的键类型同样必须支持哈希操作，且必须是可比较的（例如使用 == 操作符进行比较）。C++ 标准库为常见类型（如 int, std::string 等）提供了默认的哈希函数，但对于自定义类型，用户需要提供自定义哈希函数。

性能

• 时间复杂度：

  • 查找（find()）：平均时间复杂度为 O(1)，最坏情况下为 O(n)（当所有元素被哈希到同一个桶时）。
  • 插入（insert()）：平均时间复杂度为 O(1)，最坏情况下为 O(n)（哈希冲突严重或需要重新哈希）。
  • 删除（erase()）：平均时间复杂度为 O(1)，最坏情况下为 O(n)。
  • 遍历（通过迭代器）：平均时间复杂度为 O(n)，即遍历所有元素。

• 空间复杂度：unordered_map 使用哈希表实现，需要额外的空间来存储桶和处理哈希冲突。哈希表的空间复杂度通常是 O(n)，其中 n 是容器中元素的数量。

• 哈希冲突：哈希冲突是影响性能的关键因素。虽然 C++ 的 unordered_map 采用了链式哈希法（通过链表存储冲突元素），但是在极端情况下，若所有元素的哈希值相同，性能会退化为 O(n)。

声明

要使用 unordered_map，你需要包含 <unordered_map> 头文件。常见的声明方式如下：

#include <unordered_map>

std::unordered_map<int, std::string> map1;   // 声明一个键为 int，值为 string 的 unordered_map
std::unordered_map<std::string, int> map2;   // 声明一个键为 string，值为 int 的 unordered_map

你还可以使用初始化列表来创建 unordered_map：

std::unordered_map<int, std::string> map = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};

常用方法

插入元素

• insert(pair)：插入一个键值对，如果键已存在，则插入失败。
• insert_or_assign(key, value)：插入一个键值对，如果键已存在，则更新该键对应的值。

访问元素

• operator[]：通过键访问值。如果键不存在，operator[] 会插入一个默认构造的值并返回。
• at(key)：通过键访问值，若键不存在会抛出 std::out_of_range 异常。

删除元素

• erase(key)：删除指定键的元素。
• erase(iterator)：通过迭代器删除元素。
• clear()：清空所有元素。

查找元素

• find(key)：查找给定键的元素，如果找到，返回指向该元素的迭代器，否则返回 end()。

容量与大小

• size()：返回容器中元素的数量。
• empty()：检查容器是否为空。
• bucket_count()：返回哈希表中桶的数量。
• load_factor()：返回负载因子，即元素数量与桶数量的比值。
• rehash(n)：重新哈希，将桶的数量调整为 n，以减少哈希冲突。

示例

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个 unordered_map
    std::unordered_map<int, std::string> map;

    // 插入元素
    map.insert({1, "apple"});
    map[2] = "banana";  // 使用 operator[] 插入
    map[3] = "cherry";

    // 访问元素
    std::cout << "Key 2: " << map[2] << std::endl;  // 使用 operator[] 访问
    std::cout << "Key 3: " << map.at(3) << std::endl;  // 使用 at() 访问

    // 查找元素
    auto it = map.find(1);
    if (it != map.end()) {
        std::cout << "Found key 1: " << it->second << std::endl;
    }

    // 删除元素
    map.erase(2);  // 删除键为 2 的元素

    // 检查容器大小
    std::cout << "Size of map: " << map.size() << std::endl;

    // 清空容器
    map.clear();
    std::cout << "Size after clear: " << map.size() << std::endl;

    return 0;
}