This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.
Section: 24.2.7 [associative.reqmts] Status: NAD Submitter: Hans B os Opened: 2004-12-19 Last modified: 2016-01-28
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).