C++ STL 容器与算法深度解析

vector 内部结构（三个指针）：

┌──────────────────────────────────────────────────────┐
│  vector<int>                                          │
│  ┌─────────┐                                         │
│  │ _start   │──→┌───┬───┬───┬───┬───┬───┬───┬───┐   │
│  ├─────────┤    │ 1 │ 2 │ 3 │ 4 │ 5 │   │   │   │   │
│  │ _finish  │──→└───┴───┴───┴───┴───┴───┴───┴───┘   │
│  ├─────────┤                        ↑               │
│  │ _end_cap │────────────────────────┘               │
│  └─────────┘                                         │
│                                                      │
│  size() = _finish - _start = 5                       │
│  capacity() = _end_cap - _start = 8                  │
│  空闲空间 = _end_cap - _finish = 3                    │
└──────────────────────────────────────────────────────┘

std::vector<int> v;
v.reserve(1000);          // ✅ 预分配，避免多次扩容

// 扩容的均摊复杂度分析：
// 每次扩容为 2 倍，n 次 push_back 总共拷贝：
// n/2 + n/4 + n/8 + ... ≈ n
// 均摊每次 push_back 为 O(1)

// ⚠️ vector<bool> 不是真正的容器！
std::vector<bool> vb = {true, false, true};

// 内部每个 bool 用 1 bit 存储（而非 1 byte）
// operator[] 返回代理对象，不是 bool&

auto ref = vb[0];         // 类型是 vector<bool>::reference，不是 bool&
bool* ptr = &vb[0];       // ❌ 编译错误！不能取地址

// ✅ 替代方案
std::vector<char> vc;     // 用 char 代替
std::deque<bool> db;      // deque<bool> 是正常的
std::bitset<100> bs;      // 固定大小的位集合

deque 的分段连续存储：

┌──────────┐
│  map 数组  │ （指针数组，指向各个缓冲区）
│  ┌──────┐ │
│  │ ptr0 │─┼──→ ┌───┬───┬───┬───┐  缓冲区 0
│  ├──────┤ │    └───┴───┴───┴───┘
│  │ ptr1 │─┼──→ ┌───┬───┬───┬───┐  缓冲区 1
│  ├──────┤ │    └───┴───┴───┴───┘
│  │ ptr2 │─┼──→ ┌───┬───┬───┬───┐  缓冲区 2
│  ├──────┤ │    └───┴───┴───┴───┘
│  │ ptr3 │─┼──→ ┌───┬───┬───┬───┐  缓冲区 3
│  └──────┘ │    └───┴───┴───┴───┘
└──────────┘

• 每个缓冲区是一段连续内存
• map 是指针数组，管理所有缓冲区
• 头部/尾部插入时，在对应缓冲区操作
• 看起来连续，实际分段 → 支持 O(1) 头尾操作

红黑树示例（map<int, string>）：

            ┌───[7,B]───┐
            │            │
        ┌─[3,R]─┐    ┌─[18,R]─┐
        │       │    │         │
      [1,B]  [5,B] [10,B]   [22,B]
                      │
                   [15,R]

B = 黑色, R = 红色
按 key 有序：1, 3, 5, 7, 10, 15, 18, 22

std::map<std::string, int> m;

// 插入
m["apple"] = 3;                          // operator[]：不存在则创建
m.insert({"banana", 5});                 // insert：已存在则不覆盖
m.insert_or_assign("cherry", 7);         // C++17：覆盖式插入
m.emplace("date", 9);                    // 原地构造
auto [it, ok] = m.try_emplace("fig", 11); // C++17：key 不存在才构造 value

// ⚠️ operator[] 的陷阱
int val = m["unknown"];  // 如果不存在，会插入 {"unknown", 0}！
// ✅ 安全查找
if (auto it = m.find("key"); it != m.end()) {
    int val = it->second;
}
// 或
int val = m.count("key") ? m.at("key") : -1;

// 遍历（C++17 结构化绑定）
for (const auto& [key, value] : m) {
    std::cout << key << ": " << value << "\n";
}

哈希表结构（开链法 / 拉链法）：

bucket 数组:
┌───┐
│ 0 │ → nullptr
├───┤
│ 1 │ → [key1,val1] → [key5,val5] → nullptr
├───┤
│ 2 │ → [key2,val2] → nullptr
├───┤
│ 3 │ → nullptr
├───┤
│ 4 │ → [key3,val3] → [key4,val4] → [key7,val7] → nullptr
├───┤
│ 5 │ → nullptr
├───┤
│ 6 │ → [key6,val6] → nullptr
├───┤
│ 7 │ → nullptr
└───┘

查找过程：
  ① hash(key) % bucket_count → 定位到桶
  ② 在桶的链表中线性查找 key
  ③ 找到 → 返回 value；没找到 → 返回 end()

rehash 触发条件：
  load_factor = size / bucket_count > max_load_factor（默认 1.0）
  → 桶数翻倍，所有元素重新散列

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义 hash
struct PointHash {
    size_t operator()(const Point& p) const {
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // 组合哈希
    }
};

std::unordered_map<Point, std::string, PointHash> pm;
pm[{1, 2}] = "A";

// 大顶堆（默认）
std::priority_queue<int> maxHeap;
maxHeap.push(3); maxHeap.push(1); maxHeap.push(5);
maxHeap.top();  // 5

// 小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(3); minHeap.push(1); minHeap.push(5);
minHeap.top();  // 1

// 自定义比较
auto cmp = [](const auto& a, const auto& b) { return a.cost > b.cost; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> taskQueue(cmp);

// ❌ 错误：erase 后迭代器失效
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == target) vec.erase(it);  // ❌ it 失效
}

// ✅ 方法1：erase 返回下一个有效迭代器
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == target) it = vec.erase(it);
    else ++it;
}

// ✅ 方法2：erase-remove idiom
vec.erase(std::remove(vec.begin(), vec.end(), target), vec.end());

// ✅ 方法3：C++20 std::erase / std::erase_if
std::erase(vec, target);
std::erase_if(vec, [](int x) { return x % 2 == 0; });

std::vector<int> v = {5, 3, 1, 4, 2};

// std::sort —— IntroSort（快排+堆排+插入排序）
std::sort(v.begin(), v.end());                    // 升序
std::sort(v.begin(), v.end(), std::greater<>());  // 降序
// 时间：O(n log n)  空间：O(log n)  不稳定

// std::stable_sort —— 归并排序（内存够时）
std::stable_sort(v.begin(), v.end());
// 时间：O(n log n)  空间：O(n)  稳定

// std::partial_sort —— 堆排序取前 k 个
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// 时间：O(n log k)

// std::nth_element —— 快速选择，第 k 小
std::nth_element(v.begin(), v.begin() + 2, v.end());
// 时间：O(n) 平均

// 线性查找
auto it = std::find(v.begin(), v.end(), 3);         // O(n)
auto it2 = std::find_if(v.begin(), v.end(),
    [](int x) { return x > 3; });                    // O(n)

// 二分查找（需已排序）
bool found = std::binary_search(v.begin(), v.end(), 3);  // O(log n)
auto lb = std::lower_bound(v.begin(), v.end(), 3);       // ≥ 3 的第一个
auto ub = std::upper_bound(v.begin(), v.end(), 3);       // > 3 的第一个
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 3); // 等于 3 的范围

// transform：对每个元素变换
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
std::transform(src.begin(), src.end(), dst.begin(),
    [](int x) { return x * x; });
// dst = {1, 4, 9, 16, 25}

// accumulate：累加/累积
int sum = std::accumulate(src.begin(), src.end(), 0);         // 15
int product = std::accumulate(src.begin(), src.end(), 1,
    std::multiplies<>());                                      // 120

// C++17 reduce（可并行）
int sum2 = std::reduce(src.begin(), src.end(), 0);

// iota：生成递增序列
std::vector<int> seq(10);
std::iota(seq.begin(), seq.end(), 1);  // {1,2,3,...,10}

// generate：自定义生成
int n = 0;
std::generate(seq.begin(), seq.end(), [&n]() { return n++; });

#include <ranges>
#include <vector>
#include <iostream>

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 传统写法
std::vector<int> result;
for (auto x : v) {
    if (x % 2 == 0) {
        result.push_back(x * x);
    }
}

// Ranges 管道写法（C++20）
auto result2 = v
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * x; })
    | std::views::take(3);

for (int x : result2) {
    std::cout << x << " ";  // 4 16 36
}