Have you considered intrusive containers from Boost.Intrusive?
http://www.boost.org/doc/libs/releas...intrusive.html

In particular:
http://www.boost.org/doc/libs/releas..._multiset.html
// there's also an unordered version, but I've skipped it since you mentioned that ordering (sorting) is a requirement;

Someone mentioned set containers not implemented as red-black trees; there are a few to choose from, each offering different trade-offs:
http://www.boost.org/doc/libs/releas..._multiset.html
http://www.boost.org/doc/libs/releas..._multiset.html
http://www.boost.org/doc/libs/releas..._multiset.html
http://www.boost.org/doc/libs/releas..._multiset.html