对同一对象同时使用 Map 和 List

Question

我正在尝试同时使用列表和 unordered_map 来存储同一组对象。我是 C++ 的新手，所以仍然熟悉迭代器。

假设我有以下测试代码：

class Test {
public:
    int x;
    int y;
    int z;
    Test (int, int, int);
}

Test t1 = Test(1,2,3);
Test t2 = Test(2,4,6);
Test t3 = Test(3,6,9);

std::list<Test> list;
std::unordered_map<int, Test> map;

list.push_back(t3);
list.push_back(t2);
list.push_back(t1);
map[101] = t1;
map[102] = t2;
map[103] = t3;

是否可以通过键查找对象，然后从对象的引用（或从 unordered_map 生成器？）生成列表迭代器？

所以如果我有密钥 102，我可以在常数时间内查找 t2。然后我想迭代 forward/backward/insert/delete 相对于 t2 在列表中的位置。

我可以使用 find 获取指向 t2 的 unordered_map 迭代器。不知道如何生成从t2开始的列表迭代器（我只能在列表的开头或结尾生成迭代器，遍历遍历。）

如果有人指点我有关 STL 和迭代器的优秀教程，我将不胜感激。

谢谢！

事后思考：这是一种可以接受的方法吗？我有很多对象，需要通过整数键有效地查找它们。我还需要有效地保留它们的顺序（与这些整数键无关）和 insert/delete/traverse。

Answer 1

如果你想做的是：

Is it possible to look up an object by key, and then generate a list iterator from the reference of the object (or from the unordered_map generator?)

然后你可以利用 list 迭代器在插入或擦除时不会失效的事实（除非你擦除那个特定的迭代器）并像这样重新组织你的结构：

std::list<Test> list;
std::unordered_map<int, std::list<Test>::iterator> map;

map.insert(std::make_pair(101, 
    list.insert(list.end(), t1)));
map.insert(std::make_pair(102, 
    list.insert(list.end(), t2)));
map.insert(std::make_pair(103, 
    list.insert(list.end(), t3)));

这样您的地图查找就会准确地为您提供所需的信息：list iterator.

Answer 2

虽然 Barry 的方法不错，但还有另一种更高级、更复杂的方法。您可以将数据对象、（整数）键和所有簿记位放在一块内存中。因此数据局部性将得到改善，内存分配器的压力将更小。例如，使用 boost::intrusive:

#include <boost/intrusive/list.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <array>

using namespace boost::intrusive;

class Foo {
    // bookkeeping bits
    list_member_hook<> list_hook;
    unordered_set_member_hook<> set_hook;

    const int key;
    // some payload...

public:
    // there is even more options to configure container types
    using list_type = list<Foo, member_hook<Foo, list_member_hook<>, &Foo::list_hook>>;
    using set_type = unordered_set<Foo, member_hook<Foo, unordered_set_member_hook<>, &Foo::set_hook>>;

    Foo(int key): key(key) {};
    bool operator ==(const Foo &rhs) const {
        return key == rhs.key;
    }
    friend std::size_t hash_value(const Foo &foo) {
        return std::hash<int>()(foo.key);
    }
};

class Bar {
    Foo::list_type list;

    std::array<Foo::set_type::bucket_type, 17> buckets;
    Foo::set_type set{Foo::set_type::bucket_traits(buckets.data(), buckets.size())};

public:
    template<typename... Args>
    Foo &emplace(Args&&... args) {
        auto foo = new Foo(std::forward<Args>(args)...);
        // no more allocations
        list.push_front(*foo);
        set.insert(*foo);
        return *foo;
    }
    void pop(const Foo &foo) {
        set.erase(foo);
        list.erase(list.iterator_to(foo));
        // Lifetime management fun...
        delete &foo;
    }
};

int main() {
    Bar bar;
    auto &foo = bar.emplace(42);
    bar.pop(foo);
}

衡量两种算法对您数据的优劣程度。我的想法可能只会给您带来更大的代码复杂性。

对同一对象同时使用 Map 和 List

Using Both Map and List for Same Objects

c++

iterator

unordered-map

list

c++11