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

[Gabriel Dos Reis]

Howard Hinnant <hhinnant@apple.com> writes:

| On Nov 28, 2005, at 4:58 PM, Gabriel Dos Reis wrote:
| 
| > Howard Hinnant <hhinnant@apple.com> writes:
| >
| > [...]
| >
| > | These are **your** customers.  By the way they are coding, they are
| > | disagreeing with you.
| >
| > I'm not sure we're going to get anything useful from personalizing the
| > debate.
| 
| My deepest apologies if I offended, that was not my intent.

don't worry; I just want to make sure we don't get too personal.

|  I hereby
| owe you a beer (or beverage of your choice) in Berlin. :-)  (they are

Beer, beer, beer! :-)

[...]

| > Permeating the list<> interface with implications of something that
| > shouldn't have been there in the first place is a serious deviation.
| 
| Ok, so now what?  Don't fix it?

That is one choice; another is make it clear it is linear :-)

[...]

| >    (1) what would have been more interesting is the percentage of
| >        those usage that are not "hookey usage" of list<>.  I take that
| >        percentage to be far compelling.
| 
| Every single use that does not compare size() to 0 is not  "hookey"
| (imho).  In my previous email that is 3 out of 3 of the  examples I
| posted.

I guess, I'll rephase differently.  The concern is not just that
size() is compared to 0 -- I would think empty() is a better choice --
but whether list of "the right" choise in the first place.  I noted
your earlier example with airline booking; I need to be convinced that
it is a represetative example -- usually in realistic applications
like that, customers are linked through other criteria too, which makes
std::list not an obvious choice. 

| >    (2) if we're going to designe the interface governed by raw
| >        numbers, then I suggest we remove the invalidation stuff from
| >        iterators.  I suspect that the number of applications or
| >        programmers that would be saved from those rules would
| >        outweight what wouldbe gained from fiddling with list<>
| >        interface.
| >
| > Regarding (2), it can be suspected that the invalidation rules
| > actually reflect algorithmic and representational constraints on the
| > container anr iterator users.
| 
| The interface is already designed.  We are seeing problems in the
| field with the current design.  I (actually we - http://www.open-
| std.org/jtc1/sc22/wg21/docs/papers/2005/n1870.html#require-size-to-be-
| of-constant-complexity) are proposing to tweak the interface based on
| a decade of actual field experience.  Is that not a reasonable course
| of action?

It is!

I believe your concern is whether it will lead to the result you expect,
e.g., whether people would agree on voting on it.  I was giving you the
way I see it with respect to list<>. 

-- Gaby