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++
Prev Contents / Index Next

PStash with iterators

For most container classes it makes sense to have an iterator. Here’s an iterator added to the PStash class:

//: C16:TPStash2.h
// Templatized PStash with nested iterator
#ifndef TPSTASH2_H
#define TPSTASH2_H
#include "../require.h"
#include <cstdlib>

template<class T, int incr = 20>
class PStash {
  int quantity;
  int next;
  T** storage;
  void inflate(int increase = incr);
  PStash() : quantity(0), storage(0), next(0) {}
  int add(T* element);
  T* operator[](int index) const;
  T* remove(int index);
  int count() const { return next; }
  // Nested iterator class:
  class iterator; // Declaration required
  friend class iterator; // Make it a friend
  class iterator { // Now define it
    PStash& ps;
    int index;
    iterator(PStash& pStash)
      : ps(pStash), index(0) {}
    // To create the end sentinel:
    iterator(PStash& pStash, bool)
      : ps(pStash), index( {}
    // Copy-constructor:
    iterator(const iterator& rv)
      : ps(, index(rv.index) {}
    iterator& operator=(const iterator& rv) {
      ps =;
      index = rv.index;
      return *this;
    iterator& operator++() {
      require(++index <=,
        "PStash::iterator::operator++ "
        "moves index out of bounds");
      return *this;
    iterator& operator++(int) {
      return operator++();
    iterator& operator--() {
      require(--index >= 0,
        "PStash::iterator::operator-- "
        "moves index out of bounds");
      return *this;
    iterator& operator--(int) { 
      return operator--();
    // Jump interator forward or backward:
    iterator& operator+=(int amount) {
      require(index + amount < && 
        index + amount >= 0, 
        "PStash::iterator::operator+= "
        "attempt to index out of bounds");
      index += amount;
      return *this;
    iterator& operator-=(int amount) {
      require(index - amount < && 
        index - amount >= 0, 
        "PStash::iterator::operator-= "
        "attempt to index out of bounds");
      index -= amount;
      return *this;
    // Create a new iterator that's moved forward
    iterator operator+(int amount) const {
      iterator ret(*this);
      ret += amount; // op+= does bounds check
      return ret;
    T* current() const {
    T* operator*() const { return current(); }
    T* operator->() const { 
      require([index] != 0, 
        "PStash::iterator::operator->returns 0");
      return current(); 
    // Remove the current element:
    T* remove(){
      return ps.remove(index);
    // Comparison tests for end:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
  iterator begin() { return iterator(*this); }
  iterator end() { return iterator(*this, true);}

// Destruction of contained objects:
template<class T, int incr>
PStash<T, incr>::~PStash() {
  for(int i = 0; i < next; i++) {
    delete storage[i]; // Null pointers OK
    storage[i] = 0; // Just to be safe
  delete []storage;

template<class T, int incr>
int PStash<T, incr>::add(T* element) {
  if(next >= quantity)
  storage[next++] = element;
  return(next - 1); // Index number

template<class T, int incr> inline
T* PStash<T, incr>::operator[](int index) const {
  require(index >= 0,
    "PStash::operator[] index negative");
  if(index >= next)
    return 0; // To indicate the end
  require(storage[index] != 0, 
    "PStash::operator[] returned null pointer");
  return storage[index];

template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
  // operator[] performs validity checks:
  T* v = operator[](index);
  // "Remove" the pointer:
  storage[index] = 0;
  return v;

template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
  const int tsz = sizeof(T*);
  T** st = new T*[quantity + increase];
  memset(st, 0, (quantity + increase) * tsz);
  memcpy(st, storage, quantity * tsz);
  quantity += increase;
  delete []storage; // Old storage
  storage = st; // Point to new memory
#endif // TPSTASH2_H ///:~

Most of this file is a fairly straightforward translation of both the previous PStash and the nested iterator into a template. This time, however, the operators return references to the current iterator, which is the more typical and flexible approach to take.

The destructor calls delete for all contained pointers, and because the type is captured by the template, proper destruction will take place. You should be aware that if the container holds pointers to a base-class type, that type should have a virtual destructor to ensure proper cleanup of derived objects whose addresses have been upcast when placing them in the container.

The PStash::iterator follows the iterator model of bonding to a single container object for its lifetime. In addition, the copy-constructor allows you to make a new iterator pointing at the same location as the existing iterator that you create it from, effectively making a bookmark into the container. The operator+= and operator-= member functions allow you to move an iterator by a number of spots, while respecting the boundaries of the container. The overloaded increment and decrement operators move the iterator by one place. The operator+ produces a new iterator that’s moved forward by the amount of the addend. As in the previous example, the pointer dereference operators are used to operate on the element the iterator is referring to, and remove( ) destroys the current object by calling the container’s remove( ).

The same kind of code as before (a la the Standard C++ Library containers) is used for creating the end sentinel: a second constructor, the container’s end( ) member function, and operator== and operator!= for comparison.

The following example creates and tests two different kinds of Stash objects, one for a new class called Int that announces its construction and destruction and one that holds objects of the Standard library string class.

//: C16:TPStash2Test.cpp
#include "TPStash2.h"
#include "../require.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Int {
  int i;
  Int(int ii = 0) : i(ii) {
    cout << ">" << i << ' ';
  ~Int() { cout << "~" << i << ' '; }
  operator int() const { return i; }
  friend ostream&
    operator<<(ostream& os, const Int& x) {
      return os << "Int: " << x.i;
  friend ostream&
    operator<<(ostream& os, const Int* x) {
      return os << "Int: " << x->i;

int main() {
  { // To force destructor call
    PStash<Int> ints;
    for(int i = 0; i < 30; i++)
      ints.add(new Int(i));
    cout << endl;
    PStash<Int>::iterator it = ints.begin();
    it += 5;
    PStash<Int>::iterator it2 = it + 10;
    for(; it != it2; it++)
      delete it.remove(); // Default removal
    cout << endl;
    for(it = ints.begin();it != ints.end();it++)
      if(*it) // Remove() causes "holes"
        cout << *it << endl;
  } // "ints" destructor called here
  cout << "\n-------------------\n";  
  ifstream in("TPStash2Test.cpp");
  assure(in, "TPStash2Test.cpp");
  // Instantiate for String:
  PStash<string> strings;
  string line;
  while(getline(in, line))
    strings.add(new string(line));
  PStash<string>::iterator sit = strings.begin();
  for(; sit != strings.end(); sit++)
    cout << **sit << endl;
  sit = strings.begin();
  int n = 26;
  sit += n;
  for(; sit != strings.end(); sit++)
    cout << n++ << ": " << **sit << endl;
} ///:~

For convenience, Int has an associated ostream operator<< for both an Int& and an Int*.

The first block of code in main( ) is surrounded by braces to force the destruction of the PStash<Int> and thus the automatic cleanup by that destructor. A range of elements is removed and deleted by hand to show that the PStash cleans up the rest.

For both instances of PStash, an iterator is created and used to move through the container. Notice the elegance produced by using these constructs; you aren’t assailed with the implementation details of using an array. You tell the container and iterator objects what to do, not how. This makes the solution easier to conceptualize, to build, and to modify.

Thinking in C++
Prev Contents / Index Next

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