Implement pop_front operation for a vector in C++

Write code to implement pop_front operation for a vector in C++. The pop_front operation should remove the first element from the vector and maintain the order of the remaining elements.

We know that std::vector only supports push_back and pop_back operations. Both operations run in constant time. The pop_front operation will take at-least O(n) time since the vector is backed by an array and all the remaining elements need to be shifted by one position to the left to preserve the order. If the total number of pop_front operations is more, the std::list container should be preferred, which is implemented as a double-ended queue (deque).

So pop_front operation will take linear time and should be called only if the vector contains only a few elements. Here’s one feasible implementation of the pop_front function, which simply erases the first element of the vector using the vector::erase function. The vector::erase function requires an iterator pointing to the element to be removed from the vector, and we can get an iterator to the first element of a vector by calling vector::begin.

#include <iostream>

#include <vector>

template<typename T>

void pop_front(std::vector<T> &v)

{

if (v.size() > 0) {

v.erase(v.begin());

}

int main()

{

std::vector<int> nums = { 1, 2, 3, 4, 5 };

pop_front(nums);

for (int i: nums) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

Output:

2 3 4 5

Luckily if we don’t need to maintain the order of the remaining elements in the vector, we have a constant time solution, which includes moving the last element of the vector to the front. We can do this with the help of the std::move function.

#include <iostream>

#include <vector>

template<typename T>

void pop_front(std::vector<T> &v)

{

if (v.size() > 0)

{

v.front() = std::move(v.back());

v.pop_back();

}