STL排序是使用交换还是二进制复制？

Question

我很难找到一个好的答案.出于某种原因,我认为STL排序将使用swap来实现,以便更好地支持复杂类型,但是当我最终挖掘代码时,它似乎实际上正在进行二进制复制.有人能证实吗？我猜二进制副本实际上更适合交换.

问题:是否使用交换实现了任何STL算法或容器操作？(std::swap显然在外面.)我想知道何时为复杂类型实现我自己的交换是谨慎的.

编辑:我问的原因是你是否有类似的东西:

class MyClass {
  vector<int> vec_data;
  int a;
  int b;
}
vector<MyClass> my_vec;
sort(my_vec.begin(), my_vec.end(), MyCustomCompare);

我想确保排序不是调用向量的复制构造函数,如果调用MyData的默认复制构造函数,就会发生这种情况.因此我的问题是排序调用交换,复制分配等？

Answer 1

不,std::sort来自C++标准库不允许对具有非平凡复制/赋值运算符的对象执行二进制复制.我不明白为什么它不能在具有普通复制/赋值运算符的对象上进行二进制复制.考虑这个对象:

class Explosive {
    Explosive* const self;
public:
    Explosive() :self(this) {}
    Explosive(const Explosive&) :self(this) {}
    ~Explosive() {assert(this==self);}
    Explosive& operator=(const Explosive& rhs) {
        assert(this==self && rhs.self==&rhs); 
        return *this;
    }
    bool operator<(const Explosive& rhs) const 
    {return std::less<Explosive*>(self,rhs.self);}
};

保证C++算法不会引发断言,这意味着二进制副本无效.

Answer 2

这取决于您的 STL 实现。GCC STL 实现结合使用了内插排序和插入排序。看来std::swap（或您的专业化）将在 introsort 循环中调用，但插入排序不会调用它。

如果您没有专门化std::swap，那么默认std::swap实现将使用临时副本来实现交换。

它不使用二进制复制（某些 POD 类型除外，它们可能具有隐藏在 STL 库深处的专业化）。

另外，在 C++0x 中，插入排序似乎将使用移动语义（右值引用）。