Array, AA Implementations

[Andrei Alexandrescu]

Don wrote:
> Andrei Alexandrescu wrote:
>> 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
> Can it be amortized O(lg N) ?

Don't see why not. Also, it turns out that iteration over a tree may 
cost O(log n) per step.

Andrei