I've been experimenting recently and I've realized that uniqueness is also needed for set/map so I've been working on the following overloads for flat_xxx and map/set family:
//Precondition: User must guarantee ordered an unique sequence set::set(ordered_unique_t, Iter, Iter);
//Precondition: User must guarantee ordered an unique sequence multiset::multiset(ordered_t, Iter, Iter);
//Usage std::vector<T> v; //... std::sort(v.begin(), v.end());
flat_multimap m(ordered, v.begin(), v.end());
rbtree containers can also benefit from this optimization avoiding any comparison and thus improving construction time. I haven't looked at adding ordered range insertion (that would require checking for the correct position and in the case of set/maps assuring no duplicates, which we should handle in an efficient way) but that could be also interesting. Of course, this could break container invariants if preconditions are not met, but I think these advanced functions can be interesting for efficiency hungry boosters.
Seems fine to me. You may choose to check the precondition inside BOOST_ASSERT since it can also be done in O(n) time. -Thorsten