### 494. Wrong runtime complexity for associative container's insert and delete

**Section:** 26.2.6 [associative.reqmts] **Status:** NAD
**Submitter:** Hans B os **Opened:** 2004-12-19 **Last modified:** 2016-02-10

**Priority: **Not Prioritized

**View other** active issues in [associative.reqmts].

**View all other** issues in [associative.reqmts].

**View all issues with** NAD status.

**Discussion:**

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

**Proposed resolution:**

**Rationale:**

Only "amortized constant" in special circumstances, and we believe
that's implementable. That is: doing this N times will be O(N), not
O(log N).