Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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;
  }       
like image 257
abcdabcd987 Avatar asked May 22 '15 13:05

abcdabcd987


3 Answers

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.

like image 65
Jonathan Wakely Avatar answered Oct 16 '22 16:10

Jonathan Wakely


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.

like image 37
Mike Seymour Avatar answered Oct 16 '22 16:10

Mike Seymour


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.

like image 3
Björn Pollex Avatar answered Oct 16 '22 16:10

Björn Pollex