代码之家 › 专栏 › 技术社区 › coppro

双索引的最佳容器

containers stl c++

coppro · 技术社区 · 16 年前

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

你会推荐什么?

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

3 回复 | 直到 16 年前

Community Paul Sweatte 7 年前

我根据你的记录做了几个假设:

复制和比较密钥很便宜
系统中应该只有一个对象副本
同一个键可以引用多个对象,但只有一个对象对应于给定的键(一对多)
您希望能够有效地查找哪些对象与给定的键对应,以及哪些键与给定的对象对应。

我建议:

使用链接列表或其他容器维护系统中所有对象的全局列表。对象在链接列表上分配。
创建一个 std::multimap<Key, Object *> 它将键映射到对象指针,指向链接列表中的单个规范位置。
做下列之一:
- 创建一个 std::map<Object *, Key> 它允许查找附加到特定对象的键。确保您的代码在更改密钥时更新此映射。(这也可能是 std::multimap 如果你需要多对多的关系。)
- 将成员变量添加到 Object 包含当前 Key (允许O(1)查找)。确保您的代码在密钥更改时更新此变量。

由于你的文章提到“坐标”是关键,你可能也有兴趣阅读以下建议: Fastest way to find if a 3D coordinate is already used .

Greg Rogers 16 年前

很难理解你到底在用它做什么,但它看起来像是一个助推器。 bimap 是你想要的。除了一个特定的用例,它基本上提高了多个索引,并且更容易使用。它允许基于第一个元素或第二个元素进行快速查找。你为什么要按地图上某个物体的地址查找它的位置?使用抽象,让它为您完成所有工作。只需注意:映射中所有元素的迭代都是O(N),因此可以保证O(N)(不是更糟)查找您正在考虑的方法。

Matt Price 16 年前

一种选择是使用两个引用共享指针的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;
};

编辑:我刚注意到多重映射的要求,这仍然表达了这个想法,所以我将离开它。