Ordered Vs. Unordered Sets

In mathematics, a set has no order. The sets  {1,2,3}  and {3,2,1}   are equivalent.  STL’s std::set diverges from the mathematical definition and imposes an order on its elements. Typically the set is implemented internally as a red-black tree.  a compare predicate (by default the std::less <T>  operator) determines the position of a new element in the tree.   It allows for efficient iteration over the elements for a price:   insertion, removal and search of an element cost an average of  O(log n).  This is not too bad for small sets, however, it can become an issue for larger sets or sets accessed from performance critical code. 

If all you need is a container that will keep track weather and object is contained in a set or not.   You are better off using  unordered_set  (introduced in C++ 11) its functionality is similar to the pre-C++ 11  STL set,  Only it is implemented as a hash table with an average, insert, delete and search  times of O(1)    with large sets the difference is noticeable:

#include <iostream>
#include <chrono>
#include <unordered_set>
#include <set>
#include <string>

template <typename TimeT = std::chrono::milliseconds> struct measure {
    template <typename F, typename... Args> static typename TimeT::rep execution(F func, Args&&... args)
    {
        auto start = std::chrono::system_clock::now();
        // Now call the function with all the parameters you need.
        func(std::forward<Args>(args)...);
        auto duration = std::chrono::duration_cast<TimeT>(std::chrono::system_clock::now() - start);
        return duration.count();
    }
};

std::string baseString = "abcdefghi";

class SetContainer
{
public:
    void populate_unordered_set()
    {
        std::string s = baseString;
        while(std::next_permutation(begin(s), end(s))) {
            unorderedSet.insert(s);
        }
    }

    void populate_ordered_set()
    {
        std::string s = baseString;
        while(std::next_permutation(begin(s), end(s))) {
            orderedSet.insert(s);
        }
    }

    bool ordered_set_has(std::string val)
    {
        return (orderedSet.find(val) != orderedSet.end());
    }

    bool unordered_set_has(std::string val)
    {
        return (unorderedSet.find(val) != unorderedSet.end());
    }

    long iterate_ordered_set()
    {
        long count = 0;

        for(auto& s : orderedSet) {
            count++;
        }
        return count;
    }

    bool iterate_unordered_set()
    {
        long count = 0;
        for(auto& s : unorderedSet) {
            count++;
        }
        return count;
    }

private:
    std::unordered_set<std::string> unorderedSet;
    std::set<std::string> orderedSet;
};

using nsMeasure = measure<std::chrono::nanoseconds>;

int main(int argc, char** argv)
{
    SetContainer setContainer;
    std::cout << "Unordered set population time (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::populate_unordered_set, &setContainer)) << '\n';
    std::cout << "Ordered set population time (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::populate_ordered_set, &setContainer)) << "\n\n";

    std::string searchVal = "abcdefgih";
    std::cout << "searching for " << searchVal << " :\n";

    std::cout << "Unordered Set (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::unordered_set_has, &setContainer, searchVal)) << '\n';
    std::cout << "Ordered Set (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::ordered_set_has, &setContainer, searchVal)) << "\n\n";

    std::cout << "Unordered set's elements iteration (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::iterate_unordered_set, &setContainer)) << '\n';
    std::cout << "Ordered set's elements iteration (ns) :"
              << nsMeasure::execution(std::bind(&SetContainer::iterate_ordered_set, &setContainer)) << "\n\n"   ;

    return 0;
}


Unordered set population time (ns) :225967000
Ordered set population time (ns) :277887000

searching for abcdefgih :

Unordered Set (ns) :2000
Ordered Set (ns) :6000

Unordered set’s elements iteration (ns) :29006000
Ordered set’s elements iteration (ns) :17211000

(The handy measure template is from Nikos Athanasiou’s answer on Stackoverflow.com)

The program above was compiled with clang in release mode and -O2 flag.

As you can see from the output,  inserting element in the unordered  set, took nearly half of the time it took to insert an element in the ordered  set.  The unordered container search time  is third of the ordered set’s  search time.  On the other hand iterating over the unordered set  takes twice as much as the unordered set .

Conclusion

Like a cable subscription: there is really no reason to pay for the all inclusive plan when you are only going to watch the sci-fi channel.  If all you want is to keep track of a bunch of objects and you rarely need to iterate over the elements in the set, consider using the unordered set for better performance.