Brief Overview of STL

STL makes heavy use of templates. In short, templates provide smart way to define functions and classes with generic parameters. These parameters at compile time can be substituted with standard or user-defined types.

STL contains vector class, which is somewhat similar to array type in terms of functionality. Comparison between them (in terms of usage) you can find in this table.

  STL vector array
Can be used with any standard or user-defined type Yes Yes
Theoretical size limit Available memory Available memory
Range checking Only some versions of STL like SafeSTL No
Automatic memory management for data buffer Yes, no need to call low-level memory management routines at all No
Automatic reallocation by copy()/insert() functions Yes, for insert() always and for copy() only with iterator adapter N/A
Large selection of algorithms Yes* Yes, some STL algorithms in very limited degree*
Speed penalty Not noticeable in most cases N/A
Automatic garbage collection Yes, in some cases No
Allow to construct less buggy software due to elimination of direct memory management and pointer arithmetic Yes, in most cases No
Bloated code Depend on the compiler and STL realizations, in most cases not significant and paid off by much shorter development cycle Writing proprietary algorithms library from scratch is time consuming and saved few MB of space often are not worth such effort (with the exception for embedded systems).
*require user-defined types to meet certain criteria

Vector is a sequence container type (well, its obviously clear why vector belongs to container type). STL supports other very useful container types: list, deque, map, multimap, set, multiset, basic_string, and some others by means of sequence adapters (stack, queue, etc.).

In order to use vector class, you need to add the following lines to source code:

#include <vector>
using namespace std;

Please note that STL headers do not end with ".h" or ".hpp". So, <string> and <string.h> are different headers (first one from STL and second one from Standard C Library). Namespaces are used to prevent name conflicts between different libraries. Thus, you can define your own namespace and your own class with the name vector within namespace other than std.

Like array, STL vector indexing starts from 0. It means that the first item will have index number zero, and last item - number of items minus one (somewhat uncomfortable for those who used to use Pascal).

Declaration of vector is very similar to array declaration, but unlike array, vector can be resized at run time.

// Array of long, 3 items.
long arr[3];

// Vector with 3 uninitialized items.
vector<long> vL1(3);

Of course, its possible to declare empty vector.

// Empty vector, no items.
vector<long> v;

However, even empty vector have allocated buffer (its size can be obtained with member function capacity()). If vector is supposed to hold a large number of items, you can avoid frequent reallocations by calling member function reserve(planned number of items).

Vector items can be accessed with subscription [] operator, just like an array. Be sure that indexes are within range.

// Initialize items# 1...3 of vL1.
vL1[0] = 1, vL1[1] = 2, vL1[2] = 3;

Second, unique way to operate with vector, is by means of using iterators.

You can think about iterators as STL functional analog to C pointer arithmetic. Remember, you can operate with array and its items in C like a[1] or *(a + 1) or i = a, ++i? STL iterators are even more flexible and powerful. Each container type (vector, list, map, etc.) supports certain types of iterators (random access, bi-directional, forward, input, output). Below is self-explanatory example how to loop through vector using iterator.

// Loop through vL1 using iterator.
for (vector::iterator i = vL1.begin(); i != vL1.end(); ++i) {

; // Do something.

// *i will point to current item of vL1.


Compare with the "classic" way.

// Loop through vL1 using index counter.
for (long k = 0; k < vL1.size(); ++k) {

; // Do something.

// Use vL1[k] to access items of vL1.


Pay attention to the loop end condition: i != vL1.end() !!! i < vL1.end() may work or may not, because not all iterators support operator <, but i != vL1.end() will ALWAYS work. To loop backward through container, use reverse iterator and replace begin()/end() with rbegin()/rend() respectively. Remember NEVER access item referred by iterator end() (like i = vL1.end(), *i ...), because end() points to the past last item, not to the last item (so called past-the-end iterator); test iterator against NULL and compare iterators (it1 < it2) except equality (==) and inequality (!=). If you need to compare items pointed by iterators, use *it1 < *it2. Iterators are essential for handling containers. Almost all insert, erase, copy, search and many others functions use iterators. In fact, STL container manipulation is iterator-based. CAUTION: insert, erase and some other operations may invalidate all or certain iterators, so be careful what are you doing inside loops or when passing iterators as function argument. Look at the quick sequence container overview for more information. The common pattern of iterator invalidation is reallocation of data buffer.

As mentioned before, vector (and any other container) can be dynamically resized. To insert new items, use push_back() or insert() member functions. Deque and list, but not vector, have additional insert function push_front().

// Append one item to vL1;

// Insert "99" as item #2.
// Please note that vL2[1] = 99 will REPLACE content of item #2 !!!
vL2.insert(vL2.begin() + 1, 99);

// Insert 10 copies of item "1234" before item #3.
vL2.insert(vL2.begin() + 2, 10, 1234);

Of course, you can copy items from another container. There are two very simple ways to create carbon copy of another container. First, by means of copy constructor, and second, with "=" operator.

vector<long> vL2(vL1);


vL2 = vL1;

Also, it is possible to use copy() function and iterators as well as regular pointers.

vector vCopy(2);

// Be careful not to run past the end of output container.

copy(vL1.begin(), vL1.begin() + vCopy.size(), vCopy.begin());

// Copy from regular array sample.

copy(arr, arr + 2, vCopy.begin());

Please note that STL copy() may overrun past container end if range of input iterators exceeds size of output container, so it is a better idea to use operator "=" to create exact copy.

// Copy content of vL2 to vL1;

vL1 = vL2;

The real advantage of STL copy() is that you do not have to worry how much memory allocated for output container if you use inserter iterator adapter.

// NO ALLOCATION PROBLEMS!!! vCopy will be automatically resized.

copy(vL1.begin(), vL1.end(), inserter(vCopy, vCopy.begin()));

Second boon - you can use mentioned above iterator adapters in order to insert or append items during copy operation.

// Copy entire content of vL1 to vCopy.

// back_inserter needs to append items to vCopy.

copy(vL1.begin(), vL1.end(), back_inserter(vCopy));

// Insert entire content of vL1 to vCopy before item #2.

copy(vL1.begin(), vL1.end(), inserter(vCopy, vCopy.begin() + 1));

To erase items, we can use erase() function member with one iterator pointed to item supposed to be deleted, second version of erase() with range of iterators; or pop_back(), which erases last item. Deque and list support pop_front(), which deletes first item.

// Declare vL3 and initialize it with content of vL2 using iterators.
vector<long> vL3(vL2.begin(), vL2.end());

// Erase last item of vL3.

// Erase items #1...3 from vL3.
vL3.erase(vL3.begin(), vL3.begin() + 2);

// Erase entire content of vL3.
vL3.erase(vL3.begin(), vL3.end());

Note: Samples shown above are available in source codes.

Continued: Real power of STL revealed...

MacGuruHQ and MacGuruHQ Logo

Copyright© 1996 - 2002 by Andrei Verovski. All right reserved. Content may not be copied in whole or in part, through electronic or other means, without the author's permission. MacGuru Logo (blue penguin) by Sergey Orehov.