Don wrote:
Andrei Alexandrescu wrote:
Bill Baxter wrote:
On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
<seewebsiteforem...@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
