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

Question

I recently read an answer to StackOverflow about What is the Copy and Swap Idiom? and knew that the idiom with copy and replace could

Avoiding code duplication and providing a reliable guarantee of exclusion.

However, when I looked at the SGI STL deque implementation , I found that it was not using an idiom. I wonder why not if the idiom is somehow reminiscent of "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 does not reallocate memory if the container should not grow, which can be significant savings. Copy-and-swap always allocates memory for copying, and then frees memory for existing elements.

Consider a deque<vector<int>> , where existing vector deck elements 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 this capacity, so if vectors need to grow, they can do this 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 will replace existing elements with new elements that do not have backup capacity, so the above statements will fail, and push_back will need to allocate memory. This takes time to free and redistribute, instead of using a perfectly good memory that already exists.

Copy-and-swap is a convenient way to get exceptional security and correctness very easily, but not necessarily as efficiently as possible. In code such as STL or the standard C ++ library, you don’t want to sacrifice efficiency for an easier implementation, and such code should usually be written by experts who can be eligible for exceptions, making it the “hard way” "not only the most convenient way.

Answer 2

An idiom is an easy way to provide a reliable guarantee of exclusion, and therefore it is “best practice” in the sense of a good thing, unless you have good reason not to.

However, it has a cost: the second object must be created and destroyed. This can be expensive and, if it is associated with a large amount of memory, it can increase the use of peak memory much more than necessary. If this is a concern or if you are writing such a shared library, you should find other ways to copy the object without creating a temporary object. Exception security requires more caution than using a simple idiom.

Answer 3

While copying and swapping are best practices, in some cases this can lead to reduced efficiency. In this particular case, the code takes advantage of the fact that if for a vector to which an already sufficient amount of memory has already been assigned, the values ​​can be copied without additional memory allocation.

Answer 4

I think in this case this is done in order to avoid redundant redistributions: copy-and-swap will require a copy that must be allocated (thus, using dual memory at the same time), and then all the deque memory to be freed. This code will only be allocated if copying is larger and only the difference is required.

This really applies to deque, not to the vector - how the vector :: operator =

Moreover, it was possibly written before the idiom became popular. And even now it is not accepted.

Answer 5

The standard requirements that std::deque<T>::operator=(const std::deque<T>&) should provide a basic guarantee, that is, the container remains in valid condition in case of exception, and not a strong guarantee, which will argue the use of copy / swap.