C++ STL

一、STL实现原理及其实现

STL（Standard Template Library）是C++标准库的重要组成部分，提供了一套通用的类和函数模板，用于处理数据结构和算法。广义上讲，STL分为三大类：算法 (Algorithm)、容器 (Container) 和迭代器 (Iterator)。这些组件通过迭代器可以无缝地连接起来。更详细地说，STL由六个主要部分组成：容器、算法、迭代器、仿函数、适配器和空间配置器。

1. 容器（Containers）

容器是用来存放和管理数据的类模板。常见的STL容器包括：

顺序容器：vector, list, deque, queue, stack, forward_list
关联容器：set, map, multiset, multimap, unordered_set, unordered_map, unordered_multiset, unordered_multimap
适配器容器：stack, queue, priority_queue

这些容器各有各的用途和特点，比如vector用于动态数组，list用于双向链表，map用于键值对的存储和快速查找。

2. 算法（Algorithms）

算法是一些通用的函数模板，用于对数据进行操作。STL中的算法涵盖了常见的操作，如排序、搜索、复制、修改等。

修改操作：copy, fill, transform
排序和查找：sort, find, binary_search
数值算法：accumulate, adjacent_difference

这些算法独立于容器，通过迭代器提供一般性的接口，可以适用于不同的数据结构。

3. 迭代器（Iterators）

迭代器是STL的核心，它是一种抽象的概念，用于在容器和算法之间建立连接。STL提供了多种迭代器，包括：

输入迭代器：只读访问，支持++操作
输出迭代器：只写访问，支持++操作
正向迭代器：支持读写，支持++操作
双向迭代器：支持双向移动（++、–）
随机访问迭代器：支持随机访问（+n、-n、[ ]）

迭代器通过重载操作符（如*, ->, ++, --等）来实现类似指针的行为，使得算法能够对各种容器进行操作。

4. 仿函数（Functors）

仿函数是重载了operator()的类或类模板，使得对象可以像函数一样调用。仿函数用于自定义算法的策略或行为。例如：

struct Add {
    int operator()(int a, int b) const {
        return a + b;
    }
};

std::transform(vec1.begin(), vec1.end(), vec2.begin(), vec3.begin(), Add());

5. 适配器（Adapters）

适配器是用来修改容器、仿函数或迭代器接口的工具。STL提供了一些常用的适配器：

容器适配器：stack, queue, priority_queue
迭代器适配器：reverse_iterator, insert_iterator, ostream_iterator, istream_iterator
仿函数适配器：std::bind, std::function

例如，stack实际上是基于deque实现的，提供了堆栈操作的接口。

6. 空间配置器（Allocators）

空间配置器负责内存的分配和管理，是STL容器管理内存的基础。默认的分配器是std::allocator，它通过allocate和deallocate函数调用operator new和operator delete来分配和释放内存。

template<typename T>
class MyAllocator {
public:
    T* allocate(size_t n) {
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    
    void deallocate(T* p, size_t n) {
        ::operator delete(p);
    }
};

二、STL的优点

STL的优点在于其高度模块化和抽象性，使得它能够提供高可重用性、高性能和高移植性。容器、算法、迭代器、仿函数、适配器、空间配置器之间的良好组合和协同作用使得STL成为C++中强大的工具库。

1、高可重用性:

STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

2、高性能:

如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。

3、高移植性:

如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。

STL 的一个重要特性是将数据和操作分离，数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作。

数据与操作分离

STL的设计理念是将数据和操作分离：

数据由容器类别管理。
操作由可定制的算法定义。
迭代器在两者之间充当“粘合剂”，使算法可以与容器交互。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {4, 2, 3, 1, 5};
    
    // 使用算法排序
    std::sort(vec.begin(), vec.end());
    
    // 使用迭代器输出
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用仿函数
    struct Square {
        void operator()(int& n) const {
            n = n * n;
        }
    };
    
    std::for_each(vec.begin(), vec.end(), Square());
    
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

三、pair容器

pair 是 C++ 标准模板库（STL）中定义的一个结构体模板，用于表示一个包含两个元素的有序对。在 pair 中，两个元素可以是不同类型。这是 pair 的基本定义：

namespace std {
    template <typename T1, typename T2>
    struct pair {
        T1 first;
        T2 second;
    };
}

在上述定义中，pair 有两个公共成员 first 和 second，分别表示有序对的第一个和第二个元素。这两个元素的类型由模板参数 T1 和 T2 决定。

在关联容器中，通常使用 pair 来表示键值对，其中 first 是键（key），second 是值（value）。例如，map 的元素类型就是 pair<const key_type, mapped_type>。

以下是一些关于 pair 的使用示例：

遍历关联容器：

map<string, int> p;
auto map1 = p.cbegin();
while (map1 != p.cend()) {
    cout << map1->first << map1->second << endl;
    ++map1;
}

在这个例子中，map 中的元素是 pair，通过迭代器遍历 map，可以方便地访问每个键值对的 first 和 second。

插入元素：

1 2	p.insert({word, 1}); p.insert(pair<string, int>(word, 1));

在插入元素时，可以使用 pair 的简化语法，也可以显式地创建 pair 对象。对于不包含重复关键字的容器，插入成功会返回一个 pair，其中迭代器指向给定关键字元素，bool 指示插入是否成功。

使用 pair 的 vector 排序：

vector<pair<char, int>> result(val.begin(), val.end());
sort(result.begin(), result.end(), [](auto &a, auto &b) {
    return a.second > b.second;
});

在这个例子中，使用 pair 的 vector 存储元素，并通过排序算法对 vector 进行排序，按照 second 的值从大到小排序。这种情况下，pair 很方便地用于存储和操作有序对数据。

三、vector容器

std::vector 是 C++ 标准模板库（STL）中提供的动态数组容器，具有以下主要特点和优势：

动态数组：
- std::vector 提供了动态数组的功能，可以在运行时动态调整数组的大小。
连续内存存储：
- 元素在内存中是连续存储的，这样支持通过指针或迭代器进行高效的随机访问。
模板类：
- std::vector 是一个模板类，可以存储任意类型的元素，包括内置类型和自定义类型。
自动管理内存：
- std::vector 自动管理底层内存，包括动态分配和释放，无需手动操作内存。
动态扩容：
- 在元素数量增加时，std::vector 会自动扩展容量，确保足够的空间，避免手动管理内存和数组大小。
迭代器支持：
- 提供了迭代器支持，可以使用迭代器进行遍历、查找、排序等操作。
随机访问：
- 支持通过索引快速访问任意位置的元素，时间复杂度为 O(1)。
尾部插入和删除：
- 提供了 push_back 和 pop_back 操作，可以在数组的尾部高效地插入和删除元素。
标准接口和算法：
- std::vector 提供了一系列的标准接口和算法，例如迭代器、begin、end、size、capacity、resize、clear 等。
适用范围：
- std::vector 适用于需要频繁随机访问元素、动态调整数组大小以及尾部插入和删除操作的场景。
注意事项：
- 在大量插入或删除操作时，可能涉及到动态扩容，需要注意性能开销。
- 使用 reserve 预留一定容量，可以减少动态扩容的次数，提高效率。

示例代码：

std::vector<int> vec1;                       // 默认构造函数，创建一个空的 vector
std::vector<int> vec2(10);                   // 创建一个包含 10 个默认值（0）的 vector
std::vector<int> vec3(10, 5);                // 创建一个包含 10 个值为 5 的 vector
std::vector<int> vec4(vec3);                 // 拷贝构造函数，复制 vec3
std::vector<int> vec5 = vec3;                // 拷贝赋值操作

vec[0];                 // 访问第一个元素（不安全，可能导致越界）
vec.at(0);              // 访问第一个元素（安全，检查越界）
vec.front();           // 访问第一个元素
vec.back();            // 访问最后一个元素

vec.begin();           // 返回指向第一个元素的迭代器
vec.end();             // 返回指向最后一个元素之后的位置的迭代器
vec.rbegin();          // 返回指向最后一个元素的反向迭代器
vec.rend();            // 返回指向第一个元素之前的位置的反向迭代器

vec.size();            // 返回元素个数
vec.empty();           // 检查 vector 是否为空
vec.capacity();        // 返回当前分配的内存容量
vec.reserve(20);       // 请求至少分配 20 个元素的容量
vec.shrink_to_fit();   // 缩减容量以适应当前元素的大小

vec.push_back(10);     // 在末尾添加元素
vec.pop_back();        // 删除末尾元素
vec.insert(vec.begin() + 1, 20); // 在指定位置插入元素
vec.erase(vec.begin() + 1); // 删除指定位置的元素
vec.clear();           // 清空所有元素

std::vector<int> vec = {4, 1, 3, 2, 5};
std::sort(vec.begin(), vec.end()); // 升序排序

auto it = std::find(vec.begin(), vec.end(), 3); // 查找值为 3 的元素 
if (it != vec.end()) { // 找到了 }

int sum = std::accumulate(vec.begin(), vec.end(), 0); // 计算元素之和

std::vector<int> squared(vec.size()); // 
std::transform(vec.begin(), vec.end(), squared.begin(), [](int x) { return x * x; }); // 平方每个元素

vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end()); // 移除所有值为 3 的元素
std::reverse(vec.begin(), vec.end()); // 反转元素顺序

总体而言，std::vector 是 C++ 中一个功能强大且常用的容器，适用于多种场景，提供了高效的元素存储和访问方式。

std::vector 的底层原理

std::vector 是 C++ 标准库中最常用的动态数组容器之一。它在底层实现上采用了一些复杂的技术来管理元素和内存，以便提供高效的操作。以下是对 std::vector 底层原理和扩容过程的详细讲解：

底层数据结构：
- std::vector 内部使用一个动态分配的连续内存块来存储其元素。这个连续内存块称为“数组”，它允许 std::vector 提供高效的随机访问（即通过索引访问）。
成员变量：
- pointer：指向数组的指针，存储了实际的元素数据。
- size：当前 vector 中元素的数量。
- capacity：当前 vector 分配的内存块可以容纳的最大元素数量。

扩容过程

std::vector 的扩容过程涉及到动态内存分配和复制操作。扩容通常在以下情况下发生：

插入元素：当新元素的添加超出了当前容量时，std::vector 会自动进行扩容。
调用 reserve：当显式调用 reserve 函数请求更大的容量时，也会进行扩容。

扩容步骤

检测是否需要扩容：
- 当插入元素时，std::vector 会检查当前的 size 是否超过了 capacity。
- 如果 size 超过 capacity，需要进行扩容。
分配新的内存块：
- 计算新容量：通常，std::vector 会将新容量设置为当前容量的两倍（或者是其他的增长因子），以减少频繁的内存分配操作。
- 分配内存：使用 std::allocator（默认的内存分配器）分配一个新的、更大的内存块。
移动或复制元素：
- 复制构造函数：将旧内存块中的元素逐一复制到新内存块中。
- 移动构造函数（如果元素支持移动语义）：使用移动构造函数将元素从旧内存块移动到新内存块中，以提高效率。
释放旧内存：
- 销毁旧元素：在新内存块中创建元素后，需要销毁旧内存块中的元素（如果有必要）。
- 释放旧内存：释放之前分配的旧内存块。
更新成员变量：
- 更新指针：将 pointer 更新为指向新分配的内存块。
- 更新容量：将 capacity 更新为新的容量值。

扩容示例代码

以下是一个简单的示例，演示了如何在 std::vector 超出当前容量时进行扩容：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 初始容量通常为 0 或某个小的初始值
    std::cout << "Initial capacity: " << vec.capacity() << std::endl;

    // 向 vector 中添加元素，触发扩容
    for (int i = 0; i < 20; ++i) {
        vec.push_back(i);
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }

    return 0;
}

扩容的影响

性能：
- 扩容涉及到内存分配、元素复制或移动等操作，这可能会导致性能开销。因此，预先使用 reserve 函数设置足够的容量可以减少扩容的次数，提高性能。
异常安全性：
- 扩容过程中，复制或移动操作可能会抛出异常，因此在异常情况下，std::vector 必须保证容器的状态一致性（例如，元素不会丢失，旧内存块会被释放）。

总结

std::vector 使用一个动态分配的连续内存块来存储元素。
扩容过程涉及内存分配、元素复制或移动、旧内存释放等步骤。
扩容通常是通过将容量翻倍来减少扩容的次数，从而提高性能。
预先使用 reserve 函数可以减少扩容的次数，优化性能。

理解 std::vector 的底层原理和扩容过程有助于在实际编程中有效地使用它，特别是在需要高效的动态数组操作时。

四、list(链表)

std::list 设计要点：

链表结构：
- std::list 是基于双向链表的容器，每个元素存储在链表的一个节点中，节点通过指针相互连接。
高效的插入和删除：
- std::list 在任何位置插入或删除元素的性能都很高，因为它不需要移动大量元素，也不需要对每个元素进行构造和析构。
双向迭代器：
- std::list 提供了双向迭代器，支持前向和后向遍历。
环状结构：
- std::list 是一个环状的双向链表，符合 STL 对于“前闭后开”的原则。

std::list 实现细节：

节点结构：

std::list 的节点结构包含 prev 和 next 指针，以及存储数据的成员。

template<class T>
struct _list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

迭代器设计：

迭代器是泛化的指针，重载了 ->、--、++、*() 等运算符。它是算法与容器之间的桥梁。

template<class T, class Alloc = alloc>
class list {
protected:
    typedef list_node<T> list_node;
public:
    typedef list_node link_type;
    typedef list_iterator<T, T&, T> iterator;
protected:
    link_type node;
};

迭代器 Traits：

提供了算法对于容器所需的关联类型的信息。对于一般迭代器和指针进行了特化。

#include <iostream>
#include <list>

int main() {
    // 创建一个 std::list<int> 对象
    std::list<int> myList;

    // 向链表尾部插入元素
    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);

    // 使用迭代器遍历链表并打印元素
    std::cout << "Original List: ";
    for (const auto& element : myList) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // 在链表的开头插入元素
    myList.push_front(5);

    // 在链表中间插入元素
    std::list<int>::iterator it = ++myList.begin();
    myList.insert(it, 15);

    // 删除链表中的元素
    myList.pop_back();
    myList.erase(--myList.end());

    // 使用迭代器再次遍历链表并打印元素
    std::cout << "Modified List: ";
    for (const auto& element : myList) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

list 与 vector 的区别：

std::list 和 std::vector 是 C++ 标准库中提供的两种不同类型的容器，它们有不同的特性和使用场景。

1. 内存布局

std::vector：
- 连续内存：std::vector 是一个动态数组，其元素在内存中是连续存储的。每个元素都有固定的内存地址，这使得通过索引访问元素的时间复杂度为。
- 优势：内存连续存储有助于缓存友好性，提高了内存访问速度。
- 劣势：在插入或删除元素时，可能需要重新分配整个内存块，导致性能损失。
std::list：
- 链式存储：std::list 是一个双向链表，每个元素包含一个指向前一个元素和一个指向下一个元素的指针。元素在内存中不必连续存储。
- 优势：插入和删除元素在链表中通常非常高效，只需要调整指针即可。
- 劣势：元素不连续存储导致缓存友好性差，访问元素的时间复杂度为，因为可能需要从头或尾遍历链表。

2. 插入和删除操作

std::vector：
- 插入/删除效率：在 std::vector 的中间位置插入或删除元素可能需要移动大量元素，因此效率较低。如果在末尾插入元素，通常是高效的，但当容量不足时需要重新分配内存。
- 示例：
  1
  2
  3
  std::vector<int> vec = {1, 2, 3, 4};
  vec.insert(vec.begin() + 2, 10); // 插入 10 到索引 2，移动元素
  vec.erase(vec.begin() + 3); // 删除索引 3 的元素

std::list：

插入/删除效率：在链表的任意位置插入或删除元素的效率很高（O(1)），只需调整指针。但需要注意，找到插入位置的效率是 O(n)。

示例：

std::list<int> lst = {1, 2, 3, 4};
auto it = std::next(lst.begin(), 2);
lst.insert(it, 10);  // 在第 2 个位置插入 10
lst.erase(std::next(lst.begin(), 3));  // 删除第 3 个位置的元素

3. 随机访问

std::vector：
- 支持随机访问：由于元素在内存中是连续的，可以使用下标操作符 [] 或 at() 方法快速访问元素（时间复杂度为 O(1)）。
- 示例：
  1
  2
  std::vector<int> vec = {1, 2, 3, 4};
  int value = vec[2]; // 访问索引 2 的元素
std::list：
- 不支持随机访问：链表结构不支持下标访问，必须使用迭代器进行遍历（时间复杂度为 O(n)）。
- 示例：
  1
  2
  3
  std::list<int> lst = {1, 2, 3, 4};
  auto it = std::next(lst.begin(), 2);
  int value = *it; // 访问链表中的第 2 个元素

4. 内存管理

std::vector：
- 动态分配：std::vector 会动态分配内存，支持自动扩展。当需要更多空间时，它会重新分配更大的内存块，并将现有元素复制到新内存块中。
std::list：
- 动态分配：std::list 每个元素都会单独分配内存，内存分配粒度较小。由于链表节点之间的指针开销，可能会导致内存碎片。

5. 适用场景

std::vector：
- 适用于需要频繁访问元素或在末尾进行插入/删除操作的场景。由于其随机访问特性，适合需要快速访问和遍历的应用。
std::list：
- 适用于需要频繁在中间进行插入/删除操作的场景。由于其链表结构，适合需要高效插入和删除的应用，但不需要随机访问。

总结

std::vector：
- 优势：随机访问、高效的尾部操作
- 劣势：中间操作慢、内存重新分配
std::list：
- 优势：高效的插入/删除、内存分配粒度小
- 劣势：随机访问慢、较高的内存开销

五、deque（双端队列）

定义：
- deque 是双端开口的连续线性空间，由分段连续的空间组成。
- 允许在两端高效地进行插入和删除操作。
内部结构：
- 由一块 map（指针数组）作为主控，每个元素是指向另一片连续线性空间（缓冲区）的指针。
- 维护两个迭代器 start 和 finish 分别指向第一个元素和最后一个元素的下一个位置。
- map 的大小是动态变化的，取决于元素数量和缓冲区大小。
迭代器设计：
- deque 的迭代器 _deque_iterator 复杂，支持随机存取，并能处理缓冲区边界情况。
- 实现了常见的迭代器操作，如 operator*、operator++、operator--、operator+、operator- 等。
构造与管理：
- deque 使用两个空间配置器：data_allocator 用于元素内存，map_allocator 用于 map 内存。
- 构造函数 deque(int n, const value_type &value) 用于构造 deque 结构并设初值。
- fill_initialize 和 creat_map_and_node 用于创建和初始化 map 和缓冲区。
插入与删除操作：
- push_back 和 push_front 用于在尾部和头部插入元素。
- 插入操作中，判断是否需要扩充 map，并在缓冲区中插入元素。
- 若插入点在结尾或开头，可能需要跳过缓冲区。
性能比较：
- deque 的插入和删除操作效率较高，不受于缓冲区边界的限制。
- 与 vector 相比，deque 支持快速随机访问，但在处理内部跳转上速度较慢。

总体而言，deque 是一个适用于频繁插入和删除操作的容器，具有一些优势，但在需要高效随机访问时，可能会选择使用 vector。

下面我将通过一些示例来说明如何使用C++标准库中的deque（双端队列）。

示例1：基本操作

#include <iostream>
#include <deque>

int main() {
    // 创建一个空的双端队列
    std::deque<int> myDeque;

    // 在队尾插入元素
    myDeque.push_back(1);
    myDeque.push_back(2);
    myDeque.push_back(3);

    // 在队头插入元素
    myDeque.push_front(0);

    // 遍历输出双端队列
    for (const auto &element : myDeque) {
        std::cout << element << " ";
    }

    std::cout << std::endl;

    // 访问队头和队尾元素
    std::cout << "Front: " << myDeque.front() << std::endl;
    std::cout << "Back: " << myDeque.back() << std::endl;

    // 删除队头元素
    myDeque.pop_front();

    // 删除队尾元素
    myDeque.pop_back();

    // 输出修改后的双端队列
    for (const auto &element : myDeque) {
        std::cout << element << " ";
    }

    return 0;
}

示例2：使用迭代器

#include <iostream>
#include <deque>

int main() {
    std::deque<std::string> myDeque = {"apple", "banana", "cherry"};

    // 使用迭代器遍历输出双端队列
    std::cout << "Deque contents: ";
    for (auto it = myDeque.begin(); it != myDeque.end(); ++it) {
        std::cout << *it << " ";
    }

    std::cout << std::endl;

    // 插入元素到指定位置
    auto it = myDeque.begin() + 1;
    myDeque.insert(it, "orange");

    // 使用范围迭代器删除一部分元素
    myDeque.erase(myDeque.begin(), myDeque.begin() + 2);

    // 输出修改后的双端队列
    std::cout << "Modified deque: ";
    for (const auto &element : myDeque) {
        std::cout << element << " ";
    }

    return 0;
}

这两个示例演示了如何使用deque进行基本操作，包括插入、删除、访问元素等。你可以根据具体需求使用deque来处理数据。在实际应用中，deque通常在需要频繁在队头和队尾进行插入和删除操作的场景中发挥优势。

六、stack && queue

stack 和 queue 是 C++ 标准模板库（STL）中提供的两个常见的容器适配器，它们分别基于不同的底层容器实现，并提供了栈和队列的特定功能。下面对它们进行总结：

stack（栈）

定义：
- stack 是一个后进先出（Last In, First Out，LIFO）的容器适配器。
底层容器：
- 默认情况下，stack 使用 deque 作为底层容器，但可以通过模板参数指定其他容器。
主要操作：
- push(x)：将元素 x 压入栈顶。
- pop()：弹出栈顶元素。
- top()：访问栈顶元素。
特点：
- stack 只提供栈的基本操作，不支持遍历访问。
- 栈的操作复杂度是常数时间。
实现：
- 使用适配器模式，将底层容器的功能封装成栈的接口。

#include <iostream>
#include <stack>

int main() {
    // 创建一个整数类型的栈
    std::stack<int> myStack;

    // 压入元素
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 访问栈顶元素
    std::cout << "Top element: " << myStack.top() << std::endl;

    // 弹出栈顶元素
    myStack.pop();

    // 再次访问栈顶元素
    std::cout << "Top element after pop: " << myStack.top() << std::endl;

    // 检查栈是否为空
    if (myStack.empty()) {
        std::cout << "Stack is empty." << std::endl;
    } else {
        std::cout << "Stack is not empty." << std::endl;
    }

    // 获取栈的大小
    std::cout << "Stack size: " << myStack.size() << std::endl;

    return 0;
}

queue（队列）

定义：
- queue 是一个先进先出（First In, First Out，FIFO）的容器适配器。
底层容器：
- 默认情况下，queue 使用 deque 作为底层容器，但可以通过模板参数指定其他容器。
主要操作：
- push(x)：将元素 x 进入队尾。
- pop()：移除队首元素。
- front()：访问队首元素。
- back()：访问队尾元素。
特点：
- queue 提供队列的基本操作，支持从队尾插入，从队首删除。
- 队列的操作复杂度是常数时间。
实现：
- 使用适配器模式，将底层容器的功能封装成队列的接口。

七、heap && priority_queu

堆（Heap）

堆是一种基于完全二叉树的数据结构，分为大顶堆和小顶堆。在大顶堆中，父节点的值大于或等于其子节点的值；在小顶堆中，父节点的值小于或等于其子节点的值。在STL中，堆常常用于实现优先队列（Priority Queue）。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 创建一个整数类型的堆
    std::vector<int> intHeap = {4, 10, 7, 3, 5};

    // 将vector转换为堆
    std::make_heap(intHeap.begin(), intHeap.end());

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

    // 向堆中添加新元素
    intHeap.push_back(15);
    std::push_heap(intHeap.begin(), intHeap.end());

    std::cout << "Max heap after push: ";
    for (const auto& element : intHeap) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // 弹出堆顶元素
    std::pop_heap(intHeap.begin(), intHeap.end());
    intHeap.pop_back();

    std::cout << "Max heap after pop: ";
    for (const auto& element : intHeap) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

优先队列（Priority Queue）：

优先队列是堆的一种应用，它是一个配接器（Adapter），在STL中使用的底层容器通常是vector。优先队列的特点是按照元素的优先级排列，而非元素被推入队列的顺序。

#include <iostream>
#include <queue>

int main() {
    // 创建一个整数类型的优先队列，默认为大顶堆
    std::priority_queue<int> maxPriorityQueue;

    // 入队
    maxPriorityQueue.push(4);
    maxPriorityQueue.push(10);
    maxPriorityQueue.push(7);
    maxPriorityQueue.push(3);
    maxPriorityQueue.push(5);

    std::cout << "Max priority queue: ";
    while (!maxPriorityQueue.empty()) {
        std::cout << maxPriorityQueue.top() << " ";
        maxPriorityQueue.pop();
    }
    std::cout << std::endl;

    // 创建一个小顶堆（最小堆）
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPriorityQueue;

    // 入队
    minPriorityQueue.push(4);
    minPriorityQueue.push(10);
    minPriorityQueue.push(7);
    minPriorityQueue.push(3);
    minPriorityQueue.push(5);

    std::cout << "Min priority queue: ";
    while (!minPriorityQueue.empty()) {
        std::cout << minPriorityQueue.top() << " ";
        minPriorityQueue.pop();
    }
    std::cout << std::endl;

    return 0;
}

这两个例子分别演示了堆和优先队列的基本操作。堆的操作包括构建堆、添加元素、弹出堆顶元素，而优先队列的操作包括入队、访问队首元素、出队。优先队列默认是大顶堆（任何一个父节点的值都大于或等于其左右子节点的值），也可以通过自定义比较函数来创建小顶堆（任何一个父节点的值都小于或等于其左右子节点的值）。

八、map && set

Map：

概述： std::map 是 C++ 标准库中的关联容器，实现了有序映射，每个元素是一个键值对。
底层实现： 基于红黑树（Balanced Binary Search Tree），元素按照键的顺序排列，保持有序性。
优点：
- 有序性：元素按照键的有序性存储，方便进行范围查找和遍历。
- 提供稳定的查找、删除、插入等操作，时间复杂度为 O(log n)。
缺点：
- 平均性能较慢，与元素数量相关，不适用于频繁插入和删除操作。

#include <iostream>
#include <map>

int main() {
    // 创建一个map，键为字符串，值为整数
    std::map<std::string, int> myMap;

    // 插入元素
    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Charlie"] = 22;

    // 遍历map
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找元素
    auto it = myMap.find("Bob");
    if (it != myMap.end()) {
        std::cout << "Bob's age is: " << it->second << std::endl;
    }

    return 0;
}

2. Set：

概述： std::set 是 C++ 标准库中的关联容器，实现了有序集合，每个元素是唯一的。
底层实现： 同样基于红黑树，保持元素的唯一性，但在实际使用中更强调元素的键。
优点：
- 有序性：元素按照键的有序性存储。
- 提供稳定的查找、删除、插入等操作，时间复杂度为。
缺点：
- 平均性能较慢，与元素数量相关。

#include <iostream>
#include <set>

int main() {
    // 创建一个set，存储整数
    std::set<int> mySet;

    // 插入元素
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);

    // 遍历set
    for (const auto& value : mySet) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = mySet.find(5);
    if (it != mySet.end()) {
        std::cout << "Found 5 in the set." << std::endl;
    }

    return 0;
}

共同点：

都是关联容器，提供高效的查找操作。
内部基于红黑树，支持有序性。

选择使用场景：

使用 map 或 set 取决于是否需要存储键值对。如果只需要存储唯一的元素，而不需要关联值，可以选择 set。
如果需要按键有序存储，或者需要通过键快速查找值，可以选择 map。

3. 红黑树（Red-Black Tree）：

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个额外的属性，即节点的颜色，可以是红色或黑色。这种额外的信息有助于保持树的平衡，使得插入、删除等操作的性能保持在较高水平。

性质：

节点颜色： 每个节点要么是红色，要么是黑色。
根节点： 根节点是黑色。
叶子节点： 空（NIL 或 NULL）叶子节点是黑色。
相邻节点： 不能有两个相邻的红色节点，即红色节点不能连续出现。
路径黑色节点数： 从根节点到任意叶子节点的路径上，经过的黑色节点数量相同。

平衡性：

红黑树的关键在于保持平衡性，确保树的高度为。这样可以保证基本的查找、插入、删除等操作的时间复杂度为。

应用场景：

红黑树被广泛应用于各种编程语言的标准库中，如 C++ STL 中的 std::map 和 std::set 就是基于红黑树实现的。其平衡性和高效性使得它成为一种理想的搜索树结构。

map && unordered_map

Map:

特点：

底层使用红黑树实现，保持元素的有序性。
key-value 对形式存储，关键字起索引作用，值表示和索引相关的数据。

优点：

有序性：元素按关键字有序排列，方便查找和遍历。
查找、删除、增加等一系列操作时间复杂度稳定，都为。

缺点：

操作平均时间复杂度较慢，与 n 相关。

例子：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    myMap[1] = "One";
    myMap[3] = "Three";
    myMap[2] = "Two";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Unordered_map: