The Standard Template Library - 10 Lessons About C++ (2015)

10 Lessons About C++(2015)

Chapter 10: The Standard Template Library

10.1 Introduction

The Standard Template Library (STL) as introduced by Hewlett Packard to the C++ community was revolutionary. Why? Because it gave C++ a dimension and capability it previously did not have. Before the library's inception, programmers focused on classes and Object Oriented Programming (OOP) in an attempt to model real-world behaviour.

Classes and OOP helped boost the popularity of C++ immensely. But by themselves, classes lacked efficiency in handling algorithms and data structures in a generic way. And OOP was never the holy grail it was frequently made out to be - in many cases it did not truly promote code reuse and modularity Until template-based programming was incorporated into C++, developers and companies would hand-craft their own data structures and algorithms by writing custom libraries and routines from scratch.

Now let's fast forward to the development of a new feature to receive serious attention by Alexander Stepanov (see http://en.wikipedia.org/wiki/Alexander_Stepanov) and other researchers: templates. These facilitated a library framework that at last allowed algorithms and data structures (containers) to work with arbitrary data types.

STL now comprises of five kinds of components: containers, iterators, algorithms, function objects (functors) and allocators.

Using these components can dramatically make your programs solid and robust in many ways. Here are just a few examples:

1. Arrays of any data type which can arbitrarily grow or shrink and incorporate automatic memory management as needed.

2. Access to a large number of powerful algorithms for searching and sorting data.

3. Set operations and other numerical transformations.

4. Customized code that will frequently outperform code built from scratch.

It is no exaggeration to say that STL has made possible a revolution in the way software tasks get done. It has become an integral part of any C++ programmer’s arsenal of techniques by allowing unwieldy custom code to be replaced with programs that can be applied across a wide range of generic tasks. STL concepts themselves will be discussed in more detail in the following sections.

10.2 Choosing an STL Container

Standard STL containers can be generalized as belonging to:

Standard sequence containers (std::vector, std::list, std::deque and std::string)

Standard associative containers (std::map, std::set, std::multimap, std::multiset)

Given the number of different STL containers at your disposal, it is worth considering some rules of thumb for choosing a STL container appropriate to your particular scenario. If you anticipate your collection needing to hold just a few items, then it is probably fine to use std::vectorregardless of what you intend to do. std::vector remains a good choice if you intend to maintain a collection of items that will change very little when compared to the number of times they are accessed. Furthermore, the std::vector container will provide everything you expect from an array, allowing for a straightforward collection of items that can be randomly accessed or added and removed (at the back of the container) in a dynamic and type safe way:

#include <vector>

#include <string>

#include <algorithm>

#include <iostream>

#include <iterator>

int main()

{

const int values[] = { 1, 11, 111, 1111 };

const size_t size = sizeof( values ) / sizeof( values[ 0 ] );

std::vector<int> v( values, values + size );

v.push_back( 11111 );

std::cout << "vector: ";

std::copy( v.begin(),

v.end(),

std::ostream_iterator<int>( std::cout, " " ) );

return 0;

}

This gives the following output:

Similar in respects to std::vector is std::deque (pronounced “deck”), short for double-ended queue. std::deque allows insertions at either end of the collection, ie push_back and push_front, thus allowing you to model a queue as well as a stack. But let's move on to entirely new ground. It may be the case that the need for random access is not so important, but instead you need a container that can efficiently insert or remove items at arbitrary positions. An associative container such as std::map would be a definite no-no and std::vector would be more computationally expensive for inserting data items, especially in the middle. However, std::list is ideal for this kind of task. A practical application could be the tracking of all open Windows objects, or maintaining a list of processes running in the background, the the kind of situations whereby the number of insertions and deletions is likely to be substantial. A unique feature of std::list is its ability to splice: that is, transfer elements from one std::list to another.

#include <list>

#include <string>

#include <algorithm>

#include <iostream>

#include <iterator>

int main()

{

typedef std::list<std::string>::iterator list_it;

std::list<std::string> list1;

std::list<std::string> list2;

list1.push_front( "A" );

list1.push_back( "E" );

list1.push_back( "F" );

list1.insert( ++list1.begin(), "B" );

list2.push_front( "C" );

list2.push_front( "D" );

// Transfer (splice) elements from list2 into list1.

list_it it = list1.begin();

std::advance( it, 2 );

list1.splice( it, list2 );

std::cout << "list1: ";

std::copy( list1.begin(), list1.end(),

std::ostream_iterator<std::string>( std::cout, " " ) );

return 0;

}

The output is as shown:

So the std::vector and std::list containers are examples of sequence container uses that implement data item storage. Other sequence containers in this category include std::deque, std::array and std::forward_list. In each case, all the container items must belong to the same data type. There can never be a mix of data types such as int or std::string within the same container.

So what other uses do we have for these containers? Well, there may be times when you want to guarantee that the container stores unique values only and prevents the insertion of duplicate items. In a practical setting this might include maintaining a list of students enrolled on a course, or a collection of unique social security numbers. Therefore an associative container such as std::set would be a reliable means of guaranteeing the uniqueness of inserted data items, provided the ordering of these unique items is of no importance.

The std::set container permits easy insertion and lookup of unique values by way of the insert and find methods respectively. That is because insert will not add an new item if the value of that item is already in the set, and new elements when inserted are automatically sorted in ascending order. Furthermore std::set, like other associative containers, has certain performance guarantees: the time required to both find and insert an item is proportional to log N, where N is the number of items.

#include <set>

#include <string>

#include <algorithm>

#include <iostream>

#include <iterator>

int main()

{

// Initialise sample sets

int vals1[] = { 4, 2, 1 };

int vals2[] = { 1, 7, 5, 2 };

int size1 = sizeof( vals1 ) / sizeof ( vals1[ 0 ] );

int size2 = sizeof( vals2 ) / sizeof ( vals2[ 0 ] );

std::set<int> s1( vals1, vals1 + size1 );

std::set<int> s2( vals2, vals2 + size2 );

// Find the intersection, providing it with an output iterator

std::set<int> intersect;

set_intersection( s1.begin(),

s1.end(),

s2.begin(),

s2.end(),

std::inserter(intersect,intersect.begin()) );

std::cout << "intersection: ";

std::copy( intersect.begin(),

intersect.end(),

std::ostream_iterator<int>( std::cout, " " ) );

return 0;

}

The output is as shown:

But what if you care about the position of inserted items? In this case std::set would not be appropriate. And in fact there is no STL container that does this at the moment, although std::set comes the closest because one of the types used to parameterize the std::set template is a comparison type. This comparison type determines the order in which new items are inserted. When this is not specified, it defaults to a less-than comparison. So to maintain a set of unique integer items preserved in the order in which they were inserted such as { 101, 111, 110, 001, 101 }, std::set (while ensuring the uniqueness of the numbers inserted) would not maintain this particular ordering. In cases like this, the solution will likely to involve more complex approaches such as creating your own class to combine container types in your own class. You might want std::set for storing unique items, and std::vector for keeping track of the order in which they were inserted:

#include <set>

#include <vector>

#include <string>

#include <algorithm>

#include <iostream>

typedef std::set<std::string>::iterator Iter;

class OrderedSet

{

private:

std::set<std::string> setItems;

std::vector<Iter> setOrder;

public:

OrderedSet() {}

void insert( const std::string& item )

{

setItems.insert( item );

Iter it = setItems.find( item );

setOrder.push_back( it );

}

int order( const std::string& item )

{

Iter it = setItems.find( item );

std::vector<Iter>::iterator order_it =

std::find( setOrder.begin(), setOrder.end(), it );

return order_it - setOrder.begin();

}

};

int main()

{

OrderedSet orderedSet;

orderedSet.insert( "Bravo" );

orderedSet.insert( "Alpha" );

orderedSet.insert( "Charlie" );

orderedSet.insert( "Delta" );

std::cout << "Order = "

<< orderedSet.order("Alpha")

<< std::endl;

return 0;

}

Moving on now, the std::map class allows us to store and obtain data items that are mapped to a key. This is useful when you need a means of quickly looking up a data item associated with a key value. The std::map container, while allowing for efficient insertion and retrieval as withstd::set, differs from the std::set in that std::map stores pairs, rather than single values: std::map<Key, T>, where Key is used to reference the data object T.

A std::set<Key> is an ordered collection of keys, while a std::map<Key, T> is a collection of data objects that can be referenced by a key. A common way to use the std::map<Key, T> is as an associative-like array, whereby the user can look up a given data element using a specific key. Superficially this looks a lot like using a conventional array, but the important difference is that the index used to retrieve the array element no longer has to be an integer-like variable, but instead can be ANY type.

The secret is that std::map<Key,T> defines the operator[] function to perform the lookup to find the data element associated with the given key. If a match is found, the function returns the reference to its mapped value; otherwise a new data item is inserted with that key and the function returns the reference to its newly mapped value. To put it more simply, std::map is an "add or update" function (hat-tip: Scott Meyers). It's worth pointing out a subtle efficiency issue here: if you're adding brand new items, then the insert method is preferable to using operator[] since it will only create new items without replacing existing ones. But if you need to update an existing item in your std::map, then the operator[] would be the preferred option.

#include <map>

#include <string>

#include <algorithm>

#include <iostream>

int main()

{

typedef std::map<std::string, int> ResultsMap;

ResultsMap rmap;

rmap.insert( ResultsMap::value_type( "Physics", 88 ) );

rmap.insert( ResultsMap::value_type( "Math", 67 ) );

rmap.insert( ResultsMap::value_type( "English", 67 ) );

// operator[] usage ("add or update")

rmap[ "Math" ] = 90;

std::for_each( rmap.begin(), rmap.end(),

[](std::pair<const std::string, int>& map)

{

std::cout << map.first << " " << map.second << std::endl;

});

return 0;

}

Now let's go one step farther. The std::multimap container offers a way of mapping groups of data items to a key. This is in contrast to the std::map being a one-to-one mapping between keys and their associated data items. Rather than using the find method to look up a single item associated with its key, the equal_range method is more likely to be used to obtain the range of items associated with the group and iterate through these:

#include <map>

#include <string>

#include <algorithm>

#include <iostream>

int main()

{

typedef std::multimap<std::string, int> ResultsMap;

typedef std::multimap<std::string, int>::const_iterator ResultsIter;

ResultsMap rmap;

rmap.insert( ResultsMap::value_type( "Geography", 87 ) );

rmap.insert( ResultsMap::value_type( "Physics", 57 ) );

rmap.insert( ResultsMap::value_type( "Physics", 69 ) );

rmap.insert( ResultsMap::value_type( "Physics", 45 ) );

const std::string subject = "Physics";

const std::pair<ResultsIter, ResultsIter> group =

rmap.equal_range( subject );

std::cout << subject << " =>";

std::for_each( group.first, group.second,

[](const std::pair<const std::string, int>& gr)

{

std::cout << gr.second << " ";

});

return 0;

}

10.3 Common STL Algorithms and their Usage

Replacing the traditional for loop

Besides improved readability, there exist some nice advantages to using std::for_each in place of the traditional for loop for iterating over sequences. It will allow you to write an algorithm on top of the std::for_each that will work with any iterator and reduces the risk of typo-introduced bugs. Specifically it applies a function object (functor) to each element within a range and returns a copy of the function object after it has been applied to all of the elements in the range. Here is an example of using std::for_each to append a set of strings contained in a std::vector container. This collects each 'txt' item stored in the in the std::vector of 'Token' structs, appending them to the 'txt' member of the Appender functor, which has the Word member function to return the complete concatenated string:

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

struct Token

{

std::string txt;

Token( std::string s ) : txt( s ) {}

};

class Append

{

private:

std::string txt;

public:

Append() : txt("") {}

void operator() (const Token &x)

{ txt.append( x.txt + " " ); }

std::string Word() const

{ return txt; }

};

int main()

{

std::vector<Token> tokens;

tokens.push_back( Token( "Hello" ) );

tokens.push_back( Token( "and" ) );

tokens.push_back( Token( "welcome!" ) );

std::cout << std::for_each(

tokens.begin(),

tokens.end(),

Append() ).Word()

<< std::endl;

return 0;

}

Sorting and searching

The STL sort algorithm operates on a selected range of container elements, arranging them into a sorted order according to a user-defined predicate function object that defines how elements are compared. Here is an example of how to read a list of objects, sort them and output them to the screen:

#include <iostream>

#include <ostream>

#include <vector>

#include <algorithm>

#include <memory>

// A base class to hold, return and output a value

class Item

{

int val;

public:

Item( const int& val ) : val( val ) {}

virtual char* ItemName() = 0;

int GetVal() { return val; }

void OutputToStream( std::ostream& os )

{

os << ItemName() << "\t" << val << std::endl;

}

};

// Derived class - "old"

class OldItem : public Item

{

public:

OldItem( const int& val ) : Item( val ) { }

char* ItemName() { return (char*) "Old: "; }

};

// Derived class - "new"

class NewItem : public Item

{

public:

NewItem( const int& val ) : Item( val ) {}

char* ItemName()

{

return (char*) "New: ";

}

};

// Auto pointer to de-allocate Item objects in case you are forgetful.

typedef std::unique_ptr<Item> ItemPtr;

// Specify how we want to sort the data:

struct Ascending

{

bool operator() ( const ItemPtr& start, const ItemPtr& end )

{

return start->GetVal() < end->GetVal();

}

};

int main()

{

std::vector< ItemPtr > itemVector;

itemVector.push_back( static_cast<ItemPtr>( new OldItem( 43 ) ) );

itemVector.push_back( static_cast<ItemPtr>( new NewItem( 34 ) ) );

itemVector.push_back( static_cast<ItemPtr>( new NewItem( 443 ) ) );

itemVector.push_back( static_cast<ItemPtr>( new OldItem( 433 ) ) );

itemVector.push_back( static_cast<ItemPtr>( new OldItem( 343 ) ) );

// Sort values in ascending order...

std::sort(

itemVector.begin(),

itemVector.end(),

Ascending() );

std::for_each( itemVector.begin(), itemVector.end(), []( ItemPtr& item )

{

item->OutputToStream( std::cout );

});

return 0;

}

This gives the following output:

In fact, STL has an ample fund of algorithms to help you locate items stored in containers. These can be speedy, typically of order log N for binary_search or equal_range. And containers such as std::map are designed to keep the data sorted in a self-balancing binary search tree as they are inserted, which allows certain performance guarantees when it comes to looking these items up.

Copying, Filling, Replacing and Removing

Many tasks boil down to being able to copy objects around or remove them. Input and output iterators are often a necessary means to accomplish this since we need to specify what data we want to work with and then where to output the result.

This example copies the elements of a std::vector container to a standard output where ostream_iterator is an adaptor of an output iterator type. The iterator operations are defined such that assigning through the iterator prints to standard output, with each print followed by a whitespace character:

#include <vector>

#include <algorithm>

#include <iterator>

#include <iostream>

class descending

{

public:

bool operator()( int x, int y ) const

{ return x > y; }

};

int main()

{

int values[] = { 100, 101, -2, 23, 1010, 44, 55, 3 };

const size_t size = sizeof( values ) / sizeof( values[ 0 ] );

std::vector<int> v( values, values + size );

std::sort( v.begin(), v.end(), descending() );

std::copy( v.begin(),

v.end(),

std::ostream_iterator<int>( std::cout, " " ) );

return 0;

}

This gives the following output:

Mutating and Transforming

The std::transform algorithm applies a function to each object in a given range and copies the result of the function to a new range which is pointed to by an output iterator. This example shows how to use a function adaptor that takes two input ranges and increases the values of the first range by the second range.

#include <iostream>

#include <vector>

#include <algorithm>

#include <iterator>

template<typename T, typename InputIterator>

void Print(std::ostream& ostr,

InputIterator itbegin,

InputIterator itend,

const std::string& delimiter)

{

std::copy(itbegin, itend,

std::ostream_iterator<T>(ostr, delimiter.c_str()));

}

template<class T>

class IncreaseByVal

{

public:

T operator()( T a, T b ) const

{ return a + b; }

};

int main()

{

int x[] = { 1, 2, 3, 4, 5 };

int y[] = { 1, 2, 3, 4, 5 };

std::transform( x,

x + sizeof( x ) / sizeof( x[ 0 ] ),

y,

x,

IncreaseByVal<int>() );

Print<int, int[]>( std::cout,

x,

x + sizeof( x ) / sizeof( x[ 0 ] ),

" " );

return 0;

}

10.4 More STL Tips, Tricks and Examples

Set Algorithms

Here is a practical example: using union and set intersection to calculate the Jaccard Index, a means of measuring the similarity and/or diversity of sample sets.

#include <iostream>

#include <vector>

#include <algorithm>

#include <iterator>

#include <string>

class Token

{

private:

std::string str;

public:

Token() {}

Token( std::string val ) : str( val ) {}

std::string Word() const

{ return str; }

};

struct Ascending

{

bool operator() ( const Token& start, const Token& end )

{

return start.Word() < end.Word();

}

};

int main()

{

std::string str1[] = { "The", "crazy", "cat", "sat", "on", "the", "mat" };

std::string str2[] = { "The", "cat", "sat", "on", "the", "red", "mat" };

std::vector<Token>::iterator tok_intersect, tok_union;

int size1 = sizeof( str1 ) / sizeof( str1[ 0 ] );

int size2 = sizeof( str2 ) / sizeof( str2[ 0 ] );

std::vector<Token> tokens1( str1, str1 + size1 );

std::vector<Token> tokens2( str2, str2 + size2 );

std::vector<Token> tokens( size1 + size2 );

std::sort( tokens1.begin(), tokens1.end(), Ascending() );

std::sort( tokens2.begin(), tokens2.end(), Ascending() );

tok_intersect = std::set_intersection(

tokens1.begin(),

tokens1.end(),

tokens2.begin(),

tokens2.end(),

tokens.begin(),

Ascending() );

int intersect_size = int( tok_intersect - tokens.begin() );

tok_union = std::set_union (

tokens1.begin(),

tokens1.end(),

tokens2.begin(),

tokens2.end(),

tokens.begin(),

Ascending() );

int union_size = int( tok_union - tokens.begin() );

double JaccardIndex = (double) intersect_size / (double) union_size;

std::cout << "Jaccard Index = "

<< JaccardIndex

<< std::endl;

return 0;

}

Tokenizing and splitting strings

Tokenization is the process of breaking up text into separate items (‘tokens’) according to some delimiter, typically a whitespace or other punctuation character.

This example takes the sample text and inserts each tokenized word into a vector array:

#include <iostream>

#include <string>

#include <sstream>

#include <algorithm>

#include <iterator>

#include <vector>

template<typename T, typename InputIterator>

void Print( std::ostream& ostr,

InputIterator itbegin,

InputIterator itend,

const std::string& delimiter )

{

std::copy( itbegin,

itend,

std::ostream_iterator<T>( ostr, delimiter.c_str() ) );

}

int main()

{

typedef std::vector<std::string>::iterator str_iter;

std::string txt = "The cat sat on the mat...";

std::istringstream iss( txt );

std::vector<std::string> tokens;

std::copy(

std::istream_iterator<std::string>(iss),

std::istream_iterator<std::string>(),

std::back_inserter<std::vector<std::string>>( tokens ) );

// Print the vector std::string items

Print<std::string, str_iter>( std::cout,

tokens.begin(),

tokens.end(),

" " );

}

This gives the tokenized output as shown:

Using containers as multi-dimensional arrays

Now here is an example of how to initialize and set values from a three-dimensional array implemented using the std::vector container. The STL container approach has the added benefit that unlike pointers to objects, the memory used in creating the array will be automatically removed when going out of scope. Just use standard array notation to retrieve array values. For example:

#include <vector>

#include <stdlib.h>

const size_t HEIGHT = 5;

const size_t WIDTH = 3;

const size_t DEPTH = 7;

int main()

{

std::vector<std::vector<std::vector<double>>> array3D;

// Allocate array dimensions by doing the resizing: HEIGHT x WIDTH

array3D.resize( HEIGHT );

for ( int i = 0; i < static_cast<int>( HEIGHT ); ++i )

{

array3D[ i ].resize( WIDTH );

for ( int j = 0; j < static_cast<int>( WIDTH ); ++j )

{

array3D[ i ][ j ].resize( DEPTH );

}

}

// Initialize with some values

array3D[ 1 ][ 2 ][ 5 ] = 3.2;

array3D[ 2 ][ 0 ][ 3 ] = 4.1;

return 0;

}

How to sort a std::map

By definition you cannot sort a std::map container by value, since a std::map sorts its elements by key. However we can get around this by dumping std::map key-value pairs into a std::vector first, then sorting that std::vector with a less-than functor afterwards. This is illustrated by the following example which creates mappings between std::pair and double pairs. The STL map to create a one-to-one mapping between a pair of link node IDs (using a std::pair) and the weight value connecting these nodes (using a double):

std::map<std::pair<int,int>, double> link_map;

The first step is to physically create the mappings:

link_map[ std::pair<int,int>(0,1) ] = 1.1;

link_map[ std::pair<int,int>(1,2) ] = 0.1;

link_map[ std::pair<int,int>(2,3) ] = 6.2;

link_map[ std::pair<int,int>(3,4) ] = 3.4;

link_map[ std::pair<int,int>(4,5) ] = 5.7;

link_map[ std::pair<int,int>(5,6) ] = 2.2;

link_map[ std::pair<int,int>(0,8) ] = 1.8;

Then the std::pair node IDs and their respective weights are printed as follows. Notice that since the std::pair is used as the map key, the std::map items are automatically sorted according to this, not the weight values:

0 1 1.1

0 8 1.8

1 2 0.1

2 3 6.2

3 4 3.4

4 5 5.7

5 6 2.2

Now you need some means of obtaining the mappings so they are sorted according to their weights, not their std::pair key values. Since you can't sort the std::map itself, instead use a function to insert these mappings into a std::vector and then sort the std::vector items. This involves an additional functor which defines how the items are sorted:

template<class T>

struct less_second : std::binary_function<T,T,bool>

{

inline bool operator()( const T& lhs, const T& rhs )

{ return lhs.second < rhs.second; }

};

// Initialize and sort vector with data_t items from link_map

std::vector<data_t> sorted_edges()

{

std::vector< data_t > vec(link_map.begin(), link_map.end());

std::sort(vec.begin(), vec.end(), less_second<data_t>());

return vec;

}

Also required is data_t, an additional typedef used to define the mapping:

typedef std::pair<std::pair<int,int>, double> data_t;

So that when we print out the vector of data_t items, we can see that they are sorted according to the second map parameter (double), and not the std::pair representing node IDs:

Full code listing

#include <map>

#include <vector>

#include <iostream>

#include <algorithm>

typedef std::pair<std::pair<int,int>, double> data_t;

std::map<std::pair<int,int>, double> link_map;

std::map<std::pair<int,int>, double>::iterator link_it;

template<class T>

struct less_second : std::binary_function<T,T,bool>

{

inline bool operator()( const T& lhs, const T& rhs )

{

return lhs.second < rhs.second;

}

};

// Initialize and sort vector with data_t items from link_map

std::vector<data_t> sorted_edges()

{

std::vector< data_t > vec(

link_map.begin(),

link_map.end() );

std::sort(

vec.begin(),

vec.end(),

less_second<data_t>());

return vec;

}

void PrintLinkMap()

{

std::cout << std::endl;

std::for_each( link_map.begin(), link_map.end(),

[]( std::pair< const std::pair<int,int>, double >& lmap )

{

std::cout << lmap.first.first << " "

<< lmap.first.second << " "

<< lmap.second << std::endl;

});

}

void PrintSortedEdges( const std::vector<data_t>& vec )

{

std::cout << std::endl;

std::for_each( vec.begin(), vec.end(), []( const data_t& dt )

{

std::cout << dt.first.first << " "

<< dt.first.second << " "

<< dt.second

<< std::endl;

});

}

int main()

{

// Create mapping between node pairs and weights

link_map[ std::pair<int,int>(0,1) ] = 1.1;

link_map[ std::pair<int,int>(1,2) ] = 0.1;

link_map[ std::pair<int,int>(2,3) ] = 6.2;

link_map[ std::pair<int,int>(3,4) ] = 3.4;

link_map[ std::pair<int,int>(4,5) ] = 5.7;

link_map[ std::pair<int,int>(5,6) ] = 2.2;

link_map[ std::pair<int,int>(0,8) ] = 1.8;

PrintLinkMap();

// Sort the mapping according to link weight

std::vector<data_t> vec = sorted_edges();

PrintSortedEdges( vec );

return 0;

}

Permanently removing STL container elements

Like all STL algorithms, remove receives a pair of iterators to identify the range of container elements over which it needs to operate, as shown in its declaration:

template< class ForwardIterator, class T >

ForwardIterator remove( ForwardIterator first,

ForwardIterator last,

const T& value );

However, remove does not know about the container that holds the iterator elements, only the iterators. So remove is not able to go from the iterator to the container holding that iterator, and therefore is not physically able to remove elements from that container. That remove does not actually remove in the literal sense is a source of confusion for many! Try it and see how removeing elements from a container does not actually change the total number of elements in that container:

This gives the following output:

Using STL to generate permutations

Put simply, given an input string how to we generate all of its possible permutations? A string permutation is found by reordering the position of its elements. We know that a string of length n will have n! (n factorial) permutations. For example, the string “xyz” will have the permutations:

xyz

xzy

yxz

yzx

zxy

zyx

You can see this with the following code:

#include <iostream>

#include <algorithm>

#include <iterator>

#include <string.h>

int main()

{

char str[] = "abcd";

const size_t len = strlen( str );

do

{

std::copy( str,

str + len,

std::ostream_iterator<char>( std::cout ) );

std::cout << std::endl;

}

while ( std::next_permutation( str, str + len ) );

}

This gives the following output:

Counting the occurrences of words in a text file

Now here is an example of the power of using STL’s associative arrays as a word counter. This code reads the contents of a text file while keeping a running total of the number of occurrences of each word. Discounting the code that outputs the results and strips out the punctuation characters we do not wish to count uses just a few lines of code. This deceptively simple line of code...

counter[ tok ]++;

... is used to look up the counter value for a given word and increment its value. It navigates the red-black tree used by the standard map to find the appropriate tree node, selects the T portion of the pair <Key,T>, and then increments it.

Note that the word counter has a default constructor to set the counter value to zero. Without this, the counter is set to some arbitrary value contained in the memory when the counter[ tok ]++ line of code is run for the first time. Not the zero value we want.

#include <iostream>

#include <iomanip>

#include <fstream>

#include <algorithm>

#include <map>

#include <string>

#include <vector>

#include <iterator>

template <class T>

struct less_second : std::binary_function<T, T, bool>

{

bool operator()( const T& lhs, const T& rhs )

{ return lhs.second.value < rhs.second.value; }

};

class WordCounter

{

public:

int value;

WordCounter() : value( 0 ) {}

void operator++ (int) { value++; }

};

// Remove unwanted characters from a string

bool filter(char c)

{

return isalpha( c ) == 0;

}

const std::string path = "Hamlet.txt";

int main()

{

typedef std::pair<std::string, WordCounter > word_mapping;

std::map<std::string, WordCounter> counter;

std::ifstream input;

input.open( path.c_str() );

if ( !input )

{

std::cout << "Error in opening file\n";

return 0;

}

std::string tok;

while ( true )

{

input >> tok;

// Remove ?, !, etc characters etc from string

tok.resize( std::remove_if( tok.begin(),

tok.end(),

filter ) - tok.begin() );

if ( tok == "" || tok == "\t" || tok == "\n" )

continue;

if ( input )

{

counter[ tok ]++;

}

else break;

}

std::map< std::string, WordCounter,std::less<std::string> >::iterator it;

// And then sort and display the result:

std::vector< word_mapping > result( counter.begin(), counter.end() );

std::sort( result.begin(), result.end(), less_second<word_mapping>() );

std::for_each( result.begin(), result.end(), []( const word_mapping& wmp )

{

std::cout << std::setw (20) << wmp.first << "\t"

<< wmp.second.value << std::endl;

});

return 0;

}

The console output is shown here: