c++ - 多个列表中的项目

Question

所以我有一些遗留代码，我想使用更现代的技术。但我担心，鉴于事物的设计方式，这是一个不可选择的选择。核心问题是一个节点通常一次在多个列表中。像这样:

struct T {
    T *next_1;
    T *prev_1;
    T *next_2;
    T *prev_2;
    int value;
};

这允许核心拥有一个类型为 T 的对象被分配并插入到 2 个双向链表中，漂亮且高效。

很明显，我可以有 2 std::list<T*>的，只需将对象插入到两者中...但是有一件事效率会降低...删除。

代码通常需要“销毁”类型为 T 的对象这包括从所有列表中删除该元素。这很好，因为给定一个 T*代码可以从它所在的所有列表中删除该对象。使用类似 std::list 的东西我需要搜索对象以获取迭代器，然后将其删除(我不能只传递迭代器，因为它在多个列表中)。

是否有一个很好的 c++-ish 解决方案，或者手动滚动的方式是最好的方式吗？我觉得手动滚动的方式是答案，但我想我会问。

Answer 1

作为另一种可能的解决方案，请查看 Boost Intrusive , 其中有 an alternate list class许多属性可能会使它对您的问题有用。

在这种情况下，我认为它看起来像这样:

using namespace boost::intrusive;

struct tag1; struct tag2;

typedef list_base_hook< tag<tag1> > base1;
typedef list_base_hook< tag<tag2> > base2;

class T: public base1, public base2
{
    int value;
}

list<T, base_hook<base1> > list1;
list<T, base_hook<base2> > list2;

// constant time to get iterator of a T item:
where_in_list1 = list1.iterator_to(item);
where_in_list2 = list2.iterator_to(item);

// once you have iterators, you can remove in contant time, etc, etc.