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