C++ Vectors STL

Vectors contain contiguous elements stored as an array. Accessing members of a vector or appending elements can be done in constant time, whereas locating a specific value or inserting elements into the vector takes linear time. 

In simple words, vector are Dynamic Array with more functionality.

How do Vector acts as a Dynamic Array?
To understand this we will look into the working of a vector using a simple example. Let us say that we have elements 1,2,3,4,5,6,7,8,9,10 which we want to store in a vector.

• When we initialize a vector and don't specify any size then its default size is 1 in which we insert the 1.
• Now when we try to insert 2, we don't have any more space in a vector so that time it creates a new vector with size 4 and copies all the previous vector data to it and inserts 2.
• Now we can insert 3 and 4 without altering the size of a vector. Now again when we try to insert 5, we don't have space so that time it creates a new vector of size 8 and copies all the data to it and inserts 5.
• Now we can insert 6,7, and 8 to the vector. Now again when we try to insert 9, we don't have space so that time it again creates a new vector of size 16 and copies all the data to it and inserts 9.
• Finally, it inserts 10.

So whenever a vector increases its size then it is twice the previous vector size.

Vector Operators which are present in STL

For code demonstration purposes let us take V as a integer vector and iter as an iterator.

• assign - assign elements to a vector
• Assigning 1 to first 10 location: V.assign(10,1)
• Copying element of another vector named data: V.assign( data.begin( ), data.end( ) )
• at - returns an element at a specific location
•  To get number present at index i: V.at( i )
• back - returns the last element of a vector
• To get the last element: V.back()
• begin - returns an iterator to the beginning of the vector
• iter=V.begin( ) // returns the address of first element.
• capacity - returns the number of elements that the vector can hold
• V.capacity( )
• clear - removes all elements from the vector
• V.clear( )
• empty - True if the vector has no elements
• V.empty( )
• end - returns an iterator just past the last element of a vector
• iter=V.end( ) // returns address 1 greater then last element address. To get the address of the last element subtract 1 from iter.
• erase - removes the element from a vector
• Removing single element: V.erase( iterator )
• Removing element in a range: V.erase( startIterator, endIterator )
• front - returns the first element of a vector
• To get the first element: V.front( ) 
• insert - inserts elements into the vector
• max_size - returns the maximum number of elements that the vector can hold
• pop_back - removes the last element of a vector
• Removes the last element: V.pop_back( )
• push_back - add an element to the end of the vector
• Appends the element to the vector: V.push_back( )
• rbegin - returns a reverse_iterator to the end of the vector
• rend - returns a reverse_iterator to the beginning of the vector
• reserve - sets the minimum capacity of the vector
• Reverse the vector: reverse( V.begin( ), V.end( ) )
• resize - change the size of the vector
• size - returns the number of items in the vector
• swap - swap the contents of one vector with another vector.

Now we will be implementing these operators and learning the most of them. Let's begin by creating a vector.

assign()

• This function either gives the current vector the values from start to end or gives it a specified number of copies of value from the start position.
• This can also be used to copy an element from one vector to another as we have done in the above code.

at()

• This function returns a reference to the element in the vector at index (Index to be passed to it as Parameter ). The at() function is safer than the [] operator, because it won't let you reference items outside the bounds of the vector.

begin()

• This returns a reference iterator to the first element of the vector and runs in constant time.

end()

• The end() function returns a reference iterator just past the end of the vector.
• If you want to get the lase element then just subtract 1 from this as this will reference the last element in the vector.

push_back()

• This appends (adds the value in the dynamic array in the end) the value to the end of the vector.
• Runs in constant time ie. O(1).

pop_back()

• This removes the last element of the vector.
• Runs in constant time as in push_back().

insert()

• The insert function either
• inserts value before the given index, returning an iterator to the element inserted,
• inserts num copies of value before the given index
• inserts the elements from start to end before the given index
• Note - 
• Inserting elements into a vector can be relatively time-intensive since the underlying data structure for a vector is an array. In order to insert data into an array, you might need to displace a lot of the elements of that array, and this can take linear time. 
• If you are planning on doing a lot of insertions into your vector and you care about speed, you might be better off using a container that has a linked list as its underlying data structure(such as List or a Deque).

empty()

• The returns (1) true if the vector has no elements, (0) false otherwise.

clear()

• This deletes all of the elements in the vector.

Multidimensional Vectors.

In this section, we will learn about creating multi-dimensional vectors. In multidimensional, vector we can implement dynamic two-dimensional array, a three-dimensional array, etc. For the purpose of explanation, we will be using 2 Dimensional Dynamic Array Implementation.

Fig 2: 2D Vector

To implement the above 2d list we need to use a two-dimensional vector. Here we will implement this when we know the number of rows. Let rows are N.

• Create a 2d vector for above like this.
• vector<int> matrix[N]
• To push element in this we use the row number (that to which row we have to store a particular value ).
• Let u be the row number and v be the value to be inserted in the vector. This can be done as
• matrix[u].push_back(v)

To implement the two-dimensional vector when we don't have any idea about the number of rows or columns.

• Create a 2d vector as this
• vector < vector <int> > data.
• Here the number of rows and columns both are dynamic so to insert some data in a row, first we make 1d vector and insert column element in this and at end we insert this into the 'data' vector.
• For eg. in the first row we have five element { 1, 2, 3, 4, 5} so we will prepare 1d vector with these element (say vector<int> temp - contains 1, 2, 3, 4, 5) then we will insert this into the 'data' vector like this data.push_back(temp).

If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA