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:

Containers
- Manage a collection (container) of objects of the same type.
- May be implemented as an array, linked-list, tree, or other type of structure.
- The different kinds of containers reflect the different implementations and uses.
Iterators
- Iterators are used to traverse a container (or "walk a container") or subset of a container.
- They provide a common interface for iterating over a collection of objects. (e.g. iterate over an array vs. iterating over a linked-list.)
- They are similar to pointers in that an iterator will "point" to the "next" object in the container.
- The concept of "next" varies among different containers. (e.g. the next element in an array vs. the next element in a binary tree)
- Iterators are the "glue" between containers and algorithms.
Algorithms
- Algorithms are applied to containers (actually, ranges within containers) to process the elements.
- There are algorithms to search, sort, or otherwise access or modify the container and/or its elements.
- The algorithms work closely with iterators.
- These algorithms are often referred to as generic algorithms because they can be applied to almost any type of container or element.
- This allows an algorithm to be written once that can be used, for example, to search a list of integers, or an array (vector) of strings, or a tree of Foo objects.
- In addition to the iterators, the generic algorithms can also be directed how to perform their functions by supplying function objects or functors to the algorithm. (These are similar in use to supplying function pointers (callbacks) to plain functions in C/C++.)

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:

Elements must be copyable via a public copy constructor.
Elements must be assignable via a public assignment operator.
Elements must be destroyable via a public destructor (which must not throw).
All built-in types (like int and double) meet the above requirements.

Implementation-wise, there are essentially two types of containers:

Array-based - Stores elements in one or more (dynamically allocated) arrays of elements. Inserting into or removing from the middle (non-ends) of the structure is expensive. Standard containers vector, deque, and string are array-based.
Node-based - Stores elements in single (dynamically allocated) chunks of memory, much like a linked list. Inserting into or removing from the middle is cheap (just update pointers.) Standard containers such as list, set, and map are node-based.

Sequence containers

Are ordered collections of objects, each object has a position.
The position depends on the time the object arrived in the collection. (Temporal ordering)
The position is independent of the value of the object.
Some types of sequence containers:
- Vector - A dynamic array, meant for adding to end. (push_back)
- Deque - (Note spelling, not Dequeue, pronounced deck) A double-ended queue, meant for adding at either end. (push_front/push_back)
- List - A (doubly) linked list, typical usage and complexity.
Other, more specialized containers are container adapters: Stack, Queue, Priority Queue
Each container implementation has its own complexities.

Associative containers

Are sorted collections of objects, each object's position is determined by its value.
Associate containers always remain sorted because items are inserted into the correct position.
Some types of ordered containers:
- Set - No duplicates, each value occurs only once.
- Multiset - Same as a set but it allows duplicates.
- Map - Elements are stored as key/value pairs. The key is used for the sort. Duplicate keys are not allowed. (Used to implement associative arrays)
- Multimap - Same as map except that duplicate keys are allowed. This means that one key may have multiple values associated with it. (Used to implement a dictionary).
You can specify the sort order when you create an associative container. (The default is to use the less-than, <, operator).
Associative containers are usually implemented as a binary tree. (Red-Black tree)

Why the differences?

The different containers were created for different purposes. (efficiency)
You want to choose the container that has the best performance: constant time, logarithmic time, or linear time).
Usually, if a container is "missing" a method, it was not provided because it was too inefficient. (e.g. there is no push_front method of a vector).

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

Fortunately, Microsoft has now reverted back to the original way of preserving the capacity.

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, Clang, etc. MSC++ 7.1 and later

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

MSC++ 6.0, g++, Borland, Clang, etc.	MSC++ 7.1 and later
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:

push_back() Add an element to the end (without growing the internal array). (Constant time)
insert() Add at a particular position. (Linear time)
begin() and end() Return iterators to the first element and (one past) the last element, respectively.
erase() Deletes an element or range of elements. Elements may need to be shifted (linear time); Capacity is not reduced.
clear() Deletes all elements (linear time). Capacity is not reduced. (caveat emptor)
empty() Returns true if the vector is empty, otherwise false.
operator[] and at() Get/Set an element by index.
- The overloaded subscript operator for reading/writing to the vector doesn't throw when subscript is out of range, but certainly will corrupt memory if the subscript is out of range.
- The at(int index) method for reading and writing elements does throw when subscript is out of range.
front() and back() Return the first and last element, respectively.
size() Returns the number of elements in the vector.
capacity() Returns the number of elements that can be placed in the vector without growing the vector.
swap() Exchanges the elements of two vectors. (Constant time)

Features

Use a vector when you need array semantics (random access for reading, writing to the end).
Automatically resizes so that you don't have to worry about writing past the end.
Use reserve to avoid unnecessary re-allocations.
You can "preallocate" the amount of space you need to avoid the overhead of resizing.
Inserting and deleting will invalidate pointers or iterators to elements that follow the insertion or deletion.
- If a reallocation occurs, all pointers and iterators are invalidated.

Constructors:

vector<type> v Defalut 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:

Compiler #1	Compiler #2 (with dtor calls)
// 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	// std::vector<Foo> cont1(5); In Foo constructor: x = 2 In Foo constructor: x = 2 In Foo constructor: x = 2 In Foo constructor: x = 2 In Foo constructor: x = 2 size: 5 capacity 5 // cont1.resize(8); 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 constructor: x = 2 In Foo constructor: x = 2 In Foo constructor: x = 2 In Foo destructor: x = 2 <-- old vector deleted In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 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 In Foo destructor: x = 2 <-- old vector deleted In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 size: 8 capacity 300 In Foo destructor: x = 2 <-- vector goes out of scope In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2 In Foo destructor: x = 2

Compiler #1

Compiler #2
(with dtor calls)

  // 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

  // std::vector<Foo> cont1(5);
In Foo constructor: x = 2
In Foo constructor: x = 2
In Foo constructor: x = 2
In Foo constructor: x = 2
In Foo constructor: x = 2

size: 5
capacity 5

  // cont1.resize(8);
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 constructor: x = 2
In Foo constructor: x = 2
In Foo constructor: x = 2
In Foo destructor: x = 2  <-- old vector deleted
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
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
In Foo destructor: x = 2  <-- old vector deleted
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
size: 8
capacity 300
In Foo destructor: x = 2  <-- vector goes out of scope
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2
In Foo destructor: x = 2

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:

Resizing to a smaller size will remove items from the end (destructors will be called).
Resizing to a larger size will cause items to be added to end (default constructor calls).
Capacity may be larger than size.
Capacity is usually not reduced when resizing to a smaller size. vector.end() returns a pointer (iterator) to the end of the elements, not the end of the container.

To trim excess capacity, use the swap trick or shrink-to-fit:

int main(void)
{
  int i;

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

    // Add 1000 elements
  for (i = 0; i < 1000; ++i)
    cont1.push_back(i);

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

    // Remove the last 950
  for (i = 0; i < 950; ++i)
    cont1.pop_back();

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

    // Swap "trick"
  std::vector<int>(cont1).swap(cont1);

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

  return 0;
}

Output:

size: 1000
capacity 1024
size: 50
capacity 1024
size: 50
capacity 50

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

An unnamed temporary std::vector<int> is constructed from cont1.
```
std::vector<int>(cont1)  // unnamed_temp
```
The swap method of the unnamed temporary is called with cont1 as the parameter.
```
unnamed_temp.swap(cont1);
```
The contents are swapped between the two containers.
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.

Newer C++ STL libraries have added a shrink_to_fit method to the std::vector class so the above is no longer necessary.

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:

The C++ Standard guarantees that vector elements are stored in contiguous memory (like C arrays).
You can't write into empty positions (size < capacity) because the internal data members won't get updated. (You can't use the subscript operator to add elements.)
Just like ordinary array manipulation, modifying the underlying array can be dangerous (it's up to the programmer to protect the data/memory).
Empty vectors may contain invalid pointers to data, so check the empty() method first.

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.

They are also array-based structures.
The act much like vectors and share a lot of the interface.
The primary difference is that deques can grow in both directions (from the front and back).
They provide additional methods push_front() and pop_front().
There is no reserve() or capacity() method, so no control over when reallocation occurs.
Unused space may be freed, so the allocated space for a deque may shrink. (Implementation dependent)
Inserting and deleting will invalidate pointers or iterators to the other elements.
- This is because you have no control over (or knowledge) of when a reallocation occurs.
- You must assume the worst, which is that an allocation has occurred.
- The exception to this rule is when an element is added to the end or the front.

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.

Lists are node-based structures, which is very different from vectors and deques.
Since there is no random-access methods (indexing), accessing an arbitrary element is expensive. (Linear time)
However, removing from the middle or inserting into the middle is inexpensive because only pointers need to be manipulated. (Constant time)
Inserting and deleting does not invalidate pointers or iterators to the other elements.
List also provides push_front() and pop_front() methods.
There is no reserve() or capacity() method, since they are not necessary.
Additional methods are available such as sort, merge, unique, and splice

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:

The list class is essentially an abstraction of a double linked-list.
There is no random access, so you can't use the subscript operator.
You must traverse the elements with iterators.
Adding/removing elements (anywhere in the list) is always done in constant time. However, locating the item/position requires linear time.

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

Iterators

Iterators provide a generic method for traversing the standard containers.

Iterators are objects (instantiated from classes) so they have an interface that clients can use.
All of the standard containers support iterators, so the code for accessing elements is similar between containers.
In keeping with abstraction, this hides the implementation details of the container. (e.g. Code for traversing an array is different than code for traversing a linked-list.)
An example of using iterators on a vector:

    // 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:

begin() Returns an iterator that references the first element in the container.
end() Returns an iterator that references one past the last element in the container.
*iter Returns the object referenced by iter.

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

There are several categories of iterators, each providing different capabilities:
- Input - Read only; Forward only. (Used for input streams)
- Output - Write only; Forward only. (Used for output streams)
- Forward - Read/Write; Can only move in one direction (forward) from one element to the next.
- Bidirectional - Read/Write; Can move forward and backward from one element to the next.
- Random Access - Read/Write; Can access any element at any time (from any other element).
Not all containers provide all types of iterators. (e.g. std::list doesn't provide random access)

Forward iterators have these capabilities:

Expression Result
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

Expression	Result
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:

Expression Result
--iter
Decrements the iterator (move back one). Returns decremented iterator.
iter--
Decrements the iterator (move back one). Returns previous non-decremented iterator.

Expression	Result
--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:

Use of the subscript operator for accessing any element.
iterator arithmetic (much like pointer arithmetic) for moving to any element, e.g.
```
iter + i;
iter - i;
iter += i;
```
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:

Example Container Iterator

vector, deque, string random access

list, set, map, multiset, multimap bidirectional

forward_list forward

istream input

ostream output

Example Container	Iterator
vector, deque, string	random access
list, set, map, multiset, multimap	bidirectional
forward_list	forward
istream	input
ostream	output

Iterator Types

The standard containers provide four types of iterators:

iterator - General iterator for read/write of non-const containers.
const_iterator - Used to traverse const containers for read-only access.
reverse_iterator - For traversing containers in reverse order (read/write)
const_reverse_iterator - For traversing containers in reverse order (read only)

Obviously, the reverse versions only work with bidirectional and random access 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:

Only handles integers, so we'd need one for every type we want to print:

void print1(std::vector<int>& v);
void print1(std::vector<double>& v);
void print1(std::vector<std::string>& v);
void print1(std::vector<Foo>& v);
...

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

Only handles vectors, so we'd need one for each container:

void print1(std::vector<int>& v);
void print1(std::list<int>& v);
void print1(std::deque<int>& v);
void print1(std::set<int>& v);
...
void print1(std::vector<double>& v);
void print1(std::list<double>& v);
void print1(std::deque<double>& v);
void print1(std::set<double>& v);
...

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:

We can handle any type of vector (provided the elements have overloaded operator<<).
We can handle vectors and deques.
But there is still a limitation.

Here's an example of that limitation:

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

  // Compiler error 
print3(cont1);

And this is the error message:

main.cpp(584) : error C2676: binary '[' : 'class std::list<class std::basic_string<char,
struct std::char_traits<char>,class std::allocator<char> >,class std::allocator<
class std::basic_string<char,struct std::char_traits<char>,class std::allocator<
char> > > >' does not define this operator or a conversion to a type acceptable to 
the predefined operator' 
main.cpp(614) : see reference to function template instantiation 'void __cdecl print3(class 
std::list<class std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::allocator<class std::basic_string<char,
struct std::char_traits<char>,class std::allocator<char> > > > &)' being compiled

It's not immediately obvious what the problem is, but the error message has enough information to figure it out.

We can only handle containers that overload operator[].
It iterator terminology, we can only deal with containers that provide random access to the elements.
To handle other iterators, we need to implement the function using iterators.

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:

The compiler shows a problem (undefined identifier):

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

Why do you think the compiler won't warn about the multiplication expression above? In other words, the compiler would warn about this:

int a = 5;
int b = 6;
a * b;      // statement has no effect

What's the difference?

Continuing with the example:

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

The function template std::make_pair is a convenience function that simply constructs a pair out of its two inputs.

What about using our print5 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 print5 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;
}

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. But, this is hardly a problem since printing to the screen requires operator<<.

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:

advance() - increments an iterator's position by a certain value.
distance() - returns the distance (in elements) between to iterators.
iter_swap() - exchanges the values of two iterators.

Declaration of advance():

template<class InIt, class Dist> void advance(InIt& it, Dist n);

Notes:

Moves the iterator forward or backward.
Random access and bidirectional iterators can move backward by specifying a negative distance value.
No error checking is done, so advancing past the end is undefined.
Efficiency for random-access iterators: constant time.
Efficiency for bidirectional iterators: linear time.
Efficiency for forward iterators: linear time.

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:

The problem is that we are adding to one iterator and subtracting from another.
These operations are only defined for random access iterators.
The iterators for a std::list are bidirectional, so they don't support iterator arithmetic.

We need to use a function like advance to perform the arithmetic:

  // Create(bidirectional) iterators. Same as list<string>::iterator
StrCont::iterator start = cont1.begin(); // initialize to beginning
StrCont::iterator end = cont1.begin();   // initialize to beginning

  // Increment iterator by 2. (Complexity now is linear)
std::advance(end, 2);

  // Create a copy using first 2 strings only
StrCont cont4(start, end);
print5(cont4);  // Output: one  two

start = cont1.end();  // Set start to end
end = cont1.end();    // Set end to end

  // Decrement iterator by 3
std::advance(start, -3);

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

Notice that using the technique above, the code can handle std::vector without modification and that the advance function has constant complexity.

Iterator Adapters

There are 3 general types of iterator adapters:

Insert iterators - Also called inserters, used to insert (rather than overwrite) elements in a container. If there is not enough space, new space is allocated on-the-fly.
Stream iterators - Iterators to read from a stream or write to a stream. Generally used for I/O.
Reverse iterators - They switch the increment operator to a decrement operator internally. These iterators require containers that have rbegin() and rend() methods.

Insert Iterators

There are 3 predefined inserters:

Front inserters - Prepend elements at the front of the container by calling push_front().
Back inserters - Append elements at the end of the container by calling push_back().
Inserters - Insert elements at a specified position by calling insert().

Example:

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

#include <iterator>// May 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:

front_inserter can only be used with containers that support the push_front() method.
back_inserter can only be used with containers that support the push_back() method.
You may need to include <iterator> to use the iterator adapters (older compilers).

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_));

`vector<type> v`		Defalut 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.