多个列表中的项目

Question

所以我有一些遗传代码，我很乐意使用更多的现代技术。但我担心，鉴于事情的设计方式，这是一个不可选项。核心问题是，一次一个节点通常位于多个列表中。事情是这样的：

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

这使得核心具有T类型的单个对象分配和插入2个双向链表，美观，高效。

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

通常代码需要“销毁”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. 

Answer 2

我认为正确的答案取决于这个应用程序的性能关键。它是否在一个内部循环中，可能会使程序产生用户可感知的运行时间差异？

有一种方法可以通过创建自己的一些派生自某些STL容器的类来创建此类功能，但它可能不值得您这样做。冒着听起来很烦人的风险，我认为这可能是过早优化的一个例子。

Answer 3

这听起来像你在谈论的东西，可以通过应用图论。因此，Boost Graph Library可能会提供一些解决方案。

Answer 4

不用管理你自己的next/previous指针，你确实可以使用std :: list。要解决移除问题的性能，可以将迭代器存储到对象本身（每个std :: list可以存储一个成员）。

你可以扩展它来存储类中的一个向量或迭代器数组（如果你不知道元素存储在其中的列表的数量）。

Answer 5

list::remove是你所追求的。它将删除列表中的任何和所有对象，其值与您传递给它的值相同。

所以：

list<T> listOne, listTwo; 
// Things get added to the lists. 
T thingToRemove; 
listOne.remove(thingToRemove); 
listTwo.remove(thingToRemove); 

我也建议你的列表节点转换为一类;这样C++就会为你处理内存。

class MyThing { 
    public: 
    int value; 
    // Any other values associated with T 
}; 

list<MyClass> listOne, listTwo; // can add and remove MyClass objects w/o worrying about destroying anything. 

甚至可以将两个列表封装到他们自己的类中，并使用它们的添加/删除方法。那么当你想删除一个对象时，你只需要调用一个方法。

class TwoLists { 
    private: 
    list<MyClass> listOne, listTwo; 

    // ... 

    public: 
    void remove(const MyClass& thing) { 
    listOne.remove(thing); 
    listTwo.remove(thing); 
    } 
}; 

Answer 6

要回答的问题是为什么这个C结构存在于第一位。除非知道该功能是什么，否则无法在C++中重新实现功能。有些问题可以帮助你回答，

1. 为什么列表？数据是否需要在序列中，即按顺序？订单是否意味着什么？应用程序是否需要有序遍历？
2. 为什么两个集装箱？容器中的成员资格是否表明了元素的某种属性？
3. 为什么一个双具体链接？是否O（1）插入和删除很重要？反向迭代是否重要？

部分或全部这些问题的答案可能是“没有真正的原因，这就是他们如何实现它”。如果是这样，你可以用一个非介入性的C++容器解决方案来替换这个侵入性的C指针混乱，可能包含shared_ptrs而不是ptrs。

我得到的是，你可能不需要重新实现任何东西。您可能可以放弃整个业务，并将值存储在适当的C++容器中。

Answer 7

这是怎么回事？

struct T { 
    std::list<T*>::iterator entry1, entry2; 
    int value; 
}; 
std::list<T*> list1, list2; 

// init a T* item: 
item = new T; 
item->entry1 = list1.end(); 
item->entry2 = list2.end(); 

// add a T* item to list 1: 
item->entry1 = list1.insert(<where>, item); 

// remove a T* item from list1 
if (item->entry1 != list1.end()) { 
     list1.remove(item->entry1); // this is O(1) 
     item->entry1 = list1.end(); 
} 

// code for list2 management is similar 

你可以让T成为一个类，并使用构造函数和成员函数来为你做大部分工作。如果列表数量可变，则可以使用迭代器列表std::vector<std::list<T>::iterator>来跟踪每个列表中项目的位置。

请注意，如果您使用push_back或push_front添加到列表中，你需要分别做item->entry1 = list1.end(); item->entry1--;或item->entry1 = list1.begin();获得迭代器在正确的地方指出。