Recentemente, notei algumas pessoas mencionando questd::list::size() tem uma complexidade linear.
De acordo comalguns fontes, isso é de fato dependente da implementação, pois o padrão não diz qual deve ser a complexidade.
O comentárionesta entrada do blog diz:

Na verdade, depende de qual STL você está usando. O Microsoft Visual Studio V6 implementa size () como {return (_Size); } Considerando que o gcc (pelo menos nas versões 3.3.2 e 4.1.0) faz isso como {return std :: distance (begin (), end ()); } O primeiro tem velocidade constante, o segundo tem velocidade o (N)

Então, meu palpite é que, para a multidão de VC ++size() tem complexidade constante, pois o Dinkumware provavelmente não mudará esse fato desde o VC6. Estou bem aí?
Como é atualmente emgcc? Se é realmente O (n), por que os desenvolvedores optaram por fazê-lo?