Array, AA Implementations

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Wed Oct 21 21:39:30 PDT 2009


Bill Baxter wrote:
> On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> 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);
> 
>> 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.
> 
> I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better.

Andrei



More information about the Digitalmars-d mailing list