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

      Comments