C++のstd::unordered_mapと同じように使えるtsl::robin_map。
std::unordered_mapと比較してみた。VC++2022でInsertとFindの時間を計ってみたが、何度かやると順位が入れ替わったりするのであまり大きな差はなさそう。
https://github.com/Tessil/robin-map
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <random> #include <chrono> #include <tsl/robin_map.h> /* using KeyT = int; using ValueT = std::string; KeyT MakeKey(int i) { return i; } ValueT MakeValue(int i) { return "Value_" + std::to_string(i); } */ using KeyT = std::string; using ValueT = int; KeyT MakeKey(int i) { return "Value_" + std::to_string(i); } ValueT MakeValue(int i) { return i; }
std::vector< std::pair<KeyT, ValueT> > CreateData(int count) { std::vector< std::pair<KeyT, ValueT> > data; data.reserve(count); for (int i = 0; i < count; ++i) { data.emplace_back(MakeKey(i), MakeValue(i)); } return data; }
template<typename HashMap> void InsertTest(HashMap& mymap,const std::vector< std::pair<KeyT, ValueT> >& data) { for (size_t i = 0; i < data.size(); ++i) { mymap.insert({ data[i].first,data[i].second }); } }
template<typename HashMap> int FindTest(const HashMap& mymap, const std::vector< std::pair<KeyT, ValueT> >& data) { int results_count = 0; for (size_t i = 0; i < data.size(); ++i) { auto itr = mymap.find(data[i].first); if (itr != mymap.end()) { ++results_count; } } return results_count; }
struct test_times { std::chrono::microseconds insert_time; std::chrono::microseconds find_time; };
template<typename HashMap> test_times test( const std::vector< std::pair<KeyT, ValueT> > inserts, const std::vector< std::pair<KeyT, ValueT> > finds, HashMap& mymap) { test_times result; std::chrono::steady_clock::time_point start,end; /////////////////////////////////////////////////////////////// { // データを保存する時間の計測 start = std::chrono::high_resolution_clock::now(); mymap.reserve(inserts.size()); InsertTest(mymap, inserts); end = std::chrono::high_resolution_clock::now(); result.insert_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start); } /////////////////////////////////////////////////////////////// { // データを検索する時間の計測 start = std::chrono::high_resolution_clock::now(); volatile int ret = FindTest(mymap, finds); end = std::chrono::high_resolution_clock::now(); result.find_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start); } /////////////////////////////////////////////////////////////// return result; }
int main() { tsl::robin_map<KeyT, ValueT> mymap_robin; std::unordered_map<KeyT, ValueT> mymap_std; auto data = CreateData(100000); auto inserts = data; auto finds = data; int count = 100; int count_robin_insert = 0; int count_robin_find = 0; int count_std_insert = 0; int count_std_fine = 0; for (int i = 0; i < count; i++) { // データの並びを変える std::shuffle(inserts.begin(), inserts.end(), std::mt19937{ std::random_device{}() }); std::shuffle(finds.begin(), finds.end(), std::mt19937{ std::random_device{}() }); mymap_robin.clear(); mymap_robin.rehash(0); mymap_std.clear(); mymap_std.rehash(0); test_times robin = test(inserts, finds, mymap_robin); test_times stdmp = test(inserts, finds, mymap_std); count_robin_find += robin.find_time.count(); count_robin_insert += robin.insert_time.count(); count_std_insert += stdmp.insert_time.count(); count_std_fine += stdmp.find_time.count(); } std::cout << "robin insert time (ms): " << count_robin_insert / count << std::endl; std::cout << " std insert time (ms): " << count_std_insert / count << std::endl; std::cout << "------------------------" << std::endl; std::cout << "robin find time (ms): " << count_robin_find / count << std::endl; std::cout << " std find time (ms): " << count_std_fine / count << std::endl; return 0; }
KeyT == std::string , ValueT==int の場合
KeyT==int , ValueT == std::string の場合