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)?
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. I hereby
owe you a beer (or beverage of your choice) in Berlin. :-) (they are
now my customers too and I'm just trying to deliver to them the best
product I can).
| We have a serious performance problem today with list. It does no
| good to wish it away because we disagree with a decision that was
| made nearly a decade ago. We need to deal with the state of affairs
| as it exists today.
and that is all I'm saying. I'm not asking you to find a time-travel
machine and go tell the committee it is making a mistake about
list<>::size() and change its mind. Maybe someone suggested that, but
it wasn't me.
If I do find such a machine, I promise never to mention std::list
again. :-)
| I have repeatedly tried to back up my opinions with evidence (and
| spent time gathering it for your benefit) (examples, pointers to
| actual code, etc.). I am fully aware of your opinion. Can you
| please point me towards supporting evidence so that I can better
| understand your position?
Well, it has its origin in the design principles underpinning STL.
STL is not just about funny type names with angle brackets, double
colon, begin, end, size, and lots of parenthesis.
The fundamentals are in structuring algorithms/functions and
algorithmic complexity into concepts and relatives.
Those principles help keep a simple, consistent, efficient interface.
Right! This is something that goes deep with me too! list doesn't
have an operator[] because it would be deceptively inefficient. Nor
does it have iter-iter, or iter+n, etc. All of these would be easy
to create. They would just create an inefficient interface. An O(N)
size is an inefficient interface. My "raw numbers" are only
presented to confirm the theory with practice.
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?
Now, you're trying to argue from raw numbers.
...
I guess, we have reached a point where we would just going to
repeat the same thing over and over again.
I'm trying to not repeat myself, but to offer fresh angles and new
supporting arguments. I'm ill-equipped to be both non-repetitive,
and yet also perfectly constrained to the boundaries of my initial
argument.
(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.
(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?
-Howard