C++中vector、unordered_set和稀疏集增删遍历性能差异如何？

C++源码 // 优化版: std::vector vs 开放寻址哈希(二次探测+批量API) vs std::unordered_set #include <cstdint> #include <vector> #include <algorithm> #include <random> #include <chrono> #include <iostream> #include <iomanip> #include <unordered_set> #include <numeric> #include <cstring> #ifdef __GNUC__ #define ALWAYS_INLINE __attribute__((always_inline)) #define PURE __attribute__((pure)) #define LIKELY(x) __builtin_expect(!!(x), 1) #define UNLIKELY(x) __builtin_expect(!!(x), 0) #else #define ALWAYS_INLINE #define PURE #define LIKELY(x) (x) #define UNLIKELY(x) (x) #endif using player_id_t = uint64_t; using namespace std::chrono; // ==================== 方案1: std::vector ==================== class VectorSet { std::vector<player_id_t> data_; public: explicit VectorSet(size_t reserve = 1000) { data_.reserve(reserve); } ALWAYS_INLINE void insert(player_id_t id) { data_.push_back(id); } ALWAYS_INLINE bool erase(player_id_t id) { auto it = std::find(data_.begin(), data_.end(), id); if (it == data_.end()) return false; *it = data_.back(); data_.pop_back(); return true; } template<typename Fn> ALWAYS_INLINE void foreach(Fn&& fn) const { for (auto id : data_) fn(id); } [[nodiscard]] size_t size() const { return data_.size(); } void clear() { data_.clear(); } // 批量操作 void insert_batch(const player_id_t* ids, size_t count) { data_.reserve(data_.size() + count); for (size_t i = 0; i < count; ++i) { data_.push_back(ids[i]); } } }; // ==================== 方案2: 开放寻址哈希 (优化版) ==================== class HashSparseSet { struct Node { player_id_t id = 0; // 0 表示空槽 uint32_t dense_idx = 0; // 在 dense 数组中的索引 }; std::vector<Node> nodes_; // 哈希表（开放寻址） std::vector<player_id_t> dense_; // 密集存储，用于快速遍历