c++ - 更快地替代 STL std::map

Question

我确实有一个数据结构:

typedef std::pair<boost::shared_ptr<X>, boost::shared_ptr<X> > pair_ptr;
std::map< pair_ptr, int >

我在迭代过程中使用的。在每次迭代中，我需要 复制 std::map 并可能销毁一个拷贝。但是，std::map 可能会变得很大，超过 100k 个元素。这大大减慢了程序的速度。我已将运算符<定义为:

   inline bool operator<(const pair_ptr& a, const pair_ptr& b) 
   { 
   return (a.first < b.first) or 
        (a.first == b.first and a.second < b.second);
   }

我使用 std::map 复制构造函数和析构函数。有没有更快的选择？

Answer 1

您有很多选择 - 我们可以建议设计备选方案，但没有足够的信息来为您制作它们。

以下是您可以做的三件事:

1. 你能不能让这个键成为对的指针(并调整适本地比较)，以便对本身(包含两个 refcnt'd ptrs) 不必复制？

2. 在每次迭代中 - 您是否需要预期的 O(log n)插入/删除时间？如果你能忍受 O(n)插入/删除然后你可以使用排序的 vector 作为容器而不是 map ？ (这样你就可以在一个容器中分配/释放容器shot 而不是分配/释放大量的小树节点。)(记住:std::map不是您可以搜索的唯一数据结构，甚至不是唯一的 std::数据结构。所有可搜索的数据结构都可以工作，只需选择具有适当复杂性保证的那个，取模你的“常量”的知识(例如，堆分配是昂贵的)，为您用例。)

3. 你能(你)管理关键的两件事的生命周期吗指向独立于 map ，而这个迭代过程？如果所以你可以有一对裸指针的键，这会比ref cnt'd 在每个迭代器上创建新映射的指针。你可以有一组单独的 ref cnt'd 指针指向你所有的东西，并在那里管理这些对象的生命周期。

这些也可以组合。只是一些帮助您入门的想法。