Здравствуйте, Кодт, Вы писали:

К>Возьми набор своих данных и поставь натурный эксперимент: сколько будет коллизий.

К>Вычисление хеша тоже не за нулевое время делается, хороший хеш может убить производительность посильнее коллизий.

Проверил на целочисленных данных. Апроксимированный мой случай выглядит как "тысяча небольших чисел подряд"

Здесь http://rextester.com/l/cpp_online_compiler_visual удобно проверять.
Там можно попробовать и разные компиляторы и буст, и показывается время выполнения.

На gcc и clang с 64-битным size_t куча коллизий в boost::, нет их в std:: , но при этом boost несколько быстрее
На vc с 32-битным size_t куча коллизий в std:: и их нет в boost, при этом boost сильно быстрее.

Результаты vc в онлайн компиляторе подозрительные (долго слишком, и разница std и boost слишком большая, возможно, там дебаг).
Проверил студию локально, boost всё же быстрее.

В общем, вывод "правильно — в бусте"

#include <iostream>
#include <boost/unordered_set.hpp>
#include <unordered_set>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>

volatile size_t c;

int main()
{
    std::cout << "size_t is " << std::numeric_limits<size_t>::digits << " bit\n";
    std::unordered_set<int> v;
    //boost::unordered_set<int> v;
    for (int i = 2000 ; i < 3000 ; i++ )
    {
        v.emplace(i);
    }
    
    for (int times = 0 ; times < 50000 ; times++)
    {
        for (int i = 1000 ; i < 3000 ; i++ )
        {
            c = v.count(i);
        }    
    }


    std::map<int, int, std::greater<int> > collisions;

    for (int bucket = 0, count = v.bucket_count(); bucket < count ; bucket++)
    {
        size_t size = v.bucket_size(bucket);
        if ( size > 1 )
            collisions[size]++;
    }
    
    if ( collisions.empty() )
    {
        std::cout << "No collisions\n";
    }
    else
    {
        for ( auto& it : collisions )
        {
            std::cout << it.first << ":" << it.second << "\n";
        }
    }
    
}

Здравствуйте, Кодт, Вы писали:

К>Возьми набор своих данных и поставь натурный эксперимент: сколько будет коллизий.

К>Вычисление хеша тоже не за нулевое время делается, хороший хеш может убить производительность посильнее коллизий.

Проверил на целочисленных данных. Апроксимированный мой случай выглядит как "тысяча небольших чисел подряд"

Здесь http://rextester.com/l/cpp_online_compiler_visual удобно проверять.
Там можно попробовать и разные компиляторы и буст, и показывается время выполнения (хотя там непонятно, что за конфигурация)

На gcc и clang с 64-битным size_t куча коллизий в boost::, нет их в std:: , но при этом boost несколько быстрее
На vc с 32-битным size_t куча коллизий в std:: и их нет в boost, при этом boost сильно быстрее.
Результаты vc в онлайн компиляторе подозрительные (долго слишком, и разница std и boost слишком большая, возможно, там дебаг).

Проверил студию локально, boost всё же быстрее.

	код
	#include <iostream> #include <boost/unordered_set.hpp> #include <unordered_set> #include <map> #include <functional> #include <algorithm> #include <iterator> volatile size_t c; int main() { std::cout << "size_t is " << std::numeric_limits<size_t>::digits << " bit\n"; std::unordered_set<int> v; //boost::unordered_set<int> v; for (int i = 2000 ; i < 3000 ; i++ ) { v.emplace(i); } for (int times = 0 ; times < 50000 ; times++) { for (int i = 1000 ; i < 3000 ; i++ ) { c = v.count(i); } } std::map<int, int, std::greater<int> > collisions; for (int bucket = 0, count = v.bucket_count(); bucket < count ; bucket++) { size_t size = v.bucket_size(bucket); if ( size > 1 ) collisions[size]++; } if ( collisions.empty() ) { std::cout << "No collisions\n"; } else { for ( auto& it : collisions ) { std::cout << it.first << ":" << it.second << "\n"; } } }

На строках (небольшое количество слов некоторого скриптоязыка) получается коллизий в бусте не меньше, и std чуть лучше при тесте с локальной студией.