ANSI/ISO Standard C++ includes an extensive library of templated functions and classes called the Standard Template Library (STL). This library and the style of programming it embodies represent a recent and powerful new paradigm in programming:generic programming. The keys to using the STL effectively are iterators, function objects, and an understanding of the implicit constraints a templated function/class definition places on the types you use to instantiate it. These are precisely what we've developed in the past several lectures!
Iterators in the STL are mildly different from the iterators we've used in our List class. First of all, we used Iterator with an upper-case "I", whereas the STL uses iterator with a lower-case. That's the easy difference, the other differences aren't much more substantial. They are:
| Purpose | Our iterators | STL's iterators |
get the value referred to by an iterator itr |
itr.get() | (*itr) |
move iterator to point to the next iterator itr |
itr.next() | ++itr (or itr++) |
check iterator itr1 and itr2 for equality |
!itr1.equal(itr2) | itr1 != itr2 |
Other than that, iterators in the STL are exactly like our iterators. Function objects in the STL are exactly like what we've already discussed about function objects. So, you're ready to go!
Containers are templated classes for storing objects - like list, queue, or stack. STL has many container classes. When you instantiate an STL container with a custom class, that class must
Now, as we've dicussed, the copy constructor and assignment operator provided by default by the compiler is usually good enough for what we need, so usually these requirements are easy to meet. However, when your class involves dynamically allocated memory, this is not the case! Then you have to define your own copy constructor and assignment operator.
Some containers also require that you be able to compare two objects in the collection, i.e. decide which comes first in a given ordering. These containers, the associative containers, require either that the operator< be overloaded for the type you're using, or that you explicitly provide a function object to do the comparison. Whether operator< or a function object provides this ordering criterion, the criterion needs to define a strict weak ordering. This means that if before is your function object for comparing two elements of the collection, then you need
For any container you always have a member function size() that tells you how many elements are stored in the container, and empty() which returns true if the container has no elements in it and false otherwise.
The STL has queue, stack, and list container classes already defined. Their syntax is a little different than ours, but not a whole bunch. In this section we'll talk about the STL set class, which is an associative container for storing sets of objects - meaning no duplicates! Sets have a member function insert(x) that inserts element x into the set, and erase(p), where p is an iterator for the set, which removes the element reference by iterator pfrom the collection. The following program uses sets to read in strings from the user and print them back out again without duplicates. Note: you must include set to use STL set containers!
ex2.cpp
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
// Read strings & store in a set
cout << "Enter strings terminated with \"end\": ";
set<string> S;
string w;
while(cin >> w && w != "end")
S.insert(w);
// Print out strings in the set
cout << "What you entered (without duplicates) was: ";
for(set<string>::iterator itr = S.begin(); itr != S.end(); ++itr)
cout << (*itr) << ' ';
cout << endl;
return 0;
}
$ g++ -o go ex2.cpp $ go Enter strings terminated with "end": Hello my name is Name is my name end What you entered (without duplicates) was: Hello Name is my name $
A set is an associative container, and it needs some ordering criterion in order to determine whether it has duplicates or not (you may also have noticed that it actually keeps elements in sorted order using the criterion). By default operator< gets used, and two elements a and b are considered equal if a < b and b < a are both false. If we want a different ordering criterion - for example if we want capitalization to be ignored so that "name" and "Name" are considered the same - we need to provide a function object that does the ordering comparison the way we want it. This function object will be passed to the constructor of the set. Also, the type of the function object will have to be given when instantiating set so that instead ofset<string> we have set<string,CompAlphabetical>.
StringComp.h
#include <string>
using namespace std;
class CompAlphabetical {
void makelower(string &s) {
for(int i = 0; i < s.length(); i++)
if ('A' <= s[i] && s[i] <= 'Z')
s[i] = s[i] - 'A' + 'a';
}
public:
bool operator()(string a, string b) {
makelower(a);
makelower(b);
return a < b;
}
};
ex2b.cpp
#include <iostream>
#include <string>
#include <set>
#include "StringComp.h" // defines CompAlphabetical
using namespace std;
int main() {
// Read strings & store in a set (ignoring case)
cout << "Enter strings terminated with \"end\": ";
CompAlphabetical Cmp;
set<string,CompAlphabetical> S(Cmp);
string w;
while(cin >> w && w != "end")
S.insert(w);
// Print out strings in the set
cout << "What you entered (without duplicates) was: ";
for(set<string,CompAlphabetical>::iterator itr = S.begin(); itr != S.end(); ++itr)
cout << (*itr) << ' ';
cout << endl;
return 0;
}
compiling and running
$ g++ -o go ex2b.cpp $ go Enter strings terminated with "end": Hello my name is Name is my name end What you entered (without duplicates) was: Hello is my name $
Sophisticated C++ programmer types almost never use arrays anymore: we use vectors! The STL vector container is pretty much an array without headaches. First, you don't have to worry about new and delete with vectors - that's all done automatically. Second, a vector remembers its size. Third, pass-by-value with vectors really does result in a copy of the entire vector, unlike arrays for which we don't have a true pass-by-value concept. Most importantly, however, vectors have a member function push_back(x) that allows you to add a new element to the back of the vector without having to worry about exceeding the vector's bounds!. Note: You must include the vector library in your program if you want to use vectors.
A vector can be given a size when it's created, like an array. To create a vector A of 10 objects of type Point we'd do this:
vector<Point> A(10);
The elements of this vector can be accessed by subscript just like an array. So we could read in 10 values like this:
vector<Point> A(10);
for(int i = 0; i < 10; i++)
cin >> A[i];
However, if you don't specify a size for the vector you can simply tack new values onto the end of it with push_back.
vector<Point> A;
Point p;
for(int i = 0; i < 10; i++) {
cin >> p;
A.push_back(p);
}
cout << "read " << A.size() << " elements!" << endl;
The following program reads an arbitrary number of doubles from the user and prints out the average and standard deviation of the numbers entered. It uses, of course, vectors!
ex4.cpp
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
// Read doubles into vector V
vector<double> V;
double x;
while(cin >> x)
V.push_back(x);
// Compute the average
double sum = 0;
for(int i = 0; i < V.size(); i++)
sum += V[i];
double ave = sum/V.size();
// Compute standard deviation
sum = 0;
for(int i = 0; i < V.size(); i++)
sum += (V[i] - ave)*(V[i] - ave);
double stdev = sqrt(sum/(V.size() - 1));
// Print results
cout << "average = " << ave << endl
<< "stddev = " << stdev << endl;
return 0;
}
Compiling and running
$ go 1 2 3 4 5 6 7 8 9 ; average = 5 stddev = 2.73861 $ go 4 4 4 5 5 5 6 6 6 ; average = 5 stddev = 0.866025 $
Now, because vector is an STL container, it has iterators. So we could use iterators rather than subscripting by index. The above program rewritten with iterators looks like this:
ex4b.cpp
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
// Read doubles into vector V
vector<double> V;
double x;
while(cin >> x)
V.push_back(x);
// Compute the average
double sum = 0;
for(vector<double>::iterator p = V.begin(); p != V.end(); ++p)
sum += (*p);
double ave = sum/V.size();
// Compute standard deviation
sum = 0;
for(vector<double>::iterator p = V.begin(); p != V.end(); ++p)
sum += ((*p) - ave)*((*p) - ave);
double stdev = sqrt(sum/(V.size() - 1));
// Print results
cout << "average = " << ave << endl
<< "stddev = " << stdev << endl;
return 0;
}
In addition to containers, the STL contains a number of templated functions. Most of these are written in terms of iterators, so they can be used with sets or with vectors or with any kind of STL container. You must include the algorithm library to use these functions. Let's take a look at one that's used often: sorting.
The STL has a sort function that can be used with any container that has "random access iterators". For us, that means more or less that it can be used with vectors. The function sort takes either two or three arguments. The first argument is an iterator to the first element of range it's supposed to sort. The second argument is an iterator to the position immediately after the last element or the range it's supposed to sort. Sorting is done with operator<, unless a third argument is given, which must be a function object which can be used in place of operator< to do comparisons. The following is an example of a program that computes the median with the help of the STL sort function.
ex5.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// Read doubles into vector V
vector<double> V;
double x;
while(cin >> x)
V.push_back(x);
// Sort and compute median
sort(V.begin(),V.end());
double median;
if (V.size() % 2 == 1)
median = V[V.size()/2];
else
median = (V[V.size()/2 - 1] + V[V.size()/2])/2;
// Print results
cout << "median = " << median << endl;
return 0;
}
Compiling and running
$ g++ -o go ex5.cpp $ go 5 2 100 7 4 120 11 8 3 ; median = 7 $
Now, imagine we want to do the exact same thing, except we want to order our numbers by smallest to largest absolute value rather than simply smallest to largest. We can, once again, use sort. However, now we have to pass a function object as a third argument to sort. The function argument will have to compare by absolute value.
ex6.cpp
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
class CmpAbs {
public:
bool operator()(double x, double y) {
return fabs(x) < fabs(y);
}
};
int main() {
// Read doubles into vector V
vector<double> V;
double x;
while(cin >> x)
V.push_back(x);
// Sort and compute median
CmpAbs C;
sort(V.begin(),V.end(),C);
double median;
if (V.size() % 2 == 1)
median = V[V.size()/2];
else
median = (V[V.size()/2 - 1] + V[V.size()/2])/2;
// Print results
cout << "median = " << median << endl;
return 0;
}
Compiling and running
$ g++ -o go ex6.cpp $ go -5 2 -100 -7 4 120 11 -8 3 ; median = -7 $