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

/* Implement Sorted_Insertion_Iterator here */

/* Implement sorted_Inserter() here */

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 } ));
    }
}