The C++ STL (Standard Template Library) is a powerful set of C++ template classes to provides general-purpose templatized classes and functions that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.

At the core of the C++ Standard Template Library are following three well-structured components:

Component Description
Containers Containers are used to manage collections of objects of a certain kind. There are several different types of containers like deque, list, vector, map etc.
Algorithms Algorithms act on containers. They provide the means by which you will perform initialization, sorting, searching, and transforming of the contents of containers.
Iterators Iterators are used to step through the elements of collections of objects. These collections may be containers or subsets of containers.

Let us take the following program demonstrates the vector container (a C++ Standard Template) which is similar to an array with an exception that it automatically handles its own storage requirements in case it grows:

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
   // create a vector to store int
   vector<int> vec; 
   int i;

   // display the original size of vec
   cout << "vector size = " << vec.size() << endl;

   // push 5 values into the vector
   for(i = 0; i < 5; i++){
      vec.push_back(i);
   }

   // display extended size of vec
   cout << "extended vector size = " << vec.size() << endl;

   // access 5 values from the vector
   for(i = 0; i < 5; i++){
      cout << "value of vec [" << i << "] = " << vec[i] << endl;
   }

   // use iterator to access the values
   vector<int>::iterator v = vec.begin();
   while( v != vec.end()) {
      cout << "value of v = " << *v << endl;
      v++;
   }

   return 0;
}

When the above code is compiled and executed, it produces the following result:

vector size = 0
extended vector size = 5
value of vec [0] = 0
value of vec [1] = 1
value of vec [2] = 2
value of vec [3] = 3
value of vec [4] = 4
value of v = 0
value of v = 1
value of v = 2
value of v = 3
value of v = 4

Here are following points to be noted related to various functions we used in the above example:

  • The push_back( ) member function inserts value at the end of the vector, expanding its size as needed.
  • The size( ) function displays the size of the vector.
  • The function begin( ) returns an iterator to the start of the vector.
  • The function end( ) returns an iterator to the end of the vector.

The simplest way to get familiar with STL is to begin from its containers.

Containers
Any time you need to operate with many elements you require some kind of container. In native C (not C++) there was only one type of container: the array.

The problem is not that arrays are limited (though, for example, it’s impossible to determine the size of array at runtime). Instead, the main problem is that many problems require a container with greater functionality.

For example, we may need one or more of the following operations:

  • Add some string to a container.
  • Remove a string from a container.
  • Determine whether a string is present in the container.
  • Return a number of distinct elements in a container.
  • Iterate through a container and get a list of added strings in some order.

Of course, one can implement this functionality in an ordinal array. But the trivial implementation would be very inefficient. You can create the tree- of hash- structure to solve it in a faster way, but think a bit: does the implementation of such a container depend on elements we are going to store? Do we have to re-implement the module to make it functional, for example, for points on a plane but not strings?

If not, we can develop the interface for such a container once, and then use everywhere for data of any type. That, in short, is the idea of STL containers.


Before we begin
When the program is using STL, it should #include the appropriate standard headers. For most containers the title of standard header matches the name of the container, and no extension is required. For example, if you are going to use stack, just add the following line at the beginning of your program:

#include <stack>

Container types (and algorithms, functors and all STL as well) are defined not in global namespace, but in special namespace called “std.” Add the following line after your includes and before the code begin:

using namespace std;

Another important thing to remember is that the type of a container is the template parameter. Template parameters are specified with the ‘<’/’>’ “brackets” in code. For example:

vector<int> N;

When making nested constructions, make sure that the “brackets” are not directly following one another – leave a blank between them.

vector< vector<int> > CorrectDefinition; 
vector<vector<int>> WrongDefinition; // Wrong: compiler may be confused by'operator >>'

Vector
The simplest STL container is vector. Vector is just an array with extended functionality. By the way, vector is the only container that is backward-compatible to native C code – this means that vector actually IS the array, but with some additional features.

int elements_count = v.size();

Another very popular function to use in vector is push_back. Push_back adds an element to the end of vector, increasing its size by one. Consider the following example:

 vector<int> v; 
 for(int i = 1; i < 1000000; i *= 2) { 
      v.push_back(i); 
 } 
 int elements_count = v.size();

When you need to resize vector, use the resize() function:

 vector<int> v(20); 
 for(int i = 0; i < 20; i++) { 
      v[i] = i+1; 
 } 
 v.resize(25); 
 for(int i = 20; i < 25; i++) { 
      v[i] = i*2; 
 }

Note that if you use push_back() after resize(), it will add elements AFTER the newly allocated size, but not INTO it. In the example above the size of the resulting vector is 25, while if we use push_back() in a second loop, it would be 30.

 vector<int> v(20); 
 for(int i = 0; i < 20; i++) { 
      v[i] = i+1; 
 } 
 v.resize(25); 
 for(int i = 20; i < 25; i++) { 
      v.push_back(i*2); // Writes to elements with indices [25..30), not [20..25)
 }

To clear a vector use clear() member function. This function makes vector to contain 0 elements. It does not make elements zeroes — watch out — it completely erases the container.

There are many ways to initialize vector. You may create vector from another vector:

 vector<int> v1; 
 // ... 
 vector<int> v2 = v1; 
 vector<int> v3(v1); 

The initialization of v2 and v3 in the example above are exactly the same.

If you want to create a vector of specific size, use the following constructor:

 vector<int> Data(1000);

In the example above, the data will contain 1,000 zeroes after creation. Remember to use parentheses, not brackets. If you want vector to be initialized with something else, write it in such manner:

 vector<string> names(20, “Unknown”);

Remember that you can create vectors of any type.

Multidimensional arrays are very important. The simplest way to create the two-dimensional array via vector is to create a vector of vectors.

 vector< vector<int> > Matrix;

The simplest way to add data to vector is to use push_back(). But what if we want to add data somewhere other than the end? There is the insert() member function for this purpose. And there is also the erase() member function to erase elements, as well. But first we need to say a few words about iterators.

You should remember one more very important thing: When vector is passed as a parameter to some function, a copy of vector is actually created. It may take a lot of time and memory to create new vectors when they are not really needed. Actually, it’s hard to find a task where the copying of vector is REALLY needed when passing it as a parameter. So, you should never write:

 void some_function(vector<int> v) { // Never do it unless you’re sure what you do! 
      // ... 
 } 

Instead, use the following construction:

 void some_function(const vector<int>& v) { // OK 
      // ... 
 } 

If you are going to change the contents of vector in the function, just omit the ‘const’ modifier.

 int modify_vector(vector<int>& v) { // Correct 
      V[0]++; 
 }

Iterators

What are iterators? In STL iterators are the most general way to access data in containers. Consider the simple problem: Reverse the array A of N int’s. Let’s begin from a C-like solution:

 void reverse_array_simple(int *A, int N) { 
      int first = 0, last = N-1; // First and last indices of elements to be swapped 
      While(first < last) { // Loop while there is something to swap 
           swap(A[first], A[last]); // swap(a,b) is the standard STL function 
           first++; // Move first index forward 
           last--; // Move last index back 
      } 
 }

This code should be clear to you. It’s pretty easy to rewrite it in terms of pointers:

 void reverse_array(int *A, int N) { 
      int *first = A, *last = A+N-1; 
      while(first < last) { 
           Swap(*first, *last); 
           first++; 
           last--; 
      } 
 } 

Look at this code, at its main loop. It uses only four distinct operations on pointers ‘first’ and ‘last’:

  • compare pointers (first < last),
  • get value by pointer (*first, *last),
  • increment pointer, and
  • decrement pointer

Now imagine that you are facing the second problem: Reverse the contents of a double-linked list, or a part of it. The first code, which uses indexing, will definitely not work. At least, it will not work in time, because it’s impossible to get element by index in a double-linked list in O(1), only in O(N), so the whole algorithm will work in O(N^2). Errr…

But look: the second code can work for ANY pointer-like object. The only restriction is that that object can perform the operations described above: take value (unary *), comparison (<), and increment/decrement (++/–). Objects with these properties that are associated with containers are called iterators. Any STL container may be traversed by means of an iterator. Although not often needed for vector, it’s very important for other container types.

So, what do we have? An object with syntax very much like a pointer. The following operations are defined for iterators:

STL algorithms always use two iterators, called “begin” and “end.” The end iterator is pointing not to the last object, however, but to the first invalid object, or the object directly following the last one. It’s often very convenient.

Each STL container has member functions begin() and end() that return the begin and end iterators for that container.

Based on these principles, c.begin() == c.end() if and only if c is empty, and c.end() – c.begin() will always be equal to c.size(). (The last sentence is valid in cases when iterators can be subtracted, i.e. begin() and end() return random access iterators, which is not true for all kinds of containers. See the prior example of the double-linked list.)

The STL-compliant reverse function should be written as follows:

 template<typename T> void reverse_array_stl_compliant(T *begin, T *end) { 
      // We should at first decrement 'end' 
      // But only for non-empty range 
      if(begin != end) 
      { 
           end--; 
           if(begin != end) { 
                while(true) { 
                     swap(*begin, *end); 
                     begin++; 
                     If(begin == end) { 
                          break; 
                     } 
                     end--; 
                     if(begin == end) { 
                          break; 
                     } 
                } 
           } 
      } 
 } 

Note that this function does the same thing as the standard function std::reverse(T begin, T end) that can be found in algorithms module (#include <algorithm>).

In addition, any object with enough functionality can be passed as an iterator to STL algorithms and functions. That is where the power of templates comes in! See the following examples:

 vector<int> v; 
 // ... 
 vector<int> v2(v); 
 vector<int> v3(v.begin(), v.end()); // v3 equals to v2 

 int data[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }; 
 vector<int> primes(data, data+(sizeof(data) / sizeof(data[0])));

Furthermore, we can even use the following constructions:

 vector<int> v; 
 // ... 
 vector<int> v2(v.begin(), v.begin() + (v.size()/2)); 

It creates the vector v2 that is equal to the first half of vector v.

Here is an example of reverse() function:

 int data[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }; 
 reverse(data+2, data+6); // the range { 5, 7, 9, 11 } is now { 11, 9, 7, 5 }; 

Each container also has the rbegin()/rend() functions, which return reverse iterators. Reverse iterators are used to traverse the container in backward order. Thus:

 vector<int> v; 
 vector<int> v2(v.rbegin()+(v.size()/2), v.rend()); 

will create v2 with first half of v, ordered back-to-front.

 vector<int> v; 

 // ... 

 // Traverse all container, from begin() to end() 
 for(vector<int>::iterator it = v.begin(); it != v.end(); it++) { 
      *it++; // Increment the value iterator is pointing to 
 } 

I recommend you use ‘!=’ instead of ‘<’, and ‘empty()’ instead of ‘size() != 0′ — for some container types, it’s just very inefficient to determine which of the iterators precedes another.

The find() algorithm looks for appropriate elements in an interval. If the element is found, the iterator pointing to the first occurrence of the element is returned. Otherwise, the return value equals the end of interval. See the code:

 vector<int> v; 
 for(int i = 1; i < 100; i++) { 
      v.push_back(i*i); 
 } 

 if(find(v.begin(), v.end(), 49) != v.end()) { 
      // ... 
 } 

To get the index of element found, one should subtract the beginning iterator from the result of find():

 int i = (find(v.begin(), v.end(), 49) - v.begin(); 
 if(i < v.size()) { 
      // ... 
 }

Remember to #include <algorithm> in your source when using STL algorithms.

The min_element and max_element algorithms return an iterator to the respective element. To get the value of min/max element, like in find(), use *min_element(…) or *max_element(…), to get index in array subtract the begin iterator of a container or range:

 int data[5] = { 1, 5, 2, 4, 3 }; 
 vector<int> X(data, data+5); 
 int v1 = *max_element(X.begin(), X.end()); // Returns value of max element in vector 
 int i1 = min_element(X.begin(), X.end()) – X.begin; // Returns index of min element in vector 

 int v2 = *max_element(data, data+5); // Returns value of max element in array 
 int i3 = min_element(data, data+5) – data; // Returns index of min element in array

Another good algorithm is sort(). It’s very easy to use. Consider the following examples:

 vector<int> X; 

 // ... 

 sort(X.begin(), X.end()); // Sort array in ascending order 
 sort(all(X)); // Sort array in ascending order, use our #define 
 sort(X.rbegin(), X.rend()); // Sort array in descending order using with reverse

Data manipulation in vector
One can insert an element to vector by using the insert() function:

 vector<int> v; 
 // ... 
 v.insert(1, 42); // Insert value 42 after the first 

All elements from second (index 1) to the last will be shifted right one element to leave a place for a new element. If you are planning to add many elements, it’s not good to do many shifts – you’re better off calling insert() one time. So, insert() has an interval form:

 vector<int> v; 
 vector<int> v2; 

 // .. 

 // Shift all elements from second to last to the appropriate number of elements. 
 // Then copy the contents of v2 into v. 
 v.insert(1, all(v2));

Vector also has a member function erase, which has two forms. Guess what they are:

 erase(iterator); 
 erase(begin iterator, end iterator); 

At first case, single element of vector is deleted. At second case, the interval, specified by two iterators, is erased from vector.

The insert/erase technique is common, but not identical for all STL containers.


String
There is a special container to manipulate with strings. The string container has a few differences from vector<char>. Most of the differences come down to string manipulation functions and memory management policy.

String has a substring function without iterators, just indices:

 string s = "hello"; 
 string 
      s1 = s.substr(0, 3), // "hel" 
      s2 = s.substr(1, 3), // "ell" 
      s3 = s.substr(0, s.length()-1), "hell" 
      s4 = s.substr(1); // "ello"

Set

Consider we need a container with the following features:

  • add an element, but do not allow duples [duplicates?]
  • remove elements
  • get count of elements (distinct elements)
  • check whether elements are present in set

This is quite a frequently used task. STL provides the special container for it – set. Set can add, remove and check the presence of particular element in O(log N), where N is the count of objects in the set. While adding elements to set, the duples [duplicates?] are discarded. A count of the elements in the set, N, is returned in O(1). We will speak of the algorithmic implementation of set and map later — for now, let’s investigate its interface:

set<int> s; 

 for(int i = 1; i <= 100; i++) { 
      s.insert(i); // Insert 100 elements, [1..100] 
 } 

 s.insert(42); // does nothing, 42 already exists in set 

 for(int i = 2; i <= 100; i += 2) { 
      s.erase(i); // Erase even values 
 } 

 int n = int(s.size()); // n will be 50

The push_back() member may not be used with set. It make sense: since the order of elements in set does not matter, push_back() is not applicable here.

Since set is not a linear container, it’s impossible to take the element in set by index. Therefore, the only way to traverse the elements of set is to use iterators.

 // Calculate the sum of elements in set 
 set<int> S; 
 // ... 
 int r = 0; 
 for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) { 
      r += *it; 
 }

To determine whether some element is present in set use ‘find()’ member function. Don’t be confused, though: there are several ‘find()’ ’s in STL. There is a global algorithm ‘find()’, which takes two iterators, element, and works for O(N). It is possible to use it for searching for element in set, but why use an O(N) algorithm while there exists an O(log N) one? While searching in set and map (and also in multiset/multimap, hash_map/hash_set, etc.) do not use global find – instead, use member function ‘set::find()’. As ‘ordinal’ find, set::find will return an iterator, either to the element found, or to ‘end()’. So, the element presence check looks like this:

 set<int> s; 
 // ... 
 if(s.find(42) != s.end()) { 
      // 42 presents in set 
 } 
 else { 
      // 42 not presents in set 
 } 

Another algorithm that works for O(log N) while called as member function is count. Some people think that

 if(s.count(42) != 0) { 
      // … 
 } 

or even

 if(s.count(42)) { 
      // … 
 }

To erase an element from set use the erase() function.

 set<int> s; 
 // … 
 s.insert(54); 
 s.erase(29);

The erase() function also has the interval form:

 set<int> s; 
 // .. 

 set<int>::iterator it1, it2; 
 it1 = s.find(10); 
 it2 = s.find(100); 
 // Will work if it1 and it2 are valid iterators, i.e. values 10 and 100 present in set. 
 s.erase(it1, it2); // Note that 10 will be deleted, but 100 will remain in the

Set has an interval constructor:

 int data[5] = { 5, 1, 4, 2, 3 }; 
 set<int> S(data, data+5); 

It gives us a simple way to get rid of duplicates in vector, and sort it:

 vector<int> v; 
 // … 
 set<int> s(all(v)); 
 vector<int> v2(all(s));

Here ‘v2′ will contain the same elements as ‘v’ but sorted in ascending order and with duplicates removed.


Map
There are two explanation of map. The simple explanation is the following:

 map<string, int> M; 
 M["Top"] = 1; 
 M["Coder"] = 2; 
 M["SRM"] = 10; 

 int x = M["Top"] + M["Coder"]; 

 if(M.find("SRM") != M.end()) { 
      M.erase(M.find("SRM")); // or even M.erase("SRM") 
 }

stack

is a container where elements operate in a LIFO (Last In, First Out) context, where elements are inserted (pushed) and removed (popped) from the end of the container. Stacks default to using deque as their default sequence container (which seems odd, since vector seems like a more natural fit), but can use vector or list as well.

queue

is a container where elements operate in a FIFO (First In, First Out) context, where elements are inserted (pushed) to the back of the container and removed (popped) from the front. Queues default to using deque, but can also use list.


Useful References 

 

Advertisements