Thought soup!: Standard Template Library (STL): An Introduction Part 3

In the previous post STL : An introduction Part 2 :

Containers and their types and gave a little brush upon vectors too. This post is a continuation of the previous post and if you have not read it, I highly recommend you to take a look at it.

In this post I will be walking you through

Iterators : types and some examples.

Algorithm : some basic algorithms like sort(), insert() using vector object.

Functors( function objects) : an introduction

String class :

So lets get started with iterators, shall we!

2.4 Iterator

An iterator behaves like a generic pointer, which can be used to reference (point-to) individual element of a generic container; and transverse through elements of a container. The purpose of iterator is to make transversing (iterating) of containers independent on the type of the containers (e.g., vector<int>, queue<double>, stack<string>). With iterator, you can apply generic algorithm (such as searching, sorting and comparison) to the container, independent of types. Without iterator, you may need to write different codes for the same algorithm for different containers (e.g., different codes for searching anvector<int>, vector<double>, stack<string>).

Iterator abstracts pointer and works like pointer. It could actually be implemented as pointer, but that is totally up to the compiler. Iterator shall meet the following requirements:

The dereferencing operator * shall be defined. That is, if iter is an iterator, *iter shall be pointing to an element of the container.
The assignment operator = shall be defined. That is, if iter1 and iter2 are iterators, iter1 = iter2 shall assign iter2 to iter1.
The comparison operators == and != shall be defined. That is, if iter1 and iter2 are iterators, we can use iter1 == iter2 and iter1 != iter2 to compare them for equality. If iter1 == iter2 is true, then they shall be pointing at the same element, i.e., *iter1 == *iter2.
The increment operator ++ shall be defined. That is, if iter is an iterator, ++iter and iter++ move the iterator to point to the next element. The program shall be able to iterate through all the elements via ++iter (or iter++) operations.

In addition,

For linearly-ordered container, the + (and +=) operator shall be defined. That is, if iter is an iterator, iter+n points to the next n-th element in the linear order.
For iterator that can transverse backward, the decrement operator -- shall be defined. That is, if iter is an operator, --iter and iter-- move the iterator to point to the next element in the reverse order (or previous element in the forward order).

All STL container provides two member functions: begin() and end() that return the iterators pointing to the first element and the pass-the-end element respectively. Hence, you can use the following code to transverse all the elements in the container:

// Assume that c is a containeriter_type iter;
for (iter = c.begin(); iter != c.end(); ++iter) {
   // Use *iter to reference each element
   ......
}

Take note that the above code work for all STL containers with any type specialization. The type of iterator (iter_type) depends on the container. In STL, you can get the iterator type viacontainer<T>::iterator.

By convention, if a range of elements is specified by two iterators: first and last, then first is included and last is excluded, denoted as [first, last).

In C++11, you can use the auto to derive the type of iterator automatically, as follows:

for (auto iter = c.begin(); iter != c.end(); ++iter) {
   // Use *iter to reference each element
   ......
}

In C++11, you can also use the new for-each loop to iterate thru all the element of a container:

for (auto item : container) {
   // Use item to reference each element
   ......
}

Types of Iterators

STL defines the following types of iterators with different requirements. All iterators shall define * (dereferencing), = (assignment) and ==, != (equality comparison) operators.

Input Iterator: can be used to read element from a container (may not support write operation). It defines ++ (prefix and postfix) to transverse thru all the elements of a container in a single pass - but no guarantee that different passes will transverse through the elements in the same order. Input iterator can be used for single-pass, read-only algorithms.
Output Iterator: Similar to input iterator, but the dereferencing operator support write operation (may not support read operation). Output iterator can be used for single-pass, write-only algorithms.
Forward Iterator: the ++ operator transverses thru the elements, and always in the same order (in different passes). It support both read and write operations.
Bidirectional Iterator: a forward iterator with added support for -- (decrement, prefix and postfix) to transverse in the opposite direction.
Random-access (Direct-access) Iterator: support +, -, +=, -+ (e.g., iter+n, iter-n) to directly access any element in constant time.

In STL, each container class (such as vector) has a class scope typedef called iterator, which specifies the type of the iterator. For example, vector<int>'s iterator is called vector<int>::iterator;stack<string> is stack<string>::iterator.

STL Pre-defined Iterators (in Header <iterator>)

STL pre-defined many iterators (in header <iterator>): iterator, reverse_iterator, insert_iterator, front_insert_iterator, back_insert_iterator, istream_iterator, ostream_iterator,istreambuf_iterator, and ostreambuf_iterator.

Example: istream_iterator and ostream_iterator

/* Testing istream_iterator and ostream_iterator (TestIOIterator.cpp) */
#include <iostream>
#include <string>
#include <iterator>
using namespace std;
 
int main() {
   // Construct ostream_iterators to write int and string to cout
   ostream_iterator<int> iterOut(cout);
   ostream_iterator<string> iterOutStr(cout);
 
   *iterOutStr = "Enter two integers: ";
 
   // Construct an istream_iterator<int> to read int from cin
   istream_iterator<int> iterIn(cin);
   int number1 = *iterIn;  // dereference to get the value
   ++iterIn;               // next int in cin
   int number2 = *iterIn;
 
   *iterOutStr = "You have entered ";
   *iterOut = number1;
   *iterOutStr = " and ";
   *iterOut = number2;
}

Example: copy() to ostream_iterator

The STL algorithm copy() can be used to copy elements from one container to another container. copy() is a template function defined as follows:

template <class InputIterator, class OutputIterator>
outputIterator copy (InputIterator first, InputIterator last, OutputIterator result);

It copies the elements in the range of [first,last) to the output range beginning at result. As mentioned, InputIterator shall provide read access and OutputIterator write access. Input and output could be the same container, but result cannot be in [first,last). For example,

const int SIZE = 10;
int array[SIZE] = {11, 55, 44, 33, 88, 99, 11, 22, 66, 77};
vector<int> v(array, array + SIZE);  // Copy constructor
 
// Using copy() instead of copy constructor
vector<int> v2(SIZE);
copy(array, array + SIZE, v2.begin());

You could also copy to an output stream such as cout, i.e., print, by using the STL's pre-defined ostream_iterator (in header <iterator>), which is a class template defined as follows:

template <class T, class charT = char, class traits = char_traits<charT> >
class ostream_iterator;
   // T is the data type, charT is the character type (such as char or wchar_t)
 
// Example
ostream_iterator<int, char> out (cout, " ");
   // data type (T) is int, character type (charT) is char.
   // output stream is cout, delimiter is a space (" ")

In the following example, we used copy() to copy one container into output stream, via a ostream_iterator. This code replaces the print() user-defined function and seems to be more compact.

/*
 *  Testing ostream_iterator (TestOstreamIterator.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
 
int main() {
   const int SIZE = 10;
   int array[SIZE] = {11, 55, 44, 33, 88, 99, 11, 22, 66, 77};
   vector<int> v(array, array + SIZE);
 
   // Construct an ostream_iterator called out
   ostream_iterator<int, char> out (cout, " ");
   // Copy to ostream, via ostream_iterator - replacing the print()
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   // Copy to ostream in reverse order
   copy(v.rbegin(), v.rend(), out);
   cout << endl;
 
   // Use an anonymous ostream_iterator
   copy(v.begin(), v.end(), ostream_iterator<int, char>(cout, " "));
   cout << endl;
   return 0;
}

Example: insert_iterator

The copy() with a OutputIterator (as in the above example) override the existing data in the output range. Instead you could use one of the insert_iterator to insert elements without overriding existing data. A front_insert_iterator inserts from the front; a back_insert_iterator inserts at the end; an insert_iterator inserts before a given location.

vector<int> v(10);
back_insert_iterator<vector<int> > back_iter (v);
    // Construct a back_insert_iterator for v
    // The template type argument is the container
    // The constructor argument is the name of container
    // Need to write "> >" instead of ">>"
 
insert_iterator<vector<int> > insert_iter (v, v.begin());
    // The constructor's 2nd argument specifies insert before this location

/*
 *  Testing insert_iterator (TestInsertIterator.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
 
int main() {
   int a1[5] = {11, 55, 44, 33, 88};
   vector<int> v(a1, a1+5);
   ostream_iterator<int, char> out (cout, " ");  // for printing
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   // Construct a back_insert_iterator to insert at the end
   back_insert_iterator<vector<int> > back (v);
   int a2[3] = {91, 92, 93};
   copy(a2, a2+3, back);
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   // Use an anonymous insert_iterator to insert at the front
   int a3[3] = {81, 82, 83};
   copy(a3, a3+3, insert_iterator<vector<int> >(v, v.begin()));
   copy(v.begin(), v.end(), out);
   cout << endl;
   return 0;
}

2.5 Algorithm

C++ provides a set of generic algorithm for STD in header <algorithm>, which includes:

Searching: find(), count().
Sorting: sort(), partial_sort(), merge().
Generation, mutation and deletion:
Numeric and relational:

The algorithms operate on elements of STL container only indirectly through the iterator.

The generic algorithms are non-member functions that are applicable to all STL containers. It accepts a pair of iterators, denoted as first and last, that mark the range of operation as [first,last)(including first, but excluding last). For example,

sort(aVector.begin(), aVector.end());  // Sort the entire vector
sort(aVector.begin(), aVector.begin + aVector.size()/2);  // Sort first half

Let's begin with some examples.

Example 1: sort(), reverse(), random_shuffle() and find() on Iterators [first,last)

/*
 *  Testing algorithms (TestAlgorithm.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void print(vector<int> & v);
 
int main() {
   const int SIZE = 10;
   int array[SIZE] = {11, 55, 44, 33, 88, 99, 11, 22, 66, 77};
   vector<int> v(array, array + SIZE);
   print(v);
 
   // Sort
   sort(v.begin(), v.end());  // entire container [begin(),end())
   print(v);
 
   // Reverse
   reverse(v.begin(), v.begin() + v.size()/2);  // First half
   print(v);
 
   // Random Shuffle
   random_shuffle(v.begin() + 1, v.end() - 1);  // exclude first and last elements
   print(v);
 
   // Search
   int searchFor = 55;
   vector<int>::iterator found = find(v.begin(), v.end(), searchFor);
   if (found != v.end()) {
      cout << "Found" << endl;
   }
   return 0;
}
 
// Use iterator to print the entire vector
void print(vector<int> & v) {
   for (vector<int>::iterator iter = v.begin(); iter != v.end(); ++iter) {
      cout << *iter << " ";   // dereference
   }
   cout << endl;
}

11 55 44 33 88 99 11 22 66 77
11 11 22 33 44 55 66 77 88 99
44 33 22 11 11 55 66 77 88 99
44 55 22 77 11 33 66 88 11 99
Found

Program Notes:

Most of the algorithm functions takes at least two iterators: first and last, to specify the range [first,last) of operation. They could have additional parameters.
All STL containers provides members functions begin() and end(), which return the begin and pass-the-end elements of the container, respectively.
To apply sort, the elements shall have overloaded the '<' operator, which is used for comparing the order of the elements.

Example 2: for_each()

The for_each() applies a function to each element of the given range.

template <class InputIterator, class Function>
Function for-each (InputIterator first, InputIterator last, Function f);

/*
 *  Testing for_each algorithms (TestForEach.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void square(int & n);
void print(int & n);
 
int main() {
   vector<int> v;
   v.push_back(11);
   v.push_back(3);
   v.push_back(4);
   v.push_back(22);
 
   // Invoke the given function (print, square)
   // for each element in the range
   for_each(v.begin(), v.end, print);
   for_each(v.begin() + 1, v.begin() + 3, square);
   for_each(v.begin(), v.end, print);
   return 0;
}
 
void square(int & n) { n *= n; }
 
void print(int & n) { cout << n << " "; }

[TODO]

algorithm Functions

[TODO]

2.6 Function Object (Functors)

Most of the STL algorithms use so-called function objects or functors. A functor is an object that can be used with () operator, which includes regular functions, function pointers and class object with overloaded () operator.

for_each() algorithm

The for_each() algorithm, discussed earlier, takes a functor as its third argument, and apply the function to all the elements in the given range.

transform() algorithm

transform() algorithm has two versions, supporting unary and binary operations, respectively.

// Unary Operation
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first, InputIterator last,
                         OutputIterator result, UnaryOperation op)
   // Perform unary operation on each element in [first,last) and
   // store the output in range beginning at result

/*
 *  Testing transform() algorithms (TestTransform.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
using namespace std;
 
int square(int n) { return n*n; }
 
int main() {
   vector<int> v;
   v.push_back(2);
   v.push_back(-3);
   v.push_back(4);
   v.push_back(3);
   ostream_iterator<int, char> out(cout, " ");
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   transform(v.begin(), v.end(), v.begin(), square);
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   transform(v.begin(), v.end(), out, ::sqrt);  // in <cmath>
   return 0;
}

/*
 *  Testing transform() algorithms (TestTransform.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;
 
string & strtoupper(string & str);
 
int main() {
   vector<string> v;
   v.push_back("apple");
   v.push_back("orange");
   v.push_back("banana");
   ostream_iterator<string, char> out(cout, " ");
   copy(v.begin(), v.end(), out);
   cout << endl;
 
   transform(v.begin(), v.end(), v.begin(), strtoupper);
   copy(v.begin(), v.end(), out);
   cout << endl;
   return 0;
}
 
// Convert the given string to uppercase// Use transform() on each character with toupper()
string & strtoupper(string & str) {
   transform(str.begin(), str.end(), str.begin(), ::toupper);  // toupper in <cctype>
   return str;
}

// Binary Operation
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2,
                         OutputIterator result, BinaryOperation op)
   // Perform binary operation on each element in [first1,last1) as first argument,
   // and the respective [frist2,...) as second argument.
   // Store the output in range beginning at result

The header <functional> contains many functors that can be used in transform() algorithm, e.g., arithmetic (plus, minus, multiplies, divides, modulus, negate), relational (equal_to, not_equal_to,greater, less, greater_equal, less_equal), and logical (logical_and, logical_or, logical_not), etc.

template <class T>
struct plus;

// Example
plus<int> add;
int result = add(1, 2);

/*
 *  Testing transform() algorithms on binary operator (TestTransformBinary.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
 
int square(int n) { return n*n; }
 
int main() {
   int a1[5] = {1, 2, 3, 4, 5};
   int a2[5] = {11, 12, 13, 14, 15};
 
   vector<int> v1(a1, a1+5);
   vector<int> v2(a2, a2+5);
   ostream_iterator<int, char> out(cout, " ");
   copy(v1.begin(), v1.end(), out);
   cout << endl;
   copy(v2.begin(), v2.end(), out);
   cout << endl;
 
   transform(v1.begin(), v1.end(), v2.begin(), out, plus<int>());
       // Send result to output stream
   cout << endl;
 
   transform(v1.begin(), v1.end(), v2.begin(), v1.begin(), minus<int>());
       // Store result back to v1
   copy(v1.begin(), v1.end(), out);
   cout << endl;
   return 0;
}

Suppose that you want to add all elements by 8. The functor plus is a binary operator. You can use functors bind1st or bind2nd to bind the value of the first or second argument. For example,

/*
 *  Testing functors bind1st and bind2nd (TestFunctorBind.cpp)
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
 
int square(int n) { return n*n; }
 
int main() {
   int a1[5] = {1, 2, 3, 4, 5};
   int a2[5] = {11, 12, 13, 14, 15};
 
   vector<int> v1(a1, a1+5);
   vector<int> v2(a2, a2+5);
   ostream_iterator<int, char> out(cout, " ");
   copy(v1.begin(), v1.end(), out);
   cout << endl;
   copy(v2.begin(), v2.end(), out);
   cout << endl;
 
   transform(v1.begin(), v1.end(), out, bind2nd(minus<int>(), 8));
   cout << endl;
 
   transform(v1.begin(), v1.end(), out, bind1st(minus<int>(), 8));
   cout << endl;
   return 0;
}

2.7 STL and the string class

The string class is not part of the STL, but has implemented many STL features. string can be treated as a STL container of char. It defines member functions begin(), end(), rbegin(), rend() which returns an iterator for forward and reverse transversal. Most of the algorithms (such as transform(), sort()) are applicable to string, operating on individual characters.

/*
 *  Testing string on STL algorithms (TestStringSTL.cpp)
 */
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;
 
int main() {
   string s1("apples");
   cout << s1 << endl;   // "apples"
   sort(s1.begin(), s1.end());
   cout << s1 << endl;   // "aelpps"
 
   transform(s1.begin(), s1.end(), s1.begin(), ::toupper);
   cout << s1 << endl;   // "AELPPS"
   transform(s1.begin(), s1.end(), s1.begin(), bind1st(plus<char>(), 'a'-'A'));
   cout << s1 << endl;   // "aelpps"
   return 0;
}

Thought soup!

Pages

22 December, 2014

Standard Template Library (STL): An Introduction Part 3