Array, AA Implementations

[Andrei Alexandrescu]

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