我知道所有容器都提供一个恒定的size()操作,除了forward_list.但是map,其内部数据结构如何是红黑树,如何能够提供size()持续的复杂性？对于像vector和string这样的其他人也一样.他们用柜台吗？如果是这样,为什么不forward_list呢？
当我阅读"c ++标准库:一本教程和参考书"时,我很困惑.
How*_*ant 64
这是一个漫长而扭曲的故事.:-)
是的,地图,集合,列表等保持计数器提供恒定的时间size().在C++ 11之前,没有一个容器需要保持计数器,因为它们size() 应该是恒定的时间,但不应该是恒定的时间.在标准中,"应该"意味着可能,也许不是,"应该"意味着绝对.
实际上,在C++ 98/03中,所有容器都有一个恒定的时间size(),除了list偶数map和set(通过使用计数器).这使得一些可怕的非可移植代码使用list,其中一些假定了一个恒定的时间size(),并且其中一些假设一个恒定的时间"与其他人拼接一些". 这两个操作都不能是恒定时间,实现必须选择其中一个.
在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.