std :: sort没有复制构造
假设我有一个对象的向量，其中：
这对于引用大数据的对象来说似乎相当标准 - 例如向量的向量。
问题 ：有没有一种方法可以使用标准库中的std::sort或其他排序例程对此向量进行std::sort ，以便不进行复制，而是使用交换？ 我正在寻找一个预c++0x解决方案（ 无移动语义 ）。
重载std::swap看起来像是第一次自然的尝试，它确实有一点帮助，但它只消除了一小部分复制。
注 ：gcc行为的例子
要排序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";
}
}
像上面这样的东西是一种可行的方法。 我在C ++ 11中编写了一堆，但包含了关于如何去除额外的C ++ 11的东西（它在某些情况下实际上简化了代码，但消除了处理某些容器类事物的能力）的注释。
基本思想是将iterator的vector排序到原始容器中。 然后我们创建一个临时容器，填入一些简单的value_type s， swap这些普通的value_type s与原始容器中的正确数据swap （由排序后的iterator的vector确定），然后将此临时容器swap为原始容器。
有很多的分配，但希望便宜的东西。
为了这个工作，你正在分拣的数据需要简单的构造。 为了提高效率，在构建简单构建时所使用的数据需要便宜，并且swap需要高效。
我尽可能让ADL尽可能友好，因为我认为这是一种很好的练习。
堆排序是不稳定的（在排序过程中，等效元素的顺序可能会更改）。 我回答了其他类似的问题，我实现了自己的堆排序（PasteBin），但您可能会发现更好，更灵活的实现。
结论是，g ++的std::sort对20个元素使用了35个副本，19个任务，10个交换和35个删除（共99个操作），我的堆排序使用了62个交换，而没有其他操作。
我碰到了一个稳定的排序，它在stackoverflow上只使用swap。 我没有深入研究它。
链接地址: http://www.djcxy.com/p/11695.html