#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <string>
#include <vector>

template <typename Container, typename Comparator>
class Sorted_Insertion_Iterator
{
public:

    using value_type = typename Container::value_type;

    Sorted_Insertion_Iterator(Container& container, Comparator comp = {})
        : container { container }, comp { comp }
    {
    }

    Sorted_Insertion_Iterator& operator* ()    { return *this; }
    Sorted_Insertion_Iterator& operator++()    { return *this; }
    Sorted_Insertion_Iterator  operator++(int) { return *this; }

    bool operator==(Sorted_Insertion_Iterator const& other) const
    {
        return &container == &other.container;
    }

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

    Sorted_Insertion_Iterator& operator=(value_type const& value)
    {
        auto it = std::begin(container);
        for (; it != std::end(container); ++it)
        {
            if (!comp(*it, value)) 
                break;
        }
        container.insert(it, value);
        return *this;
    }

private:

    Container& container;
    Comparator comp;

};

template <typename Container, typename Comparator = std::less<typename Container::value_type>>
Sorted_Insertion_Iterator<Container, Comparator> sorted_inserter(Container& container,
                                                                 Comparator comparator = {})
{
    return { container, comparator };
}

int main()
{
    // Testcase #1
    {
        std::vector<int> v { 7, 3, -1, 4 };
        std::vector<int> output { };

        auto it = sorted_inserter(output);
        for (int e : v)
        {
            *it++ = e;
        }

        assert(( output == std::vector<int>{ -1, 3, 4, 7 } ));
    }

    // Testcase #2
    {
        std::list<int> output { };
        
        auto it = sorted_inserter(output);
        for (int i = 3; i > 0; --i)
        {
            *it++ = i;
        }

        assert(( output == std::list<int>{ 1, 2, 3 } ));
    }

    // Testcase #3
    {
        std::vector<double> v { 1.2, 3.4, 5.6, 7.8 };
        std::deque<double> output { };
        auto it = sorted_inserter(output, std::greater<double>{});
        std::copy(std::begin(v), std::end(v), it);
        assert(( output == std::deque<double>{ 7.8, 5.6, 3.4, 1.2 } ));
    }

    // Testcase #4
    {
        std::vector<int> v { -1, 2, -3, 4 };
        std::vector<int> output { };
        auto it = sorted_inserter(output, [](int a, int b) { return std::abs(a) < std::abs(b); });
        std::copy(std::begin(v), std::end(v), it);
        assert(( output == std::vector<int>{ -1, 2, -3, 4 } ));
    }
}