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