首页 文章

获取std :: list或std :: forward_list中节点的指针

提问于
浏览
2

我打算在我的代码中使用std :: list,我决定不使用std :: forward_list,因为对于删除(我想),整个列表将不得不遍历,对于std :: forward_list的O(N)复杂度(正在进行)单个链接列表) . 但是,当我查看文档时,我注意到两个stl容器都有O(N)复杂性来删除项目 .

经过一番思考后,我弄明白了为什么(我认为) . 这是因为在这两种情况下,必须首先扫描整个列表以找到节点,然后将其删除 . 这是正确的吗?

然后我研究了“擦除”和“擦除后”方法,它们的复杂性是“擦除的元素数量的线性(破坏)” . 这是因为,我将一个迭代器传递给节点(有点像“指针”) . 但是,我不能(或者不想)在我的代码中传递这个迭代器来访问节点中的数据 . 如果列表被修改,我不确定这个迭代器是否有效?思考?

我的问题是,有没有办法可以获得指向列表中节点的指针 . 这样,我知道它将在我的程序的整个生命周期内有效,传递它 . 我可以调查它以获取对我的数据的访问权限 .

4 回答

  • 3

    如果列表被修改,我不确定这个迭代器是否有效

    是的,在一般情况下,存储迭代器是有风险的,除非您密切关注对容器执行的操作 .

    问题是,这对指针来说是一样的 . 实际上,对于许多容器,迭代器都是作为指针实现的 .

    因此,如果您愿意,可以存储迭代器或指针,但无论如何,请密切关注迭代器失效规则:

  • 0

    但是,我不能(或者不想)在我的代码中传递这个迭代器来访问节点中的数据 .

    为什么不?迭代器易于使用且非常轻巧 . 指针在任何方面都不是更好 .

    如果列表被修改,我不确定这个迭代器是否有效?

    对于 list ,即使修改了列表,任何迭代器都将保持有效 . 当然,除非您删除迭代器指向的特定元素 . 但是's kind of obvious, you can'期望有一个不再存在的东西的迭代器(或指针) .

    vector 更危险 . 对向量的一个小改动可能使其所有迭代器无效 . )

    您可以将指针指向 list 中的任何单个元素 .

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

    指针在很多方面类似于迭代器 . 但迭代器更强大一些 . 迭代器可以递增或递减,以访问列表中的相邻元素 . 迭代器可用于从列表中删除元素 . 指针不能执行这两种操作 .

    只要不删除该特定元素,迭代器和指针都保持有效 .

  • 2

    对于列表,即使列表中的其他项目被删除,迭代器也是有效的 . 当删除列表中的迭代器引用的项时,它变为垃圾 .

    所以,只要你知道你传递的迭代器并没有被其他一些代码删除,它们就可以安全地保留 . 这看起来很脆弱 .

    即使在迭代器之外有一个构造来引用列表中的节点,它也会遭受同样的脆弱性 .

    但是,您可以让每个节点包含它存储的数据的 std::shared_ptr 而不是对象本身,然后将 std::weak_ptr 传递给这些对象,并在访问 weak_ptr 之前检查 expired .

    例如

    代替

    std::list<MyClass> foo;
    

    你将会拥有

    std::list<std::shared_ptr<MyClass>> foo;
    

    看看有关 weak_ptr 的信息here

  • 3

    有没有办法可以获得指向列表中节点的指针

    Yes ,在您的特定实现中 .

    No ,符合标准 .

    如果查看std::list documentation,则没有关于节点的单词 . 虽然除了使用 doubly linked list 之外很难想象实现 std::list 的不同方式,但没有任何方法可以阻止它 .

    您应该 almost neverundocumented internals of libraries 进行任何联系 .

相关问题