Many of the problems you set out to solve will only require a simple linear sequence such as a vector, deque, or list. All three have a member function push_back( ) that you use to insert a new element at the back of the sequence (deque and list also have push_front( )).
But now how do you retrieve those elements? With a vector or deque, it is possible to use the indexing operator[ ], but that doesn’t work with list. You can use iterators on all three sequences to access elements. Each container provides the appropriate type of iterator for accessing its elements.
One more observation and then we’ll be ready for another example. Even though the containers hold objects by value (that is, they hold copies of whole objects), sometimes you’ll want to store pointers so that you can refer to objects from a hierarchy and therefore take advantage of the polymorphic behavior of the classes represented. Consider the classic "shape" example in which shapes have a set of common operations, and you have different types of shapes. Here’s what it looks like using the STL vector to hold pointers to various Shape types created on the heap:.
//: C07:Stlshape.cpp
// Simple shapes w/ STL
#include <vector>
#include <iostream>
using namespace std;
class Shape {
public:
virtual void draw() = 0;
virtual ~Shape() {};
};
class Circle : public Shape {
public:
void draw() { cout << "Circle::draw\n"; }
~Circle() { cout << "~Circle\n"; }
};
class Triangle : public Shape {
public:
void draw() { cout << "Triangle::draw\n"; }
~Triangle() { cout << "~Triangle\n"; }
};
class Square : public Shape {
public:
void draw() { cout << "Square::draw\n"; }
~Square() { cout << "~Square\n"; }
};
typedef std::vector<Shape*> Container;
typedef Container::iterator Iter;
int main() {
Container shapes;
shapes.push_back(new Circle);
shapes.push_back(new Square);
shapes.push_back(new Triangle);
for(Iter i = shapes.begin();
i != shapes.end(); i++)
(*i)->draw();
// ... Sometime later:
for(Iter j = shapes.begin();
j != shapes.end(); j++)
delete *j;
} ///:~
The creation of Shape, Circle, Square, and Triangle should be fairly familiar. Shape is a pure abstract base class (because of the pure specifier =0) that defines the interface for all types of shapes. The derived classes redefine the virtual function draw( ) to perform the appropriate operation. Now we’d like to create a bunch of different types of Shape objects, but where to put them? In an STL container, of course. For convenience, this typedef:
typedef std::vector<Shape*> Container;
creates an alias for a vector of Shape*, and this typedef:
typedef Container::iterator Iter;
uses that alias to create another one, for vector<Shape*>::iterator. Notice that the container type name must be used to produce the appropriate iterator, which is defined as a nested class. Although there are different types of iterators (forward, bidirectional, reverse, and so on), they all have the same basic interface: you can increment them with ++, you can dereference them to produce the object they’re currently selecting, and you can test them to see if they’re at the end of the sequence. That’s what you’ll want to do 90 percent of the time. And that’s what is done in the previous example: after a container is created, it’s filled with different types of Shape pointers. Notice that the upcast happens as the Circle, Square, or Rectangle pointer is added to the shapes container, which doesn’t know about those specific types but instead holds only Shape*. As soon as the pointer is added to the container, it loses its specific identity and becomes an anonymous Shape*. This is exactly what we want: toss them all in and let polymorphism sort it out.
The first for loop creates an iterator and sets it to the beginning of the sequence by calling the begin( ) member function for the container. All containers have begin( ) and end( ) member functions that produce an iterator selecting, respectively, the beginning of the sequence and one past the end of the sequence. To test to see if you’re done, you make sure you’re != to the iterator produced by end( ). Not < or <=. The only test that works is !=. So it’s common to write a loop like:.
for(Iter i = shapes.begin(); i != shapes.end(); i++)
This says "take me through every element in the sequence.".
What do you do with the iterator to produce the element it’s selecting? You dereference it using (what else?) the ‘*’ (which is actually an overloaded operator). What you get back is whatever the container is holding. This container holds Shape*, so that’s what *i produces. If you want to call a Shape member function, you must do so with the -> operator, so you write the line:.
(*i)->draw();
This calls the draw( ) function for the Shape* the iterator is currently selecting. The parentheses are ugly but necessary to produce the desired operator precedence.
As they are destroyed or in other cases where the pointers are removed, the STL containers do not automatically call delete for the pointers they contain. If you create an object on the heap with new and place its pointer in a container, the container can’t tell if that pointer is also placed inside another container, nor if it refers to heap memory in the first place. As always, you are responsible for managing your own heap allocations. The last lines in the program move through and delete every object in the container so that proper cleanup occurs.