C++ Vectors

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: Adjacency List ( Graph Representation )

To implement the above adjacency 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> adj[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
      • adj[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.
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 CODELABS3277

Comments