因此,我有一些旧代码,我希望使用更多现代技术。但是我担心,考虑到事物的设计方式,这是一种选择。核心问题是一个节点通常一次只能出现在多个列表中。像这样:

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解决方案,还是手动滚动方式是最佳方法?我觉得手动滚动方式是答案,但是我想问一下。

最佳答案

作为另一个可能的解决方案,请查看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.

关于c++ - 多个列表中的项目,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3056698/

10-11 22:33
查看更多