Time complexity of size() for std::set

[P.J. Plauger]

* P.J. Plauger:

Ah, well. Essentially there are then, in practice, two kinds of
implementations of std::list, namely fast size, and fast (unsafe) splice.

But with a given standard library implementation there's just one.

Not necessarily. Some might choose the safer form only when "iterator
debugging" is enabled, which we often do.

Wouldn't it be better to have both, accessible to the user, who could then
make the decision to use one or the other or both, with an
implementation-defined typedef of std::list for default? Was this
considered? And if it was, considering that the two could share most of
their implementations, why was it rejected?

No, this hasn't been discussed. There are many ways to push down
one bedspring, only to have another pop up in its place. I have
little sympathy for enlarging an already interface to give
programmers their choice of low and/or high bedsprings.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[P.J. Plauger]

P.J. Plauger wrote:
.....

What is different here compared to std::copy and all other functions
that
take two iterators and expect [first, last) to be valid? Am I missing
something?

Yes and no. One philosophy of C++, inherited from C, is that you should
be given enough rope to hang yourself, and speedily at that. Another,
inherited from OOP, is that a class has the right and obligation to
protect itself from misuse.

The second philosophy may have been documented in design papers for C++;
if
so, however, it does not show in the standard.

Nonsense. Look at all the requred "protected" members, and all the
internals documented as "exposition only" (so you can't reliably
muck with them. This is the very stuff of OOP.

The standard defines C++ as
a set of mechanism that one can use to implement all sorts of misschief.

Or not.

C++ does in no way enforce or even promote OOP; designing an OO-approved
class with guarded invariants is not even simpler in C++ than designing an
OO-nightmare.

You're overstating the case to the point of incorrectness.

To propose an amendment of the standard based on a philosophical
inclination
that so far has not shown in the standard seems a little bit of a stretch.

Huh? All I was doing was supporting an oft-expressed desire to
guarantee that container size() be O(1). My observation is that
there are even hygienic reasons for disallowing the one bit of
latitude that requires size() be O(N). I'm personally quite
content with the state of the C++ Standard (in this regard).

Having said that, I still dispute your claim that there is no
flavor of OOP in Standard C++. And I can report that *many*
proposed changes to the C++ Standard have philosophical
rationale.

Often? With regard to range checking I wonder: if every iterator carries a
pointer to its container one can check the validity of a range in linear
time (and constant time for random access iterators). Any algorithm that
takes a range allows for linear time on non-random access iterators
anyway.

Could you give an example where a checking implementation is ruled out by
the complexity requirements of the standard?

Many of the complexity requirements are expressed as specific
maxima -- you just can't do more comparisons, or assignments,
or whatever. In fact, complexity requirements that merely
dictate big-O time complexity are essentially untestable and
de facto toothless, except as a QOI issue.

True! Now, opinions may vary as to whether that is a good thing or not.

It's one thing to permit it; it's quite another to *mandate* it.
That was my point.

By and large, I get by with putting a safety layer between my code and the
language: e.g., a pointer_to<T> template that wraps raw pointers and
allows
for checking 0-dereferencing and tracing allocations and deallocations, or
a safe<int> type that checks for arithmetic overflows. I am not sure
whether I want the standard to change in this regard. After all, if you
want safety, you can have it. It just comes at a price.

Agreed. The issue is whether you can simultaneously pay the price
and conform. There are compelling reasons to permit both at once,
wherever possible.

That would be the only place in the standard then. Maybe you are onto
something in setting a precedence.

Indeed this *is* a rare circumstance, which is why I've pointed
it out repeatedly.

I am by and large happy with the undefined behavior solution that the
current standard employs, although I would love to have a debug-version of
the standard library that defines all those unsound ranges and out of
bounds accesses to violate some assert().

I know where you can license one...

What bothers me though, is the latitude within the complexity
requirements.
I'd rather have the standard declare unambiguously that size() is constant
time. That would at least be predictable. (Similarly, I think the standard
could require sort() to be O(n log(n)) and nth_element() to be linear.)

I agree that big-O time complexity should favor the programmer,
wherever practically possible.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Kai-Uwe Bux]

P.J. Plauger wrote:
.....

What is different here compared to std::copy and all other functions
that
take two iterators and expect [first, last) to be valid? Am I missing
something?

Yes and no. One philosophy of C++, inherited from C, is that you should
be given enough rope to hang yourself, and speedily at that. Another,
inherited from OOP, is that a class has the right and obligation to
protect itself from misuse.

The second philosophy may have been documented in design papers for C++;
if
so, however, it does not show in the standard.

Nonsense. Look at all the requred "protected" members, and all the
internals documented as "exposition only" (so you can't reliably
muck with them. This is the very stuff of OOP.

The standard defines C++ as
a set of mechanism that one can use to implement all sorts of misschief.

Or not.

C++ does in no way enforce or even promote OOP; designing an OO-approved
class with guarded invariants is not even simpler in C++ than designing
an OO-nightmare.

You're overstating the case to the point of incorrectness.

True I should have marked this paragraph as a rant.

However, the very last sentence (that writing an OO-nightmare class in C++
is not any more difficult than writing sound and proper OO-classes) is, I
think, true. We see those nightmares posted here regularly. It must be darn
easy to write that kind of code. (And I think, I am falling into that trap
every now and then.)

Huh? All I was doing was supporting an oft-expressed desire to
guarantee that container size() be O(1). My observation is that
there are even hygienic reasons for disallowing the one bit of
latitude that requires size() be O(N).

Point taken.

I'm personally quite
content with the state of the C++ Standard (in this regard).

Generally, I would favor guarantees a little bit more stronger. Although,
here it is a minor issue and unlike other cases, this one involves a real
trade-off.

Having said that, I still dispute your claim that there is no
flavor of OOP in Standard C++. And I can report that *many*
proposed changes to the C++ Standard have philosophical
rationale.

You are right: I overstated my case. There do exist instances of OOP in the
standard.

Many of the complexity requirements are expressed as specific
maxima -- you just can't do more comparisons, or assignments,
or whatever. In fact, complexity requirements that merely
dictate big-O time complexity are essentially untestable and
de facto toothless, except as a QOI issue.

True, but I still don't see how those sharp requirements (on the number of
assignments or comparisons) would interfere with range checking. I must be
missing something here. Please let me reiterate my request for a concrete
example. (Sorry for being a pain, but I find this particular point rather
interesting; and I have already learned quite a bit from the code sample
you provided upthread).


[undisputed items snipped]


Thanks

Kai-Uwe Bux

 

[Jerry Coffin]

[ ... ]

What we give up is the *permission* that implementers currently
have to let people tie granny knots in lists, to be discovered at
a later date, so that one admittedly rare form of splice can do
its damage really fast. I consider this case at least philosophically
different from calling copy with bad arguments. YMMV.

Do you know if anybody has worked on new language for C++ 0x to require
no worse than linear complexity for list, and constant complexity for
all other containers?

 

[Jorgen Grahn]

[std::list::splice()]

Sorry, I don't get this. Do you propose that we should avoid much of the
standard library?

Where did that come from? I said nothing like that.

It's the way I understand the Standard Library. Things like std::copy offer
speed and flexibility, and in return I take care when choosing with
iterators to feed into it.

So it just made sense to me that list::splice() chooses speed over safety,
too. After all, I can keep count of a list's size myself (as long as I
don't splice it), but I cannot write a splice() which works at O(1).

[snip some informative text]

I consider this case at least philosophically
different from calling copy with bad arguments. YMMV.

Yes, that is the difference I don't see. But my understanding and experience
are limited. (And I doubt I'll ever have a use for splicing lists that way.)

/Jorgen

 

[P.J. Plauger]

...

True, but I still don't see how those sharp requirements (on the number of
assignments or comparisons) would interfere with range checking. I must be
missing something here. Please let me reiterate my request for a concrete
example. (Sorry for being a pain, but I find this particular point rather
interesting; and I have already learned quite a bit from the code sample
you provided upthread).

Our library fails a dozen-odd complexity tests in our Proofer when we
run it in iterator-debugging mode. I'm late for a big delivery right
now, so I don't have time to run the tests and identify the culprits.
But here's a quick general example. It's not about range checking, but
it is about violating complexity requirements to do good checking:

We check predicates that are required to enforce strict weak ordering
by sometimes evaluating them twice; if a < b is true we verify that
b < a is not also true. This sometimes violates the limit on the number
of compares, but it has proved repeatedly to be a godsend in detecting
program flaws before access violations obscure the cause.

Best I can do right now.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[P.J. Plauger]

[ ... ]

What we give up is the *permission* that implementers currently
have to let people tie granny knots in lists, to be discovered at
a later date, so that one admittedly rare form of splice can do
its damage really fast. I consider this case at least philosophically
different from calling copy with bad arguments. YMMV.

Do you know if anybody has worked on new language for C++ 0x to require
no worse than linear complexity for list, and constant complexity for
all other containers?

I believe there's a DR about the complexity of size() in general.
Don't remember the details.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com