27

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.

Community
  • 1
  • 1
user541686
  • 205,094
  • 128
  • 528
  • 886
  • @bames53: Example? "`vector::swap` guarantees strong exception safety if the underlying type is movable; otherwise, it guarantees basic exception safety." I couldn't find this in the standard link I put here. – user541686 Jul 28 '12 at 08:06
  • I don't see that guarantee in the standard either. What makes you think that's guaranteed? I don't think it is, and whether the element type is movable seems irrelevant to vector::swap because vector::swap is required to operate in constant time, which means in general it can't do an element-wise swap. – bames53 Jul 28 '12 at 15:26
  • 1
    @bames53: My bad, that was a typo, I meant `vector::insert` (which could *use* `std::swap` underneath). Anyway, I didn't say it's guaranteed, I just gave a *potential example* of something that I was looking for. – user541686 Jul 28 '12 at 17:06
  • I dont think Vector::insert can make that guarantee either. I think maybe the issue is that you are expecting more guarantees than there really are. – bames53 Jul 28 '12 at 17:33
  • 1
    @bames53: Really? It's kind of trivial... allocate a new container, copy the new data (destroy the copies if there's an error), then move the old data. It works; it's just possibly slow, and I'd like to know if this is guaranteed. If not, then it isn't. But like I said: *I just gave a **potential example***... if I already knew the answer then I wouldn't be needing to look it up! – user541686 Jul 28 '12 at 17:47
  • No, consider for example the remarks that apply to vector::insert "If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified." n3337, which you link to, can be treated as official. If you can't find something in there that makes a particular guarantee then its not guaranteed. All the info is there, it's just scattered among occasional sections, each of which is incomplete on its own. I think you'll have to find some non-authoritative reference that's easier to read or just learn to read the standard and how its organized. – bames53 Jul 28 '12 at 20:15
  • 1
    @bames53: What prompted me to write this question was that I could only find the `associative.reqmts.except` and the `unord.req.except` sections in the standard to answer me, which were very incomplete on their own. I never even dreamed that the `.modifiers` section, for instance, would contain exception-requirement info. So yes, *now* that the answers below are here, I can see a lot of the information is there, but when I posted this I couldn't find it. – user541686 Jul 28 '12 at 20:19

3 Answers3

18

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.

Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
Johan Lundberg
  • 26,184
  • 12
  • 71
  • 97
  • 1
    Ah, I didn't realize it at first but the PDF seems to have the info I need (I still need to check though)... doesn't contain C++11 info but still useful. :) Thanks. +1 – user541686 Jul 28 '12 at 07:57
  • That doesn't look like it has everything I need... for example, what about `std::rotate`? Is it like `std::copy`? Or is it stronger or weaker? (I realize this may be different in C++11 than C++03 and earlier -- it could use any combination of copy constructors, move constructors, copy assignments, move assignments, and swaps, depending on how it's implemented. I'd need to know what sorts of guarantees I can rely on for it, for both C++11 and C++03 eventually, but pre-C++11 is also a good start.) – user541686 Jul 28 '12 at 09:22
  • 1
    For algorithms it's not that clear. I suggest you make a list of methods you are interested in and make a new question titled 'exception safety of std algorithms'. The algorithms operate using swap, insert etc so they can not do better than the underlying containers, but you need to read on each one in the standard what the requirements are. For example for rotate the container elements needs to be swappable etc. There's no explicit statement (as far as I can find) on the guarantee in case swap throws in the middle of a rotate action. I read that as 'weak' but try asking a new question. – Johan Lundberg Jul 28 '12 at 10:01
  • Okay, I guess I'll just go with what I see in my current STL implementation regarding whatever's not present in the appendix, and base the guarantees on that... I'll more questions later if needed. That PDF is great! – user541686 Jul 29 '12 at 00:32
11

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.

Community
  • 1
  • 1
Martin York
  • 257,169
  • 86
  • 333
  • 562
  • Hmm... so, for example, if I call `vector::insert()` to insert 2 elements inside a 10000-element vector at index 9998, and the object's copy constructor might throw, then is the vector going to take all the 10000 elements and copy them somewhere, to ensure safety? – user541686 Jul 28 '12 at 08:55
  • @Mehrdad: You missed this `while inserting a **single element**` – Martin York Jul 28 '12 at 09:01
  • Uh, no, that's precisely why I asked you. If I was inserting a single element then the answer would already be in your post. I was looking for something comprehensive -- which would explain what happens in e.g. something like the scenario above. – user541686 Jul 28 '12 at 09:02
  • 23.2.1 paragraph 10: `if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.` – Martin York Jul 28 '12 at 09:03
  • 1
    @Mehrdad: You seem to be misunderstanding my answer. There is no guarantee for 2 (other than the basic). It provides a guarantee only when `while inserting a **single element**`. – Martin York Jul 28 '12 at 09:29
  • So you're saying a copy constructor throwing an exception when inserting multiple elements is going to wreak havoc on the container and/or potentially leak resources? – user541686 Jul 28 '12 at 09:30
  • @Mehrdad: Yes on havoc, No on leak. What I have provided above are the generic guarantees for all containers. If you have a specific function in mind you need to check the documentation for that particular function. In this case: **23.3.6.5 vector modifiers** `If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.` – Martin York Jul 28 '12 at 09:35
  • Wow, I didn't expect that one! Why do you say no on leak -- if there's no guarantee, then couldn't there also be a leak (in theory)? (Btw, I had trouble finding these before your post because "vector modifiers" was not something I expected to have information about exceptions.) – user541686 Jul 28 '12 at 09:43
  • It says the `effect is unspecified`. But that does not mean the object becomes invalid (unspecified is still valid behavior). Because the object is still valid it still owns and maintains all its objects and will thus correctly destroy them (the container destructor guarantees this in table 96). What it can not do is control the behavior of the object that threw but all the objects it owns will be good. Thus it does not need to make 10000 copies to guarantee safety. – Martin York Jul 28 '12 at 09:51
2

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).

bames53
  • 86,085
  • 15
  • 179
  • 244
  • Do you know what they mean by "modifiers"? It completely baffled me when I saw exception guarantees there... – user541686 Jul 29 '12 at 00:33
  • @Mehrdad The standard divides member functions for each class into various categories. If you look at the class overview you will see a list of all the functions divided into the categories. Each group has a link at the start that will take you to the section that specifies functions in that group. – bames53 Jul 29 '12 at 00:53
  • @Mehrdad E.g. section 23.3.6.0 has the vector class template overview and if you scroll down you'll see a comment "//23.3.6.3 _capacity_" followed by functions related to the size and capacity of the vector. If you follow the link to section 23.3.6.3 you'll find the specifications for each one of the functions in that group, including information on whatever exception guarantees a function provides. For example for `vector::reserve()` it is specified that "If an exception is thrown other than by the move constructor of a non-CopyInsertable type, there are no effects." – bames53 Jul 29 '12 at 00:53
  • @Mehrdad In other words, the 'modifiers' section means 'functions that the standard has categorized as modifiers'. It has nothing to do specifically with exceptions, and you will find exception information in the other groups as well, such as "constructors, copy, and assignment", "capacity", "data", "specialized algorithms", etc. – bames53 Jul 29 '12 at 00:57
  • OH... so by "modifiers" they just mean mutators?! That makes a lot of sense (aside from how `resize` and `at` aren't modifiers)... Wow, such an impedance mismatch! Thanks for the detailed explanation! – user541686 Jul 29 '12 at 01:17
  • @Mehrdad resize() and at() aren't in the "modifiers" catagory. resize() is in "capacity" (23.3.6.3) and at() is in "element access". – bames53 Jul 29 '12 at 01:42