Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com
Answertopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

  




 

 

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

A first look

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:

(*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. 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.[101]

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

 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire