Programming Interview Question: Vector

Look at the following program written in C++ and see if you can spot the error. Assume that populate_vector() is a function that returns a vector. (Note: This program will compile.)

#include <vector>
 
int main() {
   const int x = 5;
 
   std::vector<int> myvector = populate_vector();
 
   int size = myvector.size();
 
   for(int i = 0; i < size; i++){
      if(myvector.at(i) == x) {
         myvector.erase(myvector.begin()+i);
      }
   }
   return 0;
}

To view the solution click read more.

Answer

Storing the size of the vector before the loop is the biggest problem because once an element is deleted the vector size has shrunk by one, but the size variable is not updated. Calling myvector.at(i) will throw an out_of_range exception if an element was erased. If operator[] was used (i.g. if(myvector[i] == x)) the program will not throw an exception, but it is still going out of range which is never a good idea.

Code Rewrite

Since an STL container is being used, it's probably a good idea to use the provided iterators (that's what they are there for!). Initialize the iterator at the beginning and change the for loop to a while loop on the condition that the iterator is not at the end. If the current value is the value we want to erase, erase it. A nice thing about the erase function is that it returns an iterator at the position following the one just erased or the end if it was the last element. If it is not the value we want to remove, simply continue on to the next value.

#include <vector>
 
int main() {
   const int x = 5;
 
   std::vector<int> myvector = populate_vector();
 
   std::vector<int>::iterator it = myvector.begin();
   while( it != myvector.end() ) {
      if(*it == x) {
         it = myvector.erase(it);
      } else {
         ++it;
      }
   }
 
   return 0;
}