Thinking In C++. Volume 2: Practical Programming

typedef Container::iterator Iter;

int main() {

  Container shapes;

  shapes.push_back(new Circle);

  shapes.push_back(new Square);

  shapes.push_back(new Triangle);

  for(Iter i = shapes.begin();

      i != shapes.end(); i++)

    (*i)->draw();

  purge(shapes);

} ///:~

When using purge( ), carefully consider ownership issues. If an object pointer is held in more than one container, be sure not to delete it twice, and you don’t want to destroy the object in the first container before the second one is finished with it. Purging the same container twice is not a problem, because purge( ) sets the pointer to zero once it deletes that pointer, and calling delete for a zero pointer is a safe operation.

Creating your own containers

With the STL as a foundation, you can create your own containers. Assuming you follow the same model of providing iterators, your new container will behave as if it were a built-in STL container.

Consider the "ring" data structure, which is a circular sequence container. If you reach the end, it just wraps around to the beginning. This can be implemented on top of a list as follows:

//: C07:Ring.cpp

// Making a "ring" data structure from the STL

#include

#include

#include

using namespace std;

template

class Ring {

  list lst;

public:

  // Declaration necessary so the following

  // 'friend' statement sees this 'iterator'

  // instead of std::iterator:

  class iterator;

  friend class iterator;

  class iterator : public std::iterator<

    std::bidirectional_iterator_tag,T,ptrdiff_t>{

    typename list::iterator it;

    list* r;

  public:

    iterator(list& lst,

      const typename list::iterator& i)

      : r(&lst), it(i) {}

    bool operator==(const iterator& x) const {

      return it == x.it;

    }

    bool operator!=(const iterator& x) const {

      return !(*this == x);

    }

    typename list::reference operator*() const {

      return *it;

    }

    iterator& operator++() {

      ++it;

      if(it == r->end())

        it = r->begin();

      return *this;

    }

    iterator operator++(int) {

      iterator tmp = *this;

      ++*this;

      return tmp;

    }

    iterator& operator--() {

      if(it == r->begin())

        it = r->end();

      --it;

      return *this;

    }

    iterator operator--(int) {

      iterator tmp = *this;

      --*this;

      return tmp;

    }

    iterator insert(const T& x){

      return iterator(*r, r->insert(it, x));

    }

    iterator erase() {

      return iterator(*r, r->erase(it));

    }

  };

  void push_back(const T& x) {

    lst.push_back(x);

  }

  iterator begin() {

    return iterator(lst, lst.begin());

  }

 int size() { return lst.size(); }

};

int main() {

  Ring rs;

  rs.push_back("one");

  rs.push_back("two");

  rs.push_back("three");

  rs.push_back("four");

  rs.push_back("five");

  Ring::iterator it = rs.begin();

  it++; it++;

  it.insert("six");

  it = rs.begin();

  // Twice around the ring:

  for(int i = 0; i < rs.size() * 2; i++)

    cout << *it++ << endl;

} ///:~

You can see that most of the coding is in the iterator. The Ring iterator must know how to loop back to the beginning, so it must keep a reference to the list of its "parent" Ring object in order to know if it’s at the end and how to get back to the beginning.

You’ll notice that the interface for Ring is quite limited; in particular, there is no end( ), since a ring just keeps looping. This means that you won’t be able to use a Ring in any STL algorithms that require a past-the-end iterator, which is many of them. (It turns out that adding this feature is a nontrivial exercise.) Although this can seem limiting, consider stack, queue, and priority_queue, which don’t produce any iterators at all!^.

STL extensions

Although the STL containers may provide all the functionality you’ll ever need, they are not complete. For example, the standard implementations of set and map use trees, and although these are reasonably fast, they may not be fast enough for your needs. In the C++ Standards Committee it was generally agreed that hashed implementations of set and map should have been included in Standard C++; however, there was not enough time to add these components, and thus they were left out.[101]

Fortunately, alternatives are freely available. One of the nice things about the STL is that it establishes a basic model for creating STL-like classes, so anything built using the same model is easy to understand if you are already familiar with the STL.

The SGI STL from Silicon Graphics[102] is one of the most robust implementations of the STL and can be used to replace your compiler’s STL if that is found wanting. In addition, SGI has added a number of extensions including hash_set, hash_multiset, hash_map, hash_multimap, slist (a singly linked list), and rope (a variant of string optimized for very large strings and fast concatenation and substring operations).

Let’s consider a performance comparison between a tree-based map and the SGI hash_map. To keep things simple, the mappings will be from int to int:

//: C07:MapVsHashMap.cpp

// The hash_map header is not part of the

// Standard C++ STL. It is an extension that