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.

In STLplus 2 I included some error checking for misuse of iterators. In STLplus 3 I have completed the job - so I have termed the STLplus iterators "safe iterators".

Errors Caught by the Safe Iterator

• 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.
• End iterators conceptually point to a location one element after the end of the data structure. In the STL, there is actually a piece of unconstructed memory there - which looks like real memory that's been corrupted. This is bad practice. In the STLplus, the end iterator concept is a property of the iterator itself and there is no unconstructed memory anywhere. 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. 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. The STLplus safe iterator knows which object it belongs to and, if used with the wrong object, the safe_iterator class will throw the wrong_object exception.
• Iterators can point to objects that have been deleted and if these iterators are dereferenced, the results are unpredictable since the deleted object may be corrupted. In STLplus, when an object held by a container is destroyed, all iterators pointing to the object are set to the end iterator.

Classes Using the Safe Iterator

The following STLplus classes use 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) throw();

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

  // comparison - do they point to the same element? 
  bool operator ==(const safe_iterator<O,N>& right) const throw();
  bool operator !=(const safe_iterator<O,N>& right) const throw();
  // The < operator is used for putting iterators into sets
  bool operator <(const safe_iterator<O,N>& right) const throw();

  // dereference
  N& operator*(void) const throw(null_dereference,end_dereference);
  N* operator->(void) const throw(null_dereference,end_dereference);

  // 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 throw();

  // 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 throw();

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

  // called by the owner class to check the rules
  void assert_valid(const O* owner) const throw(wrong_object,null_dereference,end_dereference);
};

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 operators allow for comparisons, 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.