Does STL sort use swap or binary copy?

问题:

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.

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.

Edit: 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);

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?

回答1:

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.

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

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

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

回答2:

No, std::sort from the C++ Standard Library is not allowed to do a binary copy on objects with non-trivial copy/assignment operators. I don't see why it can't do binary copies on objects with trivial copy/assignment operators though. Consider this object:

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);}
};

The C++ algorithms are guaranteed to not set off either assert, which means a binary copy would not be valid.

回答3:

I've seen before that std::copy employs memmove in GNU libstdc++, depending on whether the element type is POD has_trivial_assignment_operator. See the source here:

template<typename _Tp>
   inline _Tp*
   __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
   {
      std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
      return __result + (__last - __first);
   }

At least in SGI, rotate, reverse, swap_ranges, random_shuffle, partition, next_permutation all employ swap.

See http://www.sgi.com/tech/stl/stl_algo.h

Also, the c++11 standard doc for std::sort specificly mentions in § 25.4.1.1:

Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable (Table 22).

Now § 17.6.3.2 contains this:

An object t is swappable with an object u if and only if:

• the expressions swap(t, u) and swap(u, t) are valid when evaluated in the context described below, and
• these expressions have the following effects:
  • the object referred to by t has the value originally held by u and
  • the object referred to by u has the value originally held by t.

The context in which swap(t, u) and swap(u, t) are evaluated shall ensure that a binary non-member function named “swap” is selected via overload resolution (13.3) on a candidate set that includes:

• the two swap function templates defined in (20.2) and
• the lookup set produced by argument-dependent lookup (3.4.2).

回答4:

It swaps, but since it's a template function it might inline the swapping code. The compiler can choose to do a binary swap as an optimization if it's a simple type.