#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>
#include <set>
#include <list>
#include <string>

template <typename It1, typename It2>
class selection_iterator
{
public:

    selection_iterator(It1 begin1, It1 end1, It2 begin2, It2 end2)
        : begin1 { begin1 }, end1 { end1 },
          begin2 { begin2 }, end2 { end2 }
    {
    }

    typename It1::value_type operator*() const
    {
        if (begin1 == end1) return *begin2;
        if (begin2 == end2) return *begin1;
        return std::min(*begin1, *begin2);
    }

    selection_iterator& operator++()
    {
        if      (begin1 == end1) ++begin2;
        else if (begin2 == end2) ++begin1;
        else
        {
            if (*begin1 < *begin2) ++begin1;
            else                   ++begin2;
        }
        return *this;
    }

    selection_iterator operator++(int)
    {
        auto copy = *this;
        ++(*this);
        return copy;
    }

    bool operator==(selection_iterator const& other) const
    {
        return begin1 == other.begin1 and begin2 == other.begin2;
    }

    bool operator!=(selection_iterator const& other) const
    {
        return !(*this == other);
    }

private:


    It1 begin1, end1;
    It2 begin2, end2;

};

template <typename It1, typename It2>
selection_iterator<It1, It2> selection(It1 begin1, It1 end1, It2 begin2, It2 end2)
{
    return selection_iterator<It1, It2>{ begin1, end1, begin2, end2 };
}

int main()
{
    // two of the same container type with same size
    {
        std::vector<int> a { 1, 3, 4 };
        std::vector<int> b { 0, 2, 5 };

        std::vector<int> result { 0, 1, 2, 3, 4, 5 };

        auto begin = selection(a.begin(), a.end(), b.begin(), b.end());
        auto end   = selection(a  .end(), a.end(), b  .end(), b.end());

        for (auto const& value : result)
        {
            assert(begin != end);
            assert(*begin++ == value);
        }
    }

    // two different container types with same size
    {
        std::list<double> a { 0.5, 1.0, 2.5 };
        std::vector<double> b { 1.5, 1.75, 2.25 };

        std::vector<double> result { 0.5, 1.0, 1.5, 1.75, 2.25, 2.5 };

        auto begin = selection(a.begin(), a.end(), b.begin(), b.end());
        auto end   = selection(a  .end(), a.end(), b  .end(), b.end());

        for (auto const& value : result)
        {
            assert(begin != end);
            assert(*begin++ == value);
        }
    }

    // two different containers, with one empty
    {
        std::list<std::string> a { "a", "b", "c" };
        std::set<std::string> b { };

        std::vector<std::string> result { "a", "b", "c" };

        auto begin = selection(a.begin(), a.end(), b.begin(), b.end());
        auto end   = selection(a  .end(), a.end(), b  .end(), b.end());

        for (auto const& value : result)
        {
            assert(begin != end);
            assert(*begin++ == value);
        }
    }
}