fork download 
  1. #include <algorithm>
  2. #include <chrono>
  3. #include <iostream>
  4. #include <set>
  5.  
  6. using Time = std::chrono::high_resolution_clock;
  7. using ms = std::chrono::milliseconds;
  8.  
  9. template <typename T>
  10. std::set<T> &subtract (std::set<T> &initSet, const std::set<T> &otherSet) {
  11.     auto it = initSet.cbegin();
  12.     auto end = initSet.cend();
  13.     auto otherIt = otherSet.cbegin();
  14.     auto otherEnd = otherSet.cend();
  15.  
  16.     while (it != end) {
  17.         const auto &value = *it;
  18.         while (otherIt != otherEnd) {
  19.             if (*otherIt >= value) {
  20.                 break;
  21.             }
  22.             ++otherIt;
  23.         }
  24.  
  25.         if (otherIt == otherEnd) {
  26.             break;
  27.         }
  28.  
  29.         if (*otherIt == value) {
  30.             it = initSet.erase(it);
  31.         }
  32.         else {
  33.             ++it;
  34.         }
  35.     }
  36.     return initSet;
  37. }
  38.  
  39. int main()
  40. {
  41.     std::set<int> initialSet;
  42.     auto it = initialSet.end();
  43.     for (int i = 0; i < 5000000; ++i) {
  44.         it = initialSet.emplace_hint(it, i);
  45.     }
  46.  
  47.     std::set<int> diffSet;
  48.     it = diffSet.end();
  49.     for (int i = 0; i < 5000000; i += 2) {
  50.         it = diffSet.emplace_hint(it, i);
  51.     }
  52.  
  53.     auto start = Time::now();
  54.  
  55.     std::set<int> setSubtractedWithStl;
  56.     {
  57.         std::set<int> initialSetCopy = initialSet;
  58.  
  59.         start = Time::now();
  60.         std::set_difference(initialSetCopy.cbegin(), initialSetCopy.cend(),
  61.                             diffSet.cbegin(), diffSet.cend(),
  62.                             std::inserter(setSubtractedWithStl, setSubtractedWithStl.end()));
  63.     }
  64.     std::cout << "Stl + destructor: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
  65.  
  66.     start = Time::now();
  67.     subtract(initialSet, diffSet);
  68.     std::cout << "Heaven: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
  69.  
  70.     const bool hasEqualSize = initialSet.size() == setSubtractedWithStl.size();
  71.     bool equal = false;
  72.     if (hasEqualSize) {
  73.         equal = std::equal(initialSet.cbegin(), initialSet.cend(),
  74.                            setSubtractedWithStl.cbegin());
  75.     }
  76.  
  77.     std::cout << "Sets are equal: " << std::boolalpha << equal << '\n';
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 2.36s 718336KB
comments (?)
stdin 
Standard input is empty
stdout 
Stl + destructor: 917
Heaven: 183
Sets are equal: true
https://ideone.com/emlYr7
language:
C++ (gcc 8.3)
created:
6 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!