The string Class and STL Introduction

The string Class

C++ does not have a "built-in" string type like some languages.
C has the "NUL terminated array of character" string, which C++ also has.
Newer C++ implementations have a string class (in the std namespace)
The C++ std::string class is much safer, flexible, easier to use than const char * C-style types
More expensive (slower, requires more memory)
Generally, you trade speed for memory usage. You make the choice.

Using C-style (NUL-terminated) strings (static arrays).

Correct Incorrect

Correct	Incorrect
`#include <iostream> #include <string.h> void Concat1() { char s1[20]; // Magic number strcpy(s1, "The quick"); strcat(s1, " brown fox"); std::cout << s1 << std::endl; char s2[25]; // Magic number strcpy(s2, "jumped over"); strcat(s2, " the lazy"); strcat(s2, " dog"); std::cout << s2 << std::endl; char s3[45]; // Magic number strcpy(s3, s1); strcat(s3, " "); strcat(s3, s2); std::cout << s3 << std::endl; }`	`#include <iostream> #include <string.h> void Concat1() { char s1[10]; // Magic number strcpy(s1, "The quick"); strcat(s1, " brown fox"); std::cout << s1 << std::endl; char s2[20]; // Magic number strcpy(s2, "jumped over"); strcat(s2, " the lazy"); strcat(s2, " dog"); std::cout << s2 << std::endl; char s3[30]; // Magic number strcpy(s3, s1); strcat(s3, " "); strcat(s3, s2); std::cout << s3 << std::endl; }`

#include <iostream>
#include <string.h>

void Concat1()
{
  char s1[20]; // Magic number
  strcpy(s1, "The quick");
  strcat(s1, " brown fox");
  std::cout << s1 << std::endl;

  char s2[25]; // Magic number
  strcpy(s2, "jumped over");
  strcat(s2, " the lazy");
  strcat(s2, " dog");
  std::cout << s2 << std::endl;

  char s3[45]; // Magic number
  strcpy(s3, s1);
  strcat(s3, " ");
  strcat(s3, s2);
  std::cout << s3 << std::endl;
}

#include <iostream>
#include <string.h>

void Concat1()
{
  char s1[10]; // Magic number
  strcpy(s1, "The quick");
  strcat(s1, " brown fox");
  std::cout << s1 << std::endl;

  char s2[20]; // Magic number
  strcpy(s2, "jumped over");
  strcat(s2, " the lazy");
  strcat(s2, " dog");
  std::cout << s2 << std::endl;

  char s3[30]; // Magic number
  strcpy(s3, s1);
  strcat(s3, " ");
  strcat(s3, s2);
  std::cout << s3 << std::endl;
}

Output #1:

The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog

Output #2 (g++):

The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog
*** stack smashing detected ***: ./a.out terminated
Aborted

Output #3 (clang++):

The quick brown fox
jumped over the lazy dog
og jumped over the lazy dog
Segmentation fault

Using C-style (NUL-terminated) strings (dynamic arrays):

Correct Incorrect

Correct	Incorrect
#include <iostream> #include <string.h> void Concat2() { char s1 = new char[20]; // Magic number strcpy(s1, "The quick"); strcat(s1, " brown fox"); std::cout << s1 << std::endl; char s2 = new char[25]; // Magic number strcpy(s2, "jumped over"); strcat(s2, " the lazy"); strcat(s2, " dog"); std::cout << s2 << std::endl; char *s3 = new char[45]; // Magic number strcpy(s3, s1); strcat(s3, " "); strcat(s3, s2); std::cout << s3 << std::endl; // Don't forget! delete [] s1; delete [] s2; delete [] s3; }	#include <iostream> #include <string.h> void Concat2() { char s1 = new char[10]; // Magic number strcpy(s1, "The quick"); strcat(s1, " brown fox"); std::cout << s1 << std::endl; char s2 = new char[20]; // Magic number strcpy(s2, "jumped over"); strcat(s2, " the lazy"); strcat(s2, " dog"); std::cout << s2 << std::endl; char *s3 = new char[30]; // Magic number strcpy(s3, s1); strcat(s3, " "); strcat(s3, s2); std::cout << s3 << std::endl; // Don't forget! delete [] s1; delete [] s2; delete [] s3; }

#include <iostream>
#include <string.h>

void Concat2()
{
  char *s1 = new char[20]; // Magic number
  strcpy(s1, "The quick");
  strcat(s1, " brown fox");
  std::cout << s1 << std::endl;

  char *s2 = new char[25]; // Magic number
  strcpy(s2, "jumped over");
  strcat(s2, " the lazy");
  strcat(s2, " dog");
  std::cout << s2 << std::endl;

  char *s3 = new char[45]; // Magic number
  strcpy(s3, s1);
  strcat(s3, " ");
  strcat(s3, s2);
  std::cout << s3 << std::endl;

    // Don't forget!
  delete [] s1;
  delete [] s2;
  delete [] s3;
}

#include <iostream>
#include <string.h>

void Concat2()
{
  char *s1 = new char[10]; // Magic number
  strcpy(s1, "The quick");
  strcat(s1, " brown fox");
  std::cout << s1 << std::endl;

  char *s2 = new char[20]; // Magic number
  strcpy(s2, "jumped over");
  strcat(s2, " the lazy");
  strcat(s2, " dog");
  std::cout << s2 << std::endl;

  char *s3 = new char[30]; // Magic number
  strcpy(s3, s1);
  strcat(s3, " ");
  strcat(s3, s2);
  std::cout << s3 << std::endl;

    // Don't forget!
  delete [] s1;
  delete [] s2;
  delete [] s3;
}

Output #1:

The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog

Output #2: (Valgrind output)

The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog1
*** Error in `./a.out': free(): invalid next size (fast): 0x0000000001538c60 ***
Aborted

Using the string class:

#include <iostream>
#include <string>

void Concat3()
{
  std::string s1 = "The quick"; // Similar to std::string s1("The quick")
  s1 += " brown fox";
  std::cout << s1 << std::endl;

  std::string s2;
  s2 = s2 + "jumped over" + " the lazy" + " dog"; // How does this work?
  std::cout << s2 << std::endl;

  std::string s3 = s1 + " " + s2;
  std::cout << s3 << std::endl;
}

Output:

The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog

Notes:

The advantages of using the string class are numerous and obvious.

No danger of overflowing an array (static or dynamic).
Not possible to leak memory (dynamic).
Don't have to learn how to perform "normal" operations. (e.g. concatenation)
They are part of the standard library so they are available on every system.
They are mature, stable, bug-free, and likely to be more efficient than writing your own.

Constructors for the string Class

void Construct()
{
    // Create an empty string (default constructor)
  std::string s0;
  std::cout << s0 << std::endl;

    // Create a string from a const char * (conversion constructor)
  std::string s1("This is a string");
  std::cout << s1 << std::endl;

    // Create a string of chars
  std::string s2(10, '#');
  std::cout << s2 << std::endl;

    // Create a string from another string (copy constructor)
  std::string s3(s1);
  std::cout << s3 << std::endl;

    // Create a string from a char * and a count
  const char *p = "The quick brown fox";
  std::string s4(p, 9);
  std::cout << s4 << std::endl;

    // Create a string from a char * and a count
  std::string s5(p + 4, 5);
  std::cout << s5 << std::endl;

    // Create a string from two pointers (between, start ===> one-past-the-end)
  std::string s6(p + 10, p + 15);
  std::cout << "|" << s6 << "|" << std::endl;

    // Create a string from the entire range
  std::string s7(p, p + std::strlen(p));
  std::cout << "|" << s7 << "|" << std::endl;
}

Output:


This is a string
##########
This is a string
The quick
quick
|brown|
|The quick brown fox|

For reference:

The quick brown fox
^    ^    ^    ^
0    5    10   15

string Input

void Input()
{
  std::string s1;
  std::cout << "Enter a word: ";

    // Read one "word"
  std::cin >> s1;

  std::cout << s1 << std::endl;

    // Ignore the rest of the line
  while (std::cin.get() != '\n')
    continue;

  std::string s2;
  std::cout << "Enter several words: ";

    // Read up to the new line
  std::getline(std::cin, s2);
  std::cout << s2 << std::endl;
}

Output:

Enter a word: Hello
Hello
Enter several words: One two three four.
One two three four.

Note that it is virtually impossible to overwrite (corrupt) memory because the string will be sized automagically to accomodate all of the characters.

Other string Methods

void Test1()
{
  std::string s1 = "DigiPen";

    // Reading the length of a string
  std::cout << "Length of " << s1 << " is " << s1.size() << std::endl;

    // You can access the internal NUL terminated string
  std::cout << "Length of " << s1.c_str() << " is " << std::strlen(s1.c_str()) << std::endl;

    // Getting at individual characters
  std::cout << "The second char is: " << s1.at(1) << std::endl;
  std::cout << "The second char is: " << s1[1] << std::endl;

    // Finding substrings
  unsigned long position = s1.find("Pen");
  if (position != std::string::npos)
    std::cout << s1.substr(position) << std::endl;
}

Output:

Length of DigiPen is 7
Length of DigiPen is 7
The second char is: i
The second char is: i
Pen

Difference between the subscript operator and the at() method:

void At()
{
  std::string s1 = "DigiPen";

    // Retrieves garbage
  std::cout << "The tenth char is: " << s1[9] << std::endl;

    // Throws an exception
  std::cout << "The tenth char is: " << s1.at(9) << std::endl;
}

Output:

The tenth char is: Ś
 12152 [sig] a 2416 open_stackdumpfile: Dumping stack trace to a.exe.stackdump
 12152 [sig] a 2416 open_stackdumpfile: Dumping stack trace to a.exe.stackdump

Catching the exception:

void At2()
{
  std::string s1 = "DigiPen";
  try 
  {
      // Throws an exception
    std::cout << "The tenth char is: " << s1.at(9) << std::endl;
  }
  catch (const std::exception &e)
  {
    std::cout << e.what() << std::endl;
  }
}

Output:

basic_string::at

There are lots of methods available in the string class to do things such as:

deleting all or part of a string
replacing all or part of a string with all or part of another string
comparing all or part of a string with all or part of another string
extracting substrings
copying substrings
just about anything else you'd need

The string class is just a typedef of a templatized basic_string class:

template <typename CharType, typename Attr = char_traits<CharType>, typename Allocator = allocator<CharType> >
class basic_string
{
  // ...
};

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;

A quick reference for string.
More references here.

STL Components

Several components make up the Standard Template Library. Three main components 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 data structure.
- The different kinds of containers reflect the different implementations and uses.
- Containers include things such as vector, list, deque, string, set, map.
- They are all class templates.
Algorithms
- Algorithms are applied to containers (actually, ranges within containers) to process the elements.
- There are algorithms to search, sort, count, 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.
- They are all function templates.
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 linked list vs. the next element in a tree, etc.)
- Iterators are the "glue" between containers and algorithms.

Containers

The STL includes containers such as arrays, stacks, queues, linked lists, etc.
A very common container is the vector (sort of like a dynamic array).
Just include <vector> to use it.

Creating a simple vector of integers and then resizing the vector:


void VecStuff()
{
  int SIZE = 5;
  std::vector<int> numbers(SIZE);  // create a vector of integers (5), all initialized to 0
  for (int i = 0; i < SIZE; i++)   // assign values to each element
    numbers[i] = i * 10;

  numbers.resize(numbers.size() * 2);  // "grow" the vector twice as big (10)

  for (int i = 0; i < SIZE * 2; i++)       // print out all elements
    std::cout << numbers[i] << std::endl;

  for (int i = SIZE; i < SIZE * 2; i++)    // assign values to the new elements
    numbers[i] = i * 100;

  for (int i = 0; i < SIZE * 2; i++)       // print out all elements
    std::cout << numbers[i] << std::endl;
}

Output:

Another example:


    // 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
    // The complexity of vector::size()
  for (unsigned 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 (unsigned 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

Revisiting a previous example: (Linked list version)

Comparing arrays and vectors: Reading integers from a file into an array.

Allocate an array to hold the numbers
Open a file for reading
While there are more numbers in the file
1. Read in a number
2. Add it to the end of the array
Close the file

Using an array Using a std::vector

void get_numbers1() { int numbers[30]; // Holds at most 30 integers int count = 0; // Open text file of numbers for reading FILE *fp = fopen("numbers.txt", "r"); if (!fp) std::cout << "Can't open file.\n"; // Process the entire file while (!feof(fp)) { int number; // Read next integer from the file if (fscanf(fp, "%i", &number) == 0) break; // Add number to the end of the array numbers[count++] = number; } // Close the file fclose(fp); // Print the array print_array(numbers, count); }

void get_numbers2() { std::vector<int> numbers; // Unlimited! // Open text file of numbers for reading FILE *fp = fopen("numbers.txt", "r"); if (!fp) std::cout << "Can't open file.\n"; // Process the entire file while (!feof(fp)) { int number; // Read next integer from the file if (fscanf(fp, "%i", &number) == 0) break; // Add number to the end of the vector numbers.push_back(number); } // Close the file fclose(fp); // Print the vector print_vector(numbers); }

These are the caveats that were discussed when using arrays:

Using an array	Using a `std::vector`
void get_numbers1() { int numbers[30]; // Holds at most 30 integers int count = 0; // Open text file of numbers for reading FILE fp = fopen("numbers.txt", "r"); if (!fp) std::cout << "Can't open file.\n"; // Process the entire file* while (!feof(fp)) { int number; // Read next integer from the file if (fscanf(fp, "%i", &number) == 0) break; // Add number to the end of the array numbers[count++] = number; } // Close the file fclose(fp); // Print the array print_array(numbers, count); }	void get_numbers2() { std::vector<int> numbers; // Unlimited! // Open text file of numbers for reading FILE fp = fopen("numbers.txt", "r"); if (!fp) std::cout << "Can't open file.\n"; // Process the entire file* while (!feof(fp)) { int number; // Read next integer from the file if (fscanf(fp, "%i", &number) == 0) break; // Add number to the end of the vector numbers.push_back(number); } // Close the file fclose(fp); // Print the vector print_vector(numbers); }

Of course, if there are more than 30 numbers, we are going to overwrite the end of the array.
Possible "fixes":

Don't read in more than 30 numbers.
Set the size of the array to more than 30 (and hope it's big enough or waste a lot of space)
Allocate the array at runtime. (Still need a size.) Choices:

Put the size in the file. (Maybe the first line contains the number of integers.) Allocate the array when the size is known.
When the array is full, allocate another, bigger array, and copy old values into it. This may need to be done many times.
Don't forget to free any memory that was allocated or else there will be a memory leak.

None of these "problems" exist with the vector because a vector implements #2 above.

Creating a vector of strings:

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

void Vector2()
{
  int SIZE = 6;
  std::vector<std::string> speeds(SIZE); // create a vector of strings (6)

  speeds[0] = "Snail (slowest)";         // assign values to each element
  speeds[1] = "Turtle (slower)";
  speeds[2] = "Penguin (slow)";
  speeds[3] = "Rabbit (fast)";
  speeds[4] = "Lion (faster)";
  speeds[5] = "Cheetah (fastest)";

    // Display each speed that contains the substring "fast"
  for (int i = 0; i < SIZE; i++)
    if (speeds[i].find("fast") != std::string::npos)
      std::cout << speeds[i] << std::endl;

}

Output:

Rabbit (fast)
Lion (faster)
Cheetah (fastest)

Other popular methods for vector (including their runtime complexity):

push_back() Add an element to the end. (Constant time if the array has room. Linear time if the array has to be grown.)
pop_back() Removes the last element. (Constant time. Nothing is actually "removed".)
insert() Add at a particular position. (Linear time)
begin() and end() Return iterators(pointers) to the first element and one-past-the-last element, respectively. (Constant time)
erase() Deletes an element or range of elements. All elements may need to be shifted; Capacity is not reduced. (Linear time)
clear() Deletes all elements. Capacity may or may not be reduced. (Linear time)
empty() Returns true if the vector is empty, otherwise false. (Constant time)
operator[] and at() Get/Set an element by index. (Constant time)
- The overloaded subscript operator for reading/writing to the vector doesn't throw an exception 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 an exception when subscript is out of range.
front() and back() Return the first and last element, respectively. (Constant time)
size() Returns the number of elements in the vector. (Constant time)
capacity() Returns the number of elements that can be placed in the vector without growing the vector. (Constant time)
swap() Exchanges the elements of two vectors. (Constant time. How can that be?)

Features

Use a vector when you need array semantics (random access for reading/writing and you're adding at the back of the vector).
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.

Some constructors:

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

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()
{
  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).

A quick reference for vector.

Lists

An STL list is a doubly linked-list. Add this header file:

#include <list>

Lists are node-based structures, which is very different from vectors (which are array-based).
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 (which are missing in vectors).

Vectors can't perform these operations in constant time, so they don't exist.
You can use insert with a vector to mimic push_front.

There is no reserve() or capacity() method, since they are not necessary.

Example: We will need these headers:

#include <iostream>
#include <list>
#include <string>

First, create a list and add some strings:

int main()
{
    // 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

Self-check: If we have a list of strings, how can we get away with passing const char pointers instead?

To print out the items, we might try this:

  // Print out the elements using subscripts like with vector
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)

In function `int main()':
error: no match for 'operator[]' in 'cont1[i]'

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() << "  "; // Read first element
  cont1.pop_front();                  // Remove first element
}
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.
Iterators overload operator++, which simply moves to the next element (whatever that means).
Adding/removing elements (anywhere in the list) is always done in constant time.

Unlike vectors, you don't need to shift any elements. (This can be a big win.)
However, locating the item/position requires linear time (no random access).

A quick reference for list.

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.
An iterator is generally just a wrapper around a pointer (with all of the appropriate operators overloaded).
All of the standard containers support iterators, so the code for accessing elements is similar (if not identical) 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 empty vector
  std::vector<int> cont1;

    // Add 5 elements (grows automatically)
  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 CS170
{
  class Foo
  {
    public:
      typedef int FooInt;   // public typedef
  };
}

Now we can use the typedef:

  // Declare variable 'i' as type CS170::Foo::FooInt
CS170::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:
      class vector_iterator
      {
        // ...
      };

      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:

  // 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 (Not genetic 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;

This is HUGE!

Introduction to Using Generic Algorithms

The algorithms of the Standard Template Library are also known as the generic algorithms because they are designed and implemented to work with the standard containers.

The generic algorithms typically work with a contiguous set of elements from a container called a range or a sequence.
These ranges are delimited by iterators. (e.g. begin() to end(). This is the largest range in a container)
Many algorithms have default behavior, so you only need to specify the range.
You can change the behavior of an algorithm by supplying additional optional parameters.
Algorithms behave in different ways. For example some are read-only (with respect to the elements), some modify elements, and some change the order of the elements.
The generic algorithms can be loosely classified into several categories:
1. Non-modifying Does not change any elements nor the order of the elements in the container. Counting, searching, comparing. (ex. find)
2. Modifying Changes the value of the elements. Transforming, generating, etc. (ex. transform)
3. Removing Removes elements from the container.(ex. remove)
4. Mutating Changes the order of the elements in the container. Reversing, rotating, shuffling. (ex. reverse)
5. Sorting Similar to mutating algorithms, but more complicated. (ex. sort)
6. Sorted range Assumes that the range to operate on is already sorted. (ex. binary_search)
7. Numeric Acts on numerical elements and combines them based on a specified function. Sums, products. (ex. accumulate)

As of June 2022, there are 85 generic algorithms in the STL. Algorithms reference

New code is the source of 99% of the bugs in your program. If you don't write new code then you won't have any bugs!

This is a partial list of algorithms:

Non-modifying Modifying Removing Mutating

for_each, count, count_if, min_element, max_element, find, find_if, search_n, search, find_end, find_first_of, adjacent_find, equal, mismatch, lexicographical_compare for_each, copy, copy_backward, transform, merge, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, replace_copy, replace_copy_if remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy reverse, reverse_copy, rotate, rotate_copy, next_permutation, prev_permutation, random_shuffle, partition, stable_partition

Non-modifying	Modifying	Removing	Mutating
for_each, count, count_if, min_element, max_element, find, find_if, search_n, search, find_end, find_first_of, adjacent_find, equal, mismatch, lexicographical_compare	for_each, copy, copy_backward, transform, merge, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, replace_copy, replace_copy_if	remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy	reverse, reverse_copy, rotate, rotate_copy, next_permutation, prev_permutation, random_shuffle, partition, stable_partition

Sorting Sorted range Numeric

sort, stable_sort, partial_sort, partial_sort_copy, nth_element, partition, stable_partition, make_heap, push_heap, pop_heap, sort_heap binary_search, includes, lower_bound, upper_bound, equal_range, merge, set_union, set_intersection, set_difference, set_symmetric_difference, inplace_merge accumulate, inner_product, adjacent_difference, partial_sum

Sorting	Sorted range	Numeric
sort, stable_sort, partial_sort, partial_sort_copy, nth_element, partition, stable_partition, make_heap, push_heap, pop_heap, sort_heap	binary_search, includes, lower_bound, upper_bound, equal_range, merge, set_union, set_intersection, set_difference, set_symmetric_difference, inplace_merge	accumulate, inner_product, adjacent_difference, partial_sum

Some simple examples: (Note the magic Print5 function)

#include <iostream>
#include <vector>
#include <algorithm>

void f1()
{
    // Container of integers and an iterator
  std::vector<int> cont1;
  std::vector<int>::iterator iter;

    // Add some integers
  cont1.push_back(5);
  cont1.push_back(7);
  cont1.push_back(3);
  cont1.push_back(8);
  cont1.push_back(7);
  cont1.push_back(1);

    // Print the container
    // 5  7  3  8  7  1
  print5(cont1); 

    // Find the maximum and print
    // Max: 8
  iter = std::max_element(cont1.begin(), cont1.end());
  std::cout << "Max: " << *iter << std::endl;

    // Find the minimum and print
    // Min: 1
  iter = std::min_element(cont1.begin(), cont1.end());
  std::cout << "Min: " << *iter << std::endl;

    // Find the first occurrence of the value 7  
    // Value 7 found.
  iter = std::find(cont1.begin(), cont1.end(), 7);
  if (iter != cont1.end())
    std::cout << "Value " << *iter << " found." << std::endl;

    // Find the second occurrence of the value 7  
    // Value 7 found.
  iter = std::find(++iter, cont1.end(), 7);
  if (iter != cont1.end())
    std::cout << "Value " << *iter << " found." << std::endl;

    // Reverse the elements and print
    // Reversed:  1  7  8  3  7  5
  std::reverse(cont1.begin(), cont1.end());
  std::cout << "     Reversed:  ";
  print5(cont1); 

    // Sort the elements and print
    // Sorted:  1  3  5  7  7  8
  std::sort(cont1.begin(), cont1.end());  // requires operator< and operator[]
  std::cout << "       Sorted:  ";
  print5(cont1);

    // Reverse the first 3 and print
    // Reverse 1st 3:  5  3  1  7  7  8
  std::reverse(cont1.begin(), cont1.begin() + 3);
  std::cout << "Reverse 1st 3:  ";
  print5(cont1); 
}

Output:

5  7  3  8  7  1
Max: 8
Min: 1
Value 7 found.
Value 7 found.
     Reversed:  1  7  8  3  7  5
       Sorted:  1  3  5  7  7  8
Reverse 1st 3:  5  3  1  7  7  8

Notes

Almost all algorithms take a range as their first two parameters.
The range is actually the first element to process and one after the last element to process.(This mimics how end() works.)
This is called a left-inclusive or half-open range and is noted like this:
[first, last)
Many algorithms require a comparison function such as the less-than operator.
Some algorithms require iterators with certain functionality, e.g. sort requires random-access (subscript operator).
Notice the lack of any apparent looping or iteration in the code.

Algorithms with Multiple Ranges

Some algorithms take multiple ranges as parameters.
This is usually because these algorithms need to operate on multiple containers.
For example, comparing elements in two containers, copying from one container to another, etc.
Usually, you specify the [first, last) elements of the first container and only the first element of the second container. (The size of the second range is implied by the first range.)
No range checking is done on the second container, so you must ensure that it has enough room.

Example: Comparing two vectors:

void f2()
{
    // Containers of integers
  std::vector<int> cont1, cont2;
  int i, size = 10;

    // Populate both with identical elements
  for (i = 0; i < size; i++)
  {
    cont1.push_back(i);
    cont2.push_back(i);
  }

    // See if the containers are the same (must be same size)
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) )
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;

    // Using the overloaded '==' operator for vectors
  if (cont1 == cont2)
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;

    // Change the first element in cont1
  cont1[0] = 100;

    // See if the containers are the same (must be same size)
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) )
    std::cout << "cont1 and cont2 are equal" << std::endl;
  else
    std::cout << "cont1 and cont2 are NOT equal" << std::endl;
}

Output:

cont1 and cont2 are equal
cont1 and cont2 are equal
cont1 and cont2 are NOT equal

A better (safer) way to check for equality would be something like this:

if ( cont1.size() == cont2.size() &&
     std::equal(cont1.begin(), cont1.end(), cont2.begin()) )

If there are more elements in the second container than the first, they are simply ignored.
Algorithms may be needed instead of built-in operators (such as the equality '= =' operator above).

Note that if we changed one of the containers (so they are different):

  // List/vector of integers
std::vector<int> cont1;
std::list<int> cont2;

this still works just fine:

std::equal(cont1.begin(), cont1.end(), cont2.begin())

However, this will no longer work. Why?

(cont1 == cont2)

What are the issues when comparing the following containers for equality? (In other words, exactly why won't it compile?)

std::vector<int> cont1;     // Vector of integers
std::vector<string> cont2;  // Vector of strings

As stated above, this is HUGE!

Example: Copying between different containers

void f4()
{
    // List/vector of integers
  std::vector<int> cont1;
  std::list<int> cont2;
  int i, size = 10;

    // Populate 
  for (i = 0; i < size; i++)
    cont1.push_back(i);

    // Make sure there is enough room in the list (elements initialized to 0)
  cont2.resize(cont1.size());

    // Copy all elements from vector to list
  std::copy(cont1.begin(), cont1.end(), cont2.begin());

    // Create a deque same size as list (elements initialized to 0)
  std::deque<int> cont3(cont2.size());

    // Copy all elements from list into deque
  std::copy(cont2.begin(), cont2.end(), cont3.begin());

    // Print the containers
  print5(cont1);
  print5(cont2);
  print5(cont3);

    // See if the containers are the same
  if ( std::equal(cont1.begin(), cont1.end(), cont2.begin()) &&
       std::equal(cont2.begin(), cont2.end(), cont3.begin()) 
     )
    std::cout << "All containers are the same" << std::endl;
  else
    std::cout << "The containers are NOT the same" << std::endl;
  
}

Output:

0  1  2  3  4  5  6  7  8  9
0  1  2  3  4  5  6  7  8  9
0  1  2  3  4  5  6  7  8  9
All containers are the same

An example using for_each and modifying it's behavior:

#include <iostream>
#include <vector>
#include <algorithm>

void Print(int value)
{
  std::cout << value << " ";
}

void PrintVec(const std::vector<int> &vec)
{
  std::vector<int>::const_iterator iter;
  for (iter = vec.begin(); iter != vec.end(); ++iter)
    Print(*iter);

  std::cout << std::endl;
}

int main()
{
    // Create an empty vector of integers
  std::vector<int> nums;

    // Put 10 random integers in the vector
  for (int i = 0; i < 10; i++)
    nums.push_back(rand() % 100);

    // Pass the vector to a function to print
  PrintVec(nums);

    // Sort the vector
  std::sort(nums.begin(), nums.end());

    // Pass each element of the vector to a function to print
  std::for_each(nums.begin(), nums.end(), Print);  
  
  return 0;
}

Output:
41 67 34 0 69 24 78 58 62 64
0 24 34 41 58 62 64 67 69 78

Templates


#include <iostream>
#include <vector>
#include <algorithm>

template <typename T>
void Print(T value)
{
  std::cout << value << " ";
}

template <typename T>
void PrintVec(const std::vector<T> &vec)
{
  std::vector<T>::const_iterator iter;
  for (iter = vec.begin(); iter != vec.end(); ++iter)
    Print(*iter);

  std::cout << std::endl;
}

int main()
{
    // Create an empty vector of integers
  std::vector<int> nums;

    // Put 10 random integers in the vector
  for (int i = 0; i < 10; i++)
    nums.push_back(rand() % 100);

    // Pass the vector to a template function to print
  PrintVec(nums);

    // Sort the vector
  std::sort(nums.begin(), nums.end());

    // Pass each element of the vector to a template function to print
  std::for_each(nums.begin(), nums.end(), Print<int>);
  
  return 0;
}

Output:
41 67 34 0 69 24 78 58 62 64
0 24 34 41 58 62 64 67 69 78

Since the PrintVec function is redundant (due to the for_each function) we can just remove it.

template <typename T>
void Print(T value)
{
  std::cout << value << " ";
}

int main()
{
    // Create an empty vector of integers
  std::vector<int> nums;

    // Put 10 random integers in the vector
  for (int i = 0; i < 10; i++)
    nums.push_back(std::rand() % 100);

    // Pass each element of the vector to a template function to print
  std::for_each(nums.begin(), nums.end(), Print<int>);
  std::cout << std::endl;

    // Sort the vector
  std::sort(nums.begin(), nums.end());

    // Pass each element of the vector to a template function to print
  std::for_each(nums.begin(), nums.end(), Print<int>);
  std::cout << std::endl;
  
  return 0;
}

Client code using a vector of string:



int main()
{
    // Create an empty vector of strings
  std::vector<std::string> critters;

  critters.push_back("Snail");   
  critters.push_back("Turtle");
  critters.push_back("Penguin");
  critters.push_back("Rabbit");
  critters.push_back("Lion");
  critters.push_back("Cheetah");

    // Pass each element of the vector to a template function to print
  std::for_each(critters.begin(), critters.end(), Print<std::string>);
  std::cout << std::endl;

    // Sort the vector
  std::sort(critters.begin(), critters.end());

    // Pass each element of the vector to a template function to print
  std::for_each(critters.begin(), critters.end(), Print<std::string>);
  std::cout << std::endl;
  
  return 0;
}

Output:

Snail Turtle Penguin Rabbit Lion Cheetah
Cheetah Lion Penguin Rabbit Snail Turtle

Algorithms reference

Other Examples

Interface to our Employee class: Employee.h

Data in file employees1.txt: (lastName_, firstName_, salary_, years_)

Faith Ian 80000 10
Tufnel Nigel 90000 12
Savage Viv 50000 4
Shrimpton Mick 50000 4
Besser Joe 40000 1
Smalls Derek 80000 10
St.Hubbins David 90000 12
Fleckman Bobbi 120000 8
Upham Danny 60000 5
McLochness Ross 60000 5
Pudding Ronnie 50000 2
Schindler Danny 60000 3

Code using vector Output

void f3() { std::ifstream infile("employees1.txt"); if (!infile.is_open()) std::cout << "Can't open file.\n"; else { std::vector<Employee> Emps; while (!infile.eof()) { std::string first, last; float salary; int years; // Read in data (assume valid data file) infile >> last; if (infile.eof()) break; infile >> first; infile >> salary; infile >> years; // Construct an Employee object Employee emp(first, last, salary, years); // Add it to the vector Emps.push_back(emp); } // Print out all of the objects // Assume there is a PrintEmp function std::for_each(Emps.begin(), Emps.end(), PrintEmp); } }

Name: Faith, Ian Salary: $80000.00 Years: 10 Name: Tufnel, Nigel Salary: $90000.00 Years: 12 Name: Savage, Viv Salary: $50000.00 Years: 4 Name: Shrimpton, Mick Salary: $50000.00 Years: 4 Name: Besser, Joe Salary: $40000.00 Years: 1 Name: Smalls, Derek Salary: $80000.00 Years: 10 Name: St.Hubbins, David Salary: $90000.00 Years: 12 Name: Fleckman, Bobbi Salary: $120000.00 Years: 8 Name: Upham, Danny Salary: $60000.00 Years: 5 Name: McLochness, Ross Salary: $60000.00 Years: 5 Name: Pudding, Ronnie Salary: $50000.00 Years: 2 Name: Schindler, Danny Salary: $60000.00 Years: 3

Adding some code to sort the data before printing it:

Code using `vector`	Output
void f3() { std::ifstream infile("employees1.txt"); if (!infile.is_open()) std::cout << "Can't open file.\n"; else { std::vector<Employee> Emps; while (!infile.eof()) { std::string first, last; float salary; int years; // Read in data (assume valid data file) infile >> last; if (infile.eof()) break; infile >> first; infile >> salary; infile >> years; // Construct an Employee object Employee emp(first, last, salary, years); // Add it to the vector Emps.push_back(emp); } // Print out all of the objects // Assume there is a PrintEmp function std::for_each(Emps.begin(), Emps.end(), PrintEmp); } }	Name: Faith, Ian Salary: $80000.00 Years: 10 Name: Tufnel, Nigel Salary: $90000.00 Years: 12 Name: Savage, Viv Salary: $50000.00 Years: 4 Name: Shrimpton, Mick Salary: $50000.00 Years: 4 Name: Besser, Joe Salary: $40000.00 Years: 1 Name: Smalls, Derek Salary: $80000.00 Years: 10 Name: St.Hubbins, David Salary: $90000.00 Years: 12 Name: Fleckman, Bobbi Salary: $120000.00 Years: 8 Name: Upham, Danny Salary: $60000.00 Years: 5 Name: McLochness, Ross Salary: $60000.00 Years: 5 Name: Pudding, Ronnie Salary: $50000.00 Years: 2 Name: Schindler, Danny Salary: $60000.00 Years: 3

  // After reading in the data, sort the data and print it.
std::sort(Emps.begin(), Emps.end());
std::for_each(Emps.begin(), Emps.end(), PrintEmp);

But the call to sort causes an error. How do you sort Employees?

We need to overload the less-than operator. (Arbitrarily sort on the last name):

bool Employee::operator<(const Employee& rhs) const
{
    // Sort by last name
  return lastName_ < rhs.lastName_;
}

Now, the code works and we get this as output:

Sort by last name	Sort by first name	Sort by salary
Name: Besser, Joe Salary: $40000.00 Years: 1 Name: Faith, Ian Salary: $80000.00 Years: 10 Name: Fleckman, Bobbi Salary: $120000.00 Years: 8 Name: McLochness, Ross Salary: $60000.00 Years: 5 Name: Pudding, Ronnie Salary: $50000.00 Years: 2 Name: Savage, Viv Salary: $50000.00 Years: 4 Name: Schindler, Danny Salary: $60000.00 Years: 3 Name: Shrimpton, Mick Salary: $50000.00 Years: 4 Name: Smalls, Derek Salary: $80000.00 Years: 10 Name: St.Hubbins, David Salary: $90000.00 Years: 12 Name: Tufnel, Nigel Salary: $90000.00 Years: 12 Name: Upham, Danny Salary: $60000.00 Years: 5	Name: Fleckman, Bobbi Salary: $120000.00 Years: 8 Name: Upham, Danny Salary: $60000.00 Years: 5 Name: Schindler, Danny Salary: $60000.00 Years: 3 Name: St.Hubbins, David Salary: $90000.00 Years: 12 Name: Smalls, Derek Salary: $80000.00 Years: 10 Name: Faith, Ian Salary: $80000.00 Years: 10 Name: Besser, Joe Salary: $40000.00 Years: 1 Name: Shrimpton, Mick Salary: $50000.00 Years: 4 Name: Tufnel, Nigel Salary: $90000.00 Years: 12 Name: Pudding, Ronnie Salary: $50000.00 Years: 2 Name: McLochness, Ross Salary: $60000.00 Years: 5 Name: Savage, Viv Salary: $50000.00 Years: 4	Name: Besser, Joe Salary: $40000.00 Years: 1 Name: Savage, Viv Salary: $50000.00 Years: 4 Name: Shrimpton, Mick Salary: $50000.00 Years: 4 Name: Pudding, Ronnie Salary: $50000.00 Years: 2 Name: Upham, Danny Salary: $60000.00 Years: 5 Name: McLochness, Ross Salary: $60000.00 Years: 5 Name: Schindler, Danny Salary: $60000.00 Years: 3 Name: Faith, Ian Salary: $80000.00 Years: 10 Name: Smalls, Derek Salary: $80000.00 Years: 10 Name: Tufnel, Nigel Salary: $90000.00 Years: 12 Name: St.Hubbins, David Salary: $90000.00 Years: 12 Name: Fleckman, Bobbi Salary: $120000.00 Years: 8

Sort by last name

Sort by first name

Sort by salary

  Name: Besser, Joe
Salary: $40000.00
 Years: 1
  Name: Faith, Ian
Salary: $80000.00
 Years: 10
  Name: Fleckman, Bobbi
Salary: $120000.00
 Years: 8
  Name: McLochness, Ross
Salary: $60000.00
 Years: 5
  Name: Pudding, Ronnie
Salary: $50000.00
 Years: 2
  Name: Savage, Viv
Salary: $50000.00
 Years: 4
  Name: Schindler, Danny
Salary: $60000.00
 Years: 3
  Name: Shrimpton, Mick
Salary: $50000.00
 Years: 4
  Name: Smalls, Derek
Salary: $80000.00
 Years: 10
  Name: St.Hubbins, David
Salary: $90000.00
 Years: 12
  Name: Tufnel, Nigel
Salary: $90000.00
 Years: 12
  Name: Upham, Danny
Salary: $60000.00
 Years: 5

  Name: Fleckman, Bobbi
Salary: $120000.00
 Years: 8
  Name: Upham, Danny
Salary: $60000.00
 Years: 5
  Name: Schindler, Danny
Salary: $60000.00
 Years: 3
  Name: St.Hubbins, David
Salary: $90000.00
 Years: 12
  Name: Smalls, Derek
Salary: $80000.00
 Years: 10
  Name: Faith, Ian
Salary: $80000.00
 Years: 10
  Name: Besser, Joe
Salary: $40000.00
 Years: 1
  Name: Shrimpton, Mick
Salary: $50000.00
 Years: 4
  Name: Tufnel, Nigel
Salary: $90000.00
 Years: 12
  Name: Pudding, Ronnie
Salary: $50000.00
 Years: 2
  Name: McLochness, Ross
Salary: $60000.00
 Years: 5
  Name: Savage, Viv
Salary: $50000.00
 Years: 4

  Name: Besser, Joe
Salary: $40000.00
 Years: 1
  Name: Savage, Viv
Salary: $50000.00
 Years: 4
  Name: Shrimpton, Mick
Salary: $50000.00
 Years: 4
  Name: Pudding, Ronnie
Salary: $50000.00
 Years: 2
  Name: Upham, Danny
Salary: $60000.00
 Years: 5
  Name: McLochness, Ross
Salary: $60000.00
 Years: 5
  Name: Schindler, Danny
Salary: $60000.00
 Years: 3
  Name: Faith, Ian
Salary: $80000.00
 Years: 10
  Name: Smalls, Derek
Salary: $80000.00
 Years: 10
  Name: Tufnel, Nigel
Salary: $90000.00
 Years: 12
  Name: St.Hubbins, David
Salary: $90000.00
 Years: 12
  Name: Fleckman, Bobbi
Salary: $120000.00
 Years: 8

Sort by first name:

bool Employee::operator<(const Employee& rhs) const
{
  return firstName_ < rhs.firstName_;
}

Sort by salary:

bool Employee::operator<(const Employee& rhs) const
{
  return salary_ < rhs.salary_;
}

Sort by first name and last name:

bool Employee::operator<(const Employee& rhs) const
{
  if (firstName_ == rhs.firstName_)
    return lastName_ < rhs.lastName_;
  else
    return firstName_ < rhs.firstName_;
}

or you could do this: (less efficient)

bool Employee::operator<(const Employee& rhs) const
{
  return (firstName_ + lastName_) < (rhs.firstName_ + rhs.lastName_);
}

Allowing the client to choose the sort order:

bool CompareByYear(const Employee& emp1, const Employee& emp2)
{
  return emp1.getYears() < emp2.getYears();
}

bool CompareBySalary(const Employee& emp1, const Employee& emp2)
{
  return emp1.getSalary() < emp2.getSalary();
}

bool CompareByName(const Employee& emp1, const Employee& emp2)
{
  return (emp1.getLastName() + emp1.getFirstName()) < (emp2.getLastName() + emp2.getFirstName());
}

Calling sort:

  // Sort by year
std::sort(Emps.begin(), Emps.end(), CompareByYear);

  // Sort by salary
std::sort(Emps.begin(), Emps.end(), CompareBySalary);

  // Sort by name
std::sort(Emps.begin(), Emps.end(), CompareByName);

Changing vector to list causes errors. How do you sort a list?

std::list<Employee> Emps;

  // read in the data

std::sort(Emps.begin(), Emps.end());  // ERROR!

std::sort requires a random access iterator (a subscript operator), which a list doesn't have. You must use the sort method of the list class:

Emps.sort();                 // use Employee::operator<
Emps.sort(CompareBySalary);  // use compare function
Emps.sort(CompareByYears);   // use compare function

Use a std::set:

  // use a set (sorted container)  
  // use a set (sorted container)  
std::set<Employee> Emps;
while (!infile.eof())
{
  std::string first, last;
  float salary;
  int years;

    // Assume valid data file
  infile >> last;
  if (infile.eof())
    break;

  infile >> first;
  infile >> salary;
  infile >> years;

  Employee emp(first, last, salary, years);
  Emps.insert(emp);  // Uses Employee::operator<
}
  // Display (already sorted)
std::for_each(Emps.begin(), Emps.end(), PrintEmp);

Output: (Employee::operator< is set to sort on first/last name)

  Name: Fleckman, Bobbi
Salary: $120000.00
 Years: 8
  Name: Schindler, Danny
Salary: $60000.00
 Years: 3
  Name: Upham, Danny
Salary: $60000.00
 Years: 5
  Name: St.Hubbins, David
Salary: $90000.00
 Years: 12
  Name: Smalls, Derek
Salary: $80000.00
 Years: 10
  Name: Faith, Ian
Salary: $80000.00
 Years: 10
  Name: Besser, Joe
Salary: $40000.00
 Years: 1
  Name: Shrimpton, Mick
Salary: $50000.00
 Years: 4
  Name: Tufnel, Nigel
Salary: $90000.00
 Years: 12
  Name: Pudding, Ronnie
Salary: $50000.00
 Years: 2
  Name: McLochness, Ross
Salary: $60000.00
 Years: 5
  Name: Savage, Viv
Salary: $50000.00
 Years: 4

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