16.4 Generic programming
A goal of generic programming is to write code that is independent of data types. The STL goes further by providing a generic representation of algorithms.
) Why iterators?
Generic programming makes the function not only independent of the data type stored in the comtainer(done by template), but also be independent of data structure of the container. The latter is achieved by using iterators. To do this, each container class should define an iterator appropriate to the class. Next, each iterator will provide the required operators, such as * ++ and whatever the algorithm requires. Then, each container class should have a past-the-end marker, and have begin() and end() methods that return iterators to the first and last element in the container. After all this, you could use apply algorithms to different containers by using one code. So iterators are essential to generic programming.
) Kinds of Iterators
Different algorithms might have different requirements for iterators. The STL defines five kinds of iterators, and different function template would indicate which type of iterator it requires.
1 input iterators
An input iterator is one that a program could use to read values from a container.
It could be dereferenced, but only read not write. Supports ++ operator for traversing the container, one-way and no back up, twice not same order.
2 output iterators
An output iterator is one that a program could use to write values into a container.
It could be dereferenced, but only write not read. Supports ++, one-way and no back up, twice not same order.
3 forward iterators
A forward iterators could both read and write, one-way ++ and with fixed order.
4 bidirectional iterator
A bidirectional iterator has all the features that a forward iterator has, and supports -- and back up.
5 random access iterator
A random access iterator allows the iterator to have operators, letting it jump to any arbitrary element of a container. If a is a random access iterator, a+n would be n elements after a.
Why so many kinds of iterators? The idea is to write an algorithm using the iterator with the fewest requirements possible, allowing it to be used with the largest range of containers.
) Concepts, Refinements, and Models
STL literature uses the word concept to describe a set of requirements. The five types of operators are pure concepts.
Bidirectional iterator inherits the feature of a forward iterator, and adding its own features. In this way, we say that bidirectional iterator is a refinement of the forward iterator.
A particular implementation of a concept is termed a model. An ordinary pointer-to-int could be a model of a random access iterator.
The pointer satisfies all requirements of an iterator, thus generic functions could be applied to operators. For instance, you could use sort() with an array of double.
C++ defines a copy() function:
int cats[10] = {6, 7, 2, 9, 4, 11, 8, 7, 10, 5};
vector<int> dice[10];
copy(cats, cats+10, dice.begin());
You could use the out_iter in the iterator header file to output elements of container by using copy():
#include <iterator>
ostream_iterator<int, char> out_iter(cout, " ");
copy(dice,begin(), dice.end(), out_iter);
You could also use rbegin() and rend() functions with out_iter for a reverse output:
#include <iterator>
ostream_iterator<int, char> out_iter(cout, " ");
copy(dice,rbegin(), dice.rend(), out_iter);
In this way, dice.regin() and dice.rand() return a reverse iterator.
Here comes a program illustrating these features:
// copyit.cpp -- copy() and iterators
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
using namespace std;
int casts[10] = {6, 7, 2, 9, 4, 11, 8, 7, 10, 5};
vector<int> dice(10);
copy(casts, casts+10, dice.begin());
cout << "Let the dice be cast!
";
ostream_iterator<int, char> out_iter(cout, " ");
copy(dice.begin(), dice.end(), out_iter);
cout << endl;
cout << "Implicit use of reverse iterator.
";
copy(dice.rbegin(), dice.rend(), out_iter);
cout << endl;
cout << "Explicit use of reverse iterator.
";
vector<int>::reverse_iterator ri;
for (ri = dice.rbegin(); ri != dice.rend(); ++ri)
cout << *ri << ' ';
cout << endl;
return 0;
}
C++ also provides back_insert_iterator and insert_iterator to insert the range marked by first and second elements to the end or start of the third element.
// inserts.cpp -- copy() and insert iterations
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>
void output(const std::string & s) {std::cout << s << " ";}
int main()
{
using namespace std;
string s1[4] = {"fine", "fish", "fashion", "fate"};
string s2[2] = {"busy", "bats"};
string s3[2] = {"silly", "singers"};
vector<string> words(4);
copy(s1, s1+4, words.begin());
for_each(words.begin(), words.end(), output);
cout << endl;
copy(s2, s2+2, back_insert_iterator<vector<string> >(words));
for_each(words.begin(), words.end(), output);
cout << endl;
copy(s3, s3+2, insert_iterator<vector<string> >(words, words.begin()));
for_each(words.begin(), words.end(), output);
cout << endl;
return 0;
}
) Kinds of Containers
A container is an object that stores other objects, which are all of a single type. When the container expires, the data in the container also expires. The type stored in a container should be copy constructable and assignable.
A container provides basic properties:(X container, T data type within it)
1 X::iterator an iterator type pointint to T
2 X::value_type return T
3 X u creates an empty container u
4 X u(a) copy constructor
5 r = a assignment
6 (&a)->~X() applies destructor to every element of a container
7 a.begin() a.end() return iterator to the begin and past-the-end
8 a.size() return the size
9 a.swap(b) Swap contents of a and b
10 a == b a != b comparison between a and b
) Time complexity
compile time : action done when compiling.
constant time : action's time doesn't depend on the size of container
linear time : action's time in proportion to the size of container
) Sequences
Sequences guarantee that elements are arranged in a definite order that doesn't change from one cycle of iteration to the next. It also requires that its elements be arranged in strict linear order. This feature allows the insert() and erase() functions. Let's look closer at six sequence container types:
1 vector
A vector container is in addition a model of the reversible container concept. It adds rbegin() and rend() to return iterators at begin and end for reversed sequence. The following code displays dice in order and reversed order:
for_each(dice.begin(), dice.end(), Show);
cout << endl;
for_each(dice.rbegin(), dice.rend(), Show);
cout << endl;
2 deque
The deque template class represents a double-ended queue, often called deque(pronounced deck). Its main difference with vector is that adding and removing contents at the start of a deque is constant time rather than linear time.
3 list
The list template class represents a doubly linked list. The critical difference between vector and list is that list provide constant-time insert and remove at any location in the list. list does not support array notation and random access. Inserting and removing doesn't alter the location of data, it only changes the link information.
Functions defined for list:
void merge(list<T, Alloc> & x)merge x with the invoking list, sorted list in the invoking one and left x empty. Linear-time complexityvoid remove(const T & val)remove all instances of val from the list. Linear-time complexityvoid sort()sorting the elements by <. nlogn time complexityvoid splice(iterator pos, list<T, Alloc> x)insert the contents of x to where the pos points to. Constant-time complexityvoid unique()collapses each consecutive group of equal elements to a single element. Linear-time complexity
Here comes code that uses these functions:
// inserts.cpp -- copy() and insert iterations
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>
void output(const std::string & s) {std::cout << s << " ";}
int main()
{
using namespace std;
string s1[4] = {"fine", "fish", "fashion", "fate"};
string s2[2] = {"busy", "bats"};
string s3[2] = {"silly", "singers"};
vector<string> words(4);
copy(s1, s1+4, words.begin());
for_each(words.begin(), words.end(), output);
cout << endl;
copy(s2, s2+2, back_insert_iterator<vector<string> >(words));
for_each(words.begin(), words.end(), output);
cout << endl;
copy(s3, s3+2, insert_iterator<vector<string> >(words, words.begin()));
for_each(words.begin(), words.end(), output);
cout << endl;
return 0;
}
4 queue
Declared in queue header file. You could only add an element to the rear of a queue, remove an element from the front of a queue, view the values of the front and rear, check number of elements, test whether it is empty.
With priority_queue, the largest item gets moved to the front of the queue.
5 stack
Only allowed to add or remove on the top, view the top content, check the number of elements and test whether it is empty.
6 array
Discussed in Chapter 4, with fixed size.
) Associative Containers
An associative container associates a value with a key and uses the key to find the value. If X is an associative container, X::value_type indicates its value type while X::key_type indicates its type of the key. Associative containers use tree data structure and provides faster search times.
The STL provides set, multiset, map, multimap. For set, the type of key is the same as the type of value, and one key only has one corresponding value. For multiset, same type with key and value but one key could correspond to multiple values. For map, the type of key is different from the type of value, and one key corresponds to one value. For multimap, the type of key is different from that of the value, but one key corresponds to multiple values.
) A set Example
You could initialize a set in this way:
set<string> A;
The elements in a set are unique. You could initialize a set by providing the first and last iterator of an array:
string s1[6] = {"a", "b", "c", "d", "e", "a"};
set<string> A(s1, s1+6);
ostream_iterator<string, char> out(cout, " ");
copy(A.begin(), A.end(), out);
The output of this code fragment, which is a, b, c, d, e, illustrates that elements are unique, as well as they are sorted.
C++ provides functions for union, intersection and difference, as long as the container is sorted, which set satisfies.
The set_union function accepts five arguments, first two mark a range, next two marks another range, the last one is an iterator that marks where the union goes to. For example, if you would like to store the union of A and B in a set C, you code like this:
set_union(A.begin(), A.end(), B.begin(), B.end(), insert_iterator<set<string> >(C, C.begin()));
set_intersection and set_difference functions have similar interface.
Two other useful functions are lower_bound() and upper_bound(), which accepts a key-type value, and returns an iterator pointing to the key that is not less or not more than the input argument, marking a range if both functions used together. Apart from that, when you are using insert() for a set, you don't need to specify the location of insertion simply because they are sorted by default.
Next comes a program illustrating the features of set:
// setops.cpp -- some set operations
#include <string>
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
int main()
{
using namespace std;
const int N = 6;
string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};
string s2[N] = {"metal", "any", "food", "elegant", "deliver", "for"};
set<string> A(s1, s1+N);
set<string> B(s2, s2+N);
ostream_iterator<string, char> out(cout, " ");
cout << "Set A: ";
copy(A.begin(), A.end(), out);
cout << endl;
cout << "Set B: ";
copy(B.begin(), B.end(), out);
cout << endl;
cout << "Union of A and B:
";
set_union(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
cout << "Intersection of A and B:
";
set_intersection(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
cout << "Difference of A and B:
";
set_difference(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
set<string> C;
cout << "Set C:
";
set_union(A.begin(), A.end(), B.begin(), B.end(), insert_iterator<set<string> >(C, C.begin()));
copy(C.begin(), C.end(), out);
cout << endl;
string s3("grungy");
C.insert(s3);
cout << "Set C after insertion:
";
copy(C.begin(), C.end(), out);
cout << endl;
cout << "Showing a range:
";
copy(C.lower_bound("ghost"), C.upper_bound("spook"), out);
cout << endl;
return 0;
}
) A multimap Example
You could declare a multimap given its key type and value type:
multimap<int, string> codes;
The actual value type combines the key type and the data type into a single pair. To do this, STL provides pair<class T, class U> templates. The value type is pair<const keytype, datatype>.
You could create a pair and insert it into a multimap object:
pair<const int, string> item(213, "Los Angeles");
codes.insert(pair);
Items are sorted by key, so there's no need to specify the location of insertion.
You can access the components of a pair by using the first and second members:
cout << item.first << " " << item.last << endl;
count() member function takes a key and returns the number of items with that key. The upper_bound() and lower_bound() takes a key and work as they are in set. The equal_range() takes a key and return iterators representing the range matching the key, by returning a pair of iterators, with first as begin and second as end. You could also use auto to simplify the type of the return value of equal_range()
Here comes an example illustrating these features:
// multmap.cpp -- use a multmap
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
typedef int KeyType;
typedef std::pair<const KeyType, std::string> Pair;
typedef std::multimap<KeyType, std::string> MapCode;
int main()
{
using namespace std;
MapCode codes;
codes.insert(Pair(415, "San Francisco"));
codes.insert(Pair(510, "Oakland"));
codes.insert(Pair(718, "Brooklyn"));
codes.insert(Pair(718, "Staten Island"));
codes.insert(Pair(415, "San Rafael"));
codes.insert(Pair(510, "Berkeley"));
cout << "Number of cities with the area code 415: " << codes.count(415) << endl;
cout << "Number of cities with the area code 718: " << codes.count(718) << endl;
cout << "Number of cities with the area code 510: " << codes.count(510) << endl;
cout << "Area Code City
";
MapCode::iterator it;
for (it = codes.begin(); it != codes.end(); ++it)
{
cout << " " << (*it).first << " " << (*it).second << endl;
}
pair<MapCode::iterator, MapCode::iterator> range = codes.equal_range(718);
cout << "Cities with area code 718:
";
for (it = range.first; it != range.second; it++)
cout << (*it).second << endl;
return 0;
}
16.5 Function Objects(functors)
A functor is any object that can be used with () in the manner of a function. This includes normal function names, pointers to functions, and class objects for which the () operator is overloaded. For example, you could implement a linear functor:
class Linear
{
private:
double slope;
double y0;
public:
Linear(double s1 = 1, double y = 0) : slope(s1), y0(y) {}
double operator()(double x) {return y0 + x * slope;}
};
This allows you to use Linear objects with ():
Linear f1;
cout << f1(2); // 2
For the for_each(), its third argument could be a functor
) Functor Concepts
A generator is a functor that could be called with no arguments.
A unary function is a functor that could be called with one argument.
A binary function is a functor that could be called with two arguments.
Besides these concepts, there are also refinements:
A unary function that returns a bool value is a predicate.
A binary function that returns a bool value is a binary predicate.
For example, in the previous use of sort(), a binary predicate is implemented as the third argument.
The list argument provides a function remove_if() which takes a predicate and remove the elements which makes the predicate return true. The following example would wipe out all elements which is greater than 100:
bool tooBig(int n) {return n > 100;}
list<int> scores;
...
scores.remove_if(tooBig);
Here comes code illustrating this feature:
//functor.cpp -- using a functor
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
template<class T>
class TooBig
{
private:
T cutoff;
public:
TooBig(const T & t) : cutoff(t) {}
bool operator()(const T & b) { return b > cutoff;}
};
void outint(int n) { std::cout << n << " ";}
int main()
{
using std::list;
using std::cout;
using std::endl;
TooBig<int> f100(100); // use the template to create a TooBig for int and initilaize an object f100 to 100
int vals[10] = {50, 100, 90, 180, 50, 210, 415, 88, 188, 201};
list<int> yadayada(vals, vals+10);
list<int> etcetera(vals, vals+10);
cout << "Original lists:
";
for_each(yadayada.begin(), yadayada.end(), outint);
cout << endl;
for_each(etcetera.begin(), etcetera.end(), outint);
cout << endl;
yadayada.remove_if(f100);
etcetera.remove_if(TooBig<int> (200));
cout << "Trimmed lists:
";
for_each(yadayada.begin(), yadayada.end(), outint);
cout << endl;
for_each(etcetera.begin(), etcetera.end(), outint);
cout << endl;
return 0;
}
In this code, one functor is declared by TooBig<int> f100(100);, and another is declared as an anonymous object in etcetera.remove_if(TooBig<int> (200)).
) Predefined Functions
Consider the transform() function.
1 The first version takes 4 arguments, first two marking a range, third marks where the data goes, the fourth is a functor that applies to each element in the range:
const int LIM = 5;
double arr1[LIM] = {36, 39, 42, 45, 48};
vector<double> gr8(arr1, arr1+LIM);
ostream_iterator<double, char> out(cout, " ");
transform(gr8.begin(), gr8.end(), out, sqrt);
2 The second version takes 5 arguments in total. The functor in this turn is a binary predicate, so the version's first and second argument mark a range, the third marks the start of range of another operand, the fourth marks where the elements go, and the five is the functor.
double add(double x, double y) {return x + y;}
...
transform(gr8.begin(), gr8.end(), m8.begin(), out, mean);
But you have to provide a separate function for each type. C++ has a functional header defines several template class function objects, including the plus<>(). So, if you use this, you could change the previous code into:
transform(gr8.begin(), gr8.end(), m8.begin(), out, plus<double>());
The STL provides functor equivalents for built-in arithmetic, relational and logical operators. They could be used with built-in types or any user defines types that overloades the corresponding operator:
+ - * / % == != > < >= <= && || ! these operators share same meaning as they are originally in C++. In addition, - has two meanings, both minus and negate(turn positive to negative), whose functor equivalents are plus minus multiplies divides modulus equal_to not_equal_to greater less greater_equal less_equal logical_and logical_or logical_not and negate.
) Adaptable functors and function adapters
The predefined functors listed above are all adaptable. They carry typedef members identifying its argument type and return type as result_type first_argument_type and second_argument_type. STL provides adapter classes to use these facilities. Suppose f2() is a two-argument function, you can use binder1st and binder2nd to turn it into one-argument function:
binder1st(f2, val) f1;
In this way, you make a single-argument function f1() which takes val as the first argument of f2(). This is only possible if f2() is adaptable function.
In this way, you could multiply each element by 2.5:
transform(gr8.begin(), gr8.end(), out, bind1st(multiplies<double>(), 2.5));
Here comes code illustrating the adaptable concept and features:
// funadap.cpp -- using function adapters
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
void Show(double);
const int LIM = 6;
int main()
{
using namespace std;
double arr1[LIM] = {28, 29, 30, 35, 38, 59};
double arr2[LIM] = {63, 64, 69, 75, 80, 99};
vector<double> gr8(arr1, arr1+LIM);
vector<double> m8(arr2, arr2+LIM);
cout.setf(ios_base::fixed);
cout.precision(1);
cout << "gr8: ";
for_each(gr8.begin(), gr8.end(), Show);
cout << endl;
cout << "m8: ";
for_each(m8.begin(), m8.end(), Show);
cout << endl;
vector<double> sum(LIM);
transform(gr8.begin(), gr8.end(), m8.begin(), sum.begin(), plus<double>());
cout << "sum: ";
for_each(sum.begin(), sum.end(), Show);
cout << endl;
vector<double> prod(LIM);
transform(gr8.begin(), gr8.end(), prod.begin(), bind1st(multiplies<double>(), 2.5));
cout << "prod: ";
for_each(prod.begin(), prod.end(), Show);
cout << endl;
return 0;
}
void Show(double v)
{
std::cout.width(6);
std::cout << v << ' ';
}
16.7 Algorithms
There are two main generic components to the algorithm function designs. First, it uses templates to provide generic types. Second, they use iterators to provide a generic representation of accessing data in a container.
) Algorithm groups
C++ categorizes algorithms into four groups:
1 nonmodifying sequence operations : algorithms that operate on each element in a range but without change of container contents.
2 mutating sequence : algorithms that operate on each element in a range but change the contents of a container
3 sorting and related operations : serveral sorting functions
4 numeric operations : focus on numeric data, such as sum, inner product, partial sums, adjacent differences and so on.
) General Properties of Algorithms
One way of classifying algorithms is on the basis of where the result goes. In-place algorithms leave their result in the same location as the input data, while copying algorithm leave their result in another place specified by an iterator.
Some algorithms come in both in-place and copying versions, STL convention is to append _copy after copying versions. Another common variation is that some functions have a version that only performs certain action when a condition is true, so you typically append _if after those functions.
) The STL and the string Class
A permutation is a rearrangement of the order of elements in a container. If you start from the beginning(alphabetically sorted), and use next_permutation() to transform the string to the next permutation, then you could get all permutations of a certain string. Here comes code illustrating this feature:
// strgstl.cpp -- applying the STL to a string
#include <iostream>
#include <string>
#include <algorithm>
int main()
{
using namespace std;
string letters;
cout << "Enter the letter grouping (quit to quit): ";
while (cin >> letters && letters != "quit")
{
cout << "Permutations of " << letters << endl;
sort(letters.begin(), letters.end());
cout << letters << endl;
while (next_permutation(letters.begin(), letters.end()))
cout << letters << endl;
cout << "Enter next sequence (quit to quit): ";
}
cout << "Done.
";
return 0;
}
) Functions versus Container Methods
Better choose container methods, because they are more specialized. For example, you might choose between remove() methods defined for list and a function remove:
la.remove(4);
This removes all instances of 4 and resizes the list. But the following won't resize:
remove(la.begin(), la.end(), 4);
However, the remove() returns the past-the-end value, and you can use erase() a the value to resize the list. Now comes code showing this feature:
// listrmv.cpp -- applying the STL to a string
#include <iostream>
#include <list>
#include <algorithm>
void Show(int);
const int LIM = 10;
int main()
{
using namespace std;
int ar[LIM] = {4, 5, 4, 2, 2, 3, 4, 8, 1, 4};
list<int> la(ar, ar+LIM);
list<int> lb(la);
cout << "Original list contents:
";
for_each(la.begin(), la.end(), Show);
cout << endl;
la.remove(4);
cout << "After using the remove() method:
";
cout << "la: ";
for_each(la.begin(), la.end(), Show);
cout << endl;
list<int>::iterator last;
last = remove(lb.begin(), lb.end(), 4);
cout << "After using the remove() function:
";
cout << "lb: ";
for_each(lb.begin(), lb.end(), Show);
cout << endl;
lb.erase(last, lb.end());
cout << "After using the erase() method:
";
cout << "lb: ";
for_each(lb.begin(), lb.end(), Show);
cout << endl;
return 0;
}
void Show(int v)
{
std::cout << v << " ";
}
Functions are also more general than container methods, meaning that you could apply those functions to different types.
) Using the STL
Components of STL are designed to be used together. Here comes code illustrating the cooperation of STL:
// usealgo.cpp -- using several STL elements
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#include <cctype>
using namespace std;
char toLower(char ch) {return tolower(ch);}
string & ToLower(string & st);
void display(const string & s);
int main()
{
vector<string> words;
cout << "Enter words (enter quit to quit):
";
string input;
while (cin >> input && input != "quit")
words.push_back(input);
cout << "You entered the following words:
";
for_each(words.begin(), words.end(), display);
cout << endl;
set<string> wordset;
transform(words.begin(), words.end(), insert_iterator<set<string> > (wordset, wordset.begin()), ToLower);
cout << "
Alphabetic list of words:
";
for_each(wordset.begin(), wordset.end(), display);
cout << endl;
map<string, int> wordmap;
set<string>::iterator si;
for (si = wordset.begin(); si != wordset.end(); ++si)
wordmap[*si] = count(words.begin(), words.end(), *si);
cout << "
Word frequency:
";
for (si = wordset.begin(); si != wordset.end(); si++)
cout << *si << ": " << wordmap[*si] << endl;
return 0;
}
string & ToLower(string & st)
{
transform(st.begin(), st.end(), st.begin(), toLower);
return st;
}
void display(const string & s)
{
cout << s << " ";
}