The string Class and STL Introduction

The string Class

Using C-style (NUL-terminated) strings (static arrays).
#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;
}
Output:
The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog
Using C-style (NUL-terminated) strings (dynamic arrays):
#include <iostream>
#include <string.h>

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

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

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

  delete[] s1;
  delete[] s2;
  delete[] s3;
}
Output:
The quick brown fox
jumped over the lazy dog
The quick brown fox jumped over the lazy dog
Using the string class:
#include <iostream>
#include <string>

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

  std::string s2;
  s2 = s2 + "jumped over" + " the lazy" + " dog";
  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

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

This is a string
##########
This is a string
The quick
quick
|brown|
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.

Other string Methods

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

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

    // You can access the internal NUL terminated string
  std::cout << "Length of " << s1.c_str() << " is " << 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 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[10] << std::endl;

    // Throws an exception
  std::cout << "The tenth char is: " << s1.at(10) << 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(10) << 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: 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.

STL Components

Several components make up the Standard Template Library. Three main components are:
  1. Containers

  2. Algorithms
  3. Iterators

Containers

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)
  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 (i = SIZE; i < SIZE * 2; i++)    // assign values to the new elements
    numbers[i] = i * 100;

  for (i = 0; i < SIZE * 2; i++)       // print out all elements
    std::cout << numbers[i] << endl;
}
Output:
0
10
20
30
40
500
600
700
800
900
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
  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.

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

Using an arrayUsing 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 the 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; // Holds unlimited integers


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

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:
    1. Put the size in the file. (Maybe the first line contains the number of integers.) Allocate the array when the size is known.
    2. When the array is full, allocate another, bigger array, and copy old values into it. This may need to be done many times.
    3. 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:

Features Some constructors:

vector<type> vDefault 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:

A quick reference for vector.

Lists

An STL list is a doubly linked-list. Add this header file:
#include <list>
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
Review Question: 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)
main.cpp: In function `int main()':
main.cpp:215: 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() << "  ";
  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:

A quick reference for list.

Iterators

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

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

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

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

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. As of April 2016, there are 85 generic algorithms in the STL.

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

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

Algorithms with Multiple Ranges


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


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

STL 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 vectorOutput
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:

  // 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 nameSort by first nameSort 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 this error. 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