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

你会推荐什么？

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

解决方案

很难理解我们到底在用它做什么，但是似乎boost bimap是我们想要的。除了特定的用例外，它基本上可以提高多索引的使用率，并且更易于使用。它允许基于第一个元素或者第二个元素进行快速查找。为什么要通过对象的地址查找对象在地图中的位置？使用抽象，让它为我们完成所有工作。请注意：映射中所有元素的迭代都是O(N)，因此可以保证O(N)(不会更糟)查找我们考虑的方式。

我根据文章做出了一些假设：

• 密钥复制和比较便宜
• 系统中对象应该只有一个副本
• 相同的键可能引用许多对象，但是只有一个对象对应给定的键(一对多)
• 我们希望能够有效地查找哪些对象对应于给定键，哪些键对应于给定对象

我建议：

• 使用链表或者其他容器维护系统中所有对象的全局列表。对象在链表上分配。
• 创建一个std :: multimap <Key，Object *>，将键映射到对象指针，指向链接列表中的单个规范位置。
• 将一个成员变量添加到包含当前"键"的"对象"中(允许进行O(1)查找)。确保更改键后代码更新此变量。

由于文章提到"坐标"作为键，因此我们可能也有兴趣阅读"最快"方式的建议，以查找是否已使用3D坐标。

一种选择是使用两个引用shared_ptrs的std :: maps。这样的事情可能会让你前进：

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;
};

编辑：我刚刚注意到多地图的要求，这仍然表达了想法，所以我将其保留。