14

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.

Puppy
  • 144,682
  • 38
  • 256
  • 465

3 Answers3

4

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 T or by any InputIterator operation there are no effects. If an exception is thrown by the move-constructor of a non-CopyInsertable T, 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 the allocator_traits<allocator_type>::construct function and destroyed using the allocator_traits<allocator_type>::destroy function. 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:

  • for a single argument that is an lvalue of type (const) T and for the form insert N copies of, T shall be CopyInsertable and CopyAssignable
  • for a single argument that is an rvalue of type T, T shall be MoveInsertable and MoveAssignable
  • for the range form, 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.

dyp
  • 38,334
  • 13
  • 112
  • 177
  • Regarding your side remark: what do you do if you *do* want to insert some elements of the container inside itself? – user541686 Oct 23 '13 at 07:59
  • @Mehrdad Use the single-element form? At least, [it's required to work](http://stackoverflow.com/q/18788780/420683). – dyp Oct 23 '13 at 08:02
3

The exact guarantee is given in C++11 23.3.6.5:

If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • What does this mean with `there are no effects`? What happens to already assigned elements in the vector? – RedX Oct 23 '13 at 07:40
  • 2
    @RedX: It means that there are no effects; everything is restored to the initial state, as if nothing happened. If there are already assigned elements, then the exception must have been thrown by "the copy constructor, move constructor, assignment operator, or move assignment operator of `T` or by any `InputIterator` operation", in which case there's no such guarantee. – Mike Seymour Oct 23 '13 at 07:47
  • 2
    So does this imply basic guarantee for if the copy constructor of T throws? – Puppy Oct 23 '13 at 12:48
  • @DeadMG: I guess so. Your interpretation is probably as good as mine. – Mike Seymour Oct 23 '13 at 14:10
1

If the insert method inserts a single element at the end of the list and does not require any memory to be allocated, offers a strong exception guarantee.

If it has to add more than one element, or has to allocate memory it offers a basic exception guarantee. Boost has a good description of the exception guarantees.

The basic guarantee: that the invariants of the component are preserved, and no resources are leaked. The strong guarantee: that the operation has either completed successfully or thrown an exception, leaving the program state exactly as it was before the operation started. The no-throw guarantee: that the operation will not throw an exception.

This means that after an exception, you know that the vector will be usable, but it may not have all of the data you had inserted in it. All of the objects that were successfully inserted will be fully constructed.

Steve
  • 7,171
  • 2
  • 30
  • 52