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);
public:
PStash() : quantity(0), storage(0), next(0) {} ~PStash();
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;
public:
iterator(PStash& pStash)
: ps(pStash), index(0) {} // To create the end sentinel:
iterator(PStash& pStash, bool)
: ps(pStash), index(ps.next) {} // Copy-constructor:
iterator(const iterator& rv)
: ps(rv.ps), index(rv.index) {} iterator& operator=(const iterator& rv) { ps = rv.ps;
index = rv.index;
return *this;
}
iterator& operator++() { require(++index <= ps.next,
"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 < ps.next &&
index + amount >= 0,
"PStash::iterator::operator+= "
"attempt to index out of bounds");
index += amount;
return *this;
}
iterator& operator-=(int amount) { require(index - amount < ps.next &&
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 { return ps.storage[index];
}
T* operator*() const { return current(); } T* operator->() const { require(ps.storage[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)
inflate();
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;
public:
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.
