Test the performance of unordered vs ordered containers.

main.cpp

/*
 * Small test of the performance of 
 *  - unordered_set vs set 
 *  - unordered_map vs map
 * Compile with g++ main.cpp -std=c++11
 * As expected, the unordered versions are faster because they use hash functions, not trees.
 */

#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>
#include <iostream>
#include <chrono>
#include <vector>
#include <cassert>
#include <string>
#include <cmath>
/*
 * Populate the container with NumElems many strings.
 * Return how long it took to fetch all of the elements.
 */
template< typename CONTAINER >
int SetTest( CONTAINER c, const int NumElems, const int NumIter )
{
    c.clear();
    std::vector<std::string> elements;
    for(int i = 1; i <= NumElems; ++i)
    {
        std::string s(i, 'a');
        c.insert(s);
        elements.push_back(s);
    }
    assert( c.size() == NumElems );
    assert( elements.size() == NumElems );
    auto start = std::chrono::steady_clock::now();
    for( int iter = 0; iter < NumIter; ++iter )
    {
        for( auto e : elements )
        {
            typename CONTAINER::const_iterator gotFromContainer = c.find( e );
            assert( gotFromContainer != c.end() );
        }
    }
    auto stop = std::chrono::steady_clock::now();
    auto diff = stop - start;
    int milliseconds = std::chrono::duration<double, std::milli>( diff ).count();
    return milliseconds;
}

/*
 * Populate the container with NumElems many strings.
 * Return how long it took to fetch all of the elements.
 */
template< typename CONTAINER >
int MapTest(CONTAINER c, const int NumElems, const int NumIter )
{
    c.clear();
    std::vector<std::pair<std::string, std::string>> elements;
    for(int i = 1; i <= NumElems; ++i)
    {
        std::string s(i, 'a');
        std::pair<std::string, std::string> p(s, s);
        c.insert(p);
        elements.push_back(p);
    }
    assert( c.size() == NumElems );
    assert( elements.size() == NumElems );
    auto start = std::chrono::steady_clock::now();
    std::string gotFromContainer;
    for( int iter = 0; iter < NumIter; ++iter )
    {
        for( auto e : elements )
        {
            gotFromContainer = c.at(e.first);
        }
    }
    auto stop = std::chrono::steady_clock::now();
    auto diff = stop - start;
    int milliseconds = std::chrono::duration<double, std::nano>( diff ).count();
    return milliseconds;
}

int main()
{
    std::map<std::string, std::string> Map;
    const int MapTime = MapTest( Map, 100, 1000 );
    std::cout << "Time to query map: " << MapTime << std::endl;

    std::unordered_map<std::string, std::string> UnorderedMap;
    const int UnorderedMapTime = MapTest( UnorderedMap, 100, 1000 );
    std::cout << "Time to query unordered_map: " << UnorderedMapTime << std::endl;

    std::set<std::string> Set;
    const int SetTime = SetTest(Set, 100, 1000);
    std::cout << "Time to query set: " << SetTime << std::endl;

    std::unordered_set<std::string> UnorderedSet;
    const int UnorderedSetTime = SetTest(UnorderedSet, 100, 1000);
    std::cout << "Time to query unordered_set: " << UnorderedSetTime << std::endl;
}