fork(3) download
copy 
  1. #include <iostream>
  2. #include <chrono>
  3. #include <random>
  4. #include <algorithm>
  5. #include <string>
  6. #include <vector>
  7. #include <deque>
  8. #include <set>
  9. #include <algorithm>
  10.  
  11. const int Size = 10000;
  12.  
  13. int rnd(int max) { static auto engine = std::default_random_engine(); return engine() % max; }
  14.  
  15. // really simple RAII timer utility
  16. struct timer
  17. {
  18.    typedef std::chrono::high_resolution_clock clock;
  19.    clock::time_point start_;
  20.  
  21.    timer() : start_(clock::now()) {}
  22.    ~timer()
  23.    {
  24.       std::cout 
  25.          << ((double)std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start_).count() / 1000.)
  26.          << "ms" << std::endl;
  27.    }
  28. };
  29.  
  30. //
  31. // std::vector<> specialisations
  32. //
  33.  
  34. // insert into a sorted vector<>
  35. void insert(std::vector<int> & c, int val)
  36. {
  37.    // first find the insertion point (naiively)
  38.    auto it = c.begin(); 
  39.    while (it != c.end() && *it <= val) ++it;
  40.  
  41.    c.insert(it, val);
  42. }
  43.  
  44. // find in a sorted vector<>
  45. bool find(std::vector<int> & c, int val)
  46. {
  47.    return c.end() != std::find(c.begin(), c.end(), val);
  48. }
  49.  
  50. bool isSorted(std::vector<int> & c)
  51. {
  52.    int prev = -1;
  53.    for (auto v : c)
  54.    {
  55.       if (v < prev) return false;
  56.       prev = v;
  57.    }
  58.    return true;
  59. }
  60.  
  61. //
  62. // std::deque<> specialisations
  63. //
  64.  
  65. // insert into a sorted deque<>
  66. void insert(std::deque<int> & c, int val)
  67. {
  68.    // first find the insertion point (naiively)
  69.    auto it = c.begin(); 
  70.    while (it != c.end() && *it <= val) ++it;
  71.  
  72.    c.insert(it, val);
  73. }
  74.  
  75. // find in a sorted deque<>
  76. bool find(std::deque<int> & c, int val)
  77. {
  78.    return c.end() != std::find(c.begin(), c.end(), val);
  79. }
  80.  
  81. bool isSorted(std::deque<int> & c)
  82. {
  83.    int prev = -1;
  84.    for (auto v : c)
  85.    {
  86.       if (v < prev) return false;
  87.       prev = v;
  88.    }
  89.    return true;
  90. }
  91.  
  92. //
  93. // std::set<> specialisations
  94. //
  95.  
  96. void insert(std::set<int> & c, int val)
  97. {
  98.    c.insert(val);
  99. }
  100.  
  101. bool find(std::set<int> & c, int val)
  102. {
  103.    return c.end() != c.find(val);
  104. }
  105.  
  106. bool isSorted(std::set<int> &)
  107. {
  108. 	// set is always sorted
  109.    return true;
  110. }
  111.  
  112. //
  113. // test drivers
  114. //
  115.  
  116. template <typename C>
  117. void test(std::string name, std::vector<int> v, C & c)
  118. {
  119.    std::cout << "testing " << name << "..." << std::endl;
  120.  
  121.    for (auto val : v) insert(c, val);
  122.    if (c.size() != Size) std::cerr << "ERROR: output is not big enough!" << std::endl;
  123.    if (!isSorted(c)) std::cout << "ERROR: output is not sorted!" << std::endl;
  124.  
  125.    {
  126.       timer t;
  127.  
  128.       for (auto val : v)
  129.       {
  130.       	auto found = find(c, val);
  131.       	if (!found) std::cerr << "not found!" << std::endl;
  132.       }
  133.    }
  134. }
  135.  
  136. int main()
  137. {
  138.    // assume we are always inserting unique numbers
  139.    // (this should bias towards std::vector because it will ensure the
  140.    // std::set is as large as possible)
  141.    std::cout << "shuffling numbers..." << std::endl;
  142.    std::vector<int> v;
  143.    for (auto i = 0; i < Size; i++) v.push_back(i);
  144.    std::random_shuffle(v.begin(), v.end());
  145.  
  146.    std::cout << "numbers shuffled. first few numbers:";
  147.    for (auto i = 0; i < 10; i++) std::cout << " " << v[i];
  148.    std::cout << std::endl;
  149.  
  150.    // vector<> test
  151.    {
  152.       std::vector<int> sorted;
  153.       sorted.reserve(Size); // ensure we arent reallocating unnecessarily
  154.  
  155.       test("vector", v, sorted);
  156.    }
  157.  
  158.    // deque<> test
  159.    {
  160.       std::deque<int> sorted;
  161.       test("deque", v, sorted);
  162.    }
  163.  
  164.    // set<> test
  165.    {
  166.       std::set<int> sorted;
  167.  
  168.       test("set", v, sorted);
  169.    }
  170. }
  171.  
Success #stdin #stdout 0.22s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
shuffling numbers...
numbers shuffled. first few numbers: 3186 1190 3593 7550 2400 468 706 3754 164 7916
testing vector...
49.821ms
testing deque...
57.908ms
testing set...
0.987ms
https://ideone.com/916fVd
language:
C++14 (gcc 8.3)
created:
9 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!