A faster std::set?

[mattpd]

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

[mattpd]

I've posted suggesting intrusive containers from Boost.Intrusive with links but apparently that got moderated. Let's try again, without helpful links, perhaps, that'll make the mods happy ;-)

[monarch_dodra]

This is an assignment I have been given ("make it faster!"). The requirement is to store large numbers of these range sets in memory.

Are you sure your algorithm is optimal? Step one of making things faster is having the best algorithm. Forget your code for just a minute and see of you can't do things smarter. You mentioned ranges, which probably means your problem is complex, but the good news is that it also means there might be better mathematical solutions.

****-written code backed-up with a good algorithm will ALWAYS cream hands down a bad algorithm, even with the most optimized code ever.

Algorithmic problems are always (IMO) the most fun. I'd help, but you haven't posted what you are actually trying to do :(

I need to do some profiling, too, but my manager seems to think std::set can be rewritten to make it more efficient.

"std::set" was written as best as it can be. If you rewrite it, and get something faster, then you didn't rewrite std::set, you created something... different. If you find std::set is not fast enough for you, then blame your choice of container, NOT the implementation of set.

----
How large is your collection of data? Would using an std::unordered_set (hash container) help? You should be able to migrate to one with minimal effort. std::unordered_set is available with C++11, but you can find an equivalent implementation at boost::hash_set.

----
Writing (or rewriting) your own container should really be last thing you should try, after you are certain there are no better ways to speed up your code.

That said, if you a are certain it is the only way, and have a good rationale for it, I wouldn't mind helping you find a good data structure.

[darwen]

One thing I've done to speed up this sort of thing before is to add all elements to a list (unordered) first, then sort the list.

You can then easily remove duplicates by checking adjacent elements.

You can also use the std::lower_bound method to find elements (doing a binary search).

This not only can have significant speed improvements over set (if you have a large number of elements) but also will reduce memory fragmentation.

Darwen.