gpt4 book ai didi

C++ STL - 为什么 std::forward_list 没有 size() 方法?

转载 作者:行者123 更新时间:2023-12-03 20:14:22 24 4
gpt4 key购买 nike

我一直在使用 C++11 的 forward_list作为一个快速插入的容器,没有太多的内存开销,因为它是一个单链表。

在意识到 forward_list没有 size()方法,我对背后的推理有点困惑。难道它不能只维护一个私有(private)字段来跟踪插入和删除的节点,从而实现 O(1) size() 操作吗?

最佳答案

N2543是提案,里面有关于size()的详细讨论.

The choice between Option 3 [not providing size()] and Option 2 [providing a O(1) size()] is more a matter of judgment. I have chosen Option 3 for the same reason that I chose insert-after instead of insert-before: Option 3 is more consistent with the goal of zero overhead compared to a hand-written C-style linked list. Maintaining a count doubles the size of a forward_list object (one word for the list head and one for the count), and it slows down every operation that changes the number of nodes. In most cases this isn't a change in asymptotic complexity (the one change in asymptotic complexity is in one of the forms of splice), but it is nonzero overhead. It's a cost that all users would have to pay for, whether they need this feature or not, and, for users who care about maintaining a count, it's just as easy to maintain it outside the list, by incrementing the count with every insert and decrementing it with every erase, as it is to maintain the count within the list.

关于C++ STL - 为什么 std::forward_list 没有 size() 方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31822494/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com