fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <random>
  5. #include <unordered_map>
  6. #include <chrono>
  7. #include <algorithm>
  8. #include <functional>
  9.  
  10. using namespace std;
  11.  
  12. struct Foo
  13. {
  14.     std::size_t hash;
  15.     std::string name;
  16. };
  17.  
  18. std::vector<Foo> generate_random_vec(std::size_t SIZE)
  19. {
  20.     const char alphanumeric[] = " 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  21.  
  22.     std::default_random_engine rng;
  23.     std::uniform_int_distribution<> dist (0, sizeof(alphanumeric) - 2);
  24.     std::vector<Foo> result;
  25.     result.resize(SIZE);
  26.  
  27.     std::random_device rd;
  28.     std::mt19937 mt(rd());
  29.     std::uniform_int_distribution<int>  dist_string_length(4, 32);
  30.  
  31.     for (std::size_t count = 0; count < SIZE; ++count)
  32.     {
  33.         std::string str;
  34.         for (uint8_t i = 0; i < dist_string_length(mt); ++i)
  35.         {
  36.             str += alphanumeric[dist(rng)];
  37.         }
  38.  
  39.         Foo obj;
  40.         obj.name = std::move(str);
  41.         result[count] = obj;
  42.     }
  43.  
  44.     return result;
  45. }
  46.  
  47. struct OrderFooByNameHash
  48. {
  49.     inline bool operator () ( const Foo& _left, const Foo& _right )  
  50.     {
  51.         return _left.hash < _right.hash;
  52.     }
  53.     inline bool operator () ( const std::hash<std::string>::result_type& _left, const Foo& _right ) const
  54.     {
  55.     	return _left < _right.hash;
  56. 	}
  57.     inline bool operator () ( const Foo& _left, const std::hash<std::string>::result_type& _right ) const
  58.     {
  59.         return _left.hash < _right;
  60.     }
  61. };
  62.  
  63.  
  64.  
  65. int main() {
  66.     Foo obj_find = {0, "String to find"};
  67.     obj_find.hash = std::hash<std::string>()(obj_find.name);
  68.     std::vector<Foo> vec_string = generate_random_vec(100000);
  69.     std::unordered_map<std::string,int> stringToMap;
  70.  
  71.     vec_string.push_back(obj_find);
  72.  
  73.     std::hash<std::string> hash_fn;
  74.     for (auto& itr : vec_string)
  75.         itr.hash = hash_fn(itr.name);
  76.  
  77.     for (auto itr : vec_string)
  78.         stringToMap.emplace(itr.name, 1);
  79.  
  80.     std::sort( vec_string.begin(), vec_string.end(), OrderFooByNameHash());
  81.  
  82.     //for (auto itr : vec_string)
  83.       //  std::cout << itr.name << std::endl;
  84.     //for (auto itr : stringToMap)
  85.       //  std::cout << itr.first << std::endl;
  86.     bool found_string = false;
  87.     std::size_t RUN_COUNT = 500000;
  88.     const auto startTime_1 = chrono::high_resolution_clock::now();
  89.     for (int count = 0; count < RUN_COUNT; ++count)
  90.     {
  91.         auto itr = std::lower_bound( vec_string.begin(), vec_string.end(), obj_find.hash, OrderFooByNameHash());
  92.         for (; itr != vec_string.end(); ++itr)
  93.     	{
  94.     	    if ((*itr).hash != obj_find.hash)
  95.     	        break;
  96.  
  97.     	    if ((*itr).name == obj_find.name)
  98.     	    {
  99.     	    	int i = 0;
  100.     	    }
  101.     	}
  102.     }
  103.     chrono::high_resolution_clock::duration elapsedTime_1 = chrono::high_resolution_clock::now() - startTime_1;
  104.     std::cout << "sorted_vector Time: " << chrono::duration_cast<chrono::milliseconds>(elapsedTime_1).count() << " ms" << std::endl;
  105.  
  106. 	const auto startTime_2 = chrono::high_resolution_clock::now();
  107.     for (int count = 0; count < RUN_COUNT; ++count)
  108.     {
  109.         const auto startTime = chrono::high_resolution_clock::now();
  110.         auto itr = stringToMap.find(obj_find.name);
  111.         if (itr != stringToMap.end() && itr->first == obj_find.name)
  112.         {
  113.             int i = 0;
  114.         }
  115.     }
  116.     chrono::high_resolution_clock::duration elapsedTime_2 = chrono::high_resolution_clock::now() - startTime_2;
  117.     std::cout << "unordered_map Time: " << chrono::duration_cast<chrono::milliseconds>(elapsedTime_2).count() << " ms" << std::endl;
  118.  
  119.     return 0;
  120. }
Success #stdin #stdout 0.41s 9072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sorted_vector Time: 20 ms
unordered_map Time: 152 ms
https://ideone.com/Y7jIly
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!