Vectors Unleashed -- A Closer Look at the STL
Vectors are popular among developers for their efficiency and simplicity. Let us take a look at the ways in which vectors can be created, and the operations that help in inserting, accessing and removing elements from them.
In the last article in this series on advanced C++ programming, we got accustomed to the various components of the standard template library (STL). Now, let us take a closer look at these components. We shall first discuss containers, which are used to store objects. The STL provides various containers that can prove helpful in different situations.
Containers in STL
The containers offered by STL are generic in nature -- hence they are type independent. They include vectors, deques, lists, sets (and multi-sets) and maps (and multi-maps). As mentioned before, vectors are dynamic arrays, and can easily replace ordinary arrays. A deque is similar to a vector, but provides faster insertions and deletions at both ends. Elements are sorted while storing in the case of both sets and multi-sets, which are identical except for the fact that multi-sets can store duplicates, while sets cannot. Maps offer storing elements in terms of key-value pairs. A multi-map differs from a map in providing the flexibility required to store duplicates. In the case of maps, as well, elements are sorted according to some criterion.
Introducing vectors
As mentioned earlier, the std::vector behaves like a dynamic array. By virtue of the generic nature of STLs, we can store any type into a vector. It should be noted that when objects are stored in a vector, they get copied. Hence, these objects should have a default constructor and assignment operator. A destructor should also be provided to facilitate the operation of deletion.
Vectors provide random access to their elements. Also, the iterators used to access the elements of the vector are random access iterators. Hence, these are very compatible with any algorithm provided by the STL library.
Vector creation and initialisation
Having introduced vectors and their characteristics, we shall now look at how we can create and initialise a vector. The STL provides various ways to do this.
1. Creating an empty vector: The code listed below creates a vector having no elements. The default capacity and size are chosen in this case, and are implementation dependent.
#include "vector"
std::vector vecInt;
2. Creating a vector from an existing one: It is possible to create a vector from an existing one. In such a case, all the content of the original vector gets copied to the newly created one. The code snippet listed below illustrates this.
std::vector vecInt(vecInt1); // vecInt1 is an already
2existing vector
3. Creating a vector with a predetermined size: We can create a vector even if we know only the number of elements it is going to store. This can enhance performance by limiting its dynamic growing capabilities. The code snippet listed below illustrates the creation of a vector, whose size is predetermined.
std::vector vecInt(1000); The code above initialises vecInt with 1000 elements. There won’t be any dynamic memory allocation till the vector reaches that size. Some implementations reserve additional memory too -- to enhance performance. Memory allocation is a very important criterion for choosing a particular type of container.
4. Creating a vector with a predetermined size and a value: Taking the method mentioned above a step further, we can also specify a default value to the vector at the time of initialisation. This is illustrated in the code snippet shown below.
std::vector vecInt(1000,27);
Here we initialise a vector with 1000 elements, and each of the elements is initialised with the value, 27.
5. Creating a vector by specifying a range: Initialising a vector by means of another has been mentioned above (refer to case 2). It is also possible to create a vector by specifying a range. A range can be specified by using iterators, as is shown in the code snippet below.
std::vector::iterator itStart = vecInt.begin();
std::vector::iterator itEnd = vecInt.end();
std::vector vecInt2(itStart,itEnd);
The code above yields the same result as in Case 2. The start and the end iterator might point to any location, thus adding flexibility to create a vector from an existing one.
Having discussed the creation of a vector, we shall now look at the various operations supported by vectors. These can be broadly classified into non-modifiable operations and modifiable operations. Non-modifiable operations mainly provide information. Some of the non-modifiable operations are size(), empty(), max_size(), capacity(), etc. Comparison operators are also non-modifiable operations. Modifiable operators change the contents of a particular vector. An assignment operator is one such example. Other modifiable operations are assign() and swap().
Non-modifiable operations
To obtain the size of a vector at any point of time, we can use the size() function.
std::vector vecInt;vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
vecInt.size(); // yields 4.
max_size() provides the maximum number of elements the vector can hold, "capacity()" provides the number of elements it can store without reallocation, and "empty()" returns whether the vector is empty or not. Vectors also support the "==", "!=", "<", ">", "<=" and ">=" operators. These have the same meaning as in C++.
Modifiable operators
Assignment operations are modifying operations. The following code snippet shows how the assignment operator can be used.
std::vector vecInt;
std::vector vecInt1;
vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
vecInt1 = vecInt; // Here contents of vecInt1 are modified to
contain the elements of vecInt.
The STL provides more flexible assignment functionality by providing the assign function for use in the manner shown below.
std::vector vecInt;
vecInt.assign(10, 27); // This assigns the 10 copies of 27
The assign function can also take a range. We need to provide the start iterator and the end iterator in case a range needs to be specified for this function.
std::vector vecInt;
std::vector vecInt1;
vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
std::vector::iterator itBegin = vecInt.begin();
std::vector::iterator itEnd = vecInt.end();
vecInt1.assign(itBegin,itEnd); // All the elements from itBegin
to itEnd are assigned to vecInt1
The STL provides the swap faction a functionality that enables the swapping of the elements of two vectors. It comes in two varieties -- first, as a member function of the vector class, and, alternatively, as a global function. The example below illustrates this functionality.
std::vector vecInt;
std::vector vecInt1;
vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
vecInt1.swap(vecInt); // This swaps all the elements from
vecInt to vecInt1
Accessing the elements of a vector
There are various ways by which elements of a vector can be accessed. The STL provides the subscript operator [], at(), front() and back() to access elements.
std::vector vecInt;vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
….
In the above example, vecInt[2] accesses the third element of the vector. There is a disadvantage of using the subscript operator. No range checking is done by default, which could lead to access violations. The STL provides a safer way to access the elements, which is similar to the subscript operator. This functionality is provided by means of the at() operator. The usage is vecInt.at(2). In case the range exceeds the permissible limits, an exception is thrown up. The first element can be accessed by using vecInt.front(), and the last element by using vecInt.back(). The following example illustrates the usage of these functions.
std::vector vecInt;vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
vecInt.push_back(14);
vecInt.push_back(15);
std::cout << "Using [] operator :" << vecInt[1] << std::endl;
// yields 11
std::cout << "Using at() : " << vecInt.at(1) << std::endl; //
yields 11
std::cout << "Using front () : " << vecInt.front() <<
std::endl; // yields 10
std::cout << "Using back () :" << vecInt.back() << std::endl;
// yields 15
Inserting and removing elements
Some inserting functions have already been used in the examples above. We shall now look at each one of these in more detail. The STL provides the insert() and push_back() functions to insert elements into the vector. The insert() function has three variants. The code listing below illustrates each of these.
std::vector vecInt;vecInt.push_back(10);
vecInt.push_back(11);
vecInt.push_back(12);
vecInt.push_back(13);
vecInt.push_back(14);
vecInt.push_back(15);
std::vector::iterator itBegin = vecInt.begin();
std::vector::iterator itEnd = vecInt.end();
// Case 1
vecInt.insert(itBegin,20); // Will insert the position of
// the element iterator
// position. Here it is at the beginning.
// Case 2
vecInt.insert(itBegin,4,20); // Will insert four copies of 20 at the beginning.
// Case 3
vecInt.insert(itBegin,itBegin,itEnd); // Will insert the whole
of vecInt at the beginning, thereby doubling the size and
duplicating the contents. This is particularly useful when we
have to copy a range from another vector.
The push_back() function inserts elements at the end, and is the most popular way used to insert elements into a vector. The above example illustrates its usage.
The typical remove operations supported by vectors are pop_back(), erase() and clear(). Another modifiable operation of interest is the resize() function, through which we can manually alter the size of the vector. To remove the last element of a vector, we can use the pop_back() function. It does not return the last value -- it just removes the last element. The erase function erases the contents at a particular location pointed to by the iterator. The usage is vecInt.earse(it), where "it" is the position pointed to by the iterator. The erase function can also specify a range to erase. To erase a range, we need to mention the iterator at the start and at the end. The resize function changes the size of the vector to a specified value. Elements are created in the resized vector by means of a default constructor. It is also possible to mention the element to be stored in the resized vector by passing it as the second parameter. To remove the entire contents of a vector, we may use the clear() function. The following example illustrates the usage:
// vecInt is a vector of integers
...
vecInt.pop_back(); // removes the last element
vecInt.erase(it); // erases the element at position ‘it’
vecInt.erase(itStart,itEnd); // erases elements in the range
itStart and itEnd
vecInt.resize(20); // Resizes the size to 20 and fills all the
created elements with the default constructor
vecInt.resize(20,88); // Resizes the size to 20 and fills the
added elements with the value 88
vecInt.clear() // Clears the content of the vector
Before concluding this article on vectors, it seems worthwhile to look at the different iterator functions provided to navigate the contents of a vector. To get the initial position of a vector, begin() can be used. Similarly, to get the end position of a vector, the end() function can be used. The functionality for reverse iteration is also provided by the STL. The counterparts for begin() and end() for reverse iteration are rbegin() and rend().
Vectors provide numerous functions for the efficient storage and management of data. I am sure that the concepts presented in this article will kindle your curiosity to explore vectors even further.
By: Indrajith K. The author is an avid Linux enthusiast having more than six years of experience in software development.
No comments:
Post a Comment