如何使用std::map提供常量大小()操作？

Question

我知道所有容器都提供一个常量的size()操作，但forward_list除外。但是，map的内部数据结构是红黑树，它如何以恒定的复杂性提供size()呢？其他如向量和字符串也是如此。他们用柜台吗？如果是的话，为什么forward_list不

当我阅读“c++标准库:教程和参考”一书时，我感到困惑。

Answer 1

这是一个又长又扭曲的故事。:-)

是的，地图，集合，列表等保持计数器提供一个恒定的时间size()。在C++11之前，没有任何容器被要求保留计数器，因为它们的size()应该是恒定的时间，但不应该是固定的时间。在标准中，“应该”指的是可能，也许不是，而“应该”是明确的意思。

实际上，在C++98/03中，所有容器都有固定时间的size()，除了list，甚至map和set (使用计数器)。这就产生了一些使用list的可怕的不可移植代码，其中一些假设为恒定时间size()，而另一些假设为恒定时间"splice some from other."，这两个操作都不能是固定时间，实现必须选择一个或另一个。

在C++11中，标准更改为size()必须是常数时间。但同时也引入了forward_list。forward_list的重点是对list进行优化。委员会不想重复list::size()的错误，有时是恒定时间，有时是线性时间。因此，决定根本不给forward_list一个size()。因此，客户端永远不会成为意想不到的线性时间size()的牺牲品。如果forward_list的客户想要这样做的话，如果他们选择这样做的话，他们仍然可以使用distance(fl.begin(), fl.end())。

有关从N2543中省略size()的理由的更多细节，请参见forward_list。