Rainer Deyke wrote:
Andrei Alexandrescu wrote:
IMHO any container must offer at the very least (I'll use stylized
signatures):
2. Iterate using at least a one-pass range
OnePassRange!E opSlice();
Requiring this to be O(1) seems silly, since the actual iteration will
never be O(1) and can't even be guaranteed to be O(n).
The idea is that the cost of creating the iterator should not be
significant. The cost of the iteration should be O(n) (not greater).
3. Remove some element from the container and give it to me
E removeAny();
IIRC, C++ had a good reason (related to exception safety) for separating
retrieval and removal operations.
C++ does not have D's latitude to relocate objects.
Note that even though length() is not part of the interface (as is in
Gobo's library), it can be computed through iteration with a generic
algorithm. The idea is to not force containers to write that themselves
or ungainly cache the length.
If the length is often needed, caching is much more efficient than
recalculating from scratch.
Yah, client code or a refined container may cache it. This has been a
long discussion in the C++ community. Short version: you can't
reasonably require O(1) length.
Andrei
