c++ - 获取指向 std::list 或 std::forward_list 中节点的指针

Question

我打算在我的代码中使用 std::list，我决定不使用 std::forward_list，因为对于删除(我认为)整个列表将不得不遍历，std::的复杂度为 O(N) forward_list(是一个链接列表)。但是，当我查看文档时，我注意到两个 STL 容器都具有 O(N) 复杂度来删除一个项目。

• http://www.cplusplus.com/reference/forward_list/forward_list/remove/
• http://www.cplusplus.com/reference/list/list/remove/

经过一番思考，我明白了原因(我认为)。这是因为在这两种情况下，都必须扫描整个列表以先找到该节点，然后再将其删除。这样对吗？

然后我研究了“erase”和“erase_after”方法，它们的复杂度是“与删除(破坏)的元素数量成线性关系。”。这是因为，我将迭代器传递给节点(有点像“指针”)。但是，我不能(或者不想)在我的代码中传递这个迭代器来访问节点中的数据。如果列表被修改，我不确定这个迭代器是否有效？想法？

我的问题是，有没有一种方法可以获得指向列表中节点的指针。这样，我知道它将在我的程序的整个生命周期内有效，传递它。我可以查看它以访问我的数据。

Answer 1

However, I cannot (or prefer not to) pass this iterator around in my code to access the data in the node.

为什么不呢？迭代器易于使用并且非常轻量级。指针在任何方面都好不到哪里去。

I am not sure if this iterator will be valid if the list is modified?

对于list，任何迭代器都将保持有效，即使列表被修改。 Except，当然，如果您删除迭代器指向的特定元素。但这很明显，您不能指望有一个指向不再存在的东西的迭代器(或指针)。

(vector 更危险。对 vector 的一个小改动可能会使它的所有迭代器失效。)

您可以获取指向列表中任何单个元素的指针。

list<int> iterator it = find(l.begin(), l.end(), 7); // get an iterator
int * ptr = &*it; // get a pointer to the same element.

指针在很多方面类似于迭代器。但是迭代器更强大一点。迭代器可以递增或递减，以访问列表中的相邻元素。迭代器可用于从列表中删除元素。指针不能做这两件事。

只要特定元素未被删除，迭代器和指针都将保持有效。