According to [lib.associative.reqmts] table 69, the runtime comlexity
of insert(p, t) and erase(q) can be done in amortized constant time.

It was my understanding that an associative container could be
implemented as a balanced binary tree.

For inser(p, t), you 'll have to iterate to p's next node to see if t
can be placed next to p.
Furthermore, the insertion usually takes place at leaf nodes. An
insert next to the root node will be done at the left of the root next
node

So when p is the root node you 'll have to iterate from the root to
its next node, which  takes O(log(size)) time in a balanced tree.

If you insert all values with insert(root, t) (where root is the root
of the tree before insertion) then each insert takes O(log(size))
time.
The amortized complexity per insertion will be O(log(size)) also.

For erase(q), the normal algorithm for deleting a node that has no
empty left or right subtree, is to iterate to the next (or previous),
which is a leaf node. Then exchange the node with the next and delete
the leaf node.
Furthermore according to DR 130, erase should return the next node of
the node erased.
Thus erasing the root node, requires iterating to the next node.

Now if you empty a map by deleting the root node until the map is
empty, each operation will take O(log(size)), and the amortized
complexity is still O(log(size)).

The operations can be done in amortized constant time if iterating to
the next node can be done in (non amortized) constant time.
This can be done by putting all nodes in a double linked list.
This requires two extra links per node.
To me this is a bit overkill since you can already efficiently insert
or erase ranges with erase(first, last) and insert(first, last).

Hans.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]