C++特性

1. std::execution/coroutine结合

核心概念

在深入代码之前，我们先了解几个关键概念：

1. 执行上下文 (Execution Context): 代表了可以执行工作的“地方”，例如一个线程池、一个 I/O 事件循环或一个 GPU 流。
2. 调度器 (Scheduler): 一个轻量级的句柄，代表了一个执行上下文。它的主要职责是创建一个“调度发送者”（Schedule Sender）。
3. 发送者 (Sender): 一个描述异步操作的类型。它知道如何启动一个操作，但本身并不执行任何工作。它像一个“蓝图”。
4. 接收者 (Receiver): 一个“回调”的泛化，定义了当异步操作完成时（成功、失败或取消）应该做什么。
5. 操作状态 (Operation State): 通过 std::execution::connect 将一个发送者和一个接收者连接起来所创建的对象。这个对象封装了执行操作所需的所有状态，并通过调用 std::execution::start 来启动。
6. 协程 (co_await): 在我们的设计中，协程将作为连接发送者和接收者的桥梁，管理工作的提交和执行流程。

使用协程实现的调度器

我们的目标是创建一个在后台使用一个或多个工作线程的线程池调度器。当 schedule() 被调用时，它返回的发送者会将工作单元（一个函数）提交给这个线程池，并利用协程来等待其执行完成。

1. 简单的线程池执行上下文

首先，我们定义一个简单的线程池作为我们的执行上下文。它包含一个线程队列和一个用于分派任务的 std::vector<std::jthread>。

#include <iostream>
#include <vector>
#include <thread>
#include <functional>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <concepts>

class simple_thread_pool {
public:
    explicit simple_thread_pool(std::size_t thread_count = std::thread::hardware_concurrency()) {
        for (std::size_t i = 0; i < thread_count; ++i) {
            threads_.emplace_back([this] { worker_thread(); });
        }
    }

    ~simple_thread_pool() {
        {
            std::unique_lock lock(mutex_);
            stop_ = true;
        }
        cv_.notify_all();
    }

    void submit(std::function<void()> work) {
        {
            std::unique_lock lock(mutex_);
            work_queue_.push(std::move(work));
        }
        cv_.notify_one();
    }

private:
    void worker_thread() {
        while (true) {
            std::function<void()> work;
            {
                std::unique_lock lock(mutex_);
                cv_.wait(lock, [this] { return stop_ || !work_queue_.empty(); });
                if (stop_ && work_queue_.empty()) {
                    return;
                }
                work = std::move(work_queue_.front());
                work_queue_.pop();
            }
            work();
        }
    }

    std::vector<std::jthread> threads_;
    std::queue<std::function<void()>> work_queue_;
    std::mutex mutex_;
    std::condition_variable cv_;
    bool stop_{false};
};

2. 协程任务类型 (task)

我们将定义一个简单的协程任务类型。当这个任务被 co_await 时，它会将等待它的协程句柄提交给线程池。

#include <coroutine>

// 前向声明
struct coroutine_scheduler;

struct task {
    struct promise_type;
    using handle_type = std::coroutine_handle<promise_type>;

    struct promise_type {
        task get_return_object() { return {handle_type::from_promise(*this)}; }
        std::suspend_always initial_suspend() noexcept { return {}; }
        std::suspend_always final_suspend() noexcept { return {}; }
        void return_void() {}
        void unhandled_exception() { std::terminate(); }
    };

    handle_type handle;
};

struct schedule_awaiter {
    coroutine_scheduler& scheduler_;

    bool await_ready() noexcept { return false; }
    void await_suspend(std::coroutine_handle<> h); // 实现将移至 scheduler 定义之后
    void await_resume() noexcept {}
};

3. 协程调度器 (coroutine_scheduler)

这是我们设计的核心。它持有对线程池的引用，并提供 schedule() 方法来创建一个发送者。

#include <execution> // 假设的 C++26 头文件

// 调度器需要满足 std::execution::scheduler 概念
struct coroutine_scheduler {
    simple_thread_pool& pool_;

    // schedule() 返回一个发送者
    auto schedule() const noexcept;

    // 提交协程句柄
    void submit(std::coroutine_handle<> h) {
        pool_.submit([h]() mutable { h.resume(); });
    }

    // 重载以支持我们的awaiter
    schedule_awaiter operator co_await() { return {*this}; }

    // 为了满足概念，需要定义相等比较
    bool operator==(const coroutine_scheduler&) const = default;
};

// await_suspend 的实现
void schedule_awaiter::await_suspend(std::coroutine_handle<> h) {
    scheduler_.submit(h);
}

4. 调度发送者 (schedule_sender)

当调用 coroutine_scheduler::schedule() 时，会返回此类型的对象。它持有调度器的引用。

template <typename Receiver>
struct coroutine_operation_state {
    // ... 实现将在下一步 ...
};

struct schedule_sender {
    using is_sender = void; // 标记这是一个发送者
    coroutine_scheduler scheduler_;

    // 定义此发送者可以发送的值、错误和停止信号的类型
    template <template <typename...> class Tuple, template <typename...> class Variant>
    using value_types = Variant<Tuple<>>;

    template <template <typename...> class Variant>
    using error_types = Variant<std::exception_ptr>;

    using sends_done = std::true_type;

    // `connect` 方法将发送者和接收者连接起来，创建操作状态
    template <std::execution::receiver Receiver>
    auto connect(Receiver&& r) && {
        return coroutine_operation_state<std::decay_t<Receiver>>{
            scheduler_, std::forward<Receiver>(r)
        };
    }
};

// coroutine_scheduler::schedule() 的实现
auto coroutine_scheduler::schedule() const noexcept {
    return schedule_sender{*this};
}

5. 协程驱动的操作状态 (coroutine_operation_state)

这是最精妙的部分。connect 的结果是一个操作状态对象。当 start() 被调用时，它会启动一个协程。这个协程 co_await 我们的调度器，从而将后续的执行（即调用接收者的 set_value）提交到线程池中。

template <std::execution::receiver Receiver>
struct coroutine_operation_state {
    coroutine_scheduler scheduler_;
    Receiver receiver_;

    // 启动操作的协程
    task run() {
        try {
            // 关键点：等待调度器，这将使协程的剩余部分
            // 在线程池的某个线程上恢复执行。
            co_await scheduler_; 

            // 在线程池的线程上，调用接收者的 set_value
            std::execution::set_value(std::move(receiver_));
        } catch (...) {
            std::execution::set_error(std::move(receiver_), std::current_exception());
        }
    }

    // `start()` 启动协程
    void start() & noexcept {
        // 创建协程，但它会立即在 initial_suspend 处暂停
        task t = run(); 
        // 恢复协程，执行到 co_await scheduler_
        t.handle.resume(); 
    }
};

完整示例与使用

现在，我们将所有部分组合在一起，并展示如何使用这个由协程驱动的调度器。

int main() {
    std::cout << "Main thread ID: " << std::this_thread::get_id() << std::endl;

    // 1. 创建执行上下文
    simple_thread_pool pool(4);

    // 2. 创建调度器
    coroutine_scheduler scheduler{pool};

    // 3. 从调度器获取一个发送者
    auto work_sender = scheduler.schedule();

    // 4. 定义一个接收者
    auto my_receiver = std::execution::then(
        work_sender,
        [] {
            std::cout << "Work executed on thread ID: " << std::this_thread::get_id() << std::endl;
        }
    );

    // 5. 使用 std::this_thread::sync_wait 等待操作完成
    // sync_wait 会连接(connect)并启动(start)发送者，并阻塞直到操作完成
    std::this_thread::sync_wait(std::move(my_receiver));

    return 0;
}

编译与运行（假设的 C++26 环境）:

如果在一个支持 std::execution 的未来 C++26 编译器中编译此代码，预期的输出将是：

Main thread ID: <ID_of_main_thread>
Work executed on thread ID: <ID_of_a_pool_thread>

这清楚地表明，通过我们的协程调度器，工作被成功地从主线程转移到了线程池中的一个工作线程上执行。

结论

这个例子展示了协程如何能被用作实现 std::execution 调度器内部机制的强大工具。通过在操作状态中启动一个协程并 co_await 调度器本身，我们能够以一种声明式且高度可读的方式，将执行流无缝地转移到目标执行上下文。

这种设计不仅优雅，而且充分利用了 C++20 协程的优势，将底层的回调和句柄管理封装在 task 和 awaiter 的实现细节中。随着 C++26 的到来，我们有理由相信，这种协程与 std::execution 的深度集成将成为构建高性能、可扩展的异步系统的标准模式。

注解

• scheduler包sender，sender包operation_state，opration_state通过协程切换上下文到线程池中。

• 协程池不好实现，因为无栈协程，和主线程共享同一份栈，不支持子调用中co_await

2. 合约

3. 静态反射

rust如何打印枚举类型的名称？通过debug萃取，编译器插桩

4. multimap/unordered_multimap

(12 封私信 / 81 条消息) GCC中unordered_(multi)set/map的实现原理 （Part 1 继承体系) - 知乎

GCC中unordered_(multi)set/map的实现原理 （Part 2 图解哈希表结构) - 知乎

4.1 unordered_multimap

好的，这是一个非常核心的C++ STL问题。std::unordered_multimap 的底层实现是基于一个改良的哈希表。

下面我们来详细分解它的实现机制和关键组成部分。

核心思想：哈希表

哈希表的核心思想是通过一个哈希函数，将键（Key）映射到数组的某个索引位置。理想情况下，这个操作是常数时间O(1)的。

具体实现细节

1. 数据结构：数组 + 链表（或其它桶结构）

std::unordered_multimap 的内部维护了一个动态数组，这个数组的每个元素通常被称为一个 “桶”（Bucket）。

• 桶数组：一个 std::vector 或其他类似的动态数组，存储着桶的头部指针。
• 桶内的链表：每个桶本身不是一个直接存储元素的位置，而是一个链表的头节点。这个链表用于存储所有哈希到同一个桶中的元素。

由于 unordered_multimap 允许重复的键，所以当不同的键值对经过哈希函数计算后，可能会得到同一个桶索引（这称为哈希冲突）。同时，即使键相同（这是允许的），它们也会被放入同一个桶中。

2. 节点存储的内容

哈希表中的每个节点（即链表的一个节点）至少存储以下内容：

• Key： 元素的键。
• Value： 元素的值。
• 哈希值缓存： 大多数实现（如GCC的libstdc++和LLVM的libc++）会存储键的哈希值。这避免了在重新哈希（Resize）或查找时需要重复计算哈希值，提高了效率。
• 下一个节点的指针： 指向链表中下一个节点的指针。

3. 工作流程

a. 插入操作 insert({key, value})

1. 计算哈希值： 对键 key 使用哈希函数 std::hash<Key> 计算其哈希值 hash_code。
2. 确定桶索引： 通过 hash_code % bucket_count 计算这个键值对应该放在哪个桶中。
3. 在桶中插入：
   • 找到对应的桶（即数组索引）。
   • 创建一个新的节点，存储键、值和哈希值。
   • 将这个新节点插入到链表的头部（这是一个O(1)操作）。注意，标准不规定插入到链表的哪个位置，但头插法是最高效的。

b. 查找操作 find(key) / equal_range(key)

1. 计算哈希值： 对键 key 计算哈希值。
2. 确定桶索引： hash_code % bucket_count。
3. 遍历桶内链表：
   • 找到对应的桶。
   • 遍历该桶内的链表，使用 key 的 == 运算符与链表中的每个节点的键进行比较。
   • 对于 find，返回第一个匹配的迭代器。
   • 对于 equal_range，返回一个迭代器对 [begin, end)，包含所有匹配的键值对。这正是它支持重复键的关键。

c. 删除操作 erase(key)

1. 同样先定位到正确的桶。
2. 遍历链表，删除所有键等于 key 的节点。

4. 负载因子与重新哈希

为了保持哈希表的高效性，必须控制桶中链表的平均长度。

• 负载因子： load_factor = size / bucket_count。即元素总数除以桶的数量。它衡量了哈希表的“拥挤程度”。
• 最大负载因子： 有一个默认值（通常是1.0），你可以通过 max_load_factor() 成员函数获取和设置。
• 重新哈希： 当 load_factor > max_load_factor 时，容器会自动进行重新哈希：
  1. 创建一个新的、更大的桶数组（通常是原来的两倍左右的一个质数大小）。
  2. 遍历旧哈希表中的每一个节点。
  3. 对于每个节点，根据其缓存的哈希值和新的桶数量，重新计算其在新数组中的桶索引：new_bucket_index = cached_hash_code % new_bucket_count。
  4. 将节点移动到新的桶数组中。
     这个过程是昂贵的，平均时间复杂度为O(n)，但能保证后续操作的效率。

现代实现的优化：桶内单链表 + 桶间指针数组

上面描述的是最经典的“拉链法”实现。在现代的STL实现（如libc++, libstdc++）中，为了优化缓存性能，通常采用一种更为紧凑的结构：

• 所有节点被存储在一个连续的数组中（一个 std::vector），每个节点包含键、值、哈希值和指向下一个节点的索引（而不是指针）。
• 桶数组本身也是一个数组，但它存储的是指向第一个节点的索引（或指针）。

这种设计减少了动态内存分配的次数，并提高了数据的内存局部性，对CPU缓存更友好。

总结：std::unordered_multimap 的特点

特性	底层实现原因
无序性	元素在哈希表中的存储位置由哈希值决定，与插入顺序无关。
平均O(1)的查找、插入、删除	基于哈希表，在负载因子可控的情况下，平均复杂度为常数。
最差O(n)的复杂度	所有元素都哈希到同一个桶中，退化为一个链表。
允许重复键	哈希冲突的链表天然支持存储多个具有相同键的元素。
迭代器失效	插入操作可能导致重新哈希，使所有迭代器失效；在特定桶中插入或删除，只会使该桶的迭代器失效。

简单来说，你可以把 std::unordered_multimap 想象成一个有很多“抽屉”（桶）的柜子。当你需要存一个东西时，你用钥匙（键）算出一个号码（哈希值），根据号码找到对应的抽屉，然后把东西扔进去。允许重复键意味着同一个抽屉里可以放多个标签相同的东西。当抽屉太满时，管理员（重新哈希）会换一个更大的柜子，并把所有东西重新整理一遍。

4.2 unordered_map/unordered_multimap

共同的基础实现

unordered_map 和 unordered_multimap 都采用：

• 桶数组：一个动态数组，每个元素是一个”桶”
• 桶内结构：每个桶包含一个链表（或类似结构），存储哈希到该桶的所有元素

// 两者都类似这样的结构
vector<forward_list<pair<Key, Value>>> buckets;

性能差异的真正原因

性能差异主要来自处理重复键的方式，而不是底层数据结构：

操作	unordered_map	unordered_multimap	性能影响
查找	找到第一个匹配项就返回	可能需要遍历所有重复键	multimap 可能更慢
插入	需要检查键是否已存在	直接插入，无需检查重复	multimap 可能更快
删除	删除第一个匹配项就返回	需要删除所有匹配的重复键	multimap 可能更慢

为什么没有用纯数组实现？

如果 multimap 在桶内使用纯数组，确实会有一些问题：

1. 插入性能问题：数组插入需要移动元素，O(n)复杂度
2. 内存浪费：需要预分配空间或频繁重新分配
3. 删除性能差：从数组中删除元素需要移动后续元素

现代实现的优化趋势

实际上，现代STL实现（如libc++、libstdc++）对两者都采用类似的优化策略：

1. 单链表（最常用）

// 两者都使用类似的结构
struct Node {
    Key key;
    Value value;
    size_t cached_hash;
    Node* next;
};

2. 小桶优化

对于元素数量很少的桶，有些实现会使用小数组内联存储，避免动态分配：

// 某些实现的优化：小桶使用内联数组，大桶使用链表
union BucketStorage {
    Node* list_head;           // 用于大桶
    InlineArray inline_data;   // 用于小桶（如前2-4个元素）
};

3. 开放寻址的变种

一些非标准但高性能的哈希表实现可能对两者都使用开放寻址：

// 伪代码：开放寻址方案
vector<optional<pair<Key, Value>>> table;
// multimap 需要额外的逻辑来处理重复键

性能对比总结

unordered_multimap 的性能特点：

• ✅ 插入可能更快：不需要检查键是否重复
• ❌ 查找通常更慢：需要处理多个相同键的元素
• ❌ 删除可能更慢：需要删除所有匹配项
• ❌ 内存使用可能更多：存储重复键的开销

unordered_map 的性能特点：

• ❌ 插入可能稍慢：需要检查键是否已存在
• ✅ 查找通常更快：找到第一个匹配项即可返回
• ✅ 删除通常更快：只需删除一个元素
• ✅ 内存使用更少：每个键只存储一次

实际建议

1. 如果不允许重复键：使用 unordered_map，性能更好
2. 如果需要重复键：使用 unordered_multimap，这是语义需求
3. 考虑替代方案：有时 unordered_map<Key, vector<Value>> 在某些场景性能更好

结论：两者的底层实现是相似的，性能差异主要来自处理重复键的逻辑不同，而不是数据结构本身的差异。选择哪个应该基于是否需要重复键的语义，而不是性能考虑。

4.3 unordered_multimap: equal_range

方案1：维护相同键的连续性（主流实现）

大多数标准库实现选择在插入时维护相同键的连续性：

iterator insert(const value_type& value) {
    size_t hash = hasher_(value.first);
    size_t bucket_idx = hash % buckets_.size();

    Node* current = buckets_[bucket_idx];
    Node* prev = nullptr;

    // 查找插入位置：找到第一个相同键的元素，或者找到插入点
    while (current != nullptr && current->key != value.first) {
        prev = current;
        current = current->next;
    }

    // 创建新节点
    Node* new_node = create_node(value, hash);

    if (current != nullptr) {
        // 找到相同键的元素，插入到该序列的末尾
        Node* last_same_key = current;
        while (last_same_key->next != nullptr && 
               last_same_key->next->key == value.first) {
            last_same_key = last_same_key->next;
        }
        new_node->next = last_same_key->next;
        last_same_key->next = new_node;
    } else {
        // 没有相同键的元素，插入到链表末尾或头部
        if (prev == nullptr) {
            // 空桶，插入头部
            new_node->next = buckets_[bucket_idx];
            buckets_[bucket_idx] = new_node;
        } else {
            // 非空桶，插入到末尾
            new_node->next = prev->next;
            prev->next = new_node;
        }
    }

    return iterator(new_node, this);
}

方案2：不保证连续性，equal_range 遍历整个桶

有些实现选择牺牲 equal_range 的性能来保证插入性能：

std::pair<iterator, iterator> equal_range(const Key& key) {
    size_t hash = hasher_(key);
    size_t bucket_idx = hash % buckets_.size();

    // 必须遍历整个桶来收集所有匹配的元素
    std::vector<Node*> matches;
    Node* current = buckets_[bucket_idx];

    while (current != nullptr) {
        if (current->key == key) {
            matches.push_back(current);
        }
        current = current->next;
    }

    if (matches.empty()) {
        return std::make_pair(end(), end());
    }

    // 返回第一个和最后一个匹配元素的迭代器
    return std::make_pair(iterator(matches.front(), this), 
                         iterator(matches.back()->next, this));
}

但这种方案的 equal_range 复杂度是 O(桶大小) 而不是 O(重复键数量)。

主流标准库的实现策略

GCC (libstdc++) 的实现

GCC 的实现实际上维护相同键的连续性：

• 插入时找到相同键的序列，插入到该序列的适当位置
• 保证相同键的元素在链表中连续存储
• 这样可以实现高效的 equal_range

LLVM (libc++) 的实现

libc++ 也采用类似策略，但可能有不同的优化：

• 通常维护相同键的连续性
• 可能对小桶使用不同策略

性能权衡

维护连续性的代价

// 插入性能分析
void insert_performance() {
    // 情况1：插入新键 - O(桶大小)，需要遍历找到插入位置
    // 情况2：插入重复键 - O(重复键数量)，需要找到相同键序列的末尾
    // 最坏情况：O(n)
    // 平均情况：良好哈希函数下 O(1)
}

不维护连续性的代价

// equal_range 性能分析  
void equal_range_performance() {
    // 情况1：维护连续性 - O(重复键数量)
    // 情况2：不维护连续性 - O(桶大小)
    // 对于查找密集型应用，这可能是不可接受的
}

实际的 equal_range 实现（维护连续性时）

std::pair<iterator, iterator> equal_range(const Key& key) {
    size_t hash = hasher_(key);
    size_t bucket_idx = hash % buckets_.size();

    Node* current = buckets_[bucket_idx];
    Node* first_match = nullptr;
    Node* last_match = nullptr;

    // 遍历找到第一个匹配的键
    while (current != nullptr && current->key != key) {
        current = current->next;
    }

    if (current == nullptr) {
        return std::make_pair(end(), end());
    }

    // 找到了第一个匹配项
    first_match = current;

    // 继续遍历直到键不匹配（由于维护了连续性，这很快）
    while (current != nullptr && current->key == key) {
        last_match = current;
        current = current->next;
    }

    return std::make_pair(iterator(first_match, this),
                         iterator(last_match->next, this));
}

总结

关键结论：

• ✅ 主流实现确实维护相同键的连续性，即使这意味着插入时可能需要更多工作
• ✅ 这样保证了 equal_range 的高效性（O(重复键数量)）
• ✅ 插入性能的轻微下降被认为是可接受的权衡
• ❌ 如果不在插入时维护连续性，equal_range 将需要遍历整个桶

所以您的质疑是完全正确的——如果简单地总是在头部插入，确实无法保证 equal_range 的连续性和高效性。实际的实现通过更智能的插入策略来解决这个问题。

4.4 multimap

您指出了一个非常重要的C++标准要求！确实，C++标准明确规定了multimap中相同键元素的插入顺序必须被保持。让我详细解释这是如何实现的。

C++标准的要求

根据C++标准（§26.4.6.2）：

• emplace 和无提示的 insert 总是插入到上限(upper bound)
• 在等效范围内，等效元素的顺序是插入顺序
• 只有使用提示的 insert 或 emplace_hint 才可能改变这个顺序

实现方案：基于时间戳的比较

为了满足这个要求，主流实现通常采用方法1的变种：时间戳比较法

核心实现

template<typename Key, typename Value>
class multimap {
private:
    // 每个节点存储插入顺序信息
    struct Node {
        Key key;
        Value value;
        uint64_t insertion_order;  // 插入时间戳
        // ... 红黑树节点其他字段
    };

    static std::atomic<uint64_t> global_counter_;  // 全局插入计数器

    // 比较函数考虑插入顺序
    struct Compare {
        bool operator()(const Node* a, const Node* b) const {
            // 首先比较键
            if (a->key < b->key) return true;
            if (b->key < a->key) return false;

            // 键相等时，比较插入顺序（后插入的"更大"）
            return a->insertion_order < b->insertion_order;
        }
    };

    RBTree<Node, Compare> tree_;

public:
    iterator insert(const value_type& value) {
        return emplace(value.first, value.second);
    }

    template<typename... Args>
    iterator emplace(Args&&... args) {
        // 分配新节点
        Node* new_node = allocate_node(std::forward<Args>(args)...);

        // 分配插入顺序标识（总是递增）
        new_node->insertion_order = global_counter_++;

        // 插入到红黑树中
        // 由于比较函数考虑插入顺序，新节点会自动插入到相同键区域的末尾
        return tree_.insert_equal(new_node);
    }

    // 带提示的插入
    iterator insert(const_iterator hint, const value_type& value) {
        // 实现提示插入逻辑...
    }
};

为什么这样满足”插入到上限”

在比较函数中：

• 当键相等时，插入顺序更大的节点被认为”更大”
• 因此新插入的节点在相同键的范围内总是被认为是”最大”的
• 在红黑树的有序遍历中，新节点会出现在相同键区域的末尾

这正好符合”插入到上限”的要求。

具体插入过程示例

假设我们按顺序插入：

1. insert(1, "a") - insertion_order = 0
2. insert(2, "b") - insertion_order = 1
3. insert(1, "c") - insertion_order = 2
4. insert(1, "d") - insertion_order = 3

红黑树中的顺序：

[1,"a"] (order=0) -> [1,"c"] (order=2) -> [1,"d"] (order=3) -> [2,"b"] (order=1)

调用 equal_range(1) 返回的范围是：

[1,"a"] -> [1,"c"] -> [1,"d"]

保持了插入顺序！

带提示插入的实现

iterator insert(const_iterator hint, const value_type& value) {
    // 创建新节点
    Node* new_node = allocate_node(value);
    new_node->insertion_order = global_counter_++;

    // 如果提示有效且可以优化插入
    if (hint != end() && can_use_hint(hint, new_node)) {
        // 使用提示进行优化插入
        return tree_.insert_with_hint(hint, new_node);
    } else {
        // 回退到普通插入
        return tree_.insert_equal(new_node);
    }
}

bool can_use_hint(const_iterator hint, Node* new_node) {
    // 检查提示是否真的能优化插入
    // 比如提示位置确实是要插入的位置
    // 这需要复杂的边界条件检查
}

内存优化策略

虽然存储insertion_order需要额外内存，但实现会进行优化：

方案1：紧凑的时间戳

// 使用32位而不是64位来节省空间
uint32_t insertion_order;

// 或者使用相对时间戳
struct Node {
    Key key;
    Value value;
    uint16_t relative_order;  // 在相同键范围内的相对顺序
    // ...
};

方案2：延迟分配

// 只有需要时才分配顺序标识
struct Node {
    Key key;
    Value value;
    union {
        uint64_t insertion_order;
        Node* next_in_order;  // 用于维护顺序的链表
    };
    bool use_linked_list;  // 标记使用哪种方式
};

主流实现的实际情况：GCC (libstdc++) 的实现

GCCs使用插入到upper_bound的方式：

// 伪代码，展示GCC的实现思路
struct _Rb_tree_node {
    // ... 标准节点字段

    // 实际上GCC可能不直接存储时间戳，而是通过其他方式
    // 维护插入顺序，比如在比较函数中考虑节点创建顺序
};

// 比较函数确保插入顺序
bool operator()(const node_type& __x, const node_type& __y) const {
    if (_M_impl._M_key_compare(_S_key(__x), _S_key(__y)))
        return true;
    if (_M_impl._M_key_compare(_S_key(__y), _S_key(__x)))
        return false;

    // 键相等时，确保新节点在旧节点之后
    // 这通过某种方式保证插入顺序
    return __x < __y;  // 或者类似的机制
}

性能考虑

这种实现的代价：

• ✅ 保证插入顺序符合标准要求
• ✅ equal_range 保持插入顺序
• ❌ 每个节点需要额外存储空间（通常8字节）
• ❌ 比较操作稍慢（需要比较额外字段）

总结

C++标准要求的插入顺序是通过以下方式实现的：

1. 每个节点存储插入顺序信息（如时间戳）
2. 比较函数在键相等时考虑插入顺序
3. **新插入的节点被认为”更大”**，因此插入到相同键区域的末尾
4. 这保证了equal_range返回的元素按插入顺序排列

这种实现虽然需要额外存储空间，但确保了标准规定的语义，使得multimap的行为对于使用者来说是确定和可预测的。

4.5 multimap: equal_range

对于基于红黑树的 std::multimap，equal_range 的实现要比哈希表版本简单和高效得多，这得益于红黑树的有序性。

equal_range 的实现原理

基本思路

1. 找到第一个匹配的键（下界）
2. 找到第一个不匹配的键（上界）
3. 返回这个范围

具体实现

template<typename Key, typename Value>
std::pair<iterator, iterator> 
multimap<Key, Value>::equal_range(const Key& key) {
    // 方法1：使用 lower_bound 和 upper_bound
    return std::make_pair(lower_bound(key), upper_bound(key));

    // 或者方法2：直接实现（更高效）
    // return equal_range_impl(key);
}

lower_bound 和 upper_bound 的实现

iterator lower_bound(const Key& key) {
    // 找到第一个 >= key 的元素
    Node* current = root_;
    Node* result = nullptr;

    while (current != nullptr) {
        if (!comp_(current->key, key)) {
            // current->key >= key，可能是我们要找的
            result = current;
            current = current->left; // 尝试找更小的但仍然 >= key 的
        } else {
            current = current->right; // 当前节点太小，向右找
        }
    }
    return iterator(result, this);
}

iterator upper_bound(const Key& key) {
    // 找到第一个 > key 的元素
    Node* current = root_;
    Node* result = nullptr;

    while (current != nullptr) {
        if (comp_(key, current->key)) {
            // current->key > key，可能是我们要找的
            result = current;
            current = current->left; // 尝试找更小的但仍然 > key 的
        } else {
            current = current->right; // 当前节点 <= key，向右找
        }
    }
    return iterator(result, this);
}

更高效的直接实现

std::pair<iterator, iterator> equal_range_impl(const Key& key) {
    Node* current = root_;
    Node* first = nullptr;  // 第一个匹配的元素
    Node* last = nullptr;   // 最后一个匹配的元素的下一位置

    // 一次性同时找到上下界
    while (current != nullptr) {
        if (comp_(current->key, key)) {
            // 当前节点 < key，向右子树找
            current = current->right;
        } else if (comp_(key, current->key)) {
            // 当前节点 > key，向左子树找
            last = current; // 记录可能的上界
            current = current->left;
        } else {
            // 找到匹配的键！
            // first 应该在左子树中相同键的最左节点
            // last 应该在右子树中相同键结束后的第一个节点

            first = current;
            last = current;

            // 在左子树中找第一个匹配的键
            Node* left_temp = current->left;
            while (left_temp != nullptr) {
                if (!comp_(left_temp->key, key)) { // left_temp->key >= key
                    if (!comp_(key, left_temp->key)) { // left_temp->key == key
                        first = left_temp;
                    }
                    left_temp = left_temp->left;
                } else {
                    left_temp = left_temp->right;
                }
            }

            // 在右子树中找最后一个匹配的键的下一个位置
            Node* right_temp = current->right;
            while (right_temp != nullptr) {
                if (comp_(key, right_temp->key)) { // right_temp->key > key
                    last = right_temp;
                    right_temp = right_temp->left;
                } else {
                    right_temp = right_temp->right;
                }
            }

            break;
        }
    }

    if (first == nullptr) {
        // 没有找到匹配的键
        return std::make_pair(iterator(nullptr, this), iterator(nullptr, this));
    }

    return std::make_pair(iterator(first, this), iterator(last, this));
}

实际示例

假设我们有一个包含以下元素的 multimap：

[1, "a"] -> [2, "b"] -> [2, "c"] -> [2, "d"] -> [3, "e"]

调用 equal_range(2)：

• lower_bound(2) 返回指向 [2, "b"] 的迭代器
• upper_bound(2) 返回指向 [3, "e"] 的迭代器
• 范围就是 [[2, "b"], [3, "e"])，包含所有键为2的元素

性能优势

时间复杂度

• 查找范围：O(log n)
• 遍历范围：O(k)，其中 k 是重复键的数量
• 总体：O(log n + k)

与 unordered_multimap 对比

特性	std::multimap (红黑树)	std::unordered_multimap (哈希表)
equal_range 复杂度	O(log n)	O(重复键数量)
元素顺序	有序	无序
范围查询	支持高效的范围查询	仅支持相等查询
内存局部性	较差（指针跳转）	较好（链表连续）

迭代器的连续性

由于红黑树的有序性，equal_range 返回的迭代器范围具有完美的连续性：

std::multimap<int, std::string> mmap = {
    {1, "a"}, {2, "b"}, {2, "c"}, {2, "d"}, {3, "e"}
};

auto range = mmap.equal_range(2);

// 可以安全地假设这些迭代器是连续的
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " "; // 输出: b c d
    // 迭代器会按顺序遍历 [2,"b"] -> [2,"c"] -> [2,"d"]
}

总结

std::multimap（基于红黑树）的 equal_range 实现：

1. 利用有序性：相同键的元素自然连续存储
2. 高效查找：O(log n) 时间找到范围边界
3. 完美连续性：返回的范围迭代器保证遍历所有相同键的元素
4. 简单可靠：不需要像哈希表那样维护特殊结构来保证连续性

这使得基于红黑树的 multimap 在需要范围查询或有序遍历的场景下比基于哈希表的版本更有优势。

5. 其他

5.1 flat_map

(12 封私信 / 81 条消息) C++23 flat_map详解 - 知乎

5.2 inplace_vector

(12 封私信 / 81 条消息) C++26 inplace_vector详解 - 知乎

bslma::Allocator

BDE Allocator Model · bloomberg/bde Wiki

5.3 hive

(12 封私信 / 81 条消息) std::hive 介绍 - 知乎

6. 高性能订单簿

(12 封私信 / 81 条消息) 如何设计一个高性能订单簿 - 知乎

直接用unordered_multimap

参考

std::execution::scheduler - cppreference.cn - C++参考手册

执行控制库 (自 C++26 起) - cppreference.cn - C++参考手册

C++23：std::execution/unifex导读-CSDN博客

Execution control library (since C++26) - cppreference.com

协程 (C++20) - cppreference.cn - C++参考手册

(25 封私信 / 80 条消息) c++ execution 与 coroutine (二) : execution概述 - 知乎

(25 封私信 / 80 条消息) ★C++20协程与stdexec(C++26 std::execution)学习笔记 - 知乎

(25 封私信 / 80 条消息) async_simple 源码分析（上） - 知乎

(25 封私信 / 80 条消息) 漫谈C++类型擦除(Type Erasure) - 知乎

(25 封私信 / 80 条消息) 浅谈The C++ Executors - 知乎

C++异步编程详解：future、promise与async | 现代C++并发编程 | C++ 编程指南

(25 封私信 / 80 条消息) C++26启航：Safe C++的破晓时刻 - 知乎

C++26 静态反射提案解析 - 知乎

(12 封私信 / 81 条消息) 笔记目录 (对象模型、STL容器、C++技巧） - 知乎

GCC中unordered_(multi)set/map的实现原理 （Part 2 图解哈希表结构) - 知乎

(12 封私信 / 81 条消息) GCC中unordered_(multi)set/map的实现原理 （Part 1 继承体系) - 知乎

(12 封私信 / 81 条消息) 【047-STL篇】C++ STL map和multimap容器全面解析：深入学习，轻松掌握 - 知乎

(12 封私信 / 81 条消息) 如何设计一个高性能订单簿 - 知乎

std::multimap<Key,T,Compare,Allocator>::equal_range - cppreference.cn - C++参考手册

BDE Allocator Model · bloomberg/bde Wiki