我打算在我的代码中使用std :: list,我决定不使用std :: forward_list,因为对于删除(我想),整个列表将不得不遍历,对于std :: forward_list的O(N)复杂度(正在进行)单个链接列表) . 但是,当我查看文档时,我注意到两个stl容器都有O(N)复杂性来删除项目 .
经过一番思考后,我弄明白了为什么(我认为) . 这是因为在这两种情况下,必须首先扫描整个列表以找到节点,然后将其删除 . 这是正确的吗?
然后我研究了“擦除”和“擦除后”方法,它们的复杂性是“擦除的元素数量的线性(破坏)” . 这是因为,我将一个迭代器传递给节点(有点像“指针”) . 但是,我不能(或者不想)在我的代码中传递这个迭代器来访问节点中的数据 . 如果列表被修改,我不确定这个迭代器是否有效?思考?
我的问题是,有没有办法可以获得指向列表中节点的指针 . 这样,我知道它将在我的程序的整个生命周期内有效,传递它 . 我可以调查它以获取对我的数据的访问权限 .
4 回答
是的,在一般情况下,存储迭代器是有风险的,除非您密切关注对容器执行的操作 .
问题是,这对指针来说是一样的 . 实际上,对于许多容器,迭代器都是作为指针实现的 .
因此,如果您愿意,可以存储迭代器或指针,但无论如何,请密切关注迭代器失效规则:
为什么不?迭代器易于使用且非常轻巧 . 指针在任何方面都不是更好 .
对于
list
,即使修改了列表,任何迭代器都将保持有效 . 当然,除非您删除迭代器指向的特定元素 . 但是's kind of obvious, you can'期望有一个不再存在的东西的迭代器(或指针) .(
vector
更危险 . 对向量的一个小改动可能使其所有迭代器无效 . )您可以将指针指向
list
中的任何单个元素 .指针在很多方面类似于迭代器 . 但迭代器更强大一些 . 迭代器可以递增或递减,以访问列表中的相邻元素 . 迭代器可用于从列表中删除元素 . 指针不能执行这两种操作 .
只要不删除该特定元素,迭代器和指针都保持有效 .
对于列表,即使列表中的其他项目被删除,迭代器也是有效的 . 当删除列表中的迭代器引用的项时,它变为垃圾 .
所以,只要你知道你传递的迭代器并没有被其他一些代码删除,它们就可以安全地保留 . 这看起来很脆弱 .
即使在迭代器之外有一个构造来引用列表中的节点,它也会遭受同样的脆弱性 .
但是,您可以让每个节点包含它存储的数据的
std::shared_ptr
而不是对象本身,然后将std::weak_ptr
传递给这些对象,并在访问weak_ptr
之前检查expired
.例如
代替
你将会拥有
看看有关
weak_ptr
的信息hereYes ,在您的特定实现中 .
No ,符合标准 .
如果查看std::list documentation,则没有关于节点的单词 . 虽然除了使用 doubly linked list 之外很难想象实现
std::list
的不同方式,但没有任何方法可以阻止它 .您应该 almost never 与 undocumented internals of libraries 进行任何联系 .