使用地图和列表同一对象 [英] Using Both Map and List for Same Objects

问题描述

我试图使用列表和unordered_map来存储同一组对象。

I'm trying to use both a list and an unordered_map to store the same set of objects. I'm new to C++, so still getting comfortable with iterators.

说我有以下测试代码：

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生成器）

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?)

所以如果我有键102，我可以在常量时间t2查找。然后，我想要相对于t2的位置在列表中向前/向后/插入/删除。

So if I have the key 102, I could look up t2 in constant time. I then want to iterate forward/backward/insert/delete relative to t2's position in the list.

我可以使用find获得一个unordered_map迭代器指向t2。我不知道如何生成一个从t2开始的列表迭代器（我只能在列表的开头或末尾生成迭代器，然后迭代。）

I can use find to get a unordered_map iterator pointing to t2. I don't know how to generate a list iterator that starts at t2 (I can only generate iterators at the beginning or the end of the list, and iterate through.)

谢谢！

Afterthought：
这是一个可以接受的方法吗？我有很多对象，需要通过整数键有效地查找它们。

Afterthought: Is this an acceptable approach? I have many objects and need to efficiently look them up by integer key. I also need to preserve their order (unrelated to these integer keys) and insert/delete/traverse efficiently.

推荐答案

虽然Barry的方法是非常有用的，但是我们需要保留它们的顺序（与这些整数键无关）是好的，还有另一个，更先进和复杂。你可以把你的数据对象，（整数）键和所有的记帐位在一个单一的内存块。因此，数据局部性将被改进，并且对存储器分配器的压力将更小。示例，使用 boost :: intrusive ：

While Barry's approach is good, there is another one, more advanced and complicated. You can put your data object, (integer) key, and all bookkeeping bits in a single chunk of memory. Thus data locality will be improved and pressure on memory allocator will be less. Example, using 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);
}

测量这两种算法对您的数据有多好。我的想法可能给你什么，但更大的代码复杂性。

Measure how good are both algorithms on your data. My idea may give you nothing but greater code complexity.

这篇关于使用地图和列表同一对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！