Making and Using STL Objects

Read Chapter 2 for an introduction to basic STL classes and their application.

Introducing vector

With strings, we can fill up a string object without knowing how much storage we're going to need. The problem with reading lines from a file into individual string objects is that you don't know up front how many strings you're going to need – you only know after you've read the entire file. To solve this problem, we need some sort of holder that will automatically expand to contain as many string objects as we care to put into it.

In fact, why limit ourselves to holding string objects? It turns out that this kind of problem – not knowing how many of something you have while you're writing a program – happens a lot. And this "container" object sounds like it would be more useful if it would hold any kind of object at all! Fortunately, the Standard C++ Library has a ready-made solution: the standard container classes. The container classes are one of the real powerhouses of Standard C++.

There is often a bit of confusion between the containers and algorithms in the Standard C++ Library, and the entity known as the STL. The Standard Template Library was the name Alex Stepanov (who was working at Hewlett-Packard at the time) used when he presented his library to the C++ Standards Committee at the meeting in San Diego, California in Spring 1994. The name stuck, especially after HP decided to make it available for public downloads. Meanwhile, the committee integrated it into the Standard C++ Library, making a large number of changes. STL's development continues at Silicon Graphics (SGI; see http://www.sgi.com/Technology/STL). The SGI STL diverges from the Standard C++ Library on many subtle points. So although it's a popular misconception, the C++ Standard does not "include" the STL. It can be a bit confusing since the containers and algorithms in the Standard C++ Library have the same root (and usually the same names) as the SGI STL. In this book, I will say "The Standard C++ Library" or "The Standard Library containers," or something similar and will avoid the term "STL".

Even though the implementation of the Standard C++ Library containers and algorithms uses some advanced concepts and the full coverage takes two large chapters in Volume 2 of this book, this library can also be potent without knowing a lot about it. It's so useful that the most basic of the standard containers, the vector, is introduced in this early chapter and used throughout the book. You'll find that you can do a tremendous amount just by using the basics of vector and not worrying about the underlying implementation (again, an important goal of OOP). Since you'll learn much more about this and the other containers when you reach the Standard Library chapters in Volume 2, it seems forgivable if the programs that use vector in the early portion of the book aren't exactly what an experienced C++ programmer would do. You'll find that in most cases, the usage shown here is adequate.

The vector class is a template, which means that it can be efficiently applied to different types. That is, we can create a vector of shapes, a vector of cats, a vector of strings, etc. Basically, with a template you can create a "class of anything". To tell the compiler what it is that the class will work with (in this case, what the vector will hold), you put the name of the desired type in "angle brackets," which means '<' and '>'. So a vector of string would be denoted vector<string>. When you do this, you end up with a customized vector that will hold only string objects, and you'll get an error message from the compiler if you try to put anything else into it.

Since vector expresses the concept of a "container," there must be a way to put things into the container and get things back out of the container. To add a brand-new element on the end of a vector, you use the member function push_back( ). (Remember that, since it's a member function, you use a '.' to call it for a particular object.) The reason the name of this member function might seem a bit verbose – push_back( ) instead of something simpler like "put" – is because there are other containers and other member functions for putting new elements into containers. For example, there is an insert( ) member function to put something in the middle of a container. vector supports this but its use is more complicated and we won't need to explore it until Volume 2 of the book. There's also a push_front( ) (not part of vector) to put things at the beginning. There are many more member functions in vector and many more containers in the Standard C++ Library, but you'll be surprised at how much you can do just knowing about a few simple features.

So you can put new elements into a vector with push_back( ), but how do you get these elements back out again? This solution is more clever and elegant – operator overloading is used to make the vector look like an array. The array (which will be described more fully in the next chapter) is a data type that is available in virtually every programming language so you should already be somewhat familiar with it. Arrays are aggregates, which mean they consist of a number of elements clumped together. The distinguishing characteristic of an array is that these elements are the same size and are arranged to be one right after the other. Most importantly, these elements can be selected by "indexing," which means you can say "I want element number n" and that element will be produced, usually quickly. Although there are exceptions in programming languages, the indexing is normally achieved using square brackets, so if you have an array a and you want to produce element five, you say a[4] (note that indexing always starts at zero).

This very compact and powerful indexing notation is incorporated into the vector using operator overloading, just like '<<' and '>>' were incorporated into iostreams. Again, you don't need to know how the overloading was implemented – that's saved for a later chapter – but it's helpful if you're aware that there's some magic going on under the covers in order to make the [ ] work with vector.

With that in mind, you can now see a program that uses vector. To use a vector, you include the header file <vector>:

//: C02:Fillvector.cpp
// Copy an entire file into a vector of string
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main() {
  vector<string> v;
  ifstream in("Fillvector.cpp");
  string line;
  while(getline(in, line))
    v.push_back(line); // Add the line to the end
  // Add line numbers:
  for(int i = 0; i < v.size(); i++)
    cout << i << ": " << v[i] << endl;
} ///:~

Much of this program is similar to the previous one; a file is opened and lines are read into string objects one at a time. However, these string objects are pushed onto the back of the vector v. Once the while loop completes, the entire file is resident in memory, inside v.

The next statement in the program is called a for loop. It is similar to a while loop except that it adds some extra control. After the for, there is a "control expression" inside of parentheses, just like the while loop. However, this control expression is in three parts: a part which initializes, one that tests to see if we should exit the loop, and one that changes something, typically to step through a sequence of items. This program shows the for loop in the way you'll see it most commonly used: the initialization part int i = 0 creates an integer i to use as a loop counter and gives it an initial value of zero. The testing portion says that to stay in the loop, i should be less than the number of elements in the vector v. (This is produced using the member function size( ), which I just sort of slipped in here, but you must admit it has a fairly obvious meaning). The final portion uses a shorthand for C and C++, the "auto-increment" operator, to add one to the value of i. Effectively, i++ says "get the value of i, add one to it, and put the result back into i. Thus, the total effect of the for loop is to take a variable i and march it through the values from zero to one less than the size of the vector. For each value of i, the cout statement is executed and this builds a line that consists of the value of i (magically converted to a character array by cout), a colon and a space, the line from the file, and a newline provided by endl. When you compile and run it you'll see the effect is to add line numbers to the file.

Because of the way that the '>>' operator works with iostreams, you can easily modify the program above so that it breaks up the input into whitespace-separated words instead of lines:

//: C02:GetWords.cpp
// Break a file into whitespace-separated words
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main() {
  vector<string> words;
  ifstream in("GetWords.cpp");
  string word;
  while(in >> word)
    words.push_back(word);
  for(int i = 0; i < words.size(); i++)
    cout << words[i] << endl;
} ///:~

The expression

while(in >> word)

is what gets the input one "word" at a time, and when this expression evaluates to "false" it means the end of the file has been reached. Of course, delimiting words by whitespace is quite crude, but it makes for a simple example. Later in the book you'll see more sophisticated examples that let you break up input just about any way you'd like.

To demonstrate how easy it is to use a vector with any type, here's an example that creates a vector<int>:

//: C02:Intvector.cpp
// Creating a vector that holds integers
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> v;
  for(int i = 0; i < 10; i++)
    v.push_back(i);
  for(int i = 0; i < v.size(); i++)
    cout << v[i] << ", ";
  cout << endl;
  for(int i = 0; i < v.size(); i++)
    v[i] = v[i] * 10; // Assignment  
  for(int i = 0; i < v.size(); i++)
    cout << v[i] << ", ";
  cout << endl;
} ///:~

To create a vector that holds a different type, you just put that type in as the template argument (the argument in angle brackets). Templates and well-designed template libraries are intended to be exactly this easy to use.

This example goes on to demonstrate another essential feature of vector. In the expression

v[i] = v[i] * 10;

you can see that the vector is not limited to only putting things in and getting things out. You also have the ability to assign (and thus to change) to any element of a vector, also through the use of the square-brackets indexing operator. This means that vector is a general-purpose, flexible "scratchpad" for working with collections of objects, and we will definitely make use of it in coming chapters.