UAF CS 311 - Allocation & Efficiency Generic Containers Notes on Assignment 5

Unformatted text preview:

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 Queues30 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

UAF CS 311 - Allocation & Efficiency Generic Containers Notes on Assignment 5

Download Allocation & Efficiency Generic Containers Notes on Assignment 5
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Allocation & Efficiency Generic Containers Notes on Assignment 5 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Allocation & Efficiency Generic Containers Notes on Assignment 5 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?