Why SGI STL don't use the copy-and-swap idiom?

Question

I recently read an answer on StackOverflow about What is the copy-and-swap idiom? and knew that the copy-and-swap idiom can

avoiding code duplication, and providing a strong exception guarantee.

However, when I looked into SGI STL deque implementation, I found that it doesn't use the idiom. I'm wondering why not, if the idiom is somehow like a "best practice"?

  deque& operator= (const deque& __x) {
    const size_type __len = size();
    if (&__x != this) {
      if (__len >= __x.size())
        erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
      else {
        const_iterator __mid = __x.begin() + difference_type(__len);
        copy(__x.begin(), __mid, _M_start);
        insert(_M_finish, __mid, __x.end());
      }
    }
    return *this;
  }       

Answer 1

The code you show doesn't reallocate memory unless the container needs to grow, which can be a significant saving. Copy-and-swap always allocates memory to do the copy then deallocates the memory for the existing elements.

Consider a deque<vector<int>> where the existing vector members of the deque have large capacities.

deque<vector<int>> d(2);
d[0].reserve(100);
d[1].reserve(100);

Using the SGI STL implementation, assigning to each element preserves that capacity, so if the vectors need to grow they can do so without allocating anything:

d = deque<vector<int>>(2);
assert(d[0].capacity() >= 100);
assert(d[1].capacity() >= 100);
d[0].push_back(42);  // does not cause an allocation

Copy-and-swap would replace the existing members with new elements that have no spare capacity, so the assertions above would fail, and the push_back would need to allocate memory. This wastes time deallocating and reallocating, instead of using the perfectly good memory that's already there.

Copy-and-swap is a convenient way to get exception-safety and correctness very easily, but not necessarily as efficiently as possible. In code like the STL or the C++ Standard Library you do not want to sacrifice efficiency for the sake of slightly easier implementation, and such code should usually be written by experts who are able to get exception-safety right by doing it "the hard way" not just the most convenient way.

Answer 2

While copy-and-swap is best practice, it can come with an efficiency penalty in certain cases. In this specific case the code is exploiting the fact that, if the vector being assigned to already has enough memory available, the values can just be copied without doing an additional memory allocation.

Answer 3

The idiom is a simple way to provide a strong exception guarantee, and so it's a "best practice" in the sense of a good thing to do unless you have a good reason not to.

However, it has a cost: a second object must be created and destroyed. This can be expensive and, if this involves a large memory allocation, can increase the peak memory usage by much more than is necessary. If that's a concern, or if you're writing a generic library like this one, you should find other ways to copy the object without creating a temporary object. Exception safety will need more care than when using the simple idiom.

Answer 4

I guess in this case this is done to avoid excess reallocations: copy-and-swap will require copy to be allocated (thus taking double storage at a moment), then all deque's memory to be deallocated. This code will allocate only if copy-from is larger and only the difference needed.

This actually applies to deque and not for vector - how is vector::operator= implemented there?

Moreover that possibly was written before the idiom became popular. And even now it's not universally accepted.

Answer 5

The standard mandates that std::deque<T>::operator=(const std::deque<T>&) should provide the basic exception guarantee - i.e. that the container is left in a valid state in the case of an exception, not the strong guarantee - which would argue for the use of copy/swap.