Key Points

Levels of a Data-Structure Specification

• Interface: the operations it offers
• In C++, the public members of a class
  • Encoding: the data the structure uses to do its job
    • In C++, the private members of a class
  • Implementation: the actual procedures that manipulate the data to satisfy the interface promises
    • In C++, the member-variable definitions of a class

Multiple Encodings for the List Interface

• Array-backed lists
  • Contents stored in an array, which resizes as necessary
  • Good at random access
  • Bad at inserting/removing at or near the start of the list
• Linked lists
  • Contents in list nodes, linked in a chain
  • Good at inserting/removing at beginning
  • Bad at random access

Iterators

Iterator Misuse: Obey These Rules

• Don't use * on a past-the-end iterator.
• Don't use ++ on a past-the-end iterator.
• Don't use -- on an iterator at the beginning (there is no such thing as a before-the-beginning iterator).
• Don't do anything to an iterator that isn't valid other than destroy it or assign a new value to it.
• Don't compare iterators from different origins.

Valid and Invalid Iterators

The interface for a data structure gives rules for when iterators will stay valid and when they will cease to be valid.

• Universally applicable reasons an iterator would be valid but not refer to an item (we can't call ++ or * on these iterators, but we can test them against other iterators from the same origin):

  • The iterator was default constructed, rather than initialized with a valid value.
  • The iterator is past the end.

• Universally applicable reasons an iterator would be not be valid:

  • The underlying container is destroyed/deallocated.

• Container-specific iterator validity rules

  • For containers with an erase member function, eraseing the item referred to by an iterator means that the iterator passed to erase is no longer valid, and also that any and all other iterators referring to the erased location are no longer valid.
  • Sequence data structures based on arrays typically don't promise that iterators will continue to be valid after an item is added or removed (so the data structure can resize the array, which moves all of its data to somewhere else in memory when it copies the array).
  • In contrast, sequence data structures based on linked lists typically do preserve iterators as much as possible, except for iterators that refer to items that have been removed.

(When logged in, completion status appears here.)

Previous Page Next Page