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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 24, 2005, at 8:27 AM, Gabriel Dos Reis wrote:

> chris jefferson <caj@cs.york.ac.uk> writes:
>
> | Not another C++ project, but I recently happened to mark a  
> university
> | C++ project which involved a list of tasks which were handled  
> FIFO and
> | also had to check if the list of tasks to do ever got too large.  
> This
> | doesn't seem an unreasonable thing to do.
> |
> | The obvious way to solve this, and the way everyone did, was to  
> use a
> | std::list to hold the tasks.
>
> Why std::deque wasn't appropriate?
>
> My conjecture is that people use std::list when in fact a better data
> structures exist.

There is no doubt that people will sometimes use the wrong data  
structure.  This problem isn't specific to std::list.  But deque  
isn't always a better answer than list.  Sometimes list is  
appropriate, and having a member splice is only the reason some of  
the time.  Other reasons include:

*  list is smaller code size than deque.
*  O(1) insertion/erase while not invalidating iterators/references/ 
pointers
*  push/pop_front/back don't invalidate iterators.
*  smaller overhead for sufficiently small size().

-Howard