shapes.push_back(new Square); shapes.push_back(new Triangle); for(Iter i = shapes.begin();
i != shapes.end(); i++) (*i)->draw();
purge(shapes); } ///:~
When using purge( ), you must be careful to consider ownership issues – if an object pointer is held in more than one container, then you must be sure not to delete it twice, and you don’t want to destroy the object in the first container before the second one is finished with it.
Purging the same container twice is not a problem, because purge( ) sets the pointer to zero once it deletes that pointer, and calling delete for a zero pointer is a safe operation.
Creating your own containers
With the STL as a foundation, it’s possible to 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:
//: C04:Ring.cpp
// Making a "ring" data structure from the STL #include <iostream>
#include <list> #include <string> using namespace std;
template<class T> class Ring {
list<T> lst; public:
//Declaration necessary so the following
//'friend' statement sees this 'iterator'
//instead of std::iterator:
class iterator;
friend class iterator;
class iterator : public std::iterator< std::bidirectional_iterator_tag,T,ptrdiff_t>{ list<T>::iterator it;
list<T>* r;
Chapter 15: Multiple Inheritance
255
public:
// "typename" necessary to resolve nesting: iterator(list<T>& lst,
const typename list<T>::iterator& i) : r(&lst), it(i) {}
bool operator==(const iterator& x) const { return it == x.it;
}
bool operator!=(const iterator& x) const { return !(*this == x);
}
list<T>::reference operator*() const { return *it;
}
iterator& operator++() { ++it;
if(it == r->end()) it = r->begin();
return *this;
}
iterator operator++(int) { iterator tmp = *this; ++*this;
return tmp;
}
iterator& operator--() { if(it == r->begin())
it = r->end(); --it;
return *this;
}
iterator operator--(int) { iterator tmp = *this; --*this;
return tmp;
}
iterator insert(const T& x){
return iterator(*r, r->insert(it, x));
}
iterator erase() {
return iterator(*r, r->erase(it));
}
};
Chapter 15: Multiple Inheritance
256
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; rs.push_back("one"); rs.push_back("two"); rs.push_back("three"); rs.push_back("four"); rs.push_back("five");
Ring<string>::iterator it = rs.begin(); it++; it++;
it.insert("six"); it = rs.begin();
// Twice around the ring:
for(int i = 0; i < rs.size() * 2; i++) cout << *it++ << endl;
} ///:~
You can see that the iterator is where most of the coding is done. 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 non-trivial exercise). Although this can seem limiting, consider stack, queue and priority_queue, which don’t produce any iterators at all!
Freely-available
STL extensions
Although the STL containers may provide all the functionality you’ll ever need, they are not complete. For example, the standard implementations of set and map use trees, and although these are reasonably fast they may not be fast enough for your needs. In the C++ Standards Committee it was generally agreed that hashed implementations of set and map should have
Chapter 15: Multiple Inheritance
257
been included in Standard C++, however there was not considered to be enough time to add these components, and thus they were left out.
Fortunately, there are freely-available alternatives. One of the nice things about the STL is that it establishes a basic model for creating STL-like classes, so anything built using the same model is easy to understand if you are already familiar with the STL.
The SGI STL (freely available at http://www.sgi.com/Technology/STL/) is one of the most robust implementations of the STL, and can be used to replace your compiler’s STL if that is found wanting. In addition they’ve added a number of extensions including hash_set, hash_multiset, hash_map, hash_multimap, slist (a singly-linked list) and rope (a variant of string optimized for very large strings and fast concatenation and substring operations).
Let’s consider a performance comparison between a tree-based map and the SGI hash_map. To keep things simple, the mappings will be from int to int:
//: C04:MapVsHashMap.cpp
//The hash_map header is not part of the
//Standard C++ STL. It is an extension that
//is only available as part of the SGI STL: #include <hash_map>
#include <iostream> #include <map> #include <ctime> using namespace std;
int main(){ hash_map<int, int> hm; map<int, int> m;
clock_t ticks = clock(); for(int i = 0; i < 100; i++)
for(int j = 0; j < 1000; j++) m.insert(make_pair(j,j));
cout << "map insertions: "
<<clock() - ticks << endl; ticks = clock();
for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++)
hm.insert(make_pair(j,j)); cout << "hash_map insertions: "
<<clock() - ticks << endl; ticks = clock();
for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++)
m[j];
Chapter 15: Multiple Inheritance
258