TABLE OF CONTENTS (HIDE)

C++ Programming Language

C++ Standard Libraries and Standard Template Library (STL)

C++ Standard Libraries

C++ provides a huge set of libraries:

Standard ANSI C library ported over to C++. These libraries are name with a prefix "c" and without the ".h", e.g., <cmath> for C's <math.h>, <cstdlib> for C's <stdlib.h>, etc.
C++ new Libraries, such as <iostream>, <iomanip>, <string>, <fstream>, <sstream>.
C++ Standard Template Library (STL): consists of containers, iterators, algorithms and function objects.
Boost C++ libraries.

The cplusplus.com at http://www.cplusplus.com/reference provides a comprehensive online references for the C++ libraries (and updated for C++11).

C Libraries and Headers

<cstring>: To be elaborated later.
<cmath>: numeric mathematical library
<cstdlib>: General utilities such as Execution (abort, exit, EXIT_SUCCESS, EXIT_FAILURE); Environment (getenv); Dynamic Memory Management (malloc, free, calloc, realloc), String Parsing (atoi, atof, atol, strtod), Pseudo-random sequence generation (rand, srand, RAND_MAX); Array searching and sorting (bsearch, qsort).
<cctype>: Checking character types (isalpha, isdigit, isalnum, isspace, isupper, islower, isblank, iscntrl, isgraph, isprint, ispunct, isxdigit) and character conversion (toupper, tolower).
<climits>, <cfloat>: Size and limit of integer types (INT_MAX, INT_MIN, UINT_MAX, CHAR_BIT; and SHRT_XXX for short, LONG_XXX for long, LLONG_XXX for long long, CHAR_XXX for char) and floating-point types (DBL_MIN, DBL_MAX, DBL_DIG, DBL_MIN_EXP, DBL_MAX_EXP; and FLT_XXX for float, LDBL_XXX for long double).
<ctime>: time, difftime, clock, gmttime, localtime, and etc.
<cstdio>: C's IO operations (scanf, printf, fscanf, fprintf, fopen, fclose, etc)
<cassert>, <cerrno>, <csignal>: Diagnostics and error
<clocale>: localization
<cstdbool>, <cstdint>, <cstddef>, <cstdarg>:
<cuchar>, <cwchar>, <cwcchar>: Unicode characters.

C++ Libraries and Headers

<ios>, <iostream>, <istream>, <ostream>, <fstream>, <sstream>:
<iomanip>:
<string>:
<regex>:
<random>:
<limits>:
<stdexcept>, <exception>:
<complex>, <tuple>, <valarray>:
<locale>:
<typeinfo>:
<chrono>:
Others: <codecvt>, <new>, <ratio>, <system_error>, <type_traits>.

FUNCTION	EXAMPLE
*int atoi(char s)** Parse string s into an int
*double atof(char s)** Parse string s into a double
int rand(void) Generate a random number between 0 and RAND_MAX (>32767) void srand (unsigned int seed) Initialize (Seed) the random number generator	rand() % 100 // between 0 and 99 rand() % 100 + 1 // between 1 and 100
void exit(int status): Exit with status code void abort(void): Abort current process *int system(const char command): Execute system command char* getenv(const char param)*: Get environment parameter's value
EXIT_SUCCESS, EXIT_FAILURE: System-dependent return code for success and failure

C++ Standard Template Libraries (STL) and Headers

STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packard Lab as proof-of-concept for so-called generic programming. It was released in 1994 and subsequently adopted into the C++98.

STL provides a collection of templates representing containers, iterators, algorithms and function objects.

A container (templatized data structure) can be used to hold fundamental-type values or almost any type of objects, e.g., vector<int>, list<string>, deque<Person>.
An iterator (a generalization of pointer) is an object that lets you transverse through elements of a container, e.g., vector<int>::iterator, list<string>::iterator.
Algorithms are used for tasks such as searching, sorting and comparison, e.g., for_each, find, sort.
Function objects are objects that act like functions.

STL is provided in the following headers:

<vector>, <list>, <deque>, <queue>, <stack>, <map>, <set>, <bitset>, <forward_list> (C++11), <unordered_map> (C++11), <unordered_set> (C++11), <array> (C++11): Containers data structures template classes.
<iterator>: Iterator for traversing the elements in a container.
<algorithm>, <numeric>, <functional>, <utility>: Algorithm and function objects.
<initializer_list> (C++11), <memory> (C++11).

Boost C++ Libraries

[TODO]

C++ Standard Template Library (STL)

Let's Get Started with Examples of vector STL Template Class

In computing, a vector refers to an array-like structure that holds a set of direct-access elements of the same kinds, instead of mathematical n-component vector. Unlike array which is fixed-size, vector is dynamically-sized. vector is a class template, declared in the vector header.

Let's begin with some examples.

Example 1: Construct vector<> object and access its elements

/* Test vector class element access  (TestVectorIndex.cpp) */
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
 
void print(const vector<int> & v);
 
int main() {
   const int SIZE = 10;
   vector<int> numbers(SIZE);  // Declare vector of int of SIZE elements, init to 0
 
   cout << "size = " << numbers.size() << endl;
   cout << "capacity = " << numbers.capacity() << endl;
   print(numbers);
 
   // Assign random numbers into vector
   srand(time(0));  // Seed the pseudo-random number generator
   for (size_t i = 0; i < numbers.size(); ++i) {
      numbers.at(i) = rand() % 100;  // at() did bound check
   }
   print(numbers);
 
   cout << "First element is " << numbers.front() << endl;
   cout << "Last element is " << numbers.back() << endl;
 
   // [] does not perform index bound check, but at() does
   cout << numbers[55] << endl;    // no error compile and run
// cout << numbers.at(55) << endl; // runtime out_of_range exception
   return 0;
}
 
// Print the content of this vector using indexing operator []
void print(const vector<int> & v) {
   for (int i = 0; i < v.size(); ++i) {
      cout << v[i] << " ";  // no bound check, but safe here
   }
   cout << endl;
}

Program Notes:

vector is a template class. We create an int specialization via vector<int>. We create a vector<int> object via constructor vector<int> numbers(SIZE); which allocates SIZE elements and initializes to 0.
The size() member function returns the number of elements. The capacity() returns the storage allocated. All STL containers dynamically allocate storage.
Elements in vector has a linear order index. You can use [] overloaded operator or at() member function to access the n-th element. Take note that [] does not perform index-bound check; but at() does at runtime and throws out_of_range exception if index exceeds bound.
The member function front() and back() returns the first and last element respectively.

Example 2: Using push_back() and pop_back() to add and remove element

/* Test modifying vector class's element (TestVectorMod.cpp) */
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
 
void print(const vector<int> & v);
 
int main() {
   vector<int> numbers;  // Declare vector of int with initial size of 0
   cout << "size = " << numbers.size() << endl;
   cout << "capacity = " << numbers.capacity() << endl;
 
   // Assign random numbers into vector
   srand(time(0));
   for (int i = 0; i < 5; ++i) {
      numbers.push_back(rand() % 100);
         // Append element at the end - vector resize automatically
   }
   print(numbers);
   cout << "size = " << numbers.size() << endl;
   cout << "capacity = " << numbers.capacity() << endl;
 
   numbers.pop_back(); // Remove the last element - size reduces by 1
   numbers.pop_back();
   print(numbers);
   cout << "size = " << numbers.size() << endl;
   cout << "capacity = " << numbers.capacity() << endl;
 
   numbers.clear();  // Remove all elements
   cout << "size = " << numbers.size() << endl;
   cout << "capacity = " << numbers.capacity() << endl;
   return 0;
}
 
// Print the content of this vector using indexing operator []
void print(const vector<int> & v) {
   for (int i = 0; i < v.size(); ++i) {
      cout << v[i] << " ";  // no bound check, but safe here
   }
   cout << endl;
}

Program Notes:

The default constructor vector<int> numbers construct a vector object with size of 0.
The member function push_back() appends the item at the end; while pop_back() removes the last element.

Example 3: Using iterator to access the container

We can use a special object called iterator to iterate through all the elements of a STL container, such as vector. The vector class provides a pair of functions begin() and end() to work with iterator. To use iterator:

// Declare a vector
vector<int> aVector(10);
// Declare an iterator called iter for vector<int>
vector<int>::iterator iter;
// Assign iter to the beginning of the vector
iter = aVector.begin()
// Use *iter to access the current element
cout << *iter << endl;
// Next element
++iter;
// The pass-the-end element is aVector.end() - to be excluded

/* Test vector class's iterator (TestVectorIterator.cpp) */
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
using namespace std;
 
void print(vector<string> & v);
 
int main() {
   vector<string> strs;
   strs.push_back("apple");
   strs.push_back("orange");
   strs.push_back("banana");
   print(strs);
   cout << "size = " << strs.size() << endl;
 
   // Test insert()
   strs.insert(strs.begin() + 2, "b4-banana");
   strs.insert(strs.begin() + 1, 2, "b4-orange");
   print(strs);
   cout << "size = " << strs.size() << endl;
 
   // Test erase()
   strs.erase(strs.begin() + 1, strs.begin() + 4);
   print(strs);
   cout << "size = " << strs.size() << endl;
 
   // insert() from another vector
   vector<string> newStrs;
   newStrs.push_back("1");
   newStrs.push_back("2");
   newStrs.push_back("3");
   strs.insert(strs.begin() + 1, newStrs.begin(), newStrs.end());
   print(strs);
   cout << "size = " << strs.size() << endl;
}
 
// Use iterator to iterate thru the entire vector
void print(vector<string> & v) {
   for (vector<string>::iterator iter = v.begin(); iter != v.end(); ++iter) {
      cout << *iter << " ";   // dereference
   }
   cout << endl;
}

Program Notes:

Each container class defines its suitable iterator, with type name of vector<T>::iterator.
The vector's member function begin() and end() returns an iterator to the first element and the pass-the-end element, respectively. The pass-the-end element shall be excluded, i.e., [begin(), end()).
Iterator works like pointer, you can use *iter (dereferencing operator) to retrieve the vector element; ++iter (increment operator) to move to the next element; iter+n to point to the +n element.
The insert() and erase() member functions works on the iterator as well. insert(iter, item) inserts item before the iter-element. insert(insert, n, item) fills n element before the iter-element. erase(fist, last) removes all element in [first, last).

In C++11, you can use the auto as the type of iterator, which asks the compiler to deduce the type automatically.

for (auto iter = strs.begin(); iter != strs.end(); ++iter) {
   cout << *iter << " ";           // Print string
}
cout << endl;

C++ introduces for-each loop, which can be used to iterate thru all the items of an array or a container:
```
for (auto item : strs) {
   cout << item << " ";
}
cout << endl;
```

The vector Template Class

Let's take a closer look at the vector template class, which serve as a sample for all the STL container classes.

Constructor

vector (const allocator_type & alloc = allocator_type());
   // Default Constructor: construct a vector object
vector (size_type n, const value_type & val = value_type(),
        const allocator_type & alloc = allocator_type());
   // Fill Constructor: construct a vector object with n-element filled with val
vector (const vector & v);
   // Copy Constructor
template <class InputIterator>
vector (InputIterator first, InputIterator last,
        const allocator_type & alloc = allocator_type());
   // Range Copy Constructor

Size and Capacity

size_type size () const;      // Return the size (number of elements)
size_type capacity () const;  // Return the storage allocated (in term of element)
bool empty () const;          // Return true if size is 0
void reserve (size_type n);   // Request for storage to hold n elements
void resize (size_type n, value_type val = value_type());
      // resize to n, remove extra element or fill with val
size_type max_size () const;  // Return the maximum number of element
void shrink_to_fit ();        // (C++11) Request to shrink storage

Accessing Element

value_type & operator[] (size_type n);  // [n] operator (without index-bound check)
value_type & at (size_type n);          // Return a reference to n-th element with index-bound check
value_type & front ();    // Return a reference to the first element
value_type & back ();     // Return a reference to the last element

Modifying Contents

void push_back (const value_type & val); // Append val at the end
void pop_back ();                        // Remove the last element
void clear ();                           // Remove all elements

Non-member Friend Functions

==, !=, <, >, <=, >=    // Comparison Operators
// E.g.
template <class T, class Alloc>
bool operator== (const vector<T,Alloc> & left, const vector<T, Alloc> & right);
   // Compare two vectors
   // For == and !=, first compare the size, then each element with equal algorithm.
   //   Stop at the first mismatch.
   // For <, >, <=, >=, use lexicographical_compare algorithm. Stop at first mismatch.
 
template <class T, class Alloc>
void swap (vector<T,Alloc> & v1, vector<T,Alloc> v2);
   // Swap the contents of containers v1 and v2.
   // Both shall has the same type, but can have different sizes.

Iterator

iterator begin();  // Return an iterator pointing to the first element
iterator end();    // Return an iterator pointing to the pass-the-end element
 
reverse_iterator rbegin(); // Return a reverse iterator pointing to the reverse beginning (last element)
                           // increasing a reverse iterator to transverse in reverse order
reverse_iterator rend();   // Return a reverse iterator pointing to the reverse past-the-end

Iterator-based Operations

iterator insert (iterator pos, const value_type & val);  // Single-Element: insert element val before iterator pos
void     insert (iterator pos, size_type n, const value_type & val);  // Fill: insert n copies of val before pos
template <class InputIterator>
void     insert (iterator pos, InputIterator first, InputIterator last)
    // Range-copy: copy the range [first, last) and insert before pos.
 
iterator erase (iterator pos);  // Single-element: remove element pointed to by iterator pos
iterator erase (iterator first, iterator last);  // Range: remove elements between [first,last)
 
void assign (size_type n, const value_type & val);  // Fill: clear old contents and assign n copies of val
template <class InputIterator>
void assign (InputIterator first, InputIterator last);  // Range: assign [first, last)

[TODO] Example

Containers

Sequence Containers, Associative Containers and Adapters

STL provides the following types of containers:

Sequence Containers: linear data structures of elements
- vector: dynamically resizable array. Support fast insertion and deletion at back; and direct access to its elements.
- deque: double-ended queue. Support fast insertion and deletion at front and back; and direct access to its elements.
- list: double-linked list. Support fast insertion and deletion anywhere in the list; and direct access to its elements.
Associative Containers: nonlinear data structures storing key-value pairs
- set: No duplicate element. Support fast lookup.
- multiset: Duplicate element allowed. Support fast lookup.
- map: One-to-one mapping (associative array) with no duplicate. Support fast key lookup.
- multimap: One-to-many mapping, with duplicates allowed. Support fast key lookup.
Container Adapter Classes:
- Stack: Last-in-first-out (LIFO) queue, adapted from deque (default), or vector, or list. Support operations back, push_back, pop_back.
- queue: First-in-first-out (FIFO) queue, adapted from deque (default), or list. Support operations front, back, push_back, pop_front.
- priority_queue: highest priority element at front of the queue. adapted from vector (default) or deque. Support operations front, push_back, pop_front.

First-class Containers, Adapters and Near Containers

The containers can also be classified as:

First-class Containers: all sequence containers and associative containers are collectively known as first-class container.
Adapters: constrained first-class containers such as stack and queue.
Near Containers: Do not support all the first-class container operations. For example, the built-in array (pointer-like), bitsets (for maintaining a set of flags), valarray (support array computation), string (stores only character type).

Container's Functions

All containers provides these functions:

Default Constructor: to construct an empty container. Other constructors are provided for specific purposes.
Copy Constructor:
Destructor:
empty(): returns true if the container is empty.
size(): returns the size (number of elements).
Assignment Operator (=)
Comparison Operators (==, !=, <, <=, >, >=).
swap(): exchanges the contents of two containers.

In addition, the first-class containers support these functions:

begin, end, cbegin, cend: Returns the begin and end iterator, or the const version.
rbegin, rend, crbegin, crend: Returns the reverse_iterator.
clear(): Removes all elements.
erase(): Removes one element given an iterator, or a range of elements given [begin, end) iterators.
max_size(): Returns the maximum number of elements that the container can hold.

Container Header

<vector>
<list>
<deque>
<queue>: queue and priority_queue
<stack>
<map>: map and multimap
<set>: set and multiset
<valarray>
<bitset>
<array> (C++11)
<forward_list> (C++11)
<unordered_map> (C++11)
<unordered_set> (C++11)

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 an vector<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 container
iter_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 via container<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;
}

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]

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;
}

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;
}

vector, valarray and array

C++ has 3 array template classes: vector, valarray, array (C++11). vector and array are STL; while valarray is not.

vector

vector is certainly the most commonly used STL container. vector is dynamically allocated, with support for push_back() and insert().

array

The array class is a wrapper for the fixed-sized built-in array with the STL container interfaces. It is designed as a substitute for the built-in array type, for applications where dynamic resizable vector is not needed (so as to reduce the overhead of dynamic array). array does not support push_back() and insert(), as it cannot be resized.

valarray

valarray is designed for numeric computation. It is variable-size but does not supports STL operations such as push_back() or insert, but provides a simple interface for many mathematical operations. For example, the arithmetic operators (such as +, -, *, /, %) and mathematical functions (such as pow, sqrt, exp, log, sin, cos, etc.) are overloaded to operate on the entire valarray (instead of individual element). For example,

/*
 *  Testing valarray (Testvalarray.cpp)
 */
#include <iostream>
#include <valarray>
using namespace std;
 
void print(const valarray<int> & va);
 
int main() {
   const int SIZE = 5;
   int a1[SIZE] = {1, 2, 3, 4, 2};
   int a2[SIZE] = {11, 12, 13, 14, 15};
   valarray<int> va1(a1, SIZE);
   valarray<int> va2(a2, SIZE);
   valarray<int> va3(SIZE);  // all 0
   print(va1);
   print(va2);
   print(va3);
 
   va3 = va1 + va2;   // + operates on all elements
   print(va3);
 
   va3 = pow(va2, va1);  // pow() operates on elements
   print(va3);
 
   cout << "sum is " << va1.sum() << endl;
   cout << "max is " << va1.max() << endl;
   cout << "min is " << va1.min() << endl;
   return 0;
}
 
void print(const valarray<int> & va) {
   for (int i = 0; i < va.size(); ++i) {
      cout << va[i] << " ";
   }
   cout << endl;
}

STL Containers

C++98/03 has 11 containers: vector, stack, list, queue, deque, priority_queue, map, multimap, set, multiset and bitset. C++11 added forward_list, unordered_map, unordered_multimap, unordered_set and unordered_multiset, and moves bitset from container category to its own separate category. string is not really part of STL, but implemented many STL concepts.

The STL container are template class, which can be instantiated with a type. The actual type has to be copy constructable (having copy constructor) and assignable (overload = operator).

Sequence Container

A sequence container requires that elements are arranged in a strict linear order.

vector: direct-access class-representation of dynamic array. Elements can be added and removed from the end in constant time. But insertion and removal not from the end require linear time. It supports direct-access, as well as bidirectional transversal.
deque: (pronounced "deck") double-ended queue, allow elements to be added and removed from both the front and the rear, at constant time. The deque implementation in STL is similar to vector, which allows direct access. It is more complex than vector, as it allows constant-time insertion and removal from the front and rear; whereas vector only for rear.
list: double-linked list that can be transverse in both direction. It support constant-time insertion and removal, but does not allow direct (random) access with no indexing operator.
forward_list (C++11): single-linked list that support forward transversal only. It is simpler than list.
queue: allow elements to be added at the rear and removed from the front at constant time. STL's queue is very restrictive that it does not support direct access nor transversal through the elements.
priority_queue: Similar to queue, but move the larger element to the front of the queue.
stack: LIFO (last-in-first-out) queue, elements can be added and removed from the top-of-stack in a last-in-first-out manner. In STL, stack is an adapter class over the vector class. It is more restrictive than vector. Elements can only be accessed, added and removed from one-end (top-of-stack). It does not support direct access, nor transversal through all the elements.
array (C++11): array is NOT a STL container because it has a fixed size and does not support operations like insert. But you can apply STL algorithms on array container.

Associative Containers

Associative container stores key-value pair or name-value pairs (i.e., associate a key with a value, and use a key to find the value). Associative container (or associative array) is actually similar to an array or vector, where a numerical index key is associated with a value, and you use the numerical key to find a value. Example of key-value pair are person-phone number(s), id-name, etc.

STL supports the following associative containers:

set: the key is the same as the value. It does not allow duplicate values. STL set is sorted and reversible.
multiset: allow duplicate values.
map: key-value pair, where keys are unique. One key is associated with one value. STL map is sorted and reversible. It needs two types to instantiate: map<key-type, value-type). To represent each key-value, STL provides a template class called pair<class K, class V>. You can instantiate the template class with specific key-type and value-type, e.g., pair<const int, string>.
multimap: one key could be associated with multiple values.
C++11 added 4 unordered associative containers: unordered_set, unordered_multiset, unordered_map, and unordered_multimap. These unordered associative containers are based on hash table (efficient in insertion, removal and search, but requires more storage spaces); whereas the ordered counterparts are based on tree.

Example: map

[TODO]

Link to "C++ References & Resources"

Latest version tested: GCC 4.6.2
Last modified: May, 2013