STL Tutorial Introduction

C++ Reference Material
STL Tutorial Introduction

Given the complexity and power of the STL (the Standard Template Library of C++), and the fact that its use is not exactly intuitive for beginners, putting together even a "tutorial introduction" becomes a somewhat daunting task right from the get go. Especially if one wants to keep it short, as I do.

Assumptions

So, how shall we proceed? First, we shall assume a couple of things:

You have a reasonable background in basic C++, up to and including templates (both classes and functions), since these play a key role in the STL. If this is true, you probably have at least heard of the STL, though you may not have used it.
You have read the STL FAQ on this site, so that we don't have to repeat that material in detail here.

Thus, you know that the STL has things called containers, iterators and algorithms. Our purpose here will be to see how these three things come together in what might be called "typical STL fashion". Though there is much else to learn about the STL, once you have a handle on this, you have made considerable progress toward becoming an STL user.

Analogies

Fortunately, we can begin by drawing some analogies between STL containers, iterators and algorithms and things you already know about.

We begin by noting that, at a superficial level at least, any STL container is analogous to an array, in that it is something that allows you to store and retrieve elements. All STL containers are implemented by template classes, which means that any given container can easily be used to hold elements of virtually any type. So, you have a choice of containers and you can choose what kind of values you would like to store in whatever container you happen to be using at the time. For example, the STL has a container called vector, which is the most array-like of all the STL containers, and in fact it is often billed as a "better array". This is everyone's favorite STL container, it is ofter referred to as the the STL's "workhorse" container (because you should probably use it unless there is a good reason to use something else), and we will use it in the examples which follow.

Your C++ experience will provide you with an opportunity to use pointers to "point at" and manipulate array elements. STL iterators are used to "point at" and manipulate STL container elements in a manner quite analogous to the way in which pointers are used in the array context. But ... each STL container class will have its own kind of iterator, one which is most appropriate for that particular container. And, in general, STL iterators are much "safer" to use than old-fashioned pointers. Interestingly, though, those "old-fashioned" pointers can be, and often are, used with STL containers in the same way that STL iterators themselves are used, bolstering the claim that an STL iterator is, after all, "just a generalized pointer to an array".

And algorithms ... well, you know what they are. Often they come in the form of stand-alone or "free" functions which usually take in some data via a parameter list and perform some task and/or return one or more computed values. And all of this is true of STL algorithms as well. But ... where STL algorithms get their additional power and flexibility is from the fact that many of their parameters are STL iterators rather than STL containers. Since these iterators can point at the elements of many different kinds of STL containers this means that STL algorithms have a "built-in" ability to deal with a variety of containers containing a variety of element types. In other words, an algorithm can work on the elements of a container without knowing or caring what kind of container it is.

Pushing the analogies further with some specific (`vector`) examples

And now, let's cut to the chase. Consider the line of C++ code

vector<int> v(10);

which declares a "vector of integers" of size 10, i.e. a place to store 10 values of type int. To include such a declaration in your program you would also need the following compiler include directive:

#include <vector>

The above declaration of v is somewhat analogous to the line of code

int a[10];

which declares an ordinary C++ "array of integers" of size 10, also a place to store 10 values of type int. So ... what's the difference, and why the big fuss about vectors? Well ... consider the following points:

Index type First, the elements of v are v[0], v[1], ... v[9], just as the elements of a are a[0], a[1], ... a[9], and both are used in the same way. But even here there is a "hidden" and potentially confusing difference to be aware of in the type of the index variable. To output the values in the array a one would normally use a loop idiom like the following:
```
int i;
for (i=0; i<10; i++) cout << a[i];
```
If we try the same thing with vector v, i.e.
```
int i;
for (i=0; i<10; i++) cout << v[i];
```
it may in fact work, but an up-to-date compiler will at least warn you that the index variable i has the "wrong" type, and the code should really be written like this:
```
vector<int>::size_type i;
for (i=0; i<10; i++) cout << v[i];
```
The reason for this is that the int data type has values (all the negative ones) that cannot possibly be valid indices for a vector. Thus the vector class would like to be sure that we always use non-negative index values when accessing vector components and provides for us a typedef alias called size_type (an unsigned integral type) for just this purpose.
A vector, unlike an array, has self-knowledge: it knows how big it is When outputting values for an array, the programmer needs to know the size of the array. Another advantage of a vector over an array is that (because the vector is a class object) the vector knows its own size. Hence we can (and should) write
```
vector<int>::size_type i;
for (i=0; i<v.size(); i++) cout << v[i];
```
which will work for any vector of whatever size. We no longer need to know and remember that (in the above case) the size of the vector v is 10.
Component initialization Unlike a, v is a class object, and we have used one of several constructors from the vector container class to create v. Among other things, this means that each element of v is guaranteed to be initialized with the default value of the component type (0 here, since the component type is int). On the other hand, the elements of a may or may not be initialized to 0, depending on where the declaration is located in the program, for example.
Adding new elements Once declared as above, the size of a is fixed and cannot be altered later in the program. But the vector class contains a push_back() member function which can be used like this
```
v.push_back(17);
```
to add the value 17 (for example) to the end of the vector. After execution of this statement the size of the vector v has increased to 11 and v[10] contains the value 17. (Remember that the first 10 values of v are all 0, and are found in the locations with indices in the range 0..9.) This ability of a vector to "grow" in order to accommodate the addition of new values to its "back end" is one of the major advantages of vectors over arrays.
Initializing a vector with elements from an array Although declaring an empty array, as in
```
int a[0];
```
makes no sense, since nothing can ever be stored in it, declaring an empty vector and then adding some values makes perfect sense:
```
vector<int> v;  //construct an empty vector to hold some integers
v.push_back(3); // v now contains 3 in v[0]
v.push_back(6); // v now contains 3 in v[0], 6 in v[1]
v.push_back(4); // v now contains 3 in v[0], 6 in v[1], 4 in v[2]
```
This is clearly a rather laborious and inconvenient way to get values into a vector. Since an array containing the same values can be initialized with the statement
```
int a[3] = {3, 6, 4};
```
or even
```
int a[] = {3, 6, 4};
```
one might hope that something like
```
vector<int> v = {3. 6, 4}; //syntax error!
```
would work for vectors, but unfortunately (as the comment indicates) this does not work. However, a useful way of combining the old and the new to initialize a vector with a sequence of specific values is illustrated by the following two lines of code:
```
int a[] = {3, 6, 4};   //initialize array a first
vector<int> v(a, a+3); //construct vector v containing values from a
```
This vector definition (declaration with initialization) requires a few words of explanation. We are using another constructor from the vector class, this time the one that takes two input parameters which are "iterators" (or in this case, ordinary pointers acting as iterators) pointing at the beginning element, and "one-past-the-last" element of a range of values to be placed in the newly constructed vector. In this case the first parameter (a), is a pointer to the first element of the array a, and the second parameter (a+3) is a pointer to the "first position beyond the last element" of the array a. This notion of a "range" of elements being determined by a pair of iterators (or pointers) pointing to the first element and "one-past-the-last" element (as opposed to the last element itself) of a sequence of values permeates the STL and is something beginning STL programmers need to get a handle on right up front. An even better way to create v with the values from a would be
```
int a[] = {3, 6, 4}; //initialize array a first
vector<int> v(a, a+sizeof(a)/sizeof(int)); //construct v with values from a
```
which works independently of the size of the array a.
Vector iterators The STL vector class provides an iterator which can be used to access the component values of any vector in the same way that ordinary pointers are used to access array elements. The member function begin() returns an iterator object pointing to the first component of the vector on which it is invoked and the member function end() returns an iterator object pointing to one-past-the-last component. The fact that it is one-past-the-last and not the last makes it convenient when writing a loop to process all vector elements, as in the following example.
```
int a[] = {3, 6, 4}; //initialize array a first
vector<int> v(a, a+sizeof(a)/sizeof(int)); //construct v with values from a
vector<int>::iterator p; //declare an iterator for a vector of integers
for (p=v.begin(); p!=v.end(); p++) cout << *p << " "; //output all values of v
```
Note that the iterator object p is incremented in the same way that an ordinary array pointer would be incremented, and that *p is used to dereference p and get access to the value to which p is pointing, once again in the same way that a pointer would be dereferenced to gain access to an array element.
Using algorithms and function objects with vectors One particularly nice feature of the STL is that it provides a large collection of algorithms that perform many of the common programming tasks that programmers frequently need to have done in their programs. Most of those algorithms are available from the <algorithm> header, but a few are located in the <numeric> header. To quickly get a sense of how this works, look at this code
```
#include <algorithm>
...
sort(v.begin(), v.end());
```
which shows the STL sort algorithm being used to sort the values in a vector. By default this algorithm sorts in ascending order and will work for a vector of any items whatsoever, as long as operator<() is defined for the components of v, so that the sort algorithm knows what it means for one component to precede another. If a sort in descending order is required instead, this can be accomplished with
```
#include <algorithm>
#include <functional>
...
sort(v.begin(), v.end(), greater<T>());
```
in which T must be the component type of v, and the expression greater<T>() provides a function object (from STL's built-in collection of function objects, available from the header <functional>) that tells the sort algorithm to change its thinking to consider one component as preceding another when it is greater than the other (which requires that operator>() be defined for the component type of the vector). Many STL algorithms have an overloaded version that permits their default behavior to be altered by providing an additional function object parameter (or ordinary function parameter) which is used by the algorithm to help it perform its task in a different way.
As a second example of an STL algorithm applied to a vector, consider
```
#include <algorithm>
...
cout << *max_element(v.begin(), v.end()) << endl;
```
which outputs the "largest" value in the vector (whatever that means for the given vector). The max_element algorithm actually returns an iterator object pointing to the largest value, rather than the largest value itself. This is why we have to dereference the return value of the algorithm: to obtain, for output, the value to which the returned iterator object is pointing.
Vector assignment and comparisons A number of other operations are available for vectors that that have no counterpart when you are working with arrays. For example, it is possible to assign one vector to another, as in
```
v1 = v2;
```
and the relational operators also work with vectors, so that you can make tests like
```
if (v1 == v2)
...
```
or
```
if (v1 < v2)
...
```
provided you understand how these things work. Assignment of vectors works just like assignment always works (or should work) ... the thing on the right of the assignment operator replaces the thing on the left of the assignment operator. The relational operators are potentially a little trickier. We can summarize the situation by saying the comparisons are "lexicographic". That's a big word meaning this: when two vectors are being compared (to see if one is "less than" the other, for example), corresponding pairs of components are compared (starting at the beginning) until a determination can be made. How the vectors compare is determined by how the first two components that are different compare. That is, if the component in the first vector is less than the corresponding component in the second vector, then the first vector is itself less than the second vector. This is just like "alphabetic" comparison, but instead of comparing letters you are comparing components (whatever they may be). This of course implies that components can in fact be compared.

Now what?

In this brief introduction you have seen just one of the STL container types (vector) and you have seen how much more versatile vectors are than arrays. You have also seen how STL algorithms can be used to manipulate or "process" the components of a vector through iterators. All of this just scratches the surface, of course, but it should give you a reasonable sense of "how things work" in the STL, at least enough to get you started.

What you need to do now is learn about some of the other STL containers (deque, list, map, multimap, set, multiset) and container adaptors (stack, queue, priority_queue), and get familiar with as many of the STL algorithms as you can manage. In doing so you will also want to learn more about how iterators behave and about the iterator adaptors for streams that are very convenient for I/O operations. And do not forget that function objects can be usefully employed in many different situations when using the STL, so you should make sure that function objects are in your personal STL toolkit if you expect to become a competent STL programmer.

As you learn about these new STL features, you should be struck by how much what you already know about vectors carries over to the other containers, particularly if your very next step is to digest the detail page on vectors provided on this web site. So ... that's what we recommend. Do note, however, that that page is a reference page, not a tutorial page. But you will also find there a large number of sample programs that should show you nearly all you would ever need to know about vectors, and a few other things along the way.

Assumptions

Analogies

Pushing the analogies further with some specific (vector) examples

Now what?

Pushing the analogies further with some specific (`vector`) examples