首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >C++标准库:实现固定时间从链接列表中删除

问C++标准库:实现固定时间从链接列表中删除
EN

Stack Overflow用户
提问于 2014-02-18 17:24:57
回答 3查看 2.6K关注 0票数 0

我希望使用标准的库数据结构(因为可以轻松地覆盖分配程序)来获得一个(可能是双倍)链接列表,该列表允许在给定指向元素的指针的中执行固定时间删除操作。

这种功能是否内置到任何标准库数据结构中?想象一下下面的列表:

代码语言:javascript
复制
myList = [ elementA, elementB, elementC ]

如果可以这样说的话,删除elementB是列表大小中的固定时间:

代码语言:javascript
复制
elementB.previous.next = pointer_to(elementC)

..。或者我必须建立我自己的链接列表来实现这一点?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-02-18 17:28:24

内置std::list支持元素的固定时间删除.

引用http://www.cplusplus.com/reference/list/list/的文档

列表是序列容器,允许在序列中的任何位置进行固定时间的插入和擦除操作,并在两个方向上进行迭代。

执行工作确实是一个双重链接的清单:

列表容器被实现为双链接列表;双链接列表可以将它们包含的每个元素存储在不同和不相关的存储位置。排序是由关联到指向其前面的元素的链接的每个元素以及到其后面的元素的链接保持的。

要从列表中删除元素,只需使用erase()成员函数:

代码语言:javascript
复制
std::list mylist;
std::list::iterator it = /* find an element */;

// remove the element in constant time
mylist.erase(it);
票数 4
EN

Stack Overflow用户

发布于 2014-02-18 17:30:18

对于双链接列表,有std::list,它支持给定迭代器(但不是指针)到该元素的元素的常时删除。

C++11添加了一个单链列表,std::forward_list。这不能完全像您所描述的那样:只有在为前面的元素设置了迭代器的情况下,才能在恒定的时间内删除元素。

如果您真的希望使用指向元素的指针而不是迭代器来操作容器,那么您将不得不放弃非侵入性的STL模型,使用类似于Boost的侵入容器之类的东西。

票数 3
EN

Stack Overflow用户

发布于 2014-02-18 17:29:26

在C++11中,使用iterator std::list::erase (const_iterator position)的时间是恒定的。这是一份双重链接的名单。所以这个应该适合你的需要。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/21860994

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档