[C++] Should the complexity of std::list::size() be O(n) or O(1)?

[Peter Dimov]

Jonathan Wakely wrote:
> On Tue, Nov 29, 2005 at 01:58:11AM +0100, Gabriel Dos Reis wrote:
>>
>>    (1) what would have been more interesting is the percentage of
>>        those usage that are not "hookey usage" of list<>.  I take
>>        that percentage to be far compelling.
>
> I think we all agree that if performance of anything except splicing
> is really important, then std::list is often the wrong choice, right?

std::list is often the right choice when either:

- O(1) insert/erase is needed;

- the element size is sufficiently large so that deque degenerates into a 
(much) less efficient or capable list;

- efficient remove_if is needed (very common IME);

- stable iterators are needed;

- stable references are needed;

- elements aren't Assignable;

- profiling indicates that the program performs better with list.

Most of these scenarios not only do not need an efficient splice, they don't 
need splice at all. std::list is definitely useful for more than splicing.