STL 算法与数据聚合模式

业务题的重点通常不是“背出外卖/推荐系统代码”，而是能根据访问模式选择容器、算法、复杂度和并发边界。

分组、聚合与 Top 结果

例如按餐厅统计订单数量和最高金额订单：

#include <algorithm>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>

struct Order {
    int id;
    std::string restaurant;
    double amount;
};

struct RestaurantStats {
    std::size_t count = 0;
    std::optional<Order> max_order;
};

std::unordered_map<std::string, RestaurantStats>
summarize(const std::vector<Order>& orders) {
    std::unordered_map<std::string, RestaurantStats> result;

    for (const auto& order : orders) {
        auto& stats = result[order.restaurant];
        ++stats.count;
        if (!stats.max_order || order.amount > stats.max_order->amount) {
            stats.max_order = order;
        }
    }
    return result;
}

• 只需按 key 查找而不要求输出有序时，unordered_map 平均 O(1)；需要稳定键序时使用 std::map，复杂度 O(log n)；
• 扫描聚合为 O(n)，不需要先排序；
• 若要找全局 Top K，维护大小为 K 的小顶堆通常是 O(n log K)，比全量排序 O(n log n) 更合适；
• 求平均值前处理空集合，且金额、时长等累计值应选择不会溢出的类型。

排序与不修改原始数据

auto ordered = orders; // 对副本排序，保留原始输入顺序
std::sort(ordered.begin(), ordered.end(),
          [](const Order& left, const Order& right) {
              return left.amount > right.amount;
          });

std::sort 会修改输入，平均/最坏复杂度由标准库算法保证为 O(n log n)，但它不是稳定排序；相同键需保留原顺序时使用 std::stable_sort，通常需要更多额外空间。比较器必须满足严格弱序，否则排序行为不可靠。

Map/Reduce 思维与线程安全快照

“Map/Reduce”在单机代码中常指两阶段：先把每条行为映射到 key 的累积值，再归约为最终统计，例如 item_id → (sum_rating, count) 后计算平均值。它不等同于真正分布式 MapReduce 框架。

共享输入持续被写入时，不要一边持有 mutex 一边做长时间排序/聚合。常见做法是先在锁内获得快照，再在锁外计算：

class OrderStore {
public:
    std::vector<Order> snapshot() const {
        std::lock_guard lock(mutex_);
        return orders_;
    }

private:
    mutable std::mutex mutex_;
    std::vector<Order> orders_;
};

// auto local_orders = store.snapshot();
// auto stats = summarize(local_orders); // 锁外执行耗时计算

这牺牲一次复制换取更短的临界区。数据量很大时可进一步采用分片、读写锁、不可变快照或批处理管道，但必须明确一致性语义。

常见易错点

• std::thread::hardware_concurrency() 可以返回 0，不能直接拿它做除数；
• 只给写操作加锁而读取/统计不加锁，仍然会产生数据竞争；
• emplace_back(std::move(obj)) 不必然优于直接 emplace_back(args...)，应先保证语义清晰；
• reserve 应在大量插入之前调用；在容器已有大量元素后调用可能触发一次额外搬迁；
• I/O 输出通常需要同步，但不要为了打印而把长时间计算都包在同一把锁里。