Error deleting elements from a vector

Question

I'm trying to do a method where I have to delete a number from a vector of integers, and that number is passed as a parameter. The problem that I'm having right now is that when I try to delete the same number in consecutive positions, only one of them is deleted.

For example:

vector = (1, 2, 2, 3, 4, 5) and I want to remove the number "2", the result will be:

vector = (1, 2, 3, 4, 5)

But if the number is not in consecutive positions, the method works fine:

vector = (1, 2, 3, 2, 4, 5) ---> remove "2"

vector = (1, 3, 4, 5)

The code that I have is this:

void deleteNumber(int n, vector<int> &numbers)
{
    bool hasEntered = false;

    int counter = 0;
    vector<int> deletedNumbers;

    for(unsigned i = 0; i < numbers.size(); i++)
    {
        if(numbers[i] != n)
        {
            counter++;
        }

        else
        {
            counter = 0;
            int counter2 = 0;
            bool deleted = false;

            for(unsigned j = 0; j < deletedNumbers.size() && deleted == false; j++) // Check if a number has been deleted before
            {
                if(deletedNumbers[j] != n)
                {
                    counter2++;
                }

                else
                {
                    deleted = true;
                    counter2 = 0;
                }
            }

            if(counter2 == (int) deletedNumbers.size()) // Remove the number if it hasn't been removed
            {
                deletedNumbers.push_back(n);
                for(unsigned k = 0; k<numbers.size(); k++)
                {
                    if(numbers[k]  == n)
                        numbers.erase(numbers.begin()+k);
                }

                counter2 = 0;
                hasEntered = true;
            }
        }
    }
}

I think that the error could be in the condition of the last for, where I finally remove the number.

The counters are used in order to determine if an element has been found or not. And also the method has to check if the item has been removed before.

If you don't understand something, please ask me.

Thanks in advance :)

Answer 1

you could try something like this:

void deleteNumber(int n, vector<int> &numbers)
{
    vector<int>numbers_without_n;
    for(unsigned i = 0; i < numbers.size(); i++)
        if(numbers[i] != n)
            numbers_without_n.push_back(numbers[i]);

    numbers = numbers_without_n;
}

Answer 2

Your code looks like too complicated, thus it can contain many bugs.

This would delete all instances of n; O(numbers.size()):

void deleteNumber(int n, vector<int> &numbers) {
  int i = 0;
  for (int j = 0; j < numbers.size(); ++j) {
    if (numbers[j] != n) numbers[i++] = numbers[j];
  }
  numbers.resize(i);
}

This would delete the first instance of n in each run; O(numbers.size()):

void deleteNumber(int n, vector<int> &numbers) {
  int i = 0;
  for (int j = 0; j < numbers.size();) {
    if (numbers[j] == n) {
      for (++j; j < numbers.size() && numbers[j] == n; ++j) {
        numbers[i++] = numbers[j];
      }
    } else {
      numbers[i++] = numbers[j++];
    }
  }
  numbers.resize(i);
}

This would delete the first instance of n; O(numbers.size()):

void deleteNumber(int n, vector<int> &numbers) {
  int i = 0;
  for (int j = 0; j < numbers.size(); ++j) {
    if (numbers[j] == n) {
      for (++j; j < numbers.size(); ++j) {
        numbers[i++] = numbers[j];
      }
      break;
    }
    numbers[i++] = numbers[j];
  }
  numbers.resize(i);
}

Pick whichever you need.

Please note that other answers, such as luk32's answer contain simpler code (using more STL) for deleting the first instance of n.

If you want to find and fix the bug in your code, I recommend that you try to find a very short input vector for which it fails, and then single-step through it in a debugger.

Answer 3

You don't need to have a loop inside the loop. The easiest way to handle the delete is to delete one item at a time and realize that this will mean you don't want to increment i when you have deleted an item. The easiest way to cancel the increment of i in the for loop is to decrement it first using --i. So you loop becomes

• Check if the item matches the number
• If so, delete the item and decrement i

Answer 4

Use std::remove and vector::erase

#include <algorithm>

void deleteNumber(int n, vector<int>& numbers)
{
   numbers.erase(std::remove(numbers.begin(), numbers.end(), n), numbers.end());
}

Answer 5

First, I'm not sure what counter and counter2 are used for - if they're just being used to determine if you've iterated to the end of the vector without finding an element, you don't need them.

For the purpose of 'check if a number has been deleted', you just need a single boolean variable at the very top of the method, i.e. not inside the scope of the for loop.

I believe the following:

if(counter2 == (int) deletedNumbers.size()) // Remove the numbers if it hasn't been removed

can be replaced with if (!deleted).

So, here's a 'fixed' version while trying to stay as close to your existing logic as possible based on your code comments. This may not be the most efficient/elegant implementation however, I believe I have seen some other answers that use algorithms from the STL library to achieve the same thing.

void deleteNumber(int n, vector<int> &numbers)
{
    bool deleted = false;

    for(unsigned i = 0; i < numbers.size(); i++)
    {
        if (numbers[i] == n)  // If we've found an instance of the number we're trying to delete
        {
            if (!deleted)  // Check if an instance has already been deleted
            {
                numbers.erase(numbers.begin() + i);  // Remove the number
                deleted = true;  // Flag that we have deleted an instance of the number
            }
        }
    }
}

Alternately, instead of using a flag for 'deleted' to prevent deleting numbers after the first instance, you could optimize by just returning after you delete the first instance - that will prevent the rest of the loop from executing.

Answer 6

Ok, since apparently std::vector::erase does exists I would use standard c++ features:

void deleteNumber(int n, vector<int> &numbers) {
 auto it = find(std::begin(numbers), std::end(numbers), n);
 if(it != numbers.end()) numbers.erase(it);
}

EDIT: Forgot that end() is not a valid argument for erase.