Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
Here s an example using the set class template, a container modeled after a traditional mathematical set and which does not accept
duplicate values. The following set was created to work with ints:
//: C07:Intset.cpp
// Simple use of STL set.
#include <cassert>
#include <set>
using namespace std;
int main() {
set<int> intset;
for(int i = 0; i < 25; i++)
for(int j = 0; j < 10; j++)
// Try to insert duplicates:
intset.insert(j);
assert(intset.size() == 10);
} ///:~
The insert( ) member does all the work: it
attempts to insert an element and ignores it if it s already there. Often the
only activities involved in using a set are simply insertion and testing to see
whether it contains the element. You can also form a union, an intersection, or
a difference of sets and test to see if one set is a subset of another. In this
example, the values 0 9 are inserted into the set 25 times, but only the 10
unique instances are accepted.
Now consider taking the form of Intset.cpp and
modifying it to display a list of the words used in a document. The solution
becomes remarkably simple.
//: C07:WordSet.cpp
#include <fstream>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
#include "../require.h"
using namespace std;
void wordSet(const char* fileName) {
ifstream source(fileName);
assure(source, fileName);
string word;
set<string> words;
while(source >> word)
words.insert(word);
copy(words.begin(), words.end(),
ostream_iterator<string>(cout,
"\n"));
cout << "Number of unique words:"
<< words.size() << endl;
}
int main(int argc, char* argv[]) {
if(argc > 1)
wordSet(argv[1]);
else
wordSet("WordSet.cpp");
} ///:~
The only substantive difference here is that the set holds strings
instead of integers. The words are pulled from a file, but the other operations
are similar to those in Intset.cpp. Not only does the output reveal that
duplicates have been ignored, but because of the way set is implemented,
the words are automatically sorted.
A set is an example of an associative container,
one of the three categories of containers provided by the Standard C++ library.
The containers and their categories are summarized in the following table:
Category
|
Containers
|
Sequence Containers
|
vector, list, deque
|
Container Adaptors
|
queue, stack, priority_queue
|
Associative Containers
|
set, map, multiset, multimap
|
These categories represent
different models that are used for different needs. The Sequence Containers
simply organize their elements linearly, and are the most fundamental type of
containers. For some problems, special properties need to be attached to these
sequences, and that s exactly what the Container Adaptors do they model
abstractions such as a queue or stack. The associative containers organize
their data based on keys, allowing for fast retrieval of that data.
All the containers in the standard library hold copies
of the objects you place in them, and expand their resources as needed, so your
objects must be copy-constructible (have an accessible copy constructor)
and assignable (have an accessible assignment operator). The key
difference between one container and another is the way the objects are stored
in memory and what operations are available to the user.
A vector, as you already know, is a linear sequence
that allows rapid random access to its elements. However, it s expensive to
insert an element in the middle of a co-located sequence like a vector,
just as it is with an array. A deque (double-ended-queue, pronounced deck ) also allows random access that s nearly as fast as vector, but it s
significantly faster when it needs to allocate new storage, and you can easily
add new elements at the front as well as the back of the sequence. A list is a doubly linked list, so it s expensive to move around randomly but cheap to
insert an element anywhere. Thus list, deque and vector
are similar in their basic functionality (they all hold linear sequences), but
different in the cost of their activities. For your first attempt at a program,
you could choose any one and experiment with the others only if you re tuning
for efficiency.
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( ), which inserts elements at the beginning of the sequence).
But how do you retrieve the elements stored in a sequence
container? 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.
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 thus take advantage of the
polymorphic behavior of the classes represented. Consider the classic shape
example where 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 using the 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
<< endl; }
~Circle() { cout << "~Circle <<
endl; }
};
class Triangle : public Shape {
public:
void draw() { cout << "Triangle::draw
<< endl; }
~Triangle() { cout << "~Triangle <<
endl; }
};
class Square : public Shape {
public:
void draw() { cout << "Square::draw
<< endl; }
~Square() { cout << "~Square <<
endl; }
};
int main() {
typedef std::vector<Shape*> Container;
typedef Container::iterator Iter;
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 an abstract base
class (because of the pure specifier =0) that defines the
interface for all types of Shapes. The derived classes override the virtual
function draw( ) to perform the appropriate operation. Now we d
like to create a bunch of different types of Shape objects, and the
natural place to store them is in an STL container. 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, random, 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 the iterator is not equal to the iterator produced
by end( ); don t use < or <=. The only tests
that work are != and ==, 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:
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. The easiest and safest way to
handle pointers in containers is to use smart pointers. It should be noted that
auto_ptr can t be used for this purpose, so you will need to look
outside of the C++ Standard Library for a suitable smart pointers.
You can change the type of container that this program uses
with two lines. Instead of including <vector>, you include <list>,
and in the first typedef you say:
typedef std::list<Shape*> Container;
instead of using a vector. Everything else goes
untouched. This is possible not because of an interface enforced by inheritance
(there is little inheritance in the STL), but because the interface is enforced
by a convention adopted by the designers of the STL, precisely so you could
perform this kind of interchange. Now you can easily switch between vector
and list or any other container that supports the same interface (both
syntactically and semantically) and see which one works fastest for your needs.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |