Is copy-and-swap always the best solution?

Question

I have seen the copy-and-swap idiom recommended in various places as the recommended/best/only way to implement strong exception safety for the assignment operator. It seems to me that this approach also has a downside.

Consider the following simplified vector-like class which utilizes copy-and-swap:

class IntVec {
  size_t size;
  int* vec;
public:
  IntVec()
    : size(0),
      vec(0)
  {}
  IntVec(IntVec const& other)
    : size(other.size),
      vec(size? new int[size] : 0)
  {
    std::copy(other.vec, other.vec + size, vec);
  }

  void swap(IntVec& other) {
    using std::swap;
    swap(size, other.size);
    swap(vec, other.vec);
  }

  IntVec& operator=(IntVec that) {
    swap(that);
    return *this;
  }

  //~IntVec() and other functions ...
}

Implementing the assignment via the copy constructor may be efficient and guarantee exception safety, but it can also cause an unneeded allocation, potentially even causing an uncalled for out-of-memory error.

Consider the case of assigning a 700MB IntVec to a 1GB IntVec on a machine with a <2GB heap limit. An optimal assignment will realize it already has enough memory allocated and only copy the data into it's already allocated buffer. The copy-and-swap implementation will cause an allocation of another 700MB buffer before the 1GB one is released, causing all 3 to try co-exist in memory at once, which will throw an out-of-memory error needlessly.

This implementation would solve the problem:

IntVec& operator=(IntVec const& that) {
  if(that.size <= size) {
    size = that.size;
    std::copy(that.vec, that.vec + that.size, vec);
  } else
    swap(IntVec(that));
  return *this;
}

So the bottom line is:
Am I right that this is a problem with the copy-and-swap idiom, or do normal compiler optimizations somehow eliminate the extra allocation, or am I overlooking some problem with my "better" version that the copy-and-swap one solves, or am I doing my math/algorithms wrong and the problem doesn't really exist?

Answer 1

There are two problems with the implementation reusing the space

• If you're assigning very_huge_vect = very_small_vect; the extra memory will not be released. This may be what you want or may be not.

• In case of integers all is fine, but what about objects for which the copy operation may throw an exception? You'll end up with a messed up array where part of the copy has been done and that has been truncated. Much better would be to leave the target untouched if the copy operation fails (what the swap idiom does).

By the way, as a general rule, in very few cases you can find anything that looks like "always the best solution". If you're looking for a silver bullet, programming is not going to be the right place.

Answer 2

To fix your particular problem, modify copy-swap to clear-copy-swap.

This can be made somewhat generic via:

Foo& operator=( Foo const& o ) {
  using std::swap;
  if (this == &o) return *this; // efficient self assign does nothing
  swap( *this, Foo{} ); // generic clear
  Foo tmp = o; // copy to a temporary
  swap( *this, tmp ); // swap temporary state into us
  return *this;
}
Foo& operator=( Foo && o ) {
  using std::swap;
  if (this == &o) return *this; // efficient self assign does nothing
  swap( *this, Foo{} ); // generic clear
  Foo tmp = std::move(o); // move to a temporary
  swap( *this, tmp ); // swap temporary state into us
  return *this;
}

while this does cause that large allocation to happen, it happens immediately after the large deallocation occurs.

The key part of copy-swap is that it makes a correct implementation, and getting exception-safe copy right is tricky.

You'll note that the above, if an exception is thrown, results that the lhs could be in an empty state. In comparison, the standard copy-swap will result in a valid copy, or the lhs being unchanged.

Now, there is one final little trick we can do. Suppose our state is captured in a vector of substates, and those substates have exception-safe swap or move. Then we can:

Foo& move_substates( Foo && o ) {
  if (this == &o) return *this; // efficient self assign does nothing
  substates.resize( o.substates.size() );
  for ( unsigned i = 0; i < substates.size(); ++i) {
    substates[i] = std::move( o.substates[i] );
  }
  return *this;
}

which emulates your copy-contents, but does it by move instead of copy. We can then exploit this in our operator=:

Foo& operator=( Foo && o ) {
  using std::swap;
  if (this == &o) return *this; // efficient self assign does nothing
  if (substates.capacity() >= o.substates.size() && substates.capacity() <= o.substates.size()*2) {
    return move_substates(std::move(o));
  } else {
    swap( *this, Foo{} ); // generic clear
    Foo tmp = std::move(o); // move to a temporary
    swap( *this, tmp ); // swap temporary state into us
    return *this;
  }
}

and now we reuse our internal memory and avoid an allocation if we are moving from a source, and we aren't too much larger than the source, if you are afraid of memory allocations.

Answer 3

Yes, running out of memory is a potential problem.

You already know what problem copy and swap solves. It is how you "undo" a failed assignment.

With your more efficient method there is no way to go back if the assignment fails at some stage in the process. And, if an object is badly written a failed assignment might even leave the object corrupt and the program will crash during object destruction.

Answer 4

Am I right that this is a problem with the copy-and-swap idiom

It depends; if you do have so large vectors, then yes you're right.

am I overlooking some problem with my "better" version that the copy-and-swap one solves

1. You're optimizing for the rare case. Why perform extra checks and add cyclomatic complexity to your code ? (unless ofcourse, having soo big vectors is the norm in your application)

2. Since C++11 the r-valuness of temporaries can be harvested by c++. So passing your argument by const& throws away optimizations.

Bottom line: The word always is easy to disprove. If there was a universal solution, always better than any alternative, I suppose the compiler could adopt it and implicitly generate a default assignment operator based on this

On the previous note, the implicitly-declared copy assignment operator has the form

T& T::operator=(const T&);

accepting its argument by const& and not by value (as in the copy and swap idiom)

Answer 5

Two caveats with your approach.

1. Consider the case of assigning a 1KB IntVec to a 1GB IntVec. You'll end up with a massive chunk of allocated but unused (wasted) memory.
2. What if an exception is thrown during copy? If you're overwriting the existing location, you end up with corrrupted, partially-copied data.

As you pointed out, getting around these issues may not be very memory efficient, but software design is always about tradeoffs.

Answer 6

You can see how STL implements operator= of vector.

template <class _Tp, class _Alloc>
vector<_Tp,_Alloc>& 
vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
{
  if (&__x != this) {
    const size_type __xlen = __x.size();
    if (__xlen > capacity()) {
      iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_end_of_storage = _M_start + __xlen;
    }
    else if (size() >= __xlen) {
      iterator __i = copy(__x.begin(), __x.end(), begin());
      destroy(__i, _M_finish);
    }
    else {
      copy(__x.begin(), __x.begin() + size(), _M_start);
      uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
    }
    _M_finish = _M_start + __xlen;
  }
  return *this;
}