Philosophy

Iterators in the STL are badly designed - there are several major pitfalls with using them as a result of their design. However, I wanted STLplus to feel like the STL to make it easier to use, so felt I should use the iterator concept despite the problems associated with them. Some of the STLplus components therefore also use iterators.

The problems with STL iterators are:

• Unassigned iterators are poorly defined and can not only point to random memory but have no checking to stop them from being dereferenced.
• End iterators conceptually point to a location one element after the end of the data structure. The STL classes actually have a piece of unconstructed memory to represent the end - which looks like real memory that's been corrupted. This is extraordinarily bad practice.
• Iterators don't know which container created them. For example, in the STL, creating an iterator from one list and then accidentally using it in a second list can potentially corrupt the list.
• When an object held by a container is destroyed, iterators can still point to the deallocated memory and there's nothing to stop them from being dereferenced.

Errors Caught by the Safe Iterator

The STLplus safe iterators were designed to solve the problems with the STL iterators. The following solutions have been implemented:

• Unassigned iterators initialise to a "null" iterator. It is illegal to try to dereference a null iterator - the safe_iterator class throws a null_dereference exception.
• The end iterator concept is a property of the iterator itself and there is no unconstructed memory. It is illegal to dereference the end iterator - the safe_iterator class will throw an end_dereference exception.
• Iterators must be used with the container that created them. The safe iterator knows which object it belongs to and, if used with the wrong object, will throw the wrong_object exception.
• When an object held by a container is destroyed, all iterators pointing to the object are set to the end iterator. This prevents iterators being used to access deallocated memory.

Classes Using the Safe Iterator

The following STLplus classes use safe iterators, all of them based on the safe_iterator class:

• digraph
• ntree
• hash

Interface

Here is the user interface to the safe_iterator class:

template<typename O, typename N>
class stlplus::safe_iterator
{
public:
  // construct a null iterator
  safe_iterator(void);

  // construct a valid iterator from the owner node's master iterator
  safe_iterator(const master_iterator<O,N>&);

  // comparison - used to create comparison operators for putting
  // iterators into maps and hashes
  bool equal(const safe_iterator<O,N>& right) const;
  int compare(const safe_iterator<O,N>& right) const;

  // dereference
  N& operator*(void) const;
  N* operator->(void) const;

  // a null iterator is one that has not been initialised with a value yet
  // i.e. you just declared it but didn't assign to it
  bool null(void) const;

  // an end iterator is one that points to the end element of the list of nodes
  // in STL conventions this is one past the last valid element and must not be dereferenced
  bool end(void) const;

  // a valid iterator is one that can be dereferenced
  // i.e. non-null and non-end
  bool valid(void) const;

  // called by the owner class to check the rules
  void assert_valid(const O* owner) const;
};

The void constructor ensures that an unassigned iterator is classified as a null iterator.

The second iterator is used internally by the container object to create a valid iterator.

Built-in comparison methods allow for comparison operators to be written for any iterator derived from safe_iterator, for example to test for the end condition in a for loop or any other conditional. They also allow iterators to be added to sets (the < operator) and hashes (the == operator).

The dereference operators are only legal on valid iterators - any attempt to dereference a null or end iterator will throw an exception.

The methods null(), end() and valid() allow the programmer to test the validity of an iterator before dereferencing it.

The assert_valid method is called by the owning container to check that the iterator belongs to it before using it. If not, it will throw the wrong_object exception. Also, if the owner needs to dereference the iterator, it will check whether it is valid and if not, throw either the null_dereference or end_dereference exception.