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

[Gabriel Dos Reis <gdr at integrable-solutions dot net>]

Howard Hinnant <hhinnant@apple.com> writes:

| On Nov 24, 2005, at 3:57 PM, Gabriel Dos Reis wrote:
| 
| > Certainly.  My point was that I'm not convinced penalizing proper list
| > operations is the right resolution.
| 
| I'm not convinced that labeling list::size() as improper is correct
| characterization. 

Well, I don't know who said it was "improper".  
Certainly, I don't believe it is a proper list operation as splice().

| I have no trouble thinking of applications which
| need to know the size of the list. 

That is probably true, but it is beside the point.
The point is not whether an application may need size() on list or not.

| What is improper is having an O(N) size.   It should either be O(1),
| or not exist.

By the same token distance() shall be either O(1) or not exist.

| The fact that it exists and is O(N) is what is
| improper imho.  I continue to come across code that uses list::size
| in the mistaken belief that it is O(1).

The claim wasn't whether people would be mistaken -- you'd always find
people mistaken about one aspect or the other.  The issue is whether
it is a proper list operation, as splice().  I claim the answer is no.
An error was made in putting it there in the first place.  I rather
sequester that error instead of spreading through over the rest of
the interface.

[...]

| This is not a simple case of people not being sufficiently educated.
| This is a very poor interface design on the part of std::list.
| 
| >   3.  Leave it as is.
| >   4.  Be clear that size() is linear for list<>.
| 
| These are unacceptable because they leave in place the bad interface.

Then penalizing other proper list operations is worst.

[...]

| The spec for the example I'm working with is:
| 
| Consider an aircraft seating program which has a function called
| free_upgrade.  This function tries to upgrade passengers from economy
| to first class, but is subject to the size limits of first class
| seating, and also subject to weight & balance rules to keep the
| aircraft stable.  It is also smart enough to not split up a party
| that's traveling together.  Here is how it might look:

[...]

| The parameters to the problem might look something like:
| 
| const std::size_t first_class_initial_size = 25;
| const std::size_t first_class_limit = 50;
| const std::size_t economy_class_initial_size = 100;
| const std::size_t max_group_size = 5;
| 
| I'm giving each Passenger a first and last name.  And Passengers that
| are adjacent in the lists, and have the same last name are
| constrained to travel together (either all or none of that subgroup
| will be upgraded).  Passenger groups occur with uniform randomness in
| the range [1, max_group_size].
| 
| I've coded this up 3 ways so far:
| 
| 1.  Assuming an O(1) size, and being right.
| 2.  Assuming an O(N) size, and being right - sizes are computed and
| cached externally.
| 3.  Assuming an O(1) size, but being wrong (size is actually O(N)).

[...]

| Case 3 is pretty much always a disaster.  With the first set of
| parameters it is 39% slower.  With the latter set of parameters it is
| 73 times slower.
| 
| Imho, we need to do whatever it takes to make sure our customers
| don't accidently fall into the case 3 trap.

Agreed.  But, you have to press me hard to vote 1.

-- Gaby