我希望使用标准的库数据结构(因为可以轻松地覆盖分配程序)来获得一个(可能是双倍)链接列表,该列表允许在给定指向元素的指针的中执行固定时间删除操作。
这种功能是否内置到任何标准库数据结构中?想象一下下面的列表:
myList = [ elementA, elementB, elementC ]如果可以这样说的话,删除elementB是列表大小中的固定时间:
elementB.previous.next = pointer_to(elementC)..。或者我必须建立我自己的链接列表来实现这一点?
发布于 2014-02-18 17:28:24
内置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:30:18
对于双链接列表,有std::list,它支持给定迭代器(但不是指针)到该元素的元素的常时删除。
C++11添加了一个单链列表,std::forward_list。这不能完全像您所描述的那样:只有在为前面的元素设置了迭代器的情况下,才能在恒定的时间内删除元素。
如果您真的希望使用指向元素的指针而不是迭代器来操作容器,那么您将不得不放弃非侵入性的STL模型,使用类似于Boost的侵入容器之类的东西。
发布于 2014-02-18 17:29:26
在C++11中,使用iterator std::list::erase (const_iterator position)的时间是恒定的。这是一份双重链接的名单。所以这个应该适合你的需要。
https://stackoverflow.com/questions/21860994
复制相似问题