Question

Explain in your own words the algorithm (= sequence of steps) you would use in order to implement a function Vector::pop_front() and a function List::operator [](int i). Although these functions are not provided in the Standard Template Library (STL) for vector and list, we could certainly create them. In your explanations above, state the likely (and good) reason why the STL does not include these functions.

Answer 1

push_back() and pop_back() functions is included in vector as it takes O(1) time to execute.
- If we want to insert an element in the beginning (push_front()) of the vector then we will have to shift all the existing elements by 1 in the right direction and then put the element at the beginning.
- Similarly if we want to delete an element from the beginning of vector (pop_front()) then we have to shift all existing elements by 1 in the left direction because the starting index becomes vacant.
So both the operations will take O(n) time to perform and this is why STL does not include these functions in vector.

Algorithm for function Vector::pop_front():
Step 1: Read vector V
Step 2: for i = 0 to V.size() -1 repeat step 3
Step 3: V[i] = V[i+1]
Step 4: Delete last value using V.pop_back();

Since List does not provide random access of it's node. So if we want to access any node of list we have to traverse from the beginning of the list (list.begin()).
So to access the n-th node, the execution will take O(n) time and this is why STL does not include this function too.

Algorithm for function List::operator[](int i)
Step 1: Read list L
Step 2: Read i which is passed in parameter
Step 3: Set the iterator it as list.begin using list <int> :: iterator it = list.begin();
Step 4: for i = 0 to i repeat step 5
Step 5: increase it by 1 using it++
Step 6: return the value of iterator (*it)