Sequence Containers- Vectors (sstutor)

Sequence Containers

As the name implies, these containers will have elements arranged in a linear manner. There are 3 types of sequence containers:

Vectors
Deque
List

There are many functions which are common to all sequence containers while a few are specific to some of them.

Vectors

A vector is basically an array, which can grow dynamically in size as and when required. The programmer does not need to worry much about memory management since this is taken care of automatically. The following are some interesting points to note regarding vectors:

Though vectors can grow dynamically in size, they still need to occupy contiguous memory locations (just like arrays). So, suppose you increase the size of your vector from 4 elements to 5 and if there isn’t contiguous memory space available at the current location then the vector will be moved to some other memory location where contiguous space for all the elements are available (effectively it will copy the elements to the new location and then destroy the old one). This process brings to light one disadvantage of using vectors.
Another problem is when you are inserting an element in the middle of a vector. In this case, all the elements that should follow the inserted element have to be shifted before the element can be inserted.
Vectors are useful when random access to elements is needed. This can be done using subscripts (just like arrays).
Vectors provide boundary checking also (something that isn’t available in arrays and which generally leads to a lot of errors in programs). Boundary checking means that you cannot attempt to reference a vector element outside the defined range (for example if your vector can hold 100 elements then you cannot attempt to access the 105^th element. This was a problem in arrays since such checking is not available).
Vectors are recommended if your program is going to add elements to the end of the vector and if random access is required.

Function	Use
*front( )	Returns the value of the first element stored in the vector.
*back ( )	Returns the last element value stored in the vector.
*push_back( )	Pushing a new element (specified by the argument) into the container
*pop_back( )	Pops out the element at the end of the container (no arguments for this function).
*assign( )	Assign values to elements of the container
capacity( )	Returns the maximum elements that can be stored in the vector before automatic resizing

Note: * denotes that these functions are available in all sequence containers.

Capacity and Size of a vector:

Vectors keep resizing automatically as they increase in size. Thus memory is allocated automatically when needed as demonstrated in the program below:

#include <iostream>
#include <vector>
using namespace std;

int main( )
{
vector<int> intvector;
intvector.push_back(1);
cout<<"Size is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

intvector.push_back(2);
cout<<"\nSize is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

intvector.push_back(3);
cout<<"\nSize is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

intvector.push_back(4);
cout<<"\nSize is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

intvector.push_back(5);
cout<<"\nSize is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

intvector.push_back(6);
cout<<"\nSize is:"<<intvector.size( )<<" Capacity : "<<intvector.capacity( );

return 0;
}

The output is:

Size is:1 Capacity : 1

Size is:2 Capacity : 2

Size is:3 Capacity : 4

Size is:4 Capacity : 4

Size is:5 Capacity : 8

Size is:6 Capacity : 8

Size denotes the amount of memory space currently being used by the vector and capacity denotes the amount of memory allocated for the vector (as more space is needed this will keep increasing). It can be observed

Thus memory is allocated as follows:

If the size of the vector is less than the capacity (i.e. the vector can still accommodate more elements without more memory being wanted) and if you insert an element, extra memory will not be allocated.
If the size is equal to the capacity and if you insert an element then the capacity (i.e. the space occupied by the vector) will be doubled.

Using overloaded operators on STL containers:

Let’s take a look at the overloaded operators which are available in all containers using a simple program.

//illustrating the use of overloaded operators in STL vectors

#include <iostream>
#include <vector>
using namespace std;

int main( )
{
vector<int> intvec1;
vector<int> intvec2;
vector<int>::const_iterator ptr; //declaring a constant iterator

intvec1.push_back(10);
intvec1.push_back(20);
intvec2.push_back(20);

if (intvec1<intvec2)
{
cout<<endl<<"Vector 1 is less than vector 2."<<endl;
intvec1=intvec2;
}

cout<<endl<<"Vector 1 now contains: ";

for ( ptr=intvec1.begin( ); ptr!=intvec1.end( ); ptr++ )
{
cout<<" "<<*ptr; //dereferencing the iterator
}

return 0;
}

The output will be:

Vector 1 is less than vector 2.

Vector 1 now contains: 20

The code

vector<int>::const_iterator ptr;

is used to declare a constant iterator which can be used to only read the elements of a container.

When using the overloaded operators on containers, take note of the following points:

The 2 containers being compared should be of the same type (i.e. if we have a vector containing integers then it can be compared or assigned to another vector of type integer).

The relational operators work on an element by element comparison. In the above program:

Even though the size of vector 1 is more than vector 2, the first element of vector 2 is greater than that of vector 1 (20 > 10).

Go to the next section on Subscripts and Vectors

Go back to Contents page 2.