的std ::排序没有拷贝构造

Question

假设我有哪里对象的矢量：

• 复制的建设和分配是昂贵的
• 默认的建设和两个对象的交换是便宜。

对于引用大数据的对象（例如矢量向量），这看起来很标准。

问题：有没有办法排序这一点使用std::sort其它分类常规从标准库载体，或者，让不会进行复制操作，但交换来代替？我正在寻找一个c++0x前解决方案（无移动语义）。

重载std::swap看起来像是第一次自然尝试，它确实有一点帮助，但它只能摆脱一小部分复制。

注意：海湾合作委员会的行为

实例排序100 81 64 49 36 25 16 9 4 1 0 1 4 9 16 25 36 49 64 81，我的gcc的std ::排序调用到19个拷贝构造函数，92个分配和6个互换。

Answer 1

// 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的iterator s分类到原始容器中。然后，我们创建一个临时的容器，东西琐碎value_type s转换它，swap那些琐碎value_type s的从原来的容器正确的数据（如排序iterator S的vector确定），然后swap我们原来的容器这个临时容器。

有很多分配，但希望便宜的东西。

为了达到这个目的，您正在排序的数据需要进行微不足道的构造。为了提高效率，当你使用简单构建的数据需要很便宜，并且需要高效的数据。

我试图让ADL尽可能友好，因为我觉得这是一个很好的习惯。

Answer 2

Heap-sort是不稳定的（在排序过程中等效元素的顺序可能会发生变化）。我回答了一个other similar question，我自己实现了堆排序（PasteBin），但您可能会发现更好，更灵活的实现。

结论是，g ++的std::sort对20个元素使用了35个副本，19个任务，10个交换和35个删除（总共99个操作），我的堆排序使用了62次交换，而没有其他操作。

我刚碰到一个稳定的排序，只使用交换here on stackoverflow。我没有深入研究它。