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

[Gabriel Dos Reis]

chris jefferson <caj@cs.york.ac.uk> writes:

| Howard Hinnant wrote:
| >
| > Here is an extremely biased summary of my personal opinion on the
| > subject.  It includes a just-completed survey of how the boost
| > library is using list::size and the affected variant of list::splice
| > (motivation is to survey actual use cases as opposed to contrived
| > code).  It also includes a proposal for a new list::splice overload
| > that subsumes the functionality of the problem child and yet remains
| > O(1).
| >
| > http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html
| >
| > I would be very interested in the results of similar surveys done on
| > other C++ projects.
| >
| 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.

-- Gaby