Menu
I'm wondering, exactly what is the exception safety guarantee for std::vector::insert? I am interested in both the single-argument and the range overloads of this function.
631
vector insert() function in C++ STL std::vector::insert() is a built-in function in C++ STL that inserts new elements before the element at the specified position, effectively increasing the container size by the number of elements inserted.
Exception safe programming is programming so that if any piece of code that might throw an exception does throw an exception, then the state of the program is not corrupted and resources are not leaked. Getting this right using traditional methods often results in complex, unappealing and brittle code.
Strong exception guarantee -- If the function throws an exception, the state of the program is rolled back to the state just before the function call. (for example, std::vector::push_back) Basic exception guarantee -- If the function throws an exception, the program is in a valid state.
insert(): Inserts new elements into the vector at a particular position. ts time complexity is O(N + M) where N is the number of elements inserted and M is the number of the elements moved . pop_back(): Removes the last element from the vector. Its time complexity is O(1).
Generally, the single-element form of insert has a strong exception guarantee for any container as per [container.requirements.general]/10, but vector::insert is an exception to this rule:
[vector.modifiers]/1 applies to vector::insert; InputIterator here refers to the overload of insert that inserts a range.
If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of
Tor by anyInputIteratoroperation there are no effects. If an exception is thrown by the move-constructor of a non-CopyInsertableT, the effects are unspecified.
vector is an allocator-aware container, which means that it uses an allocator for memory allocation and construction of its elements [container.requirements.general]/3
For the components affected by this subclause that declare an
allocator_type, objects stored in these components shall be constructed using theallocator_traits<allocator_type>::constructfunction and destroyed using theallocator_traits<allocator_type>::destroyfunction. These functions are called only for the container's element type, not for internal types used by the container.
I think this implies that local objects, which are not elements of the container, can be created without using the allocator (e.g. for copy-and-swap). Otherwise, the requirements on the ctors of the value type would be pointless; the allocator's construct function might have different exception guarantees than the value type's ctor.
CopyInsertable is specified in [container.requirements.general]/13 by requiring that
allocator_traits<A>::construct(m, p, v);
is well-formed; where A is the allocator type, m is of type A, p is a pointer to T, v is an expression of type (const) T, and T is the value type of the container. This is an inplace construction from one argument (copy- or move-construction).
Similarly, MoveConstructible is specified, but v is (always) an rvalue of type T. EmplaceConstructible follows the same form for zero or more arguments instead of v.
The insert function for sequence containers imposes different requirements on the value type for its various forms [sequence.reqmts]; here including additional requirements for vector:
const) T and for the form insert N copies of, T shall be CopyInsertable and CopyAssignable
T, T shall be MoveInsertable and MoveAssignable
T shall be EmplaceConstructible from the dereferenced iterators (*); additionally, MoveInsertable and MoveAssignable if the iterators of the range are no forward iterators(*) Note: EmplaceConstructible only from the dereferenced iterators is not enough if the container has to be resized for the insertion (and, e.g. the *i for such an iterator is not of the value type). It is possible that the specification requires the range form to inherit the requirements of the single-element form, i.e. either MoveAssignable or CopyAssignable.
Side remark: The range form of insert requires that the two iterators do not point in the container in which they are to be inserted.
I interpret the exception specifications as follows:
The additional statement about CopyInsertable in the exception specification of vector::insert probably distinguishes between the basic guarantee and no guarantee: The dtor of a container is generally required to call the dtor of all elements and deallocate all memory (in the general container requirements). That is, unless the behaviour is unspecified/undefined, the basic guarantee holds.
Why there is a requirement that combines CopyInsertable and the move-ctor (instead of allocator::construct with an rvalue), I don't know. The move-ctor is only used directly for objects that are not elements of the container (indirectly possibly via allocator::construct).
The other remarks about "no effects" (-> strong guarantee) are not applied to the allocator operations (construct). The allocator operations obviously do not have to be noexcept. As you can provide a non-default allocator that doesn't use the value type's copy- and move-ctor for construct, insert has to provide the strong exception guarantees even for the construct allocator operations. For example, if the allocator's construct is not noexcept, during a resize, the elements cannot be move-constructed but have to be copied.
Move- and copy-assignment have to be noexcept for the strong guarantee as the elements might need to be shifted around for insert; copy- and move-ctor might need to be noexcept for the strong guarantee because of local objects created in the algorithm.
79
answered Sep 28 '22 00:09
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With