我知道所有容器都提供了一个常量size()操作，除了forward_list。但是内部数据结构为红黑树的map如何提供恒定复杂度的size()呢？对于 vector 和字符串等其他人也是如此。他们使用柜台吗？如果是这样，为什么不 forward_list？

当我读这本书时我很困惑c++标准库:教程和引用。

最佳答案

这是一个漫长而曲折的故事。 :-)

是的，map、set、list 等保持计数器提供恒定的时间 size()。在 C++11 之前，所有容器都不需要保留计数器，因为它们的 size() 应该是常数时间，而不是 shall 是恒定的时间。在标准中，“should”的意思是可能，也许不是，“shall”的意思是肯定的。

实际上，在 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有关从 forward_list 中省略 size() 的理由的更多详细信息。

https://stackoverflow.com/questions/27871739/