Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

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 <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;
template<class T> class Ring {
list<T> lst;
// Declaration necessary so the following
// 'friend' statement sees this 'iterator'
// instead of std::iterator:
class iterator;
friend class iterator;
class iterator : public std::iterator<
typename list<T>::iterator it;
list<T>* r;
iterator(list<T>& lst,
const typename list<T>::iterator& i)
: it(i), r(&lst) {}
bool operator==(const iterator& x) const {
return it ==;
bool operator!=(const iterator& x) const {
return !(*this == x);
typename list<T>::reference operator*() const {
return *it;
iterator& operator++() {
if(it == r->end())
it = r->begin();
return *this;
iterator operator++(int) {
iterator tmp = *this;
return tmp;
iterator& operator--() {
if(it == r->begin())
it = r->end();
return *this;
iterator operator--(int) {
iterator tmp = *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<string> rs;
Ring<string>::iterator it = rs.begin();
++it; ++it;
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 are many. (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!

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire