[C++] Should the complexity of std::list::size() be O(n) or O(1)?
Gabriel Dos Reis
gdr@integrable-solutions.net
Tue Nov 29 04:05:00 GMT 2005
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
More information about the Libstdc++
mailing list