fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <iterator>
  4. #include <vector>
  5. #include <set>
  6. #include <ctime>
  7. #include <algorithm>
  8.  
  9. int main()
  10. {
  11.     using namespace std;
  12.  
  13.     vector<string> vs(2000000);
  14.     for (int i = 0; i < vs.size(); ++i)
  15.     {
  16.         vs[i] = to_string(i);
  17.     }
  18.  
  19.     set<string> ss(vs.begin(), vs.end());
  20.  
  21.     {
  22.         cout << "linear search on vector" << endl;
  23.         time_t now = clock();
  24.         auto s = find(vs.begin(), vs.end(), "1000000");
  25.         cout << "linear search for \"1000000\" took: " 
  26.         	<< double(clock() - now) / CLOCKS_PER_SEC  << " found " << *s << endl;
  27.     }
  28.     {
  29.         cout << "\nbinary search on vector" << endl;
  30.         sort(vs.begin(), vs.end());
  31.         time_t now = clock();
  32.         auto s = lower_bound(vs.begin(), vs.end(), "1000000");
  33.         cout << "binary search for \"1000000\" took: " 
  34.         	<< double(clock() - now) / CLOCKS_PER_SEC  << " found " << *s << endl;
  35.     }
  36.     {
  37.         cout << "\nbinary search on set" << endl;
  38.         time_t now = clock();
  39.         auto s = ss.find("1000000");
  40.         cout << "binary search for \"1000000\" took: " 
  41.         	<< double(clock() - now) / CLOCKS_PER_SEC << " found " << *s << endl;
  42.     }
  43. }
Success #stdin #stdout 4.68s 97152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
linear search on vector
linear search for "1000000" took: 0.03 found 1000000

binary search on vector
binary search for "1000000" took: 0 found 1000000

binary search on set
binary search for "1000000" took: 0 found 1000000
https://ideone.com/dCBnL3
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!