fork download

#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
 
// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<typename std::iterator_traits<It>::iterator_category, T>::value;
 
 
// quick sort
template <typename BidIt, typename Pred = typename std::less<typename std::iterator_traits<BidIt>::value_type>>
void qsort(BidIt first, BidIt last, Pred compare = {}) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "bidirectional iterator required");
 
    auto size = std::distance(first, last);
 
    if (size > 1) {
        using content_type = typename std::iterator_traits<BidIt>::value_type;
 
        content_type pivot = *first;
        std::vector<content_type> left(size), right(size);
        auto left_end = left.begin();
        auto right_end = right.begin();
 
        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }
 
        qsort(left.begin(), left_end, compare);
        qsort(right.begin(), right_end, compare);
 
        std::copy(left.begin(), left_end, first);
        *std::next(first, std::distance(left.begin(), left_end)) = pivot;
        std::copy(right.begin(), right_end, std::next(first, std::distance(left.begin(), left_end) + 1));
    }
}
 
struct integer
{
	integer() = delete; //not default constructible
	integer(int y):
				x(y)
	{}
 
	int x;
};
 
bool operator<(const integer& lhs, const integer& rhs)
{
	return lhs.x < rhs.x;
}
 
int main() {
	std::vector<integer> v{1, 0, -1, 4, 2};
	qsort(v.begin(), v.end());
}

In file included from /usr/include/c++/6/vector:63:0,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_uninitialized.h: In instantiation of ‘static _ForwardIterator std::__uninitialized_default_n_1<true>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = integer*; _Size = long unsigned int]’:
/usr/include/c++/6/bits/stl_uninitialized.h:575:20:   required from ‘_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = integer*; _Size = long unsigned int]’
/usr/include/c++/6/bits/stl_uninitialized.h:637:44:   required from ‘_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = integer*; _Size = long unsigned int; _Tp = integer]’
/usr/include/c++/6/bits/stl_vector.h:1309:36:   required from ‘void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = integer; _Alloc = std::allocator<integer>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
/usr/include/c++/6/bits/stl_vector.h:281:30:   required from ‘std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = integer; _Alloc = std::allocator<integer>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<integer>]’
prog.cpp:24:44:   required from ‘void qsort(BidIt, BidIt, Pred) [with BidIt = __gnu_cxx::__normal_iterator<integer*, std::vector<integer> >; Pred = std::less<integer>]’
prog.cpp:58:26:   required from here
/usr/include/c++/6/bits/stl_uninitialized.h:540:37: error: use of deleted function ‘integer::integer()’
    return std::fill_n(__first, __n, _ValueType());
                                     ^~~~~~~~~~~~
prog.cpp:43:2: note: declared here
  integer() = delete; //not default constructible
  ^~~~~~~

Standard output is empty