I know all containers provide a constant size() operation, except forward_list. But how can map, whose internal data structure is red-black tree, provide size() in constant complexity? Same for others like vector and string. Do they use a counter? If so, why doesn't forward_list?
我知道所有容器都提供了一个常量size()操作，除了forward d_list。但是map(其内部数据结构为红黑树)如何能够以不变的复杂性提供size()呢?向量和字符串也是一样的。他们使用柜台吗?如果是，为什么不转发list呢?
I am confused when I read the book The c++ standard library: a tutorial and reference.
当我读《c++标准库:教程和参考》这本书时，我很困惑。
1 个解决方案
#1
64
This is a long and twisted story. :-)
这是一个漫长而曲折的故事。:-)
Yes, map, set, list, etc. keep counters to supply a constant time size(). Prior to C++11, none of the containers were required to keep counters, as their size() should be constant time, but not shall be constant time. In the standard, "should" means maybe, maybe not, and "shall" means definitely.
是的，映射、设置、列表等保持计数器以提供恒定的时间大小()。在c++ 11之前，没有任何容器需要保存计数器，因为它们的大小()应该是常数时间，但不是常数时间。在标准中，should表示可能，也许不是，shall表示肯定。
In practice, in C++98/03 all containers had a constant time size(), except for list, even map and set (by using a counter). This made for some horribly non portable code using list, some of which assumed a constant time size(), and some of which assumed a constant time "splice some from other." Both of those operations can not be constant time, implementations had to choose one or the other.
在实践中，在c++ 98/03中，所有容器都有一个常量时间大小()，除了列表，甚至是map和set(使用计数器)。这使得使用list的代码变得非常不可移植，其中一些代码假设了一个常量时间大小()，而另一些代码则假设了一个常量时间“从其他代码拼接”。这两种操作都不是固定的时间，实现必须选择一个或另一个。
In C++11, the standard was changed to say that size() must be constant time. However forward_list was also introduced at the same time. And the whole point of forward_list is to be an optimization of list. And the committee did not want to repeat the mistake of list::size(), sometimes being constant time, and sometimes being linear time. So the decision was to not give forward_list a size() at all. Thus clients would never fall victim to an unexpected linear time size(). Clients of forward_list who want to do that computation still have distance(fl.begin(), fl.end()) at their disposal if they should choose to do so.
在c++ 11中，标准被更改为size()必须是常数时间。然而，同时也引入了forward_list。而forward_list的全部意义就是对list进行优化。而且委员会不想重复list的错误:size()，有时是常数时间，有时是线性时间。因此，我们的决定是完全不给forward d_list一个size()。因此，客户机永远不会成为意外的线性时间大小()的牺牲品。要进行该计算的forward_list的客户端仍然可以使用distance(fl.begin()、fl.end()，如果他们愿意这样做的话。
See N2543 for more details on the rationale for omitting size() from forward_list.
有关从forward_list中删除size()的基本原理，请参见N2543。
#1
64
This is a long and twisted story. :-)
这是一个漫长而曲折的故事。:-)
Yes, map, set, list, etc. keep counters to supply a constant time size(). Prior to C++11, none of the containers were required to keep counters, as their size() should be constant time, but not shall be constant time. In the standard, "should" means maybe, maybe not, and "shall" means definitely.
是的，映射、设置、列表等保持计数器以提供恒定的时间大小()。在c++ 11之前，没有任何容器需要保存计数器，因为它们的大小()应该是常数时间，但不是常数时间。在标准中，should表示可能，也许不是，shall表示肯定。
In practice, in C++98/03 all containers had a constant time size(), except for list, even map and set (by using a counter). This made for some horribly non portable code using list, some of which assumed a constant time size(), and some of which assumed a constant time "splice some from other." Both of those operations can not be constant time, implementations had to choose one or the other.
在实践中，在c++ 98/03中，所有容器都有一个常量时间大小()，除了列表，甚至是map和set(使用计数器)。这使得使用list的代码变得非常不可移植，其中一些代码假设了一个常量时间大小()，而另一些代码则假设了一个常量时间“从其他代码拼接”。这两种操作都不是固定的时间，实现必须选择一个或另一个。
In C++11, the standard was changed to say that size() must be constant time. However forward_list was also introduced at the same time. And the whole point of forward_list is to be an optimization of list. And the committee did not want to repeat the mistake of list::size(), sometimes being constant time, and sometimes being linear time. So the decision was to not give forward_list a size() at all. Thus clients would never fall victim to an unexpected linear time size(). Clients of forward_list who want to do that computation still have distance(fl.begin(), fl.end()) at their disposal if they should choose to do so.
在c++ 11中，标准被更改为size()必须是常数时间。然而，同时也引入了forward_list。而forward_list的全部意义就是对list进行优化。而且委员会不想重复list的错误:size()，有时是常数时间，有时是线性时间。因此，我们的决定是完全不给forward d_list一个size()。因此，客户机永远不会成为意外的线性时间大小()的牺牲品。要进行该计算的forward_list的客户端仍然可以使用distance(fl.begin()、fl.end()，如果他们愿意这样做的话。
See N2543 for more details on the rationale for omitting size() from forward_list.
有关从forward_list中删除size()的基本原理，请参见N2543。