Find in vector vs unordered_map, C++ (clang)

Find in vector vs unordered_map

//clang 3.7.0

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <algorithm>
#include <random>

std::pair<double, std::chrono::nanoseconds> testVector(std::size_t size, std::size_t repeate) {
    
    std::vector<std::pair<std::size_t, double>> vec(size);
    
    std::size_t count = 0;
    for(auto&& elem : vec) {
        elem.first = count;
        elem.second = static_cast<double>(count);
        ++count;
    }
    
    std::random_device rd;
    std::mt19937 g(rd());
    
    std::shuffle(vec.begin(), vec.end(), g);

auto start = std::chrono::high_resolution_clock::now();
    double sum = 0.0;
    for(int j = 0; j < repeate; ++j) {
        for(std::size_t i = 0; i < size; ++i) {
            auto it = std::find_if(vec.begin(), vec.end(), [&](const auto& elem) {return elem.first == i;});
            sum += it->second;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    
    return {sum, std::chrono::duration_cast<std::chrono::nanoseconds>(end - start)}; 
}

std::pair<double, std::chrono::nanoseconds> testUnorderedMap(std::size_t size, std::size_t repeate) {
    
    std::unordered_map<std::size_t, double> map(size);
    
    for(std::size_t i = 0; i < size; ++i) {
        map[i] = static_cast<double>(i);
    }
    
    auto start = std::chrono::high_resolution_clock::now();
    double sum = 0.0;
    for(int j = 0; j < repeate; ++j) {
        for(std::size_t i = 0; i < size; ++i) {
            auto it = map.find(i);
            sum += it->second;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    
    return {sum, std::chrono::duration_cast<std::chrono::nanoseconds>(end - start)}; 
}

int main()
{
    std::cout << "Vector \n";
    
    std::cout << "size\t rep\t time (ns)\t per find (ns)\n";
    std::size_t size = 5;
    for (std::size_t rep = 1; rep < (1<<20); rep += rep) {
        double sum = rep * size*(size-1)/2.0;
        auto res = testVector(size, rep);
        if( sum != res.first) {std::cout << "ERROR"; break;}
        std::cout << size << "\t" << rep << "\t" << res.second.count() <<"\t" << static_cast<double>(res.second.count()) / size / rep << "\n";
    }
    
    std::cout << "\n";
    
    std::cout << "size\t rep\t time (ns)\t per find (ns)\n";
    
    std::size_t rep = (1<<10);
    for (std::size_t size = 1; size < (1<<12); size += size) {
        double sum = rep * size*(size-1)/2.0;
        auto res = testVector(size, rep);
        if( sum != res.first) {std::cout << "ERROR"; break;}
        std::cout << size << "\t" << rep << "\t" << res.second.count() <<"\t" << static_cast<double>(res.second.count()) / size / rep << "\n";
    }
    
    std::cout << "\nUnorderedMap \n";
    
    std::cout << "size\t rep\t time (ns)\t per find (ns)\n";
    size = 5;
    for (std::size_t rep = 1; rep < (1<<20); rep += rep) {
        double sum = rep * size*(size-1)/2.0;
        auto res = testUnorderedMap(size, rep);
        if( sum != res.first) {std::cout << "ERROR"; break;}
        std::cout << size << "\t" << rep << "\t" << res.second.count() <<"\t" << static_cast<double>(res.second.count()) / size / rep << "\n";
    }
    
    std::cout << "\n";
    
    std::cout << "size\t rep\t time (ns)\t per find (ns)\n";
    
    rep = (1<<10);
    for (std::size_t size = 1; size < (1<<12); size += size) {
        double sum = rep * size*(size-1)/2.0;
        auto res = testUnorderedMap(size, rep);
        if( sum != res.first) {std::cout << "ERROR"; break;}
        std::cout << size << "\t" << rep << "\t" << res.second.count() <<"\t" << static_cast<double>(res.second.count()) / size / rep << "\n";
    }
    
    
}


run \| edit \| history \| help	0