假设我有一个对象向量，其中：
这对于引用大数据的对象来说似乎是相当标准的——例如向量的向量。
问题：有没有办法使用std::sort或标准库中的其他排序例程对这个向量进行排序，这样就不会发生复制，而是使用交换？我正在寻找一个预c++0x解决方案（没有移动语义）。
重载std::swap似乎是第一次自然尝试，它确实有点帮助，但它只消除了一小部分复制。
注意：gcc 行为示例
为了 sort 100 81 64 49 36 25 16 9 4 1 0 1 4 9 16 25 36 49 64 81，我的 gcc std::sort 调用了 19 个复制构造函数、92 个赋值和 6 个交换。
// 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";
}
}
something like the above is a viable approach. I wrote a bunch of it in C++11, but included comments on how to strip out the extra C++11 stuff (it actually simplifies the code in some cases, but removes the ability to handle some container-like things).
The basic idea is to sort a vector of iterators into your original container. Then we create a temporary container, stuff trivial value_types into it, swap those trivial value_types with the correct data from the original container (as determined by the vector of sorted iterators), then swap this temporary container for our original container.
There is lots of allocation, but hopefully of cheap stuff.
For this to work, the data you are sorting needs be trivial constructable. For this to be efficient, the data you are working with when trivially constructed needs to be cheap, and swap needs to be efficient.
I attempted to make this as ADL friendly as I can, because I find that to be good practice.
堆排序是一种仅交换排序，它是不稳定的（等价元素的顺序可能会在排序过程中发生变化）。我回答了另一个类似的问题，我自己实现了堆排序（PasteBin），但你可能会发现更好、更灵活的实现。
结论是 g++std::sort对 20 个元素使用了 35 次复制、19 次赋值、10 次交换和 35 次删除（总共 99 次操作），我的堆排序使用了 62 次交换，仅此而已。
我刚刚遇到了一个稳定的排序，它只在 stackoverflow 上使用 swap 。我没有深入研究它。