Where can I find all the exception guarantees for the Standard Containers and Algorithms?

Question

Yes, I've looked at the C++ standards that I could find (or the drafts), but I'm not finding any comprehensive of the exception guarantees given by STL containers. All I can find are occasional sections with incomplete descriptions on some of the functions for some of the types. Or perhaps it's there but I'm just not finding it, I don't know.

Note: I'm not asking for a list of all the guarantees people can think of, which is basically in this question.
I'm looking for the authoritative source of this information itself -- or preferably, a free version of the source (e.g. a draft of the standard) where I can more or less treat as official.

Answer 1

Reading the standard can be scary (let's come back to the standard), but Bjarne Stroustrup has written a really nice appendix on this subject in his book 'The C++ Programming Language'. He posted this appendix at

http://www.stroustrup.com/3rd_safe0.html , at http://www.stroustrup.com/3rd_safe.pdf

It's pretty long and detailed (and well written). You may for example find section E.4 interesting, quote:

E.4 Standard Container Guarantees

If a library operation itself throws an exception, it can – and does – make sure that the objects on which it operates are left in a well-defined state. For example, at() throwing out_of_range for a vector (§16.3.3) is not a problem with exception safety for the vector . The writer of at() has no problem making sure that a vector is in a well-defined state before throwing.

In addition, section E.4.1 states

In addition to the basic guarantee, the standard library offers the strong guarantee for a few operations that insert or remove elements.

have a look at page 956. It contains a table of guarantees for various operations for vector, deque, list and map. In summary, all operations on those containers are either nothrow or strong, except for N - element insert into map which offers the basic guarantees.

Note: the above text is old and does not address C++11, but should still be correct enough for most aims and purposes.

When it comes to C++11...

the standard first states, about the containers array, deque, forward_list, list, vector, map, set, unordered_map, unordered_set, queue,stack: at

23.2.1/10:

Unless otherwise specified (see 23.2.4.1, 23.2.5.1, 23.3.3.4, and 23.3.6.5) all container types defined in this Clause meet the following additional requirements:

— if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.
— if an exception is thrown by a push_back() or push_front() function, that function has no effects.
— no erase(), clear(), pop_back() or pop_front() function throws an exception.
— no copy constructor or assignment operator of a returned iterator throws an exception.
— no swap() function throws an exception.
— no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

The quirks pointed out in the respective sections referred to above (each called Exception safety guarantees) are mostly about special against-the-wall cases like when dealing with exceptions from the contained types' hashing, comparison operations as well as throwing swap and throwing move operations.

Answer 2

n3376

23.2.1 General container requirements [container.requirements.general]

Paragraph 10

Unless otherwise specified (see 23.2.4.1, 23.2.5.1, 23.3.3.4, and 23.3.6.5) all container types defined in this Clause meet the following additional requirements:
— if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.
— if an exception is thrown by a push_back() or push_front() function, that function has no effects.
— no erase(), clear(), pop_back() or pop_front() function throws an exception.
— no copy constructor or assignment operator of a returned iterator throws an exception.
— no swap() function throws an exception.
— no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
[Note: The end() iterator does not refer to any element, so it may be invalidated. —endnote]

23.2.4 Associative containers [associative.reqmts]

23.2.4.1 Exception safety guarantees [associative.reqmts.except]

1 For associative containers, no clear() function throws an exception. erase(k) does not throw an exception unless that exception is thrown by the container’s Compare object (if any).
2 For associative containers, if an exception is thrown by any operation from within an insert or emplace function inserting a single element, the insertion has no effect.
3 For associative containers, no swap function throws an exception unless that exception is thrown by the swap of the container’s Compare object (if any).

23.2.5 Unordered associative containers [unord.req]

23.2.5.1 Exception safety guarantees [unord.req.except]

1 For unordered associative containers, no clear() function throws an exception. erase(k) does not throw an exception unless that exception is thrown by the container’s Hash or Pred object (if any).
2 For unordered associative containers, if an exception is thrown by any operation other than the container’s hash function from within an insert or emplace function inserting a single element, the insertion has no effect.
3 For unordered associative containers, no swap function throws an exception unless that exception is thrown by the swap of the container’s Hash or Pred object (if any).
4 For unordered associative containers, if an exception is thrown from within a rehash() function other than by the container’s hash function or comparison function, the rehash() function has no effect.

23.3.3.4 deque modifiers [deque.modifiers]

void push_back(T&& x); Paragraph 2

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

iterator erase(const_iterator first, const_iterator last); Paragraph 6

Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment operator, or move assignment operator of T.

23.3.6.5 vector modifiers [vector.modifiers]

void push_back(T&& x); Paragraph 2

If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

iterator erase(const_iterator first, const_iterator last); Paragraph 5

Throws: Nothing unless an exception is thrown by the copy constructor, move constructor, assignment operator, or move assignment operator of T.

Answer 3

The document you've linked to, the n3337 draft standard, can be treated as official. It's the C++11 standard plus minor editorial changes.

You just need to learn to read the standard, which is understandable because it's not intended to be easy reading.

To find the exception guarantees for any particular library operation, check that operation's specification for remarks and comments on exceptions. If the function is a member function then check the specification of the type for comments on exception safety and what requirements it fulfills. Then check the fulfilled requirements for exception guarantees that must be made by objects to fulfill those requirements.

For generic types and algorithms also check the requirements placed on the template parameters in order to see what requirements those types have to meet in order for all the exception guarantees made by the type or algorithm or member function to hold (if the template parameters don't meet the specified requirements then using the template with those parameters has undefined behavior and none of the template's specifications apply).