STL排序使用交换还是二进制副本? [英] Does STL sort use swap or binary copy?

问题描述

我很难找到一个好的答案.出于某种原因，我认为可以使用交换来实现STL排序，以更好地支持复杂类型，但是由于我最终对代码进行了一点挖掘，看来它实际上是在进行二进制复制.有人可以确认吗?我猜想二进制副本实际上会更倾向于交换.

I'm having trouble finding a good answer to this. For some reason I thought STL sort would be implemented using swap for better support of complicated types, but as I ended up digging through the code a bit it appears it is actually doing a binary copy. Can someone confirm this? I guess binary copy would actually be preferred to swap.

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

Side Question: Are any of the STL algorithms or container operations implemented using swap? (Outside of std::swap obviously.) I want to be aware of when it is prudent to implement my own swap for complicated types.

我要问的原因是您是否有类似的东西:

Reason I'm asking is if you have something like:

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

我想确保排序没有调用向量的副本构造函数，如果您调用MyData的默认Copy构造函数，则会发生这种情况.因此，我的问题是排序调用交换，复制分配等?

I want to make sure the sort isn't calling the copy constructor of the vector, which would happen if you called the default Copy constructor of MyData. Hence my question is sort calling swap, copy assign, etc?

推荐答案

这取决于您的STL实现. GCC STL实现使用了introsort的组合和插入排序.看来std::swap(或您的专长)将在introsort循环中被调用，但插入排序将不会被调用.

It depends on your STL implementation. The GCC STL implementation uses a combination of introsort and insertion sort. It appears that std::swap (or your specialization) will be invoked in the introsort loop, but it will not be invoked by the insertion sort.

如果您没有专业化的std::swap，则默认的std::swap实现将使用临时副本来实现交换.

If you don't have a specialization of std::swap, then the default std::swap implementation will use a temporary copy to implement swap.

它不使用二进制副本(某些POD类型除外，这些POD类型可能在STL库的深处隐藏了专业化知识.)

It does not use binary copy (except for some POD types, which may have specializations hidden deep within the STL libraries).

此外，在C ++ 0x中，插入排序似乎也将使用移动语义(右值引用).

Also, in C++0x, it seems likely that the insertion sort will use move semantics (rvalue references).

这篇关于STL排序使用交换还是二进制副本?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！