std :: map如何提供一个常量size（）操作？
我知道所有的容器提供了一个恒定的size()操作，除了forward_list 。 但是如何map ，其内部数据结构是红黑树，提供了size()的复杂度？ 像vector和string的其他人一样。 他们使用柜台吗？ 如果是这样，为什么不forward_list ？
当我读这本书的C ++标准库时，我感到困惑：一个教程和参考 。
这是一个漫长而扭曲的故事。 🙂
是的，地图，设置，列表等保持计数器提供一个恒定的时间size() 。 在C ++ 11之前，没有一个容器需要保留计数器，因为它们的size() 应该是恒定的时间，但不是恒定的时间。 在这个标准中，“should”的意思可能是，也许不是，“shall”的意思是肯定的。
实际上，在C ++ 98/03中，除了list ，even map和set （通过使用计数器）之外，所有容器都具有恒定的时间size() ）。 这使得使用list一些可怕的不可移植的代码，其中一些代码假设了一个恒定的时间size() ，而其中一些代码假设了一个固定的时间“与其他代码拼接”。 这两个操作都不能保持一定的时间，实现必须select一个或另一个。
在C ++ 11中，标准被改为说size()必须是常量时间。 不过forward_list也是同时引入的。 而forward_list的整个目标就是优化list 。 委员会不想重复list::size()的错误，有时是不变的时间，有时是线性时间。 所以决定不给forward_list size() 。 因此，客户永远不会成为意外的线性时间size()受害者size() 。 forward_list客户想要做这个计算的客户仍然有distance(fl.begin(), fl.end())在他们的处置，如果他们应该这样做。
有关从forward_list省略size()的基本原理的更多详细信息，请参阅N2543 。
