13,093,531 members (62,801 online)
alternative version

#### Stats

65.2K views
62 bookmarked
Posted 18 Oct 2007

# The complete guide to STL: Part 1 - Vector

, 18 Oct 2007
 Rate this:
An introduction to the STL vector.

## 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:

1. Containers – classes capable of holding multiple elements of the same type.
2. Iterators – generalize the main methods to access a container element.
3. 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:

1. 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.
2. list – implements the double linked list.
3. 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:

1. set – defines a set of unique, sorted elements.
2. multiset – defines a set of sorted elements.
3. map – defines a set of unique, sorted elements, an element being a key – value pair.
4. 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:

1. stack – it can adapt vector, list, and deque.
2. queue – can adapt list and deque.
3. 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 `double`s:

```vector<double> vec;
cout << "Size of vec is " << vec.size();

// Output
// Size of vec is 0```

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();

// Output
// Size of vec is 5```

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] << " ";

// Output
// Size of vec is 5
// vec: 8.8 8.8 8.8 8.8 8.8```

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] << " ";

// Output
// vec: 3.45 67 10 0.67 8.99```

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] << " ";

// Output
// veccopy: 3.45 67 10 0.67 8.99```

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] << " ";

// Output
// vec: 3.45 67 10 0.67 8.99```

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] << " ";

// Output
// vec: 8.8 8.8 8.8 8.8 8.8```

### 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] << " ";

// Output
// vec: 8.8 8.8 8.8 8.8 8.8```

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) << " ";

// Output
// vec: 8.8 8.8 8.8 8.8 8.8```

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 << " ";

// Output
// vec: 8.8 8.8 8.8 8.8 8.8```

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;

// Output
// 3.45 8.99```

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 << " ";

// Output
// reverse of vec: 8.99 0.67 10 67 3.45```

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");

// Output
// vec: 2.0 4.0 6.0```

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);

// insert value 67 at the position specified by iterator it
it = vec.end();
vec.insert(it, 67);
print(vec, "vec");

// insert value 90 three times at the position specified by iterator it
it = vec.begin();
vec.insert(it, 3, 90);
print(vec, "vec");

// insert values from an array at the positon specified by iterator it
double array[5] = {1, 2, 3, 4, 5};
it = vec.begin() + 3;
vec.insert(it, array, array + 5);
print(vec, "vec");

// Output
// vec: 2 4 6 67
// vec: 90 90 90 2 4 6 67
// vec: 90 90 90 1 2 3 4 5 2 4 6 67```

### 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");

// Output
// vec: 3.45 67 10 0.67```

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;

// erase second element of vec
it = vec.begin() + 1;
vec.erase(it);

print(vec, "vec");

// Output
// vec: 3.45 10 0.67 8.99```

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();

// Output
// size of vec is 0```

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";

// Output
// vec is 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();

// Output
// vec size is 1
// vec capacity is 1
// vec maximum size is 536870911```

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();

// Output
// vec capacity is 1
// vec capacity is: 50```

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");

// case when new size <= size of vector
vec.resize(3);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");

// case when new size > size of vector
vec.resize(10);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");

// Output
// vec size is 5
// vec: 3.45 67 10 0.67 8.99
// vec size is 3
// vec: 3.45 67 10
// vec size is 10
// vec: 3.45 67 10 0 0 0 0 0 0 0```

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;
}

// Output
// 1 3 5 7 9
// 2 4 6 8 10
//
// 1 3 5 7 9
// 2 4 6 8 10```

### Vectors of pointers

As mentioned before, vectors can also store pointers. In the following example, we create a vector capable of storing pointers to `double`s:

```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] << " ";

// Output
// 00481C30 00481BF0 00481A10 10 20 30```

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();

// Output
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Point: 1, 5
// Point: 3, 5
// Point: 0, 0```

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();

// Output
// Bill Gates 50
// John Malcom 67
// Scott Meyers 34
// Mark Gosling 40
// Anonymous 0
//
// Bill Gates 50
// John Malcom 67```

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.

## Share

 Software Developer (Senior) Romania
No Biography provided

## You may also be interested in...

 Pro

 View All Threads First Prev Next
 Good article Hatem Mostafa20-Oct-07 3:07 Hatem Mostafa 20-Oct-07 3:07
 As it is for beginners u took my 5. Thank u for this v good article. One advice: Next time u update the article add a section "Updates" at the end of the article to include any new update. I think u have added the section of "Two dimensional vectors", or I missed it in my first read. Some times we back to good articles to check for any new updates to read Any way keep writing. Waiting for u next article. Thanks Hatem
 Re: Good article cristitomi21-Oct-07 9:57 cristitomi 21-Oct-07 9:57
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Aug-17 20:22 Refresh 1