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 2:32 PM, Gabriel Dos Reis wrote:
| 
| > Since it was a mistake to put it there in the first place, why shall
| > we penalize proper list operations by trying to make an error run
| > faster?
| 
| "Trying to make an error run faster" implies the wrong thing.  This
| statement is often stated as "why get the wrong answer faster", which
| is something I completely agree with.  An O(1) size doesn't compute
| the wrong answer.  It merely shifts a performance tradeoff.

But, analysis has shown that there is no convincing argument (except
probably convience) that list<> should support size() in the first place.
That is the mistake.  Perpetuating the error by penalizing proper list
operations is NOT a performance tradeoff.

| The status quo (size() may be O(1) or O(N)) is unacceptable because
| people, even experts, will do things like this:

<sarcasm>
   "The role of experts is not to be more right than others, but to
    be wrong for more obscure reasons"
         -- <I can't remember right now>
:-)
</sarcasm>

| 
| http://home.twcny.rr.com/hinnant/cpp_extensions/
| On_list_size.html#boost%20survey
| 
| It just happens because c.size() is usually O(1) for most c.  We've
| been trained that way.  Having it sometimes be O(N) for some c is
| just error prone, especially in generic code (no different than
| strstream being technically correct and even really useful sometimes,
| but prone to misuse because of a poor interface design, leading to
| memory leaks).

or no different than map<> or set<> not satisfying the container
requirements or vector<bool> not being a container, or string and
vector<char> not comparing the same, or random access containers not
having the same invalidating patterns, etc.

| If we want to prevent this mistake from occurring in the future, I
| see only two choices:

there are at least four choices.

| 
| 1.  Remove list::size.
| 2.  Make list::size O(1).

  3.  Leave it as is.
  4.  Be clear that size() is linear for list<>.

| Pick the less evil.
| 
| Imho, adding a guaranteed O(1) "splice some from other" signature
| helps to make choice 2 a little more palatable.

-- Gaby