fork download
copy 
  1. #include <vector>
  2. #include <string>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <set>
  6. #include <algorithm>
  7. #include <chrono>
  8. #include <iterator>
  9.  
  10. using namespace std;
  11.  
  12. multiset<int> HW(const multiset<int>& a, const multiset<int>& b)
  13. {
  14.     multiset<int> c (a);
  15.     c.insert(b.begin(),b.end());
  16.     return c;
  17. }
  18.  
  19. multiset<int> AnT(const multiset<int>& a, const multiset<int>& b)
  20. {
  21.     multiset<int> c = a;
  22.  
  23.     auto it_hint = c.begin();
  24.     for (const int &src : b)
  25.     {
  26.         it_hint = c.insert(it_hint, src);
  27.         ++it_hint;
  28.     }
  29.     return c;
  30. }
  31.  
  32. multiset<int> AnTmerge(const multiset<int>& a, const multiset<int>& b)
  33. {
  34.     multiset<int> c;
  35.     std::merge(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.end()));
  36.     return c;
  37. }
  38.  
  39. class muTimer
  40. {
  41.     using Clock = std::chrono::high_resolution_clock;
  42.     bool active = false;
  43.     Clock::duration   duration_;
  44.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  45.  
  46.     muTimer(const muTimer&)             = delete;
  47.     muTimer& operator=(const muTimer&)  = delete;
  48. public:
  49.     using ns       = std::chrono::nanoseconds;
  50.     using mks      = std::chrono::microseconds;
  51.     using ms       = std::chrono::milliseconds;
  52.     muTimer() { reset(); start(); }
  53.     ~muTimer() = default;
  54.     muTimer& reset()
  55.     {
  56.         duration_ = std::chrono::nanoseconds(0);
  57.         active    = false;
  58.         return *this;
  59.     }
  60.     muTimer& start()
  61.     {
  62.         if (!active)
  63.         {
  64.             start_ = Clock::now();
  65.             active = true;
  66.         }
  67.         return *this;
  68.     }
  69.     muTimer& stop()
  70.     {
  71.         if (active)
  72.         {
  73.             stop_      = Clock::now();
  74.             duration_ += stop_ - start_;
  75.             active     = false;
  76.         }
  77.         return *this;
  78.     }
  79.     template<typename T = mks>
  80.         unsigned long long duration()
  81.     {
  82.         return static_cast<unsigned long long>
  83.             (std::chrono::duration_cast<T>(stop_-start_).count());
  84.     }
  85. };
  86.  
  87. int main(int argc, const char * argv[])
  88. {
  89.     multiset<int> a;
  90.     multiset<int> b;
  91.  
  92.     for(int i = 0; i < 1000'000; ++i)
  93.     {
  94.         a.insert(rand());
  95.         b.insert(rand());
  96.     }
  97.  
  98.     multiset<int> c, d, e;
  99.  
  100.     {
  101.         muTimer mt;
  102.         c = HW(a,b);
  103.         mt.stop();
  104.         cout << mt.duration() << endl;
  105.     }
  106.  
  107.     {
  108.         muTimer mt;
  109.         d = AnT(a,b);
  110.         mt.stop();
  111.         cout << mt.duration() << endl;
  112.     }
  113.  
  114.     {
  115.         muTimer mt;
  116.         e = AnTmerge(a,b);
  117.         mt.stop();
  118.         cout << mt.duration() << endl;
  119.     }
  120.  
  121. }
  122.  
Success #stdin #stdout 3.08s 390144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
362377
344378
636014
https://ideone.com/iT59fP
language:
C++14 (gcc 8.3)
created:
4 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!