B. Stroustrup - The C++ Programming Language (794319), страница 85
Текст из файла (страница 85)
We can avoid repetition:template<class T, class A>vector<T,A>& vector<T,A>::operator=(const vector& a){vector temp {a};// copy allocatorstd::swap(∗this,temp);// swap representationsreturn ∗this;}// offers the strong guarantee (§13.2)The old elements are destroyed by temp’s destructor, and the memory used to hold them is deallocated by temp’s vector_base’s destructor.The reason that the standard-library swap() (§35.5.2) works for vector_bases is that we definedvector_base move operations for swap() to use.The performance of the two versions ought to be equivalent. Essentially, they are just two different ways of specifying the same set of operations.
However, the second implementation isshorter and doesn’t replicate code from related vector functions, so writing the assignment that wayought to be less error-prone and lead to simpler maintenance.Note that I did not test for self-assignment, such as v=v. This implementation of = works byfirst constructing a copy and then swapping representations. This obviously handles self-assignment correctly. I decided that the efficiency gained from the test in the rare case of self-assignmentwas more than offset by its cost in the common case where a different vector is assigned.In either case, two potentially significant optimizations are missing:[1] If the capacity of the vector assigned to is large enough to hold the assigned vector, wedon’t need to allocate new memory.[2] An element assignment may be more efficient than an element destruction followed by anelement construction.Implementing these optimizations, we get:template<class T, class A>vector<T,A>& vector<T,A>::operator=(const vector& a)// optimized, basic guarantee (§13.2) only{if (capacity() < a.size()) { // allocate new vector representation:vector temp {a};// copy allocatorswap(∗this,temp);// swap representationsreturn ∗this;// implicitly destroy the old value}Section 13.6.3Assignmentif (this == &a) return ∗this;383// optimize self assignmentsize_type sz = size();size_type asz = a.size();vb.alloc = a.vb.alloc;// copy the allocatorif (asz<=sz) {copy(a.begin(),a.begin()+asz,vb.elem);for (T∗ p = vb.elem+asz; p!=vb.space; ++p)// destroy sur plus elements (§16.2.6)p−>˜T();}else {copy(a.begin(),a.begin()+sz,vb.elem);uninitialized_copy(a.begin()+sz,a.end(),vb.space); // construct extra elements}vb.space = vb.elem+asz;return ∗this;}These optimizations are not free.
Obviously, the complexity of the code is far higher. Here, I alsotest for self-assignment. However, I do so mostly to show how it is done because here it is only anoptimization.The copy() algorithm (§32.5.1) does not offer the strong exception-safety guarantee. Thus, ifT::operator=() throws an exception during copy(), the vector being assigned to need not be a copy ofthe vector being assigned, and it need not be unchanged. For example, the first five elements mightbe copies of elements of the assigned vector and the rest unchanged. It is also plausible that an element – the element that was being copied when T::operator=() threw an exception – ends up with avalue that is neither the old value nor a copy of the corresponding element in the vector beingassigned. However, if T::operator=() leaves its operands in valid states before it throws (as itshould), the vector is still in a valid state – even if it wasn’t the state we would have preferred.The standard-library vector assignment offers the (weaker) basic exception-safety guarantee ofthis last implementation – and its potential performance advantages.
If you need an assignmentthat leaves the vector unchanged if an exception is thrown, you must either use a library implementation that provides the strong guarantee or provide your own assignment operation. For example:template<class T, class A>void safe_assign(vector<T,A>& a, const vector<T,A>& b)// simple a = b{vector<T,A> temp{b};// copy the elements of b into a temporar yswap(a,temp);}Alternatively, we could simply use call-by-value (§12.2):template<class T, class A>void safe_assign(vector<T,A>& a, vector<T,A> b){swap(a,b);}// simple a = b (note: b is passed by value)I never can decide if this last version is simply beautiful or too clever for real (maintainable) code.384Exception HandlingChapter 1313.6.4 Changing SizeOne of the most useful aspects of vector is that we can change its size to suit our needs. The mostpopular functions for changing size are v.push_back(x), which adds an x at the end of v, andv.resize(s), which makes s the number of elements in v.13.6.4.1 reserve()The key to a simple implementation of such functions is reserve(), which adds free space at the endfor the vector to grow into.
In other words, reserve() increases the capacity() of a vector. If the newallocation is larger than the old, reserve() needs to allocate new memory and move the elements intoit. We could try the trick from the unoptimized assignment (§13.6.3):template<class T, class A>void vector<T,A>::reserve(size_type newalloc)// flawed first attempt{if (newalloc<=capacity()) return;// never decrease allocationvector<T,A> v(capacity());// make a vector with the new capacitycopy(elem,elem+size(),v.begin())// copy elementsswap(∗this,v);// install new value} // implicitly release old valueThis has the nice property of providing the strong guarantee.
However, not all types have a defaultvalue, so this implementation is flawed. Furthermore, looping over the elements twice, first todefault construct and then to copy, is a bit odd. So let us optimize:template<class T, class A>void vector<T,A>::reserve(size_type newalloc){if (newalloc<=capacity()) return;vector_base<T,A> b {vb.alloc,newalloc};uninitialized_move(elem,elem+size(),b.elem);swap(vb,b);} // implicitly release old space// never decrease allocation// get new space// move elements// install new baseThe problem is that the standard library doesn’t offer uninitialized_move(), so we have to write it:template<typename In, typename Out>Out uninitialized_move(In b, In e, Out oo){for (; b!=e; ++b,++oo) {new(static_cast<void∗>(&∗oo)) T{move(∗b)}; // move constructb−>˜T();// destroy}return b;}In general, there is no way of recovering the original state from a failed move, so I don’t try to.This uninitialized_move() offers only the basic guarantee.
However, it is simple and for the vastmajority of cases it is fast. Also, the standard-library reserve() only offers the basic guarantee.Section 13.6.4.1reserve()385Whenever reserve() may have moved the elements, any iterators into the vector may have beeninvalidated (§31.3.3).Remember that a move operation should not throw. In the rare cases where the obvious implementation of a move might throw, we typically go out of our way to avoid that. A throw from amove operation is rare, unexpected, and damaging to normal reasoning about code. If at all possible avoid it.
The standard-library move_if_noexcept() operations may be of help here (§35.5.1).The explicit use of move() is needed because the compiler doesn’t know that elem[i] is just aboutto be destroyed.13.6.4.2 resize()The vector member function resize() changes the number of elements. Given reserve(), the implementation resize() is fairly simple. If the number of elements increases, we must construct the newelements. Conversely, if the number of elements decrease, we must destroy the surplus elements:template<class T, class A>void vector<T,A>::resize(size_type newsize, const T& val){reserve(newsize);if (size()<newsize)uninitialized_fill(elem+size(),elem+newsize,val);elsedestroy(elem.size(),elem+newsize);vb.space = vb.last = vb.elem+newsize;}// construct new elements: [size():newsize)// destroy sur plus elements: [newsize:size())There is no standard destroy(), but that easily written:template<typename In>void destroy(In b, In e){for (; b!=e; ++b)// destroy [b:e)b−>˜T();}13.6.4.3 push_back()From an exception-safety point of view, push_back() is similar to assignment in that we must takecare that the vector remains unchanged if we fail to add a new element:template< class T, class A>void vector<T,A>::push_back(const T& x){if (capacity()==size())reserve(sz?2∗sz:8);vb.alloc.construct(&vb.elem[size()],val);++vb.space;}// no more free space; relocate:// grow or star t with 8// add val at end// increment sizeNaturally, the copy constructor used to initialize ∗space might throw an exception.
If that happens,386Exception HandlingChapter 13the value of the vector remains unchanged, with space left unincremented. However, reserve() mayalready have reallocated the existing elements.This definition of push_back() contains two ‘‘magic numbers’’ (2 and 8). An industrial-strengthimplementation would not do that, but it would still have values determining the size of the initialallocation (here, 8) and the rate of growth (here, 2, indicating a doubling in size each time the vectorwould otherwise overflow).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
