向量

![[OJ-1#vector]]

栈

std::stack 是一种后进先出（Last-In, First-Out，简称 LIFO）的数据结构。你可以把它想象成一摞盘子：你只能在最上面放盘子，也只能从最上面取盘子。最后放上去的盘子，最先被取出来。

在 C++ 中，std::stack 并不是一个独立的容器，而是一个容器适配器（container adapter）。这意味着它是在其他现有容器类型（如 std::vector, std::deque, std::list）的基础上实现的，通过限制这些底层容器的接口，来提供特定的栈功能。默认情况下，std::stack 使用 std::deque 作为其底层容器。

头文件：

C++

#include <stack>

示例代码：

#include <iostream>
#include <stack>
#include <string>

int main() {
    // 创建一个存储字符串的栈
    std::stack<std::string> books;

    // 1. 使用 empty() 和 size() 检查初始状态
    if (books.empty()) {
        std::cout << "书架（栈）是空的。" << std::endl;
    }
    std::cout << "当前书本数量: " << books.size() << std::endl;
    std::cout << "--------------------------" << std::endl;

    // 2. 使用 push() 推入元素（入栈）
    std::cout << "依次放入三本书..." << std::endl;
    books.push("C++ Primer");
    books.push("Effective C++");
    books.push("The Lord of the Rings");

    std::cout << "当前书本数量: " << books.size() << std::endl;

    // 3. 使用 top() 访问栈顶元素
    // 在调用 top() 或 pop() 之前，最好检查栈是否为空
    if (!books.empty()) {
        std::cout << "最顶上的书是: " << books.top() << std::endl;
    }
    std::cout << "--------------------------" << std::endl;

    // 4. 使用 pop() 移除栈顶元素（出栈）
    std::cout << "取走最顶上的书..." << std::endl;
    books.pop();

    // 再次访问栈顶
    if (!books.empty()) {
        std::cout << "现在最顶上的书是: " << books.top() << std::endl;
    }
    std::cout << "当前书本数量: " << books.size() << std::endl;
    std::cout << "--------------------------" << std::endl;

    // 5. 遍历并清空栈
    std::cout << "依次取出所有书本：" << std::endl;
    while (!books.empty()) {
        std::cout << "取出了: " << books.top() << std::endl;
        books.pop(); // 先访问，再弹出
    }

    // 最终检查
    if (books.empty()) {
        std::cout << "书架（栈）现在又空了。" << std::endl;
    }
    std::cout << "当前书本数量: " << books.size() << std::endl;

    return 0;
}

队列

头文件：

#include <queue>

代码示例：

#include <iostream>
#include <queue>
#include <string>

int main() {
    // 创建一个存储字符串的队列
    std::queue<std::string> customer_line;

    // 1. 使用 empty() 和 size() 检查初始状态
    if (customer_line.empty()) {
        std::cout << "排队队列是空的。" << std::endl;
    }
    std::cout << "当前排队人数: " << customer_line.size() << std::endl;
    std::cout << "--------------------------" << std::endl;

    // 2. 使用 push() 将元素加入队尾（入队）
    std::cout << "张三、李四、王五依次来排队..." << std::endl;
    customer_line.push("张三");
    customer_line.push("李四");
    customer_line.push("王五");

    std::cout << "当前排队人数: " << customer_line.size() << std::endl;

    // 3. 使用 front() 和 back() 访问队头和队尾元素
    // 在调用 front(), back(), pop() 之前，最好检查队列是否为空
    if (!customer_line.empty()) {
        std::cout << "排在最前面的是: " << customer_line.front() << std::endl;
        std::cout << "排在最后面的是: " << customer_line.back() << std::endl;
    }
    std::cout << "--------------------------" << std::endl;

    // 4. 使用 pop() 移除队头元素（出队）
    std::cout << "队首的 " << customer_line.front() << " 办理完业务，离开队列。" << std::endl;
    customer_line.pop();

    // 再次访问队头和队尾
    if (!customer_line.empty()) {
        std::cout << "现在排在最前面的是: " << customer_line.front() << std::endl;
        std::cout << "排在最后面的是: " << customer_line.back() << std::endl;
    }
    std::cout << "当前排队人数: " << customer_line.size() << std::endl;
    std::cout << "--------------------------" << std::endl;

    // 5. 遍历并清空队列
    std::cout << "所有人依次办理业务离开：" << std::endl;
    while (!customer_line.empty()) {
        std::cout << customer_line.front() << " 办理完成，离开队列。" << std::endl;
        customer_line.pop(); // 先访问，再出队
    }

    // 最终检查
    if (customer_line.empty()) {
        std::cout << "队列现在又空了。" << std::endl;
    }
    std::cout << "当前排队人数: " << customer_line.size() << std::endl;

    return 0;
}

值对<pair>

头文件：

#include <utility>

可以通过构造函数创建：

#include <iostream>
#include <utility>
#include <string>

int main() {
    // 创建一个包含 int 和 string 的 pair
    std::pair<int, std::string> p1(1, "apple");

    // 也可以使用C++11之后的列表初始化
    std::pair<std::string, double> p2{"pi", 3.14};

    // 默认构造函数，成员会被值初始化
    // (对于内置类型如int, double就是0; 对于string是空字符串)
    std::pair<int, std::string> p3; 
}

指定两个类型然后创建。

使用 std::make_pair() 辅助函数：

auto p4 = std::make_pair(10, "orange"); // 自动推断为 std::pair<int, const char*>
auto p5 = std::make_pair(std::string("hello"), 5.0f); // 自动推断为std::pair<std::string, float>

使用上主要是与<vector>等进行嵌套，用来解决某些问题（如把计数器嵌入进值）

访问 std::pair 的两个成员非常直接，通过成员变量 first 和 second 即可。

std::pair<int, std::string> fruit(1, "apple");

std::cout << "ID: " << fruit.first << std::endl;      // 输出: ID: 1
std::cout << "Name: " << fruit.second << std::endl;   // 输出: Name: apple

// 修改成员
fruit.first = 2;
fruit.second = "banana";

std::cout << "New ID: " << fruit.first << std::endl;   // 输出: New ID: 2
std::cout << "New Name: " << fruit.second << std::endl; // 输出: New Name: banana

std::pair 的比较操作：

std::pair 自带了全套的比较运算符 (==, !=, <, >, <=, >=)。比较规则是**字典序（lexicographical）**的：

1. 首先比较 first 成员。如果 a.first < b.first，那么 a < b 就为 true，比较结束。
2. 如果 first 成员相等，则继续比较 second 成员。如果 a.second < b.second，那么 a < b 才为 true。
3. == 运算符只有在 a.first == b.first 并且 a.second == b.second 时才为 true。

基本就是想的那种比较方法，比较正经，没什么好说的。

键值对

即std::map ，存储的元素是键值对（key-value pair）。

头文件：

C++

#include <map>

核心特性：

1. 键值对存储：map 中的每个元素都由一个**键（Key）和一个与之关联的值（Value）**组成。
2. 键的唯一性：在一个 map 中，所有的键都必须是唯一的。如果你尝试插入一个已经存在的键，插入操作会失败（或者在某些使用方式下会覆盖原有的值）。
3. 自动排序：这是 std::map 最重要的特性之一。它会根据键的大小，自动对所有元素进行排序。默认情况下，它使用键类型的 < 运算符进行升序排序。当你遍历一个 map 时，你会发现输出的元素是按键排好序的。
4. 底层实现：std::map 通常是基于**红黑树（Red-Black Tree）**这种自平衡二叉搜索树实现的。这保证了其插入、删除、查找等主要操作的时间复杂度都是对数级别的，即 O(logn)，其中 n 是容器中元素的数量。这在处理大量数据时依然能保持高效。

操作示例，打印的操作是手动构建实现的，这点和python还是差别挺大的。

#include <iostream>
#include <map>
#include <string>

// 用于打印 map 内容的辅助函数
void print_map(const std::map<std::string, int>& m) {
    std::cout << "{ ";
    for (const auto& pair : m) {
        // pair 的类型是 std::pair<const std::string, int>
        std::cout << "\"" << pair.first << "\": " << pair.second << " ";
    }
    std::cout << "}" << std::endl;
}

int main() {
    // 1. 创建一个 map，键是 string 类型，值是 int 类型
    std::map<std::string, int> student_scores;

    // 2. 插入元素
    // (a) 使用 std::make_pair 和 insert
    student_scores.insert(std::make_pair("Li Ming", 95));
    // (b) 使用列表初始化 (C++11) 和 insert
    student_scores.insert({"Wang Hong", 88});
    // (c) 使用 emplace (C++11, 更高效)
    student_scores.emplace("Zhang Wei", 92);
    // (d) 使用下标运算符 [] (最简单直接的方式)
    // 如果键不存在，则创建；如果存在，则覆盖。
    student_scores["Zhao Lei"] = 76;
    student_scores["Wang Hong"] = 90; // "Wang Hong" 已存在，值从 88 被更新为 90

    std::cout << "初始化后的分数表 (已按姓名首字母排序):" << std::endl;
    print_map(student_scores);
    std::cout << "当前学生人数: " << student_scores.size() << std::endl;
    std::cout << "------------------------------------" << std::endl;

    // 3. 访问元素
    // (a) 使用下标运算符 []
    std::cout << "Li Ming's score: " << student_scores["Li Ming"] << std::endl;
    // (b) 使用 at() 方法 (更安全)
    // at() 会进行边界检查，如果键不存在，会抛出 std::out_of_range 异常
    try {
        std::cout << "Zhang Wei's score: " << student_scores.at("Zhang Wei") << std::endl;
        // std::cout << student_scores.at("Non-existent"); // 这行会抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }
    // 注意：如果使用 [] 访问一个不存在的键，会自动创建该键并对其值进行默认初始化！
    // std::cout << student_scores["Sun Qi"]; // 这会向 map 中插入 {"Sun Qi", 0}
    
    std::cout << "------------------------------------" << std::endl;

    // 4. 查找元素
    // 使用 find() 方法，如果找到，返回指向该元素的迭代器；否则返回 end() 迭代器
    auto it = student_scores.find("Zhao Lei");
    if (it != student_scores.end()) {
        std::cout << "找到了 Zhao Lei，分数是: " << it->second << std::endl;
    } else {
        std::cout << "没有找到 Zhao Lei。" << std::endl;
    }
    
    // 使用 count() 方法，因为键是唯一的，所以返回值只可能是 0 或 1
    if (student_scores.count("Li Ming")) {
        std::cout << "Li Ming 在分数表中。" << std::endl;
    }
    std::cout << "------------------------------------" << std::endl;

    // 5. 删除元素
    // 使用 erase() 方法，通过键来删除
    student_scores.erase("Li Ming");
    std::cout << "删除 Li Ming 之后:" << std::endl;
    print_map(student_scores);

    return 0;
}

无序集合

头文件：

#include <unordered_set>

特性：

1. 只存储键：与 map 不同，set 容器只存储键本身，没有与之关联的值。你可以把它看作是一个只有键没有值的 std::unordered_map。
2. 元素唯一性：容器中的每个元素都必须是唯一的。如果你尝试插入一个已经存在的元素，插入操作会失败，容器内容不会改变。
3. 无序存储：这是与 std::set 最大的区别。std::unordered_set 中的元素不会自动排序。当你遍历它时，元素的顺序通常看起来是“随机”的，并且可能会在程序的不同运行中或内容发生改变后发生变化。
4. 基于哈希表：为了实现快速操作，std::unordered_set 的底层是基于**哈希表（Hash Table）实现的。元素被存储在“桶（buckets）”中，具体哪个桶由元素的哈希值（hash value）**决定。
5. 极高的平均性能：由于使用了哈希表，其插入、删除和查找操作的平均时间复杂度为常数级 O(1)。这是它相对于 std::set（对数级 O(logn)）的最大优势。但在最坏情况下（所有元素哈希冲突），性能可能会退化到线性级 O(n)。

代码示例：

#include <iostream>
#include <unordered_set>
#include <set>
#include <string>

// 用于打印集合内容的辅助函数
template<typename T>
void print_collection(const T& collection, const std::string& name) {
    std::cout << name << " contains: { ";
    for (const auto& elem : collection) {
        std::cout << elem << " ";
    }
    std::cout << "}" << std::endl;
}

int main() {
    // 1. 创建一个 unordered_set
    std::unordered_set<std::string> fruit_basket;

    // 2. 插入元素
    fruit_basket.insert("apple");
    fruit_basket.insert("banana");
    fruit_basket.emplace("orange");

    std::cout << "--- Initial State ---" << std::endl;
    print_collection(fruit_basket, "Unordered Set");

    // 尝试插入一个重复元素
    auto result = fruit_basket.insert("apple");
    if (!result.second) {
        std::cout << "\n'apple' already exists. Insertion failed." << std::endl;
        // result.first 是指向已存在元素的迭代器
        // result.second 是一个布尔值，表示插入是否成功
    }
    std::cout << "Current size: " << fruit_basket.size() << std::endl;
    
    std::cout << "\n--- Finding Elements ---" << std::endl;
    // 3. 查找元素 (非常快)
    // 使用 find()
    if (fruit_basket.find("banana") != fruit_basket.end()) {
        std::cout << "'banana' was found in the basket." << std::endl;
    } else {
        std::cout << "'banana' was not found." << std::endl;
    }
    // 使用 count() - 因为元素唯一，返回值只能是 0 或 1
    if (fruit_basket.count("grape") > 0) {
        std::cout << "'grape' was found." << std::endl;
    } else {
        std::cout << "'grape' was not found." << std::endl;
    }

    std::cout << "\n--- Deleting Elements ---" << std::endl;
    // 4. 删除元素
    fruit_basket.erase("banana");
    print_collection(fruit_basket, "After erasing 'banana'");

    std::cout << "\n--- Comparison with std::set ---" << std::endl;
    // 对比 std::set 的行为
    std::set<std::string> sorted_fruit_basket;
    sorted_fruit_basket.insert("apple");
    sorted_fruit_basket.insert("orange");
    sorted_fruit_basket.insert("banana"); // 同样的数据

    print_collection(fruit_basket, "Final Unordered Set"); // 注意顺序
    print_collection(sorted_fruit_basket, "Final Ordered Set");   // 注意顺序
    
    return 0;
}

这里关于insert方法，其虽然可以直接插入，但是也可以读取相应的result返回，它返回一个 std::pair。这个 pair 包含两个部分：

1. first：一个迭代器 (iterator)。
2. second：一个布尔值 (bool)，也就是 true 或 false。

当 true 的时候，代表插入成功。返回的迭代器指向刚刚被成功插入的新元素。当false的时候指向的是那个导致插入失败的、已经存在的旧元素。

有序集合

std::set 是一个存储唯一元素的有序集合。你可以把它想象成一个数学上的集合概念，但额外增加了自动排序的功能。

头文件：

#include <set>

核心特性：

1. 元素唯一性：在一个 set 中，每个元素的值都必须是唯一的。如果你尝试插入一个已经存在的元素，插入操作会被忽略，容器内容不会改变。
2. 自动排序：这是 std::set 与 std::unordered_set 最根本的区别。set 中的元素会根据其值自动进行排序。默认情况下，它使用元素类型的 < 运算符进行升序排序。因此，无论你以何种顺序插入元素，遍历 set 时得到的总是一个有序序列。
3. 只存储键：与 map 不同，set 只存储元素（或称为“键”），没有与之关联的值。它的主要目的是判断某个元素是否存在于集合中，并维护这个集合的有序性。
4. 基于平衡二叉搜索树：std::set 的底层通常是基于红黑树（Red-Black Tree）实现的。红黑树是一种自平衡的二叉搜索树，它能保证插入、删除和查找操作的时间复杂度都是对数级别的，即 O(logn)，其中 n 是容器中元素的数量。这使得 set 在各种操作上都具有稳定且高效的性能。

主要操作函数

#include <iostream>
#include <set>
#include <string>

// 用于打印集合内容的辅助函数
void print_set(const std::set<int>& s) {
    std::cout << "{ ";
    for (int elem : s) {
        std::cout << elem << " ";
    }
    std::cout << "}" << std::endl;
}

int main() {
    // 1. 创建一个 set
    std::set<int> numbers;

    // 2. 以无序的方式插入元素
    std::cout << "--- Inserting Elements ---" << std::endl;
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(50);
    numbers.insert(20);
    numbers.insert(40);

    // 遍历 set，观察其自动排序的特性
    std::cout << "Set contains (auto-sorted): ";
    print_set(numbers);

    // 3. 尝试插入一个重复元素
    auto result = numbers.insert(20);
    if (!result.second) {
        std::cout << "\n'20' already exists. Insertion failed." << std::endl;
    }
    std::cout << "Current size: " << numbers.size() << std::endl;

    std::cout << "\n--- Finding Elements ---" << std::endl;
    // 4. 查找元素 (O(log n) 时间复杂度)
    if (numbers.find(50) != numbers.end()) {
        std::cout << "'50' was found." << std::endl;
    } else {
        std::cout << "'50' was not found." << std::endl;
    }
    
    if (numbers.count(15) == 0) {
        std::cout << "'15' was not found." << std::endl;
    }
    
    std::cout << "\n--- Range Finding ---" << std::endl;
    // 5. 使用 lower_bound 和 upper_bound
    // set: { 10 20 30 40 50 }
    
    // lower_bound(30) -> 查找第一个不小于30的元素
    auto it_lower = numbers.lower_bound(30);
    std::cout << "Lower bound of 30 is: " << *it_lower << std::endl; // 输出 30

    // upper_bound(30) -> 查找第一个大于30的元素
    auto it_upper = numbers.upper_bound(30);
    std::cout << "Upper bound of 30 is: " << *it_upper << std::endl; // 输出 40

    std::cout << "\nElements between 20 and 50 (exclusive of 20, inclusive of 50):" << std::endl;
    for (auto it = numbers.upper_bound(20); it != numbers.upper_bound(50); ++it) {
        std::cout << *it << " "; // 输出 30 40 50
    }
    std::cout << std::endl;

    std::cout << "\n--- Deleting Elements ---" << std::endl;
    // 6. 删除元素
    numbers.erase(30);
    std::cout << "After erasing 30: ";
    print_set(numbers);
    
    return 0;
}

序列

std::list 是一个序列容器，它允许在序列中的任何位置进行常数时间的插入和删除操作，并且可以双向迭代。

头文件：

#include <list>

核心特性：

1. 底层实现：std::list 的底层是双向链表 (Doubly-linked List)。每个元素都存储在独立的内存节点中，每个节点除了包含元素本身的数据外，还包含两个指针，分别指向前一个元素和后一个元素。
2. 非连续内存：与 std::vector 不同，list 的元素在内存中是不连续存储的。这带来了几个重要的影响：
   • 快速的插入和删除：在 list 的任何位置插入或删除一个元素，只需要修改相邻节点的指针即可，这个操作的时间复杂度是常数级的 O(1)（前提是已经有了指向该位置的迭代器）。这与 vector 形成鲜明对比，后者在中间插入/删除元素可能需要移动大量后续元素，时间复杂度为 O(n)。
   • 不支持随机访问：由于内存不连续，你无法像 vector 那样通过 list[i] 的方式直接访问第 i 个元素。要访问一个元素，必须从头或尾开始，顺着指针一个一个地数过去，时间复杂度为 O(n)。
3. 迭代器稳定性：在 std::list 中插入元素不会使任何指向其他元素的迭代器、指针或引用失效。同样，删除元素也只会使指向被删除元素的迭代器、指针和引用失效。

主要操作函数：

特殊操作：

代码示例：

#include <iostream>
#include <list>
#include <string>

void print(const std::string& name, const std::list<int>& l) {
    std::cout << name << ": { ";
    for(int n : l) std::cout << n << " ";
    std::cout << "}\n";
}

int main() {
    // splice
    std::list<int> l1 = {1, 2, 3};
    std::list<int> l2 = {10, 20, 30};
    auto it1 = l1.begin();
    ++it1; // it1 指向 2
    l1.splice(it1, l2); // 将 l2 所有元素移动到 l1 的 2 前面
    print("l1 after splice", l1); // l1: { 1 10 20 30 2 3 }
    print("l2 after splice", l2); // l2: { }

    // remove_if
    l1.remove_if([](int n){ return n > 15; }); // 移除所有大于15的数
    print("l1 after remove_if", l1); // l1: { 1 10 2 3 }

    // sort & unique
    l1.push_back(1);
    l1.push_back(10);
    print("l1 before sort", l1); // l1: { 1 10 2 3 1 10 }
    l1.sort();
    print("l1 after sort", l1);  // l1: { 1 1 2 3 10 10 }
    l1.unique();
    print("l1 after unique", l1); // l1: { 1 2 3 10 }

    // merge
    std::list<int> l3 = {5, 8, 12}; // 必须是有序的
    l1.merge(l3);
    print("l1 after merge", l1); // l1: { 1 2 3 5 8 10 12 }
    print("l3 after merge", l3); // l3: { }
}

数组

std::array 是 C++11 标准库中引入的一个容器，它封装了一个固定大小的数组。与 C 风格的数组相比，std::array 提供了更安全、更方便的接口，并且能够像其他 STL 容器（如 std::vector）一样使用。

头文件，创建和正常数组的区别是需要有类型，数量这个两个参数：

#include <array>

std::array<T, N> arrayName;

特点：

• 固定大小：一旦创建，std::array 的大小就不能改变。这个大小是其类型的一部分，在编译时就必须确定。
• 内存分配：std::array 的数据存储在栈（stack）上（如果作为局部变量）或静态存储区，与 C 风格数组行为一致。这使得它的内存分配非常高效，避免了堆（heap）分配的开销。
• 性能：由于其固定大小和内存布局，它的性能与 C 风格数组几乎完全相同，访问元素非常快。
• 安全性：提供了边界检查（通过 at() 成员函数），并且其大小是已知的，可以轻松传递给函数而不会丢失大小信息。
• STL 兼容性：支持迭代器，可以与标准库算法（如 std::sort, std::find）无缝协作。

元素访问函数：

容量函数：

修改函数：

在创建后可以完全当成一个支持迭代器的数组来用。

双端队列

std::deque（双端队列）是 C++ 标准模板库（STL）中的一种序列容器，定义在 <deque> 头文件中。它支持在头部和尾部进行高效的插入和删除操作，总的来说是<vector>和<list>的合体版。

头文件：

#include <deque>

特性：

1. 双端操作：在头部和尾部插入/删除元素的时间复杂度为 O(1)
2. 随机访问：支持通过索引直接访问元素（时间复杂度 O(1)）
3. 动态内存：自动管理内存，根据需要动态增长
4. 非连续存储：元素存储在多个固定大小的内存块中（与 vector 的连续存储不同）

双端队列的构造：

双端队列元素的访问，支持d[index]的访问，很不错：

容量相关函数：

特殊操作函数：

#include <iostream>
#include <deque>

int main() {
    // 创建 deque
    std::deque<int> d = {2, 3, 4};
    
    // 添加元素
    d.push_front(1);  // 头部添加
    d.push_back(5);   // 尾部添加
    
    // 访问元素
    std::cout << "Front: " << d.front() << "\n";  // 1
    std::cout << "Back: " << d.back() << "\n";    // 5
    std::cout << "Element at 2: " << d[2] << "\n"; // 3
    
    // 中间插入
    d.insert(d.begin() + 3, 99);  // 在位置3插入99
    
    // 删除元素
    d.pop_front();  // 删除头部
    d.pop_back();   // 删除尾部
    
    // 遍历 deque
    std::cout << "Deque contents: ";
    for (auto it = d.begin(); it != d.end(); ++it) {
        std::cout << *it << " ";
    }
    // 输出: 2 3 99
    
    return 0;
}

向量，列表和双向队列的对比