P.J. Plauger said:
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.
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. The standard defines C++ as
a set of mechanism that one can use to implement all sorts of misschief.
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.
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.
You can indeed call copy with a bad pair of iterators and write all over
memory. Extra iterator debugging logic can catch some such calls, but not
all. And even if an implementation wanted to do this sort of checking all
the time, it can't. Time complexity requirements in the C++ Standard often
forbid it.
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?
So the C++ Standard partly institutionalizes the wild 'n wooly
approach to programming.
True! Now, opinions may vary as to whether that is a good thing or not.
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.
Template class list has just one member function, which splices in part
of another list, that *requires* linear time to do its work safely.
Some of us have seen to it that the C++ Standard *permits* this member
function to take that time if the implementer so chooses. It so happens
that this is the only member function across all containers that *can*
go faster by taking advantage of another latitude in the C++ Standard --
to have list::size() take linear time instead of constant. Put simply,
slow size() is there to permit fast partial splice (which is still not
guaranteed).
So here is at least one case in the C++ Standard where:
a) people don't like the prospect that calling size() for a container
might take linear time
b) we could remove that requirement from the C++ Standard if all
implementations did their counting at partial-splice time
c) while we're counting the nodes moved during a partial splice, we
can even enforce the integrity goals of OOP
That would be the only place in the standard then. Maybe you are onto
something in setting a precedence.
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.
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().
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.)
Best
Kai-Uwe Bux
)