Array, AA Implementations

[Steven Schveighoffer]

On Thu, 22 Oct 2009 09:07:47 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> 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.

Yes, but it's actually O(n) to traverse the entire tree, because you  
traverse 2n edges in the tree (one left and one right) twice (once to go  
down, and once to go back).

-Steve