I think it should be declared const for all (multi)set types except for splay trees (because in this case a search rebalances the tree),
Insert check rebalances the three if needed. This is amortized constant-time so I should change this complexity in the documentation.
Best,
Ion