STL Components

This is from the introduction in Scott Meyer's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library:

Introduction

You're already familiar with the STL. You know how to create containers, iterate over their contents, add and remove elements, and apply common algorithms, such as find and sort. But you're not satisfied. You can't shake the sensation that the STL offers more than you're taking advantage of. Tasks that should be simple aren't. Operations that should be straightforward leak resources or behave erratically. Procedures that should be efficient demand more time or memory than you're willing to give them. Yes, you know how to use the STL, but you're not sure you're using it effectively.

I wrote this book for you.

In Effective STL, I explain how to combine STL components to take full advantage of the library's design. Such information allows you to develop simple, straightforward solutions to simple, straightforward problems, and it also helps you design elegant approaches to more complicated problems. I describe common STL usage errors, and I show you how to avoid them. That helps you dodge resource leaks, code that won't port, and behavior that is undefined. I discuss ways to optimize your code, so you can make the STL perform like the fast, sleek machine it is intended to be.

The information in this book will make you a better STL programmer. It will make you a more productive programmer. And it will make you a happier programmer. Using the STL is fun, but using it effectively is outrageous fun, the kind of fun where they have to drag you away from the keyboard, because you just can't believe the good time you're having. Even a cursory glance at the STL reveals that it is a wondrously cool library, but the coolness runs broader and deeper than you probably imagine. One of my primary goals in this book is to convey to you just how amazing the library is, because in the nearly 30 years I've been programming, I've never seen anything like the STL. You probably haven't either.

Components

Several components make up the Standard Template Library. Three of which are: In one way, the STL separates the data from the algorithms, which is in stark contrast to how the object-oriented paradigm is supposed to work.


More #pragmas for Suppressing Warnings

(Some of these are now obsolete with Microsoft C++ 7.1)

#ifdef _MSC_VER
#pragma warning(disable: 4290) // Suppress 'C++ Exception Specification ignored'
#pragma warning(disable: 4710) // Suppress 'function ... not inlined' for Release builds
#pragma warning(disable: 4514) // Suppress '... unreferenced inline function has been removed'
#pragma warning(disable: 4786) // Suppress '... truncated to 255 chars in debug'
#pragma warning(push, 3)       // Set warning levels to a quieter level for the STL
#endif

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#ifdef _MSC_VER
#pragma warning(pop)           // Restore warning levels for our code
#endif

Containers

Sure, the STL has iterators, algorithms, and function objects, but for most C++ programmers, it's the containers that stand out. More powerful and flexible than arrays, they grow (and often shrink) dynamically, manage their own memory, keep track of how many objects they hold, bound the algorithmic complexity of the operations they support, and much, much more. Their popularity is easy to understand. They're simply better than their competition, regardless of whether that competition comes from containers in other libraries or is a container type you'd write yourself. STL containers aren't just good. They're really good. -- Scott Meyers in Effective STL

STL containers provide value semantics, meaning that they contain a copy of the object you add. (As opposed to the original object.) There are requirements for elements added to an STL container: Implementation-wise, there are essentially two types of containers: Sequence containers Associative containers Why the differences?

Vectors

A dynamic array, meant for adding items to the end. Add this header file:
#include <vector>
to the program.

Example:

int main(void)
{
  unsigned i;

    // Create empty vector of integers
  std::vector<int> cont1;

    // Add 7 random integers (each added at the end)
  cont1.push_back(2);
  cont1.push_back(3);
  cont1.push_back(7);
  cont1.push_back(5);
  cont1.push_back(4);
  cont1.push_back(6);
  cont1.push_back(1);

    // Print out the elements using subscripts
  for (i = 0; i < cont1.size(); ++i)
    std::cout << cont1[i] << "  ";
  std::cout << std::endl;

  cont1[2] = 8;    // change the 3rd element to 8 (using subscript operator)
  cont1.at(3) = 9; // change the 4th element to 9 (using at method)

  cont1[15] = 13;    // attempt to change the 16th element (undefined behavior)
  cont1.at(15) = 13; // attempt to change the 16th element (throws std::out_of_range exception)

    // Print out the elements
  for (i = 0; i < cont1.size(); ++i)
    std::cout << cont1[i] << "  ";

  std::cout << std::endl;

    // Display the number of elements in the container
  std::cout << "size: " << cont1.size() << std::endl;

    // Display the amount of elements that can be accommodated
    // without reallocating
  std::cout << "capacity " << cont1.capacity() << std::endl << std::endl;

  cont1.clear();  // Remove all elements (calling destructors, if any)

    // Show size and capacity after clear
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;
Output:
2  3  7  5  4  6  1
2  3  8  9  4  6  1
size: 7
capacity 8

size: 0       
capacity 8
Adding code to above:
  
    // Add some elements
  for (i = 0; i < 7; ++i)
    cont1.push_back(i);

    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

    // Add two more
  cont1.push_back(0);
  cont1.push_back(0);

    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

  return 0;
}
Output:
size: 7
capacity 8

size: 9
capacity 16
Oh, but if it were only true... From: comp.lang.c++ > std::vector<>::clear semantics:

message 1
message 2

So, the original output above (from MSC++ 6.0, g++, Borland, and probably every other compiler) now looks like this in MSC++ 7.1

2  3  7  5  4  6  1
2  3  8  9  4  6  1
size: 7
capacity 9

size: 0       
capacity 0
Another example:

// Create an empty vector of integers
std::vector<int> cont1;

  // Show size and capacity
std::cout << "Empty:" << std::endl;
std::cout << "size = " << std::setw(2) << cont1.size();
std::cout << ", capacity = " << std::setw(2) << cont1.capacity() << std::endl;

std::cout << "Adding 18 integers:" << std::endl;
for (int i = 0; i < 18; i++)
{
  cont1.push_back(i);
  std::cout << "size = " << std::setw(2) << cont1.size();
  std::cout << ", capacity = " << std::setw(2) << cont1.capacity() << std::endl;
}

Output:

MSC++ 6.0, g++, Borland, etc.MSC++ 7.1
Empty:
size =  0, capacity =  0
Adding 18 integers:
size =  1, capacity =  1
size =  2, capacity =  2
size =  3, capacity =  4
size =  4, capacity =  4
size =  5, capacity =  8
size =  6, capacity =  8
size =  7, capacity =  8
size =  8, capacity =  8
size =  9, capacity = 16
size = 10, capacity = 16
size = 11, capacity = 16
size = 12, capacity = 16
size = 13, capacity = 16
size = 14, capacity = 16
size = 15, capacity = 16
size = 16, capacity = 16
size = 17, capacity = 32
size = 18, capacity = 32
Empty:
size =  0, capacity =  0
Adding 18 integers:
size =  1, capacity =  1
size =  2, capacity =  2
size =  3, capacity =  3
size =  4, capacity =  4
size =  5, capacity =  6
size =  6, capacity =  6
size =  7, capacity =  9
size =  8, capacity =  9
size =  9, capacity =  9
size = 10, capacity = 13
size = 11, capacity = 13
size = 12, capacity = 13
size = 13, capacity = 13
size = 14, capacity = 19
size = 15, capacity = 19
size = 16, capacity = 19
size = 17, capacity = 19
size = 18, capacity = 19

Self-check Compile the samples above and see how each compiler deals with the capacity.


Other popular methods for vector:

Features Constructors:

vector<type> vDefalut constructor creates an empty vector.
vector<type> v1(v2)Copy constructor.
vector<type> v(n)Creates a vector with n elements set to default value. (Default constructor)
vector<type> v(n, value)Creates a vector with n elements set to value.
vector<type> v(beg, end)Creates a vector from the specified range of elements.

We'll use this class Foo so we can see the constructions:

class Foo
{
  public:
    Foo(int x = 2) {
      std::cout << "In Foo constructor: x = " << x << std::endl;
      x_ = x;
    };

    Foo (const Foo& rhs) {
      std::cout << "In Foo copy constructor: x = " << rhs.x_ << std::endl;
      x_ = rhs.x_;
    }

    int GetX(void) const { 
      return x_; 
    }

  private:
    int x_;
};

std::ostream & operator<<(std::ostream &os, const Foo &foo)
{
  return os << foo.GetX();
}
This program shows how the resize() and reserve() methods work:
int main(void)
{
    // Create vector of 5 Foo objects (5 constructor calls)
  std::vector<Foo> cont1(5);
  
    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

    // Create new vector with 8 Foo objects (5 are old, 3 are new)
  cont1.resize(8);

    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

    // Create a vector with space for 300 Foo objects 
    // (The previous 8 Foo objects are copied into new vector)
  cont1.reserve(300);

    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

  return 0;
}
Output:
  // std::vector<Foo> cont1(5);
In Foo constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
size: 5
capacity 5

  // cont1.resize(8);
In Foo constructor: x = 2
In Foo copy constructor: x = 2   <-- original object
In Foo copy constructor: x = 2   <-- original object
In Foo copy constructor: x = 2   <-- original object
In Foo copy constructor: x = 2   <-- original object
In Foo copy constructor: x = 2   <-- original object
In Foo copy constructor: x = 2   <-- new (default) object
In Foo copy constructor: x = 2   <-- new (default) object
In Foo copy constructor: x = 2   <-- new (default) object
size: 8
capacity 10

  // cont1.reserve(300);
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
In Foo copy constructor: x = 2
size: 8
capacity 300

Self-check Try the example above with different compilers and observe the results. Can you explain the output? Is the output different?

Using the reserve() method before putting anything into the container:
int main(void)
{
    // Create an empty vector 
  std::vector<Foo> cont1;
  
    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

    // Create new vector with space for 300 Foo objects 
  cont1.reserve(300);

    // Show size and capacity
  std::cout << "size: " << cont1.size() << std::endl;
  std::cout << "capacity " << cont1.capacity() << std::endl;

  return 0;
}
Output:
  // std::vector<Foo> cont1; 
size: 0
capacity 0

  // cont1.reserve(300);
size: 0
capacity 300
Notes: A closer look at the swap. This is how the swap works (long way):

std::vector<int> temp(cont1); // Construct temp via copy constructor
temp.swap(cont1);             // Swap contents of cont1 with temp
    // temp eventually goes out of scope and is cleaned up
This is the short way, using an unnamed temporary:

    // Swap trick
  std::vector<int>(cont1).swap(cont1);
  1. An unnamed temporary std::vector<int> is constructed from cont1.
    std::vector<int>(cont1)  // unnamed_temp
    
  2. The swap method of the unnamed temporary is called with cont1 as the parameter.
    unnamed_temp.swap(cont1);
    
  3. The contents are swapped between the two containers.
  4. The destructor for the unnamed temporary is called immediately after the swap.
Note that the swap method is very efficient. It is only swapping the pointers to the internal arrays, not the elements themselves.

Using vectors with C API Functions

void FillArray(int *array, int size)
{
  for (int i = 0; i < size; i++)
    array[i] = i * i;
}

int main(void)
{
  int i, size = 10;

    // Create a vector with size elements (initialized to 0) 
  std::vector<int> cont1(size);

    // Print them
  for (i = 0; i < size; ++i)
    std::cout << cont1[i] << "   ";
  std::cout << std::endl;

    // Update array contents
  FillArray(&cont1[0], cont1.size());

    // Print them
  for (i = 0; i < size; ++i)
    std::cout << cont1[i] << "   ";
  std::cout << std::endl;

  return 0;
}
Output:
0   0   0   0   0   0   0   0   0   0
0   1   4   9   16   25   36   49   64   81
Notes:

More information on the methods available for vector members on MSDN.

Deques

A dynamic array, meant for adding items to both ends. Add this header file:
#include <deque>
to the program. Deques (pronounced "Decks") are double-ended queues. Example:
int main(void)
{
    // Create empty deque for integers
  std::deque<int> cont1;

    // Add 7 random integers
  cont1.push_back(2);  // add to end
  cont1.push_back(3);  // add to end
  cont1.push_back(4);  // add to end
  cont1.push_back(5);  // add to end
  cont1.push_front(6); // insert at front
  cont1.push_front(7); // insert at front
  cont1.push_front(8); // insert at front

    // Print out the elements using subscripts
  for (unsigned int i = 0; i < cont1.size(); ++i)
    std::cout << cont1[i] << "  ";
  std::cout << std::endl;

  return 0;
}
Output:
8  7  6  2  3  4  5
or, we can use a different loop to print out the values (destructive):
while (!cont1.empty())
{
  std::cout << cont1.front() << "  ";
  cont1.pop_front();
}
std::cout << std::endl;

More information on the methods available for deque members on MSDN.

Lists

A doubly linked-list. Add this header file:
#include <list>
Lists are double linked-lists. Example: We will need these headers:
#include <iostream>
#include <list>
#include <string>
First, create a list and add some strings:
int main(void)
{
    // Create empty list of strings
  std::list<std::string> cont1;

    // Add 7 strings
  cont1.push_back("one");    // add to end
  cont1.push_back("two");    // add to end
  cont1.push_back("three");  // add to end
  cont1.push_back("four");   // add to end
  cont1.push_front("five");  // insert at front
  cont1.push_front("six");   // insert at front
  cont1.push_front("seven"); // insert at front
To print out the items, we might try this:
  // Print out the elements using subscripts
for (unsigned int i = 0; i < cont1.size(); ++i)
  std::cout << cont1[i] << std::endl;   
but we would quickly be met with this error message: (or something similar)
main.cpp(476) : error C2676: binary '[' : 'class std::list,
class std::allocator >,class std::allocator,class std::allocator > > >' 
does not define this operator or a conversion to a type acceptable to the predefined operator
There is no random access (no operator[]) so we need another way to iterate over the list. So, we use our while loop (not a good idea):
  // Print the contents of the list
while (!cont1.empty())
{
  std::cout << cont1.front() << "  ";
  cont1.pop_front();
}
std::cout << std::endl;
Output:
seven  six  five  one  two  three  four
What we really want to do is to use an iterator:
  // Declare an iterator 
std::list<std::string>::iterator it;

  // "Walk" (iterate) over the list until the end
for (it = cont1.begin(); it != cont1.end(); ++it)
  std::cout << *it << "  ";  // dereference the iterator to get the value

std::cout << std::endl;
Output:
seven  six  five  one  two  three  four
Summary:

More information on the methods available for list members on MSDN.

Iterators

Iterators provide a generic method for traversing the standard containers.
    // Create vector, add 5 integers
  std::vector<int> cont1;
  for (int i = 0; i < 5; ++i)
    cont1.push_back(i);

    // Create an iterator of the proper type
  std::vector<int>::iterator iter;

    // Iterate over the container, printing each element
  for (iter = cont1.begin(); iter != cont1.end(); ++iter)
    std::cout << *iter << "  ";
Output:
0  1  2  3  4
A closer look at this syntax:
  // Create an iterator of the proper type
std::vector<int>::iterator iter;
Suppose we add a public typedef to a class:

namespace DigiPen
{
  class Foo
  {
    public:
      typedef int FooInt;   // public typedef
  };
}
Now we can use the typedef:

  // Declare variable 'i' as type DigiPen::Foo::FooInt
DigiPen::Foo::FooInt i;
All container classes provide an iterator typedef. The vector class looks something like this:

namespace std
{
  template <typename T>
  class vector
  {
    public:
        // Nested templated class (uses same T as above)
      class vector_iterator : public std::iterator<std::random_access_iterator_tag, T>
      {
        // ...
      };

      typedef vector_iterator iterator; // public iterator
  };
}
That allows us to use iterator as a type:

  // Create an iterator of the proper type
std::vector<int>::iterator iter;
Common syntax of declaring the variable within the for loop: (vector methods)
  // Iterate over the container, printing each element
for (std::vector<int>::iterator iter = cont1.begin(); iter != cont1.end(); ++iter)
  std::cout << *iter << "  ";
Using a typedef in the client for convenience: (this example uses std::list)
  // Create a typedef for an iterator that's used
  // with lists of integers
typedef std::list<int>::iterator IntIter;

  // Use the typedef to declare a loop variable
for (IntIter iter = cont1.begin(); iter != cont1.end(); ++iter)
  std::cout << *iter << "  ";

Common usage:

Since containers are instantiated from templates, their associated iterators are also instantiated from templates. The type iterator is defined in the container as a typedef. So, our code looks like this:
  // Create an iterator for a vector of ints
std::vector<int>::iterator iter;
This creates an iterator that can be used to iterate over a vector of integers. If we wanted to iterate over a vector of strings:
  // Create an iterator for a vector of strings
std::vector<std::string>::iterator iter;
or for a std::list of doubles:
  // Create an iterator for a list of doubles
std::list<double>::iterator iter;
So, if our code contained a std::list of integers (instead of a std::vector):
    // Create list, add 5 integers
  std::list<int> cont1;
  for (int i = 0; i < 5; ++i)
    cont1.push_back(i);

    // Create an iterator for a list of integers
  std::list<int>::iterator iter;

    // Iterate over the container, printing each element
  for (iter = cont1.begin(); iter != cont1.end(); ++iter)
    std::cout << *iter << "  ";
Note that the loop doesn't change. This is why iterators are the backbone of the generic algorithms.

A final example showing the client creating a typedef for the container as well:

  // Any of these typedefs will work
typedef std::vector<int> Container;
//typedef std::list<int> Container;
//typedef std::deque<int> Container;

  // Create container, add 5 integers
Container cont1;
for (int i = 0; i < 5; ++i)
  cont1.push_back(i);

  // Use the typedef to declare a loop variable
for (Container::iterator iter = cont1.begin(); iter != cont1.end(); ++iter)
  std::cout << *iter << "  ";
std::cout << std::endl;


Iterator Categories Forward iterators have these capabilities:
ExpressionResult
iter_type()
Instantiates an iterator of type iter_type (Default constructor)
iter_type(iter)
Instantiates an iterator of type iter_type from iter. (Copy/conversion constructor)
*iter
Dereferences the iterator (returns the object referenced by the iterator)
iter->member
Returns a member of the object referenced by the iterator
++iter
Increments the iterator (move to the next element). Returns incremented iterator.
iter++
Increments the iterator (move to the next element). Returns previous non-incremented iterator.
iter1 = iter2
Assigns iter2 to iter1
iter1 == iter2
Checks for equality
iter1 != iter2
Checks for inequality
Bidirectional iterators have all of the capabilities of forward iterators, and add the ability to move backward through the elements:
ExpressionResult
--iter
Decrements the iterator (move back one). Returns decremented iterator.
iter--
Decrements the iterator (move back one). Returns previous non-decremented iterator.
Random access iterators provide all of the capabilities of bidirectional iterators, but add some other functionality:
  1. Use of the subscript operator for accessing any element.
  2. iterator arithmetic (much like pointer arithmetic) for moving to any element, e.g.
    iter + i;
    iter - i;
    iter += i;
    
  3. Comparison operators for determining the relative positions of two iterators, e.g.
    iter1 < iter2;
    iter1 > iter2;
    iter1 <= iter2;
    iter1 >= iter2;
    
Different containers provide different iterators:
ContainerIterator
vector, deque, stringrandom access
list, set, map, multiset, multimapbidirectional
istreaminput
ostreamoutput

Iterator Types

The standard containers provide four types of iterators:

Example - Creating a generic print function

It gets tedious to have to write the code to print the contents of a container every time:

  // Create vector, add 5 integers
std::vector<int> cont1;

  // do something ...

  // Print the contents of the container (vector)
for (std::vector<int>::iterator iter = cont1.begin(); iter != cont1.end(); ++iter)
  std::cout << *iter << "  ";
std::cout << std::endl;
It would be nice if we could just do this:
std::cout << cont1 << std::endl;
but that won't work. So, we come up with print1, which works just fine:

Print1

void print1(std::vector<int>& v)
{
  for (unsigned i = 0; i < v.size(); i++)
    std::cout << v[i] << "  ";
  std::cout << std::endl;
}
This code:
  // Create vector, add 5 integers
std::vector<int> cont1;
for (int i = 0; i < 5; ++i)
  cont1.push_back(i);

  // Print the vector of ints
print1(cont1);
now prints:
0  1  2  3  4
It's a nice start but: It should be pretty obvious what the solution is.

This leads us to our second version, called Print2:

Print2

template <typename T>
void print2(std::vector<T>& v)
{
  for (unsigned i = 0; i < v.size(); i++)
    std::cout << v[i] << "  ";
  std::cout << std::endl;
}
Now we can deal with all of this code:
  // Create vector for integers, add 5 of them
std::vector<int> cont1;
for (int i = 0; i < 5; ++i)
  cont1.push_back(i);

  // Create vector for strings, add 3 of them
std::vector<std::string> cont2;
cont2.push_back("one");
cont2.push_back("two");
cont2.push_back("three");

  // Create vector of Foo objects, add 5 of them
std::vector<Foo> cont3;
for (i = 0; i < 5; ++i)
  cont3.push_back(i * i);

print2(cont1); // Print the vector of integers 
print2(cont2); // Print the vector of strings 
print2(cont3); // Print the vector of Foo objects
Output:
0  1  2  3  4
one  two  three
0  1  4  9  16
This code has a problem with the print function:
  // Create deque for integers, add 5 of them
std::deque<int> cont1;
for (int i = 0; i < 5; ++i)
  cont1.push_back(i);

  // Compiler error: print2 function can't handle a deque
print2(cont1);
So we modify the template to include the container type as well:

Print3

template <typename T>
void print3(T& v)
{
  for (unsigned i = 0; i < v.size(); i++)
    std::cout << v[i] << "  ";
  std::cout << std::endl;
}
Now: Using iterators instead of subscripts:

Print4

template <typename T>
void print4(T& v)
{
  typename T::iterator iter;
  for (iter = v.begin(); iter != v.end(); ++iter)
    std::cout << *iter << "  ";
  std::cout << std::endl;
}
allows us to handle a lot more structures. For example:
  // Create a list of doubles
std::list<double> cont1;
for (int i = 1; i <= 5; ++i)
  cont1.push_back(1.0 / i);

  // Create a set of strings
std::set<std::string> cont2;
cont2.insert("one");
cont2.insert("two");
cont2.insert("three");
cont2.insert("four");

print4(cont1);  // Print the list of doubles
print4(cont2);  // Print the set of strings
Output:
1  0.5  0.333333  0.25  0.2
four  one  three  two
By the way, notice any thing about the order of the strings in the set?

There's still a slight problem that this code exposes:

  // Create a list of strings
std::list<std::string> cont1;
cont1.push_back("one");
cont1.push_back("two");
cont1.push_back("three");
cont1.push_back("four");

  // Create a copy of the list of strings
const std::list<std::string> cont2(cont1);

print4(cont1);  // Print the first list of strings
print4(cont2);  // Print the second list of strings
The compiler emits these errors

Iterator types

We need to modify the function slightly to handle this case:

Print5

template <typename T>
void print5(const T& v)
{
  typename T::const_iterator iter;
  for (iter = v.begin(); iter != v.end(); ++iter)
    std::cout << *iter << "  ";
  std::cout << std::endl;
}
Now we can print both lists:
print4(cont1);  // Print the first list of strings
print5(cont2);  // Print the second list of strings
Note that we can use print5 to print the first list as well.

Iterator typedef


A note about the typename keyword:

Neither Microsoft's 6.0/7.1 nor Borland's compiler uncovers the problem below. The GCC compiler does show the problem (undefined identifier):

template <typename T>
void f1(const T& a)
{
  int b;
  T::value * b;      // What is the meaning of this?
  T::newtype * ptr;  // What is the meaning of this? (Compiler error)
}
The error message:
main.cpp: In function `void f1(const T&) [with T = X]':
main.cpp:1054: error: `ptr' undeclared (first use this function)
The problem is more noticeable if we have this class and we instantiate it:
class X {
public:
  static const int value = 10;
  typedef int newtype;
};

int main(void)
{
  X a;
  f1(a);

  return 0;
}
Corrected:

template <typename T>
void f1(const T& a)
{
  int b;
  T::value * b;               // Implicit assumption: value is non-type
                              //   (multiplication expression)  
  typename T::newtype * ptr;  // Explicit: newtype is a type
                              //   (declaration)  
}

What about using our Print function with this code:
  // Create a map to hold integer/string pairs
std::map<int, std::string> cont1;

  // Put 3 pairs into the map
cont1.insert(std::make_pair<int, std::string>(1, "one"));
cont1.insert(std::make_pair<int, std::string>(2, "two"));
cont1.insert(std::make_pair<int, std::string>(3, "three"));

  // Print the map
print5(cont1);
Why is this error generated? Print5
main.cpp(618) : error C2679: binary '<<' : no operator defined which takes a 
                right-hand operand of type 'const struct std::pair,
                class std::allocator > >' (or there is no acceptable conversion)
main.cpp(696) : see reference to function template instantiation 
                'void __cdecl print5(class std::map,class std::allocator >,
                struct std::less,class std::allocator,class std::allocator > > > &)' 
                being compiled

There is nothing wrong with the print function. We need to add this to our code:

std::ostream &operator<<(std::ostream &os, const std::pair<int, std::string>& pair)
{
  os << "(" << pair.first << ", " << pair.second << ")";
  return os;
}
A quick look at the std::pair class (partial listing)

template<typename T, typename U> 
struct pair
{   
    // General typedefs
  typedef T first_type;
  typedef U second_type;

    // Default constructor
  pair() : first(T()), second(U()) 
  { 
  }

    // Constructor
  pair(const T& v1, const U& v2) : first(v1), second(v2)
  { 
  }

  T first;  // the first value
  U second; // the second value

    // other code
};
Of course, that's not going to help us here:
  // Create an empty map of double/Foo
std::map<double, Foo> cont2;

  // Create 3 Foo objects
Foo f1(100); Foo f2(200); Foo f3(300);

  // Insert pairs of double/Foo into the map
cont2.insert(std::make_pair<double, Foo>(1.0, f1));
cont2.insert(std::make_pair<double, Foo>(3.14, f2));
cont2.insert(std::make_pair<double, Foo>(6.8, f3));

  // Print out the contents of the map
print5(cont2);
We have the same problem we had above. We need more genericity:
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U>& pair)
{
  os << "(" << pair.first << ", " << pair.second << ")";
  return os;
}
This code works only if the elements of the pair have overloaded operator<< as well.

By the way, each code snippet does the same thing:

  // 1. Create unnamed pair and insert (template params explicit)
cont1.insert(std::make_pair<int, std::string>(1, "one"));

  // 2. Create unnamed pair and insert (template params deduced)
cont1.insert(std::make_pair(1, std::string("one")));

  // 3. Create pair by name and insert
std::pair<int, std::string> pr(1, "one");
cont1.insert(pr);

  // 4. Create default pair (0, ""), assign first/second, insert
std::pair<int, std::string> pr2;
pr2.first = 1;
pr2.second = "one";
cont1.insert(pr2);

Map example using pairs

Functions for Iterators

There are 3 functions provided for iterators: Declaration of advance():
template<class InIt, class Dist> void advance(InIt& it, Dist n); 
Notes: Example:
int main(void)
{
  std::vector<int> cont1;

    // Put 5 integers in vector
  for (int i = 0; i < 5; ++i)
    cont1.push_back(i);

    // Print out vector
  std::vector<int>::iterator it;
  for (it = cont1.begin(); it != cont1.end(); ++it)
    std::cout << *it << "  ";
  std::cout << std::endl;

    // Set iterator to beginning of container
  it = cont1.begin();

    // Print out first element
  std::cout << *it << std::endl;

    // Advance to 3rd element (2 elements further)
  std::advance(it, 2);

    // Print out 3rd element
  std::cout << *it << std::endl;

    // Backup one element
  std::advance(it, -1);

    // Print out 2nd element
  std::cout << *it << std::endl;

  return 0;
}
Output:
0  1  2  3  4
0
2
1

More Examples Using Iterators

#include <iostream>
#include <vector>
#include <string>

int main(void)
{
    // Create a typedef for a vector of strings
  typedef std::vector<std::string> StrCont;
    
    // Create a vector of strings
  StrCont cont1;

    // Put 5 strings in the vector
  cont1.push_back("one");    
  cont1.push_back("two");    
  cont1.push_back("three");  
  cont1.push_back("four");   
  cont1.push_back("five");   

    // Create a copy using all strings
  StrCont cont2(cont1); 
  print5(cont2);  // Output: one  two  three  four  five     

    // Create a copy using all strings
  StrCont cont3(cont1.begin(), cont1.end());
  print5(cont3);  // Output: one  two  three  four  five

    // Create a copy using first 2 strings only
  StrCont cont4(cont1.begin(), cont1.begin() + 2);
  print5(cont4);  // Output: one  two

    // Create a copy using last 3 strings
  StrCont cont5(cont1.end() - 3, cont1.end());
  print5(cont5);  // Output: three  four  five

    // Create a copy using all in reverse order
  StrCont cont6(cont1.rbegin(), cont1.rend());
  print5(cont6);  // Output: five  four  three  two  one
  
  return 0;
}
Output:
one  two  three  four  five
one  two  three  four  five
one  two
three  four  five
five  four  three  two  one
Now, to use a std::list instead of a std::vector, we want to simply change the typedef:
  // Create a typedef for a list of strings
typedef std::list<std::string> StrCont;
But this causes some problems with this code:
  // Create a copy using first 2 strings only. Compiler error!
StrCont cont4(cont1.begin(), cont1.begin() + 2);

  // Create a copy using last 3 strings. : Compiler error!
StrCont cont5(cont1.end() - 3, cont1.end());
Notes:

Iterator Adapters

There are 3 general types of iterator adapters: (found in the <iterator> header file)

Insert Iterators

There are 3 predefined inserters:

Example:
int Random1_30(void)
{
  return rand() % 30 + 1;
}

#include <iterator>// Need this for the inserters

void f26(void)
{
  typedef std::list<int> ContainerType;

    // Create container all set to 0
  ContainerType cont1(10), cont2(10);
  
    // Create empty containers
  std::list<int> cont3, cont4, cont5;

    // Fill cont1 with random values
    // 12  18  5  11  30  5  19  19  23  15
  std::generate(cont1.begin(), cont1.end(), Random1_30);

    // Copy values from cont1 to cont2 (pre-allocated)
    // 12  18  5  11  30  5  19  19  23  15
  std::copy(cont1.begin(), cont1.end(), cont2.begin());

    // Insert values from cont1 at front of cont3 (allocate as needed)
    // 15  23  19  19  5  30  11  5  18  12
  std::copy(cont1.begin(), cont1.end(), std::front_inserter(cont3));

    // Insert values from cont1 at back of cont4 (allocate as needed)
    // 12  18  5  11  30  5  19  19  23  15
  std::copy(cont1.begin(), cont1.end(), std::back_inserter(cont4));

    // Insert values from cont1 into cont5 at element 3 (allocate as needed)
    // 99  99  99  12  18  5  11  30  5  19  19  23  15  99  99  99  99  99  99  99
  cont5.resize(10, 99);
  ContainerType::iterator iter = cont5.begin();
  std::advance(iter, 3);
  std::copy(cont1.begin(), cont1.end(), std::inserter(cont5, iter));

    // Print the containers
  print5(cont1);
  print5(cont2);
  print5(cont3);
  print5(cont4);
  print5(cont5);
}
Notes: The power of iterators: (words_ is an empty vector of strings)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iterator>

#include "Tester.h"

bool Tester::Load(const std::string& filename)
{
  std::ifstream infile(filename.c_str());
  if (!infile.is_open())
    return false;
  else
  {
    std::istream_iterator<std::string> it(infile);
    std::istream_iterator<std::string> eof;
    std::copy(it, eof, std::back_inserter(words_));
    return true;
  }
}

void Tester::Print(bool oneline) const
{
  if (oneline)
    std::copy(words_.begin(), words_.end(), std::ostream_iterator<std::string>(std::cout, " "));
  else
    std::copy(words_.begin(), words_.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

  std::cout << std::endl;
}
The code to read in the words could have been done on one line:
using namespace std;
copy(istream_iterator<string>(infile), istream_iterator<string>(), back_inserter(words_));


Other handy reference material on MSDN:

From GNU: