Array, AA Implementations

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Wed Oct 21 18:35:53 PDT 2009


Yigal Chripun wrote:
> On 19/10/2009 23:42, Andrei Alexandrescu wrote:
>> Yigal Chripun wrote:
>>> here's an example of a well designed, consistent API:
>>> http://www.gobosoft.com/eiffel/gobo/structure/index.html
>>
>> This is a solid framework, unlike Java's containers which are a joke. I
>> disagree with some of Gobo's abstractions (e.g. I believe all containers
>> must be traversable and that primitives such as count() have no place in
>> a general container) but generally the framework seems to be very well
>> put together. It's a great source of inspiration for Phobos. Thanks very
>> much for the link.
>>
>> Andrei
> 
> My understanding of this design is that they identified all the 
> orthogonal properties relevant to containers and that specific 
> containers are a composition of a specific set of such properties.
> Eiffel has MI (different from the c++ implementation) which is helpful 
> if you already have suitable default implementations for these properties.
> 
> regarding "traversable" property:
> what if I want a container for a non-ordered type? an example would be a 
> container of complex numbers, how would you traverse it?
> 
> what about hash tables?

Well as others mentioned, a hash table is traversable, just not in a 
particularly ordered manner.

IMHO any container must offer at the very least (I'll use stylized 
signatures):

1. Got any?

bool empty();

2. Iterate using at least a one-pass range

OnePassRange!E opSlice();

3. Remove some element from the container and give it to me

E removeAny();

4. Add an element to the container is possible

bool add(E);

5. Nuke

void clear();

I think any container must support these primitives in O(1), and I find 
it difficult to think of a significant category of containers that can't 
support them (but then there may as well be, so please join me in 
thinking of that). A lot of stuff can be done with only these few methods.

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.

Please let me know of any thoughts.


Andrei



More information about the Digitalmars-d mailing list