Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 908
Jason T. Avatar asked Nov 21 '11 22:11

Jason T.


1 Answers

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.

like image 187
Mooing Duck Avatar answered Sep 25 '22 07:09

Mooing Duck