C++ STL 知识点详解

#include <memory>

// 创建（C++14 推荐 make_unique，C++11 需手动 new）
auto ptr = std::make_unique<int>(42);
auto arr = std::make_unique<int[]>(10);  // 数组版本

// 不支持拷贝
auto ptr2 = ptr;        // ❌ 编译错误

// 支持移动
auto ptr3 = std::move(ptr);  // ✅ 所有权转移到 ptr3，ptr 变为空

// 自定义删除器示例：管理文件句柄
FILE* open_file(const char* path) {
    return std::fopen(path, "r");
}

auto file = std::unique_ptr<FILE, decltype(&std::fclose)>(
    open_file("test.txt"), &std::fclose
);
// 作用域结束时自动调用 fclose

#include <memory>

// 推荐用 make_shared（一次内存分配，性能更好）
auto ptr1 = std::make_shared<int>(42);
auto ptr2 = ptr1;       // ✅ 拷贝，引用计数 +1
{
    auto ptr3 = ptr2;   // ✅ 引用计数 = 3
}                       // ptr3 析构，引用计数 = 2
// ptr1, ptr2 析构后引用计数归零，对象才被释放

// 引用计数查询
auto ptr = std::make_shared<std::string>("hello");
std::cout << ptr.use_count();  // 1
{
    auto ptr2 = ptr;
    std::cout << ptr.use_count();  // 2
}
std::cout << ptr.use_count();  // 1

┌─────────────────────────────────────────────────┐
│                  控制块 (堆上)                    │
│                                                 │
│  强引用计数 (strong_count) ──── shared_ptr 引用它  │
│  弱引用计数 (weak_count)   ──── weak_ptr 引用它    │
│  删除器 (deleter)                                │
│  分配器 (allocator)                              │
│                                                 │
└─────────────────────────────────────────────────┘
         ▲                   ▲
         │                   │
         │ 控制块指针          │ 对象指针
    ┌────┴─────┐        ┌────┴─────┐
    │shared_ptr│        │  对象     │
    │   #1     │        │  (堆上)   │
    └──────────┘        └──────────┘
    ┌────┴─────┐
    │shared_ptr│
    │   #2     │
    └──────────┘
    ┌────┴─────┐
    │weak_ptr  │
    └──────────┘

// 控制块生命周期示意
auto sptr = std::make_shared<int>(42);
// 控制块: strong=1, weak=0

auto wptr = std::weak_ptr<int>(sptr);
// 控制块: strong=1, weak=1

auto sptr2 = sptr;
// 控制块: strong=2, weak=1

sptr2.reset();
// 控制块: strong=1, weak=1  （对象还在）

sptr.reset();
// 控制块: strong=0, weak=1  （对象已释放，但控制块还在！）
// 因为 weak_ptr 还在引用控制块，所以控制块不能销毁

wptr.reset();
// 控制块: strong=0, weak=0  （控制块释放）

// make_shared：一次内存分配
auto ptr1 = std::make_shared<int>(42);
// 堆上布局：[控制块 + 对象] ← 一块连续内存

// new + shared_ptr：至少两次内存分配
auto ptr2 = std::shared_ptr<int>(new int(42));
// 第一次分配：[int 对象]
// 第二次分配：[控制块]

#include <memory>

auto sptr = std::make_shared<int>(42);
std::weak_ptr<int> wptr = sptr;  // weak_ptr 从 shared_ptr 创建

// 访问前必须先升级为 shared_ptr
if (auto locked = wptr.lock()) {  // lock() 返回 shared_ptr
    std::cout << *locked << std::endl;
} else {
    std::cout << "对象已被销毁" << std::endl;
}

// ❌ 循环引用：A 和 B 互相用 shared_ptr 持有对方，引用计数永远不为零
class B;
class A {
public:
    std::shared_ptr<B> b;
    ~A() { std::cout << "A destroyed" << std::endl; }
};
class B {
public:
    std::shared_ptr<A> a;
    ~B() { std::cout << "B destroyed" << std::endl; }
};

// ✅ 用 weak_ptr 打破循环
class B;
class A {
public:
    std::shared_ptr<B> b;
    ~A() { std::cout << "A destroyed" << std::endl; }
};
class B {
public:
    std::weak_ptr<A> a;  // 用 weak_ptr，不增加引用计数
    ~B() { std::cout << "B destroyed" << std::endl; }
};

// 推荐：用 make 工厂函数
auto ptr = std::make_shared<int>(42);   // C++11
auto uptr = std::make_unique<int>(42);  // C++14

// 不推荐：手动 new
auto ptr2 = std::shared_ptr<int>(new int(42));

vector 内部维护三个指针：
┌──────────────┬──────────────┬────────────────┐
│    start     │    finish    │ end_of_storage │
│  指向首元素  │  指向末尾+1  │  指向容量末尾   │
└──────────────┴──────────────┴────────────────┘
  size = finish - start
  capacity = end_of_storage - start

std::vector<int> v;
v.push_back(1);  // 可能触发扩容

std::vector<int> v(5);
v.size();       // 5（当前有 5 个元素）
v.capacity();   // 可能 >= 5（分配的内存容量，实现相关）

std::vector<int> v;

v.reserve(100);   // 预留 100 容量，size 仍是 0，无元素
v.size();         // 0
v.capacity();     // >= 100

v.resize(50);     // 改变 size 为 50，新元素值为 0
v.size();         // 50
v.capacity();     // >= 100（未变）

v.resize(200);    // size 变 200，超过 capacity 触发扩容

           map（指针数组）
        ┌────┬────┬────┬────┬────┐
        │ p0 │ p1 │ p2 │ p3 │ p4 │
        └─┬──┴─┬──┴─┬──┴─┬──┴─┬─┘
          │    │    │    │    │
          ▼    ▼    ▼    ▼    ▼
        ┌───┐┌───┐┌───┐┌───┐┌───┐
        │buf││buf││buf││buf││buf│  每个缓冲区固定大小（如 512 字节）
        └───┘└───┘└───┘└───┘└───┘
        首端                        尾端

#include <deque>

std::deque<int> d;
d.push_front(1);  // ✅ 头端插入，O(1)
d.push_back(2);   // ✅ 尾端插入，O(1)
d[0];             // ✅ 随机访问

#include <map>
#include <unordered_map>

std::map<int, std::string> m;            // 有序，按 key 排序
std::unordered_map<int, std::string> um; // 无序，哈希

m[1] = "one"; m[3] = "three"; m[2] = "two";
for (auto& [k, v] : m) { /* 1, 2, 3 有序 */ }

um[1] = "one"; um[3] = "three"; um[2] = "two";
for (auto& [k, v] : um) { /* 顺序不定 */ }

// 需要范围查询 → map
auto it = m.lower_bound(100);   // 第一个 >= 100 的键

// 只查找 → unordered_map
auto found = um.find(100);      // 平均 O(1)

#include <list>

std::list<int> l;
l.push_back(1);
l.push_front(2);
auto it = l.begin();
++it;
l.insert(it, 10);   // 已知位置插入 O(1)
l.erase(it);        // 删除 O(1)
// l[0];            ❌ 不支持随机访问

// list 的优势场景：频繁中间插入，且迭代器稳定
std::list<int> l = {1, 2, 3, 4, 5};
auto it = l.begin();
++it; ++it;          // 指向 3
l.insert(it, 99);    // O(1)，且其他迭代器不失效

#include <array>
#include <algorithm>

std::array<int, 5> arr = {1, 2, 3, 4, 5};   // 固定大小 5

arr.size();          // 5（编译期已知）
arr[2];              // 随机访问 O(1)，不检查边界
arr.at(2);           // 带边界检查，越界抛 std::out_of_range

// 支持标准库算法
std::sort(arr.begin(), arr.end());

// C++17 结构化绑定（需要 <tuple> 的 get 接口）
auto [a, b, c, d, e] = arr;

// 不会退化为指针，需显式 .data()
int* p = arr.data();   // ✅ 显式拿裸指针
// int* p2 = arr;      // ❌ 编译错误（C 数组则会隐式退化）

// 值语义：整体拷贝
std::array<int, 5> arr2 = arr;   // ✅ 深拷贝每个元素

#include <memory>
#include <thread>
#include <mutex>

std::shared_ptr<int> g;   // 全局共享的 shared_ptr 对象
std::mutex mtx;

// ✅ 方案一：用 std::atomic_load / atomic_store 原子地读写
void reader_atomic() {
    std::shared_ptr<int> p = std::atomic_load(&g);   // 原子读，得到局部副本
    if (p) { /* 使用 p，p 保证对象存活 */ }
}
void writer_atomic() {
    std::shared_ptr<int> p = std::make_shared<int>(42);
    std::atomic_store(&g, p);   // 原子写
}

// ✅ 方案二：加锁保护同一个 shared_ptr 对象
void reader_lock() {
    std::lock_guard<std::mutex> lk(mtx);
    std::shared_ptr<int> p = g;   // 加锁后安全读
}

// ✅ 各线程持有自己的副本 → 引用计数原子增减，天然安全
void worker() {
    std::shared_ptr<int> local = std::make_shared<int>(1);
    auto another = local;      // 只动原子引用计数
    // ... 拷贝/析构都安全
}

#include <memory>

// ❌ 错误：从裸 this 构造 shared_ptr → 两个控制块 → double free
class Bad {
public:
    std::shared_ptr<Bad> get_shared() {
        return std::shared_ptr<Bad>(this);   // 新建控制块，与外部已有的 shared_ptr 不共享
    }
};

// ✅ 正确：继承 enable_shared_from_this，用 shared_from_this()
class Good : public std::enable_shared_from_this<Good> {
public:
    std::shared_ptr<Good> get_shared() {
        return shared_from_this();   // 返回共享同一个控制块的 shared_ptr
    }
};

auto w = std::make_shared<Good>();
auto w2 = w->get_shared();   // w2 与 w 共享同一控制块，use_count == 2
std::cout << w.use_count();  // 2

#include <string>
#include <iostream>

std::string s1 = "hi";           // 短字符串 → SSO，存在对象内部，无堆分配
std::string s2(1000, 'a');       // 长字符串 → 堆分配

std::cout << s1.capacity();      // 如 15（实现相关，SSO 缓冲区大小）
std::cout << s2.capacity();      // >= 1000

// 小字符串的数据在对象内部，长字符串的数据在堆上
std::cout << static_cast<const void*>(s1.data());  // 指向对象内部
std::cout << static_cast<const void*>(s2.data());  // 指向堆

#include <vector>
#include <string>

struct Point {
    int x, y;
    Point(int a, int b) : x(a), y(b) {}
};

std::vector<Point> v;
v.push_back(Point(1, 2));   // 先构造临时 Point(1,2)，再移动进 vector
v.emplace_back(1, 2);       // 直接用 (1,2) 在 vector 末尾原地构造，无临时对象

// 复杂/昂贵类型差距更明显
std::vector<std::string> vs;
vs.push_back(std::string(10, 'a'));  // 先构造临时 string，再移动
vs.emplace_back(10, 'a');            // 直接原地构造 string(10,'a')

#include <vector>
#include <list>
#include <algorithm>

// 指针：指向连续内存的数组
int arr[] = {1, 2, 3};
int* p = arr;
*(p + 1);            // 2（指针支持 +n 随机访问）

// vector 迭代器：连续内存，随机访问（常实现为指针）
std::vector<int> v = {1, 2, 3};
auto vit = v.begin();
*(vit + 1);          // 2，随机访问迭代器支持 +n

// list 迭代器：非连续内存，只能 ++/--，不支持 +n
std::list<int> l = {1, 2, 3};
auto lit = l.begin();
++lit;               // ✅ 双向迭代器支持 ++
// *(lit + 1);      // ❌ list 迭代器不支持随机访问

// 指针可作为迭代器直接用于算法
std::sort(arr, arr + 3);   // 数组指针满足随机访问迭代器要求

#include <algorithm>
#include <vector>
#include <functional>

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

std::sort(v.begin(), v.end());                       // 默认升序，introsort
std::sort(v.begin(), v.end(), std::greater<int>());  // 自定义比较器

// introsort 的思路（示意）：
// 1. 区间较小时 → 插入排序
// 2. 递归深度 > 2*log2(n) → 堆排序
// 3. 否则 → 快速排序（三数取中选 pivot）

#include <optional>
#include <vector>
#include <iostream>

// 查找：找不到时返回空 optional，而不是返回 -1 或空指针
std::optional<int> find_even(const std::vector<int>& v) {
    for (int x : v) {
        if (x % 2 == 0) return x;   // 隐式构造 optional<int>
    }
    return std::nullopt;            // 显式"无值"
}

auto r = find_even({1, 3, 5});
if (r) {                            // 判断是否有值
    std::cout << *r << std::endl;   // 解引用取值
}
std::cout << r.value_or(-1) << std::endl;   // 无值时给默认值 -1

#include <variant>
#include <string>
#include <iostream>
#include <type_traits>

std::variant<int, std::string> v;

v = 42;                                  // 现在是 int
std::cout << std::get<int>(v);           // 42
std::cout << v.index();                  // 0（当前是第 0 个类型 int）

v = std::string("hello");                // 现在是 string
std::cout << std::get<1>(v);             // 按索引取值：hello
// std::get<int>(v);                     // ❌ 当前是 string，抛 std::bad_variant_access

// std::visit：统一处理所有可能类型
std::visit([](auto&& arg) {
    using T = std::decay_t<decltype(arg)>;
    if constexpr (std::is_same_v<T, int>)
        std::cout << "int: " << arg;
    else
        std::cout << "string: " << arg;
}, v);

#include <any>
#include <string>
#include <vector>
#include <iostream>

std::any a;

a = 42;                            // 存 int
a = std::string("hello");          // 换成 string，类型可任意变化
a = std::vector<int>{1, 2, 3};     // 换成 vector

std::cout << std::any_cast<std::string>(a).size();  // 需要知道当前类型才能取值
// std::any_cast<int>(a);          // ❌ 当前不是 int，抛 std::bad_any_cast

#include <string_view>
#include <string>
#include <iostream>

std::string s = "hello world";

std::string_view sv = s;            // 只存指针+长度，不拷贝字符串
std::cout << sv;                    // hello world
std::cout << sv.size();             // 11

// 零拷贝切片：substr 只移动指针、改长度，不新建字符串
std::string_view sub = sv.substr(0, 5);   // "hello"，O(1)，无分配
std::cout << sub;                   // hello

// 直接指向字符串字面量，也无拷贝
std::string_view lit = "hello";     // 不分配、不拷贝

// 用 string_view 做参数：接受 string / const char* / 字面量，均零拷贝
void print(std::string_view s) {
    std::cout << s;
}
print(std::string("abc"));   // 隐式转 string_view，不拷贝
print("abc");                // 直接是 string_view

#include <string_view>
#include <string>
#include <cstdio>

// ❌ 坑一：悬垂引用——view 指向临时 string，临时对象析构后 view 悬空
std::string_view make_view() {
    std::string s = "temporary";
    return s;             // 隐式转 string_view，但 s 在返回后析构 → 悬垂！
}

// ❌ 坑二/三：string_view 不保证 \0，不能直接给 printf
std::string s = "hello world";
std::string_view sv = s;
std::string_view sub = sv.substr(0, 5);   // "hello"，但 sub 后面不是 \0
// printf("%s", sub);          // ❌ 不能隐式转 const char*，且不保证 \0 结尾
printf("%.*s", (int)sub.size(), sub.data());  // ✅ 显式用长度打印

#include <set>
#include <iostream>

std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(3);          // 重复插入无效，set 只保留一个 3
for (int x : s) { /* 输出 1, 3，有序且去重 */ }

std::multiset<int> ms;
ms.insert(3);
ms.insert(1);
ms.insert(3);          // 允许重复，ms 里有两个 3
for (int x : ms) { /* 输出 1, 3, 3，有序但可重复 */ }

// multiset 统计与查找
ms.count(3);                       // 2（出现次数）
auto range = ms.equal_range(3);    // 返回 [first, last)，覆盖所有等于 3 的元素

// 场景一：去重排序
std::set<int> unique_sorted = {5, 1, 5, 3, 1};
// 遍历得到 1, 3, 5（自动去重 + 升序）

// 场景二：允许重复的有序序列
std::multiset<int> ms2 = {100, 95, 100, 88};
ms2.erase(ms2.find(100));   // 只删除一个 100
// ms2.erase(100);          // 注意：会删除所有 100

#include <vector>
#include <list>
#include <set>
#include <unordered_map>

// ❌ vector：push_back 触发扩容后，旧迭代器失效
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);          // 可能扩容 → it 失效
// *it;                  // ❌ 未定义行为

// ❌ vector：中间删除，删除点之后全部失效
auto it2 = v.begin() + 2;
v.erase(it2);            // it2 及其之后的迭代器失效
// 正确做法：用 erase 的返回值继续遍历
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);   // erase 返回下一个有效迭代器
    else ++it;
}

// ✅ list：插入删除不影响其他迭代器
std::list<int> l = {1, 2, 3};
auto lit = l.begin();
++lit;                   // 指向 2
l.erase(lit);            // 只 lit 失效，其他仍有效

// ✅ set：删除只使被删迭代器失效
std::set<int> s = {1, 2, 3};
auto sit = s.find(2);
s.erase(sit);            // 只 sit 失效

// ❌ unordered_map：rehash 导致全部失效
std::unordered_map<int, int> um;
um.reserve(100);         // 提前预留，避免后续 rehash 失效

#include <memory>
#include <new>
#include <utility>

// 自定义 allocator 的核心接口示意
template <class T>
struct MyAllocator {
    using value_type = T;

    // 分配 n 个 T 的裸内存（不构造对象）
    T* allocate(std::size_t n) {
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    // 释放裸内存（不析构对象）
    void deallocate(T* p, std::size_t) {
        ::operator delete(p);
    }
    // 在 p 处原地构造对象
    template <class U, class... Args>
    void construct(U* p, Args&&... args) {
        ::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
    }
    // 析构对象（不释放内存）
    template <class U>
    void destroy(U* p) {
        p->~U();
    }
};

// 二级配置器思想示意（简化）
// 16 条自由链表：8, 16, 24, ..., 128 字节
// 分配 30 字节 → 向上取整到 32 字节档 → 从 32 字节链表取一块
// 释放 30 字节 → 挂回 32 字节链表，供后续复用