Стирание элементов из вектора

c++ vector stl erase

126066 просмотра

4 ответа

Я хочу очистить элемент от вектора, используя метод стирания. Но проблема здесь в том, что элемент не гарантированно встречается в векторе только один раз. Это может присутствовать несколько раз, и мне нужно очистить их все. Мой код примерно такой:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    std::vector<int>::iterator endIter = myNumbers_in.end();
    for(; iter != endIter; ++iter)
    {
        if(*iter == number_in)
        {
            myNumbers_in.erase(iter);
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<int> myNmbers;
    for(int i = 0; i < 2; ++i)
    {
        myNmbers.push_back(i);
        myNmbers.push_back(i);
    }

    erase(myNmbers, 1);

    return 0;
}

Этот код явно дает сбой, потому что я изменяю конец вектора, перебирая его. Каков наилучший способ достичь этого? Т.е. есть ли способ сделать это без многократного повторения вектора или создания еще одной копии вектора?

Автор: Naveen Источник Размещён: 07.10.2019 08:45

Ответы (4)


151 плюса

Решение

Используйте идиому удаления / удаления :

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

В результате происходит removeсжатие элементов, которые отличаются от значения, которое будет удалено ( number_in) в начале, vectorи возвращает итератор к первому элементу после этого диапазона. Затем eraseудаляет эти элементы (значение которых не указано).

Автор: Motti Размещён: 07.12.2008 11:07

48 плюса

Вызов erase лишит законной силы итераторы, вы можете использовать:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    while (iter != myNumbers_in.end())
    {
        if (*iter == number_in)
        {
            iter = myNumbers_in.erase(iter);
        }
        else
        {
           ++iter;
        }
    }

}

Или вы можете использовать std :: remove_if вместе с функтором и std :: vector :: erase:

struct Eraser
{
    Eraser(int number_in) : number_in(number_in) {}
    int number_in;
    bool operator()(int i) const
    {
        return i == number_in;
    }
};

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());

Вместо написания собственного функтора в этом случае вы можете использовать std :: remove :

std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());
Автор: dalle Размещён: 07.12.2008 10:22

12 плюса

  1. Вы можете перебирать, используя индекс доступа,

  2. Чтобы избежать сложности O (n ^ 2), вы можете использовать два индекса: i - текущий индекс тестирования, j - индекс для хранения следующего элемента и в конце цикла новый размер вектора.

код:

void erase(std::vector<int>& v, int num)
{
  size_t j = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] != num) v[j++] = v[i];
  }
  // trim vector to new size
  v.resize(j);
}

В этом случае у вас нет аннулирования итераторов, сложность равна O (n), а код очень лаконичен, и вам не нужно писать некоторые вспомогательные классы, хотя в некоторых случаях использование вспомогательных классов может принести пользу в более гибком коде.

Этот код не использует eraseметод, но решает вашу задачу.

Используя чистый stl, вы можете сделать это следующим образом (это похоже на ответ Motti):

#include <algorithm>

void erase(std::vector<int>& v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}
Автор: sergtk Размещён: 07.12.2008 11:44

3 плюса

В зависимости от того, почему вы это делаете, лучше использовать std :: set, чем std :: vector.

Это позволяет каждому элементу появляться только один раз. Если вы добавите его несколько раз, в любом случае будет только один экземпляр для удаления. Это сделает операцию стирания тривиальной. Операция стирания также будет иметь меньшую временную сложность, чем в векторе, однако добавление элементов происходит медленнее в наборе, поэтому это может быть не большим преимуществом.

Это, конечно, не сработает, если вас интересует, сколько раз элемент был добавлен к вашему вектору или порядок добавления элементов.

Автор: Laserallan Размещён: 07.12.2008 11:18
Вопросы из категории :
32x32