>>102
位置指定が正しい場合にのみ、定数時間で挿入ができるらしい。
ttp://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html

で、「正しい位置」は lower_bound で取れる。