|
 |
|
| |
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.
|
|
|
