Sunday, May 6, 2012

Exception Handling in STL

Exception Handling

The STL almost never checks for logical errors. Therefore, almost no exceptions are generated by the STL itself due to a logical problem. In fact, there is only one function call for which the standard requires that it might cause an exception directly: the at() member function for vectors and deques. (It is the checked version of the subscript operator.) Other than that, the standard
requires that only the usual standard exceptions may occur, such as bad_alloc for lack of memory or exceptions of user-defined operations.

When are exceptions generated and what happens to STL components when they are? For a long time during the standardization process there was no defined behavior regarding this. In fact, every exception resulted in undefined behavior. Even the destruction of an STL container after an exception was thrown during one of its operations resulted in undefined behavior, such as a crash. Thus, the STL was useless when you needed guaranteed, defined behavior because it was not even possible to unwind the stack.

How to handle exceptions was one of the last topics addressed during the standardization process. Finding a good solution was not easy, and it took a long time for the following reasons:
  1. It was very difficult to determine the degree of safety the C++ standard library should provide. You might argue that it is always best to provide as much safety as possible. For example, you could say that the insertion of a new element at any position in a vector ought to either succeed or have no effect. Ordinarily an exception might occur while copying later elements into the next position to make room for the new element, from which a full recovery is impossible. To achieve the stated goal, the insert operation would need to be implemented to copy every element of the vector i nto new storage, which would have a serious impact on performance. If good performance is a design goal (as is the case for the STL), you can't provide perfect exception handling in all cases. You have to find a compromise that meets both needs.
  2. There was a concern that the presence of code to handle exceptions could adversely affect performance. This would contradict the design goal of achieving the best possible performance. However, compiler writers state that, in principle, exception handling can be implemented without any significant performance overhead (and many such implementations exist). There is no doubt that it is better to have guaranteed, defined behavior for exceptions without a significant performance penalty instead of the risk that exceptions might crash your system.

As a result of these discussions, the C++ standard library now gives the following basic guarantee for exception safety: The C++ standard library will not leak resources or violate container invariants in the face of exceptions.

Unfortunately, for many purposes this is not enough. Often you need a stronger guarantee that specifies that an operation has no effect if an exception is thrown. Such operations can be considered to be atomic with respect to exceptions. Or, to use terms from database programming, you could say that these operations support commit-or-rollback behavior or are transaction safe.

Regarding this stronger guarantee, the C++ standard library now guarantees the following:
  • For all node-based containers (lists, sets, multisets, maps and multimaps), any failure to construct a node simply leaves the container as it was. Furthermore, removing a node can't fail (provided destructors don't throw). However, for multiple-element insert operations of associative containers, the need to keep elements sorted makes full recovery from throws impractical. Thus, all single-element insert operations of associative containers support commit-or-rollback behavior. That is, they either succeed or have no effect. In addition, it is guaranteed that all erase operations for both single- and multiple elements always succeed. 
    • For lists, even multiple-element insert operations are transaction-safe. In fact, all list operations, except remove(), remove_if(), merge(), sort(), and unique(), either succeed or have no effect. For some of them the C++ standard library provides conditional guarantees. Thus, if you need a transaction-safe container, you should use a list.
  • All array-based containers (vectors and deques) do not fully recover when an element gets inserted. To do this, they would have to copy all subsequent elements before any insert operation, and handling full recovery for all copy operations would take quite a lot of time. However, push and pop operations that operate at the end do not require that existing elements have to get copied. So if they throw, it is guaranteed that they have no effect. Furthermore, if elements have a type with copy operations (copy constructor and assignment operator) that do not throw, then every container operation for these elements either succeeds or has no effect.
Note that all these guarantees are based on the requirement that destructors never throw (which should always be the case in C++). The C++ standard library makes this promise, and so must the application programmer. If you need a container that has a full commit-or-rollback ability, you should use either a list (without calling the sort() and unique() member functions) or an associative container (without calling their multiple-element insert operations). This avoids having to make copies before a modifying operation to ensure that no data gets lost. Note that making copies of a container could be very expensive.

If you can't use a node-based container and need the full commit-or-rollback ability, you have to provide wrappers for each critical operation. For example, the following function would almost safely insert a value in any conta iner at a certain position:

template <class T, class Cont, class Iter>
void insert (const Cont& coll, Iter pos, const T& value)
   Cont tmp(coll); //copy container and all elements 
   tmp. insert (pos, value); //modify the copy
   coll. swap (tmp); //use copy (in case no exception was thrown)

Note that I wrote "almost," because this function still is not perfect. This is because the swap() operation throws when, for associative containers, copying the comparison criterion throws. You see, handling exceptions perfectly is not easy.

No comments:

Post a Comment