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

[Gabriel Dos Reis <gdr at cs dot tamu dot edu>]

Howard Hinnant <hhinnant@apple.com> writes:

| 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.

I know.  My own codes I'm working on right now uses lists (although
not standard lists).  However, I maintain the conjecture that in most
cases when people use std::list, and constant-time size() matters, most of
the time there are better data structures.  In the remaining cases, I
doubt std::list is the right answer (not because of size().)

|  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().

I suspect that these points are conflicting, and don't make the case
for a constant-time size() for std::list<>.

-- Gaby