双索引的最佳容器

Question

设置允许双索引的容器的最佳方法（在 C++ 中）是什么？ 具体来说，我有一个对象列表，每个对象都由一个键索引（每个键可能有多个）。 这意味着多重映射。 然而，这样做的问题在于，这意味着查找对象位置的线性查找可能比线性查找更糟糕。 我宁愿避免重复数据，因此让每个对象维护自己的坐标并必须在地图中移动自己会很糟糕（更不用说移动自己的对象可能会在成员函数中间接调用析构函数！）。 我宁愿有一些容器通过对象指针和坐标维护索引，并且对象本身保证稳定的引用/指针。 然后每个对象都可以将迭代器存储到索引（包括坐标），充分抽象，并知道它在哪里。 Boost.MultiIndex 似乎是最好的主意，但它非常可怕，而且我不希望我的实际对象需要是常量。

你会推荐什么？

编辑：Boost Bimap 看起来不错，但它提供稳定的索引吗？ 也就是说，如果我更改坐标，对其他元素的引用必须保持有效。 我想使用指针进行索引的原因是因为对象没有内在排序，并且指针可以在对象更改时保持不变（允许其在 Boost MultiIndex 中使用，IIRC 确实提供了稳定的索引）。

Answer 1

我根据您的文章做出几个假设：

• 复制和比较密钥的成本很低
• 系统中应该只有该对象的一份副本
• 相​​同的密钥可能引用许多对象，但只有一个对象对应于给定的密钥（一个-to-many）
• 您希望能够有效地查找哪些对象对应于给定的键，以及哪个键对应于给定的对象

我建议：

• 使用链接列表或其他容器来维护所有对象的全局列表系统中的对象。 对象分配在链表上。
• 创建一个 std::multimap 将键映射到对象指针，指向链表中的单个规范位置。
• 执行以下操作之一：
  • 创建一个 std::map

由于您的文章提到“坐标”作为键，您可能还有兴趣阅读 查找 3D 坐标是否已使用的最快方法。

Answer 2

很难理解你到底在用它做什么，但它看起来像 boost bimap 就是你想要的。 除了特定的用例之外，它基本上是 boost 多索引，并且更易于使用。 它允许基于第一个元素或第二个元素进行快速查找。 为什么要通过地址查找地图中对象的位置？ 使用抽象并让它为您完成所有工作。 请注意：映射中所有元素的迭代时间复杂度为 O(N)，因此可以保证查找您正在考虑的方式为 O(N) （不是更糟）。

Answer 3

一种选择是使用两个引用shared_ptr 的std::map。 像这样的事情可能会让你继续：

template<typename T, typename K1, typename K2>
class MyBiMap
{
public:
    typedef boost::shared_ptr<T> ptr_type;

    void insert(const ptr_type& value, const K1& key1, const K2& key2)
    {
        _map1.insert(std::make_pair(key1, value));
        _map2.insert(std::make_pair(key2, value));
    }

    ptr_type find1(const K1& key)
    {
        std::map<K1, ptr_type >::const_iterator itr = _map1.find(key);
        if (itr == _map1.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

    ptr_type find2(const K2& key)
    {
        std::map<K2, ptr_type >::const_iterator itr = _map2.find(key);
        if (itr == _map2.end())
            throw std::exception("Unable to find key");
        return itr->second;
    }

private:
    std::map<K1, ptr_type > _map1;
    std::map<K2, ptr_type > _map2;
};

编辑：我刚刚注意到多重地图的要求，这仍然表达了这个想法，所以我会留下它。