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:

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!