set_difference_custom_implementation.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ratio>

// NOTE source: https://www.fluentcpp.com/2018/01/12/how-is-stdset_difference-implemented/

template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator mySetDifference(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, InputIterator2 last2,
                    OutputIterator output)
{
   auto current1 = first1;
   auto current2 = first2;

   while(current1 != last1) {
       if (current2 == last2) {
           return std::copy(current1, last1, output);
       }

       if (*current1 < *current2) {
           *output = *current1;
           ++output;
           ++current1;
       } else {
           if (*current1 > *current2) {
               ++current2;
           } else {
               ++current1;
               ++current2;
           }
       }
   }

   return output;
}

int main()
{
    std::vector<int> a {1,2,3,6,7,7,10,11,12};
    std::vector<int> b {4,6,7,8};

    std::vector<int> resultFromSTLImplementation;
    auto start1 = std::chrono::high_resolution_clock::now();
    std::set_difference(begin(a), end(a), begin(b), end(b), std::back_inserter(resultFromSTLImplementation));
    auto end1 = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double, std::milli> elapsedSeconds1 = end1 - start1;
    std::cout << "---stl set_difference run time: " << elapsedSeconds1.count() << std::endl;
    for (auto it : resultFromSTLImplementation) {
        std::cout << it << std::endl;
    }
    
    std::vector<int> resultFromMyImplementation;
    auto start2 = std::chrono::high_resolution_clock::now();
    mySetDifference(begin(a), end(a), begin(b), end(b), std::back_inserter(resultFromMyImplementation));
    auto end2 = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double, std::milli> elapsedSeconds2 = end2 - start2;
    std::cout << "---my set_difference run time: " << elapsedSeconds2.count() << std::endl;
    for (auto it : resultFromMyImplementation) {
        std::cout << it << std::endl;
    }

    if (resultFromSTLImplementation == resultFromMyImplementation) {
        std::cout << "solution is ok" << std::endl;
    }

    return 0;
}