Introduction to STL
STL is a useful library containing template classes which implement the most used data types like: vector, linked list, set, map, and others. STL has three main components:
- Containers – classes capable of holding multiple elements of the same type.
- Iterators – generalize the main methods to access a container element.
- Algorithms - implement different operations, independent of the container used.
Containers
STL containers can store any kind of data type, including user defined ones, but the programmer must make sure that the stored elements support the set of functions specific to the chosen container. Insertion into a container assumes the copy of an element, so the copy constructor is indispensable. There are three types of STL containers:
Sequence containers are linear data structures which permit an access based on the order of the element in the container. Thus, the access is controlled by the programmer through insertion and deletion of elements. The STL sequence container classes are presented below:
- vector – implements a vector stored in dynamic memory. It can be resized, assigned to another vector, and permits element access with out of bounds checking.
- list – implements the double linked list.
- deque – implemented similar to the vector.
Associative containers store values (that can be considered keys) or key – value pairs, thus facilitating direct access to stored elements. The elements can be found directly because the keys are always kept sorted. The STL associative container classes are presented below:
- set – defines a set of unique, sorted elements.
- multiset – defines a set of sorted elements.
- map – defines a set of unique, sorted elements, an element being a key – value pair.
- multimap – defines a set of sorted elements, an element being a key – value pair.
Adaptive containers don't have their own implementations, allocators, or iterators. They adapt other containers. Their advantage is that they add new functionality to existing containers, and the programmer can choose the container to adapt. In other words, adaptive containers can be implemented only using sequence containers. The STL adaptive container classes are presented below:
- stack – it can adapt vector, list, and deque.
- queue – can adapt list and deque.
- priority_queue – can adapt vector and deque.
Iterators
An iterator is a pointer to an element of a container (sequence or associative) which keeps the state information for that container, including the current position. So, iterators are implemented with respect to the container type, but they have a general behavior, allowing for pre and post increment and decrement operations and comparison.
Algorithms
Some functions, specific to each container, are included in the class of the respective container, but others are implemented independent of the container. STL algorithms are the standard operations on the elements of a container (insert, erase, find, sort, size, swap ...) which can be described container independently. This container independence is obtained by indirect access of an element through iterators.
The vector container
In this first part of the tutorial series, we will present the vector container, the most studied and used STL container.
Creating a vector: Constructors
In order to use a vector, we must include the <vector> header, and in some cases, it is useful to declare using the std namespace:
#include <vector>
using namespace std;
The following piece of code creates an empty vector (of zero size), capable of holding doubles:
vector<double> vec;
cout << "Size of vec is " << vec.size();
The size() member function returns the actual size of the vector. At creation time, we can specify the size of the newly created vector. Here, we create a vector with five empty elements:
vector<double> vec(5);
cout << "Size of vec is " << vec.size();
We create a vector with five elements, and each element will have the value 8.8:
vector<double> vec(5, 8.8);
cout << "Size of vec is " << vec.size() << endl;
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
The first parameter of the constructor is the size of the vector, and the second parameter represents the value that will be assigned to each newly created element. Notice that, for printing the elements of the vector, we use the [] operator, which is overloaded in the vector class. We can also create a vector based on an array of elements:
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
Below, we see how to use the copy constructor on vectors. We copy the above created vector vec into the veccopy vector:
vector<double> veccopy(vec);
cout << "veccopy: ";
for(int i = 0; i < veccopy.size(); i++)
cout << veccopy[i] << " ";
Another interesting feature is that we can assign values to an STL vector. This is done using the assign() member function. Below, we assign the values of an array to the vector vec.
vector<double> vec;
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vec.assign(array, array + 5);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
The following code assigns five values of 8.8 to the vector vec:
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
Printing the elements of a vector
There are three different ways to print the content of a vector. The first way is to make use of the [] operator, as shown in the example above:
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
The second way is to use the at() member function of the vector class, which is given as parameter an integer position, and returns the element located at that position in the vector:
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < 5; i++)
cout << vec.at(i) << " ";
The third way makes use of iterators. First, we declare an iterator for our vector. Next, using it, we step through all elements of the vector, printing the value of each one.
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
vector<double>::iterator it;
for(it = vec.begin(); it != vec.end(); it++)
cout << *it << " ";
The code above translates in the following way: at first, the iterator points to the first element of the vector. The begin() function is used, which returns an iterator to the first element of the vector. While there are more elements in the vector, print the value of the current iterator, and then increment the iterator to point to the next element of the vector. The end() function returns an iterator which points to the position after the last element of the vector. So, when the iterator is assigned the value returned by the end() function, the vector has no more elements. For incrementing, we use the ++ operator, overloaded in the vector class, and for printing, we use the * operator, also overloaded in the vector class. For iterator manipulation, there are two functions of vector which come in handy: the front() function which returns an iterator to the first element in the vector, and the back() which returns an iterator to the last element in the vector.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec;
vec.assign(array, array + 5);
vector<double>::iterator it;
it = &vec.front();
cout << *it << " ";
it = &vec.back();
cout << *it;
We can also print the elements of the vector in reverse order, using a reverse iterator and the rbegin() and rend() functions. First, we declare a reverse_iterator object and we use the same methodology as for a normal iterator, keeping in mind that rbegin() returns a reverse iterator to the last element of the vector and rend() returns a reverse iterator to the first element of the vector.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec;
vec.assign(array, array + 5);
vector<double>::reverse_iterator rit;
cout << "reverse of vec: ";
for(rit = vec.rbegin(); rit != vec.rend(); rit++)
cout << *rit << " ";
We will put the code for printing a vector into a function, print, which we will use later. The function receives two parameters: the first one is the vector which we want to print, and the second one is a string representing the name of the vector. The code of the function is given below:
void print(vector<double> vec, char * name)
{
vector<double>::iterator it;
cout << name << ": ";
for(it = vec.begin(); it != vec.end(); it++)
cout << *it << " ";
}
Inserting elements into a vector
The first way to add elements to a vector is to use the push_back() function, which adds an element, given as the parameter, to the end of the vector.
vector<double> vec;
vec.push_back(2.0);
vec.push_back(4.0);
vec.push_back(6.0);
print(vec, "vec");
For advanced insertion of elements, we can use the insert() function which inserts an element or a range of elements at a position specified by an iterator. The elements and the iterator are passed as parameters to the insert() function.
vector<double> vec;
vector<double>::iterator it;
vec.push_back(2.0);
vec.push_back(4.0);
vec.push_back(6.0);
it = vec.end();
vec.insert(it, 67);
print(vec, "vec");
it = vec.begin();
vec.insert(it, 3, 90);
print(vec, "vec");
double array[5] = {1, 2, 3, 4, 5};
it = vec.begin() + 3;
vec.insert(it, array, array + 5);
print(vec, "vec");
Removing elements from a vector
The simplest way is to use the pop_back() function, which removes the last element of the vector.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vec.pop_back();
print(vec, "vec");
The function erase() is also used to delete elements from a vector. It receives as parameter an iterator to the element we want to remove.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vector<double>::iterator it;
it = vec.begin() + 1;
vec.erase(it);
print(vec, "vec");
To remove all elements from a vector, we use the clear() function.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vec.clear();
cout << "size of vec is " << vec.size();
If we want to test if a vector is empty or not, we can use the empty() function, which returns true if the vector is empty and false otherwise.
vector<double> vec;
if(vec.empty())
cout << "vec is empty";
else
cout << "vec is not empty";
Sizing and resizing a vector
In order to find the current number of elements of a vector, we use the size() function, which returns the number of elements in the vector. If we want to find the maximum number of elements the vector can store, we use the max_size() function. The function capacity() returns the size of the allocated storage space for the elements of the vector.
vector<double> vec;
vec.push_back(100);
cout << "vec size is " << vec.size() << endl;
cout << "vec capacity is " << vec.capacity() << endl;
cout << "vec maximum size is " << vec.max_size();
To increase the capacity of a vector, we use the reserve() function, which increases the capacity of the vector to the value given as the parameter.
vector<double> vec;
vec.push_back(100);
cout << "vec capacity is " << vec.capacity() << endl;
vec.reserve(50);
cout << "vec capacity is " << vec.capacity();
The most advanced function to resize a vector is the function resize() which receives as parameter the number of elements the vector has to store. If the current size of the vector (curSize) is greater than the new size (newSize), the vector is reduced to newSize elements, the rest of the elements being deleted. If curSize is less than newSize, the vector is expanded to newSize elements, by adding at the end of the vector as many elements as necessary to reach newSize elements.
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
vec.resize(3);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
vec.resize(10);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
An important thing to notice is that, unlike the reserve() function, which only changes the size of the vector, the resize() function can also change the contents of the vector, by adding new elements or removing existing ones.
Two dimensional vectors
Two dimensional vectors are vectors of vectors. When we add elements to a two dimensional vector, we add, in fact, one dimensional vectors. Below is an example of how to create and print a two dimensional vector. First, we use indexing to print the vector. In the second part, we show how to use iterators on two dimensional vectors:
vector< vector<double> > matrix;
double array1[5] = {1, 3, 5, 7, 9};
vector<double> vec1(array1, array1 + 5);
double array2[5] = {2, 4, 6, 8, 10};
vector<double> vec2(array2, array2 + 5);
matrix.push_back(vec1);
matrix.push_back(vec2);
for(int i = 0; i < matrix.size(); i++)
{
for(int j = 0; j < matrix[i].size(); j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
vector< vector<double> >::iterator it2d;
vector<double>::iterator it1d;
for(it2d = matrix.begin(); it2d != matrix.end(); it2d++)
{
for(it1d = (*it2d).begin(); it1d != (*it2d).end(); it1d++)
{
cout << *it1d << " ";
}
cout << endl;
}
Vectors of pointers
As mentioned before, vectors can also store pointers. In the following example, we create a vector capable of storing pointers to doubles:
vector<double*> vec;
double * d1 = new double(10);
double * d2 = new double(20);
double * d3 = new double(30);
vec.push_back(d1);
vec.push_back(d2);
vec.push_back(d3);
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
for(i = 0; i < vec.size(); i++)
cout << *vec[i] << " ";
As we can see, first, the addresses of the three pointers are shown, as evidence that the vector, indeed, stores pointers. Next, we print the values stored at those addresses.
Vectors of user defined elements
Besides primitive types and pointers, STL vectors can also store user defined elements. Next, we define a class, named Point, with two integer data members, x and y, which represent the coordinates of the point:
class Point
{
int x;
int y;
public:
Point()
: x(0), y(0)
{
}
Point(int px, int py)
: x(px), y(py)
{
}
Point(const Point& pt)
: x(pt.x), y(pt.y)
{
cout << "Inside the copy constructor!" << endl;
}
void print()
{
cout << "Point: " << x << ", " << y << endl;
}
};
For the above class, the copy constructor is indispensable, as we will see. Now, we declare a vector capable of storing Point elements, and we add some elements to the vector:
vector<Point> vecp;
Point p1(1, 5);
Point p2(3, 5);
Point p3;
vecp.push_back(p1);
vecp.push_back(p2);
vecp.push_back(p3);
for(int index = 0; index < vecp.size(); index++)
vecp[index].print();
As we can see, the copy constructor was called six times. So, to make sure all copying is correctly performed, we must add the copy constructor to a class or a structure if we intend to use it in a vector.
Avoiding memory leaks when using a vector
A frequent problem that appears when using a vector is the one that refers to memory leaks. Let's take, for example, the class Person, with two data members, name and age; name is a pointer to a char and age is an integer:
class Person
{
char * name;
int age;
public:
Person(char * pname = "Anonymous", int page = 0)
:age(page)
{
name = new char[strlen(pname) + 1];
strcpy(name, pname);
}
Person(const Person& rhs)
:age(rhs.age)
{
name = new char[strlen(rhs.name) + 1];
strcpy(name, rhs.name);
}
void Print()
{
cout << name << " " << age << endl;
}
};
We create a vector for storing Person objects, and we add five objects to it:
vector<Person> vecp;
Person p1("Bill Gates", 50);
Person p2("John Malcom", 67);
Person p3("Scott Meyers", 34);
Person p4("Mark Gosling", 40);
Person p5;
vecp.push_back(p1);
vecp.push_back(p2);
vecp.push_back(p3);
vecp.push_back(p4);
vecp.push_back(p5);
for(int i = 0; i < vecp.size(); i++)
vecp[i].Print();
cout << endl;
vecp.resize(2);
for(i = 0; i < vecp.size(); i++)
vecp[i].Print();
Now, at some point, we may need to resize the vector to a smaller capacity than its current one, say we resize the vector to two elements. The last three elements will be removed from the vector, in order to bring it to the desired size. The elements will be destroyed, but the memory occupied by each name char pointer will not be released (since the standard destructor will be called for each element that is being removed). Thus, memory leaks appear. This is a simple example. In reality, more complicated problems can appear, resulting in huge memory leaks, memory corruption, and worse scenarios.
The solution to avoid memory leaks is very simple. We just need to add a destructor to the Person class to take care of releasing the memory occupied by the char pointer. Thus, each time an element is destroyed, its destructor will be called, which will correctly release the allocated memory.
class Person
{
....................................
~Person()
{
delete [] name;
}
};
Complexity
The vector container uses contiguous space of dynamic memory, thus it permits accessing an element through the [] operator, computing the offset from the beginning. When the allocated space is entirely used, the vector reallocates itself into a bigger, unique memory block, freeing the old memory zone. This involves: invoking the specific memory allocator, calling the copy constructor for moving each element into the new memory block, calling the destructor for each element in the old memory block, and freeing the container memory. Ideally, a vector container is allocated once, when we can estimate its maximum capacity.
The vector container is efficient for adding/removing elements at/from the end of the container (using the push_back() and pop_back() functions). Those operations don't require moving the elements to make room for a newly inserted element, or to occupy the free memory resulting from deleting an element. It is also efficient to access an element using the [] operator, because it involves only incrementing the beginning address of the block with the index (position) of the element in the vector. Inserting (deleting) elements at the beginning or in the middle of the vector is inefficient, because it requires moving the elements to make room for the new element (to occupy the free memory).
Another problem which needs to be considered is the one related to invalid iterators. As a consequence of reallocating a vector or deleting an element to which an iterator points, iterators can become invalid. So, before reusing an iterator, we must make sure that we have correctly initialized it.
