This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
----- Original Message -----
From: "chris jefferson" <caj@cs.york.ac.uk>
To: "Howard Hinnant" <hhinnant@apple.com>
Cc: "libstdc++" <libstdc++@gcc.gnu.org>
Sent: Thursday, November 24, 2005 1:09 PM
Subject: Re: [C++] Should the complexity of std::list::size() be O(n) or
O(1)?
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. To check for too many tasks, about 3/4 of
people used list::size, and about 1/4 kept the size counter themselves
(out of a group of 25ish).
"Totally obvious" except for the fact that this is one rational for
std::deque. Insert at one end, remove at the other, elements don't move,
size is known.
I am in the crowd of people who say that list::size simply shouldn't
exist at all, but if it has to exist (and being honest, it can't be
removed now), it should be O(1). The idea of being "O(1) most of the
time, except after a splice" might be OK,
And this would, of course, be O(1), but with a constant factor that is
too large. Now size() would have to look for recent splices before
returning the count. Having k*1 timing is no good, if the k is large!
Bo Persson