Allocation & EfficiencyGeneric ContainersNotes on Assignment 5CS 311 Data Structures and AlgorithmsLecture SlidesFriday, October 30, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell30 Oct 2009 CS 311 Fall 2009 2Unit OverviewHandling Data & SequencesMajor Topics Data abstraction Introduction to Sequences Smart arrays Array interface Basic array implementation Exception safety Allocation & efficiency Generic containers Linked Lists Node-based structures More on Linked Lists Sequences in the C++ STL Stacks Queues30 Oct 2009 CS 311 Fall 2009 3ReviewArray InterfaceCtors & Dctor Default ctor Ctor given size Copy ctor DctorMember Operators Copy assignment BracketGlobal Operators NoneAssociated Global Functions NoneNamed Public Member Functions size empty begin end resize insert remove swap30 Oct 2009 CS 311 Fall 2009 4ReviewBasic Array ImplementationWhat data members should class SmArray have? Size of the array: size_type size_; Pointer to the array: value_type * data_;What class invariants should it have? Member “size_” should be nonnegative. Member “data_” should point to an int array, allocated with new [], owned by *this, holding size_ ints.Note: This design has a serious (but not obvious) problem, as we will see.30 Oct 2009 CS 311 Fall 2009 5ReviewException Safety — Refresher [1/3]Exceptions are objects that are “thrown”, generally to signal error conditions.We can catch all exceptions, using “...”. In this case, we do not get to look at the exception, since we do not know what type it is.try {p = new Foo[mySize]; // May throw}catch (...) {fixThingsUp();throw;} Inside any catch block, we can re-throw the same exceptionusing throw with no parameters.30 Oct 2009 CS 311 Fall 2009 6ReviewException Safety — Refresher [2/3]The following can throw in C++: “throw” throws. “new” may throw std::bad_alloc if it cannot allocate. A function that (1) calls a function that throws, and (2) does not catch the exception, will throw. Functions written by others may throw. See their doc’s.The following do not throw: Built-in operations on built-in types. Including the built-in operator[]. Deallocation done by the built-in version of “delete”. Note: “delete” also calls destructors. These can throw. C++ Standard I/O Libraries (default behavior)30 Oct 2009 CS 311 Fall 2009 7ReviewException Safety — Refresher [3/3]If a destructor is called between a throw and a catch, and that destructor throws, then the program terminates. Therefore, destructors should not throw.30 Oct 2009 CS 311 Fall 2009 8ReviewException Safety — Introduction [1/2]Issues: Does a function ever signal client code that an error has occurred, and if it does: Are the data left in a usable state? Do we know something about that state? Are resource leaks avoided?These issues are collectively referred to as safety.We consider these in the context of exceptions: exception safety.However, most of the ideas we will discuss apply to any kind of error signaling technique.30 Oct 2009 CS 311 Fall 2009 9ReviewException Safety — Introduction [2/2]There are a number of commonly used safety levels. These are stated in the form of guarantees that a function makes.In this class, we will adopt the convention that a function throws when it cannot satisfy its postconditions. When a function exits without satisfying its postconditions, we will say it has failed.Thus, a function we write must do one of two things: Succeed (satisfy its postconditions), or Fail, throw an exception, and satisfy its safety guarantee.30 Oct 2009 CS 311 Fall 2009 10ReviewException Safety — The Three Standard GuaranteesBasic Guarantee Data remain in a usable state, and resources are never leaked, even in the presence of exceptions.Strong Guarantee If the operation throws an exception, then it makes no changes that are visible to the client code.No-Throw Guarantee The operation never throws an exception.Notes Each guarantee includes the previous one. The Basic Guarantee is the minimum standard for all code. The Strong Guarantee is the one we generally prefer. The No-Throw Guarantee is required in some special situations.30 Oct 2009 CS 311 Fall 2009 11ReviewException Safety — Writing Exception-Safe Code [1/2]To make sure code is exception-safe: Look at every place an exception might be thrown. For each, make sure that, if an exception is thrown, either we terminate normally and meet our postconditions, or we throw and meet our guarantees.A bad design can force us to be unsafe. Thus, good design is part of of exception safety. An often helpful idea is that every module has exactly one well defined responsibility (the Single Responsibility Principle). In particular: A non-const member function should not return an object by value.30 Oct 2009 CS 311 Fall 2009 12ReviewException Safety — Writing Exception-Safe Code [2/2]TO DO Figure out and comment the exception-safety guarantees made by all functions implemented so far in class SmArray. Can/should any of these be improved? No. All the constructors offer the Strong Guarantee, which cannot be improved, since they do dynamic allocation, and so might fail. All other functions written so far offer the No-Throw Guarantee.Done. See the latest versions of smarray.h, smarray.cpp, on the web page.30 Oct 2009 CS 311 Fall 2009 13ReviewException Safety — Commit Functions [1/5]Often it is tricky to offer the Strong Guarantee when modifying multiple parts of a large object.Solution Create an entirely new object with the new value. If there is an error, destroy the new object. The old object has not changed, so there is nothing to roll back. If there is no error, commit to our changes using a non-throwing operation.A good commit function is a non-throwing swap function.30 Oct 2009 CS 311 Fall 2009 14ReviewException Safety — Commit Functions [2/5]Swap member functions usually look like this:void MyClass::swap(MyClass & other); This should exchange the values of *this and other.If the data members are all built-in types (including pointers!), then we can usually just call std::swap on them.void MyClass::swap(MyClass & other){std::swap(x, other.x);std::swap(y, other.y);}30 Oct 2009
View Full Document