多個列表中的項目

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();獲得迭代器在正確的地方指出。