std :: sort без копирования

// C++03 solution won't work with arrays and some other custom containers.
// Mostly drop this block:
#include <type_traits>
#include <vector>
#include <algorithm>
#include <iostream>
namespace aux {
using std::begin; using std::end;
template<typename C> auto adl_begin( C&& c )->decltype( begin(c) );
template<typename C> auto adl_end( C&& c )->decltype( end(c) );

template<typename C>
struct container_traits:
std::iterator_traits< typename std::decay< decltype( aux::adl_begin( *(C*)nullptr ) ) >::type >
{
typedef typename std::decay< decltype( adl_begin( *(C*)nullptr ) ) >::type iterator_type;
};
}

// C++03 solution won't work with arrays.  Inside std::less, use Container::value_type:
template<
typename Container,
typename Comparison = std::less<
typename aux::container_traits<Container>::value_type
>
>
void indirect_sort_then_swap( Container& c, Comparison&& comp = Comparison() ) {
typedef aux::container_traits<Container> con_traits;
typedef typename con_traits::value_type value_type;
typedef typename con_traits::iterator_type iterator_type;
std::vector< iterator_type > indirect;
{
// C++03 solution can use c.begin(), but will not work with arrays:
using std::begin; using std::end;
auto begin_ = begin(c);
auto end_ = end(c);
for( auto it = begin_; it != end_; ++it ) {
indirect.push_back( it );
}
}
// In C++03, write a functor class that does this:
auto indirect_sort = [&comp]( iterator_type const& left, iterator_type const& right )->bool {
return comp(*left, *right);
};
std::sort( indirect.begin(), indirect.end(), indirect_sort );
// at this point, indirect is a vector with the contents of c sorted by iterator:
// a hard part remains, namely to take this information and sort c with minimal swaps
// That is hard.  I will instead create an easy approach, namely create an empty
// copy of c full of empty elements, and directly swap the correct entry of c into
// each slot, then I swap c with its copy.
// the downside is that my container now needs to support push_back.  Oh well.
Container c2;
// C++03 solution cannot use auto here.  But we know the type of indirect:
for (auto it = indirect.begin(); it != indirect.end(); ++it) {
// See previous comment
auto itv = *it;
c2.push_back( value_type() );
using std::swap;
swap( *itv, c2.back() );
}
// by this point, the contents of c have been swap-moved to c2
// swap them back:
{
using std::swap;
swap( c, c2 );
}
}

int main() {
std::vector<int> foo;
foo.push_back(7);
foo.push_back(3);
indirect_sort_then_swap(foo);
for (auto i:foo) {
std::cout << i << "\n";
}
}

что-то вроде вышеизложенного является жизнеспособным подходом. Я написал кучу этого в C ++ 11, но включил комментарии о том, как убрать лишние вещи из C ++ 11 (в действительности это упрощает код в некоторых случаях, но лишает возможности обрабатывать некоторые вещи, похожие на контейнеры).

Основная идея заключается в сортировке vector из iterators в ваш оригинальный контейнер. Затем мы создаем временный контейнер, вещи тривиальные value_typeв это, swap эти тривиальные value_types с правильными данными из исходного контейнера (как определено vector отсортировано iterators), тогда swap это временный контейнер для нашего оригинального контейнера.

Есть много распределения, но, надеюсь, из дешевых вещей.

Чтобы это работало, данные, которые вы сортируете, должны быть тривиально конструируемыми. Для того, чтобы это было эффективно, данные, с которыми вы работаете при простом построении, должны быть дешевыми, и swap должен быть эффективным.

Я попытался сделать это как можно более дружественным к ADL, потому что считаю, что это хорошая практика.