C++標準庫：實現恆定的時間從鏈接列表中刪除

我想使用標準庫數據結構（因爲可以輕鬆地覆蓋分配器）以獲得（可能雙倍）鏈接列表，允許恆定時間刪除操作給定指向元素的指針。C++標準庫：實現恆定的時間從鏈接列表中刪除

此功能是否內置於任何標準庫數據結構中？想象一下以下列表：

myList = [ elementA, elementB, elementC ]

刪除elementB是列表的大小固定的時間如果能說些什麼，這樣的效果：

elementB.previous.next = pointer_to(elementC)

...還是我必須建立自己的鏈表爲了達成這個？

來源

2014-02-18 Zach

您不能使用單個鏈接的列表，但雙向鏈接的列表可以使用。 – McLovin

給定一個元素的*指針，否。但是每個人都在回答，就好像你說的「給出一個迭代器」。對於只有指針而不是迭代器的問題，這很重要嗎？ –

你可以使用* iterator *而不是*指針*給元素嗎？ –

內置std::list支持元素的恆定時間刪除。在http://www.cplusplus.com/reference/list/list/從文檔

報價：

列表是序列容器，使固定的時間插入和序列內的任何地方擦除操作，並反覆在兩個方向上。

的實施確實是一個雙向鏈表：

列表容器被實現爲雙向鏈表;雙鏈表可以將它們包含的每個元素存儲在不同和不相關的存儲位置中。通過關聯到前面元素的鏈接的每個元素和後面元素的鏈接來保持排序。

爲了從列表中刪除的元素，簡單地使用erase()成員函數：

std::list mylist; 
std::list::iterator it = /* find an element */; 

// remove the element in constant time 
mylist.erase(it);

來源

2014-02-18 17:28:24 TypeIA

但是這假定你有位置。我有一個指向元素的指針，而不是位置。是否仍有可能通過'std :: list'實現不斷的刪除？ – Zach

@Zach（編輯/更正）'mylist.remove（* ptrToItem）;'將刪除項目，但不是固定時間。你需要一個迭代器才能工作。 – TypeIA

那是恆定的時間嗎？文檔似乎表明remove（）遍歷整個列表（即線性時間） - 或者這是行爲無證的？ //www.cplusplus.com/reference/list/list/remove/ – Zach

在C++ 11的使用iterator std::list::erase (const_iterator position)被garantied爲恆定時間。它你是一個雙向鏈表。所以這應該符合你的需求。

來源

2014-02-18 17:29:26 hivert

對於一個雙向鏈表，它有std::list，它支持給定一個迭代器（但不是指針）到那個元素的元素的定時移除。

C++ 11添加了一個單鏈表，std::forward_list。這不能完全符合你所描述的內容：如果你有一個迭代器用於前面的元素，你只能在常量時間內移除一個元素。

如果你真的想操縱使用指針的元素，而不是迭代器的容器，那麼你就必須放棄非侵入STL模型，並使用類似Boost的intrusive containers。

來源

2014-02-18 17:30:18

有趣的是，知道不使用迭代器/索引存在於Boost intrusive（element.unlink（））中。我只能想象這在一些非常有限的用例中是有用的，但是這種模式似乎很受用於Win NT LINKED_LIST的舊C開發人員的歡迎https://msdn.microsoft.com/en-us/library/windows/hardware/ff563802 （v = vs.85）的.aspx – log0

C++標準庫：實現恆定的時間從鏈接列表中刪除

回答

相關問題