Альтернатива для std: vector для удаления ее элементов при прохождении цикла?

Question

У меня есть моя петля, проходящая через элементы вектора. Хотя в этом цикле некоторые элементы (я хочу, чтобы они были) удалены. Хотя std :: vector не позволяет это делать, и я хотел бы получить альтернативу.

for(unsigned int j = 0; j < rectArray.size(); j++) 
{ 
if(rectArray[j] == 2) 
    { 
    rectArray.erase(rectArray.begin() + j); 
    } 
//... 
} 

Считаете ли вы, что std :: list будет хорош здесь? Могу ли я использовать что-то еще?

Answer 1

Я бы предложил изменить ваш код таким образом, чтобы он использовал итераторы вместо фактического вектора. Это намного чище и эффективнее, как это:

for (auto it = rectArray.begin(); it != rectArray.end(); ++it) 
{ 
    // Access the current element with *it 
    // If you want you can pass `it` and `rectArray.end()` as 
    // the lower and upper bounds of the new collection, 
    // rather than doing expensive resizes of the vector. 
} 

Обратите внимание, что auto является C++ 11 функция (как я использовал его). Если ваш компилятор поддерживает, что вы также можете использовать 11 C++ в Еогеасп:

for (auto it : rectArray) { 
    // same as before 
} 

Answer 2

Извлечение элемента из середины вектора дорого - потому что вам нужно переместить все последующие элементы вниз.

Если вам нужно добавить/удалить элементы в середину контейнера, список обычно лучше.

Answer 3

Если элементы вектора очень дороги для копирования, самым простым, вероятно, является std::copy_if (или иначе скопировать те, которые вы хотите сохранить) в новый вектор, а затем замените их на оригинал. Также есть remove_if, а затем resize.

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

Answer 4

Список будет лучше, чем вектор - так как вам не потребуется ничего, чтобы удалить элементы из середины списка. С другой стороны, удаление элементов из середины вектора имеет линейную сложность.

Answer 5

Возможная альтернатива std::remove_if. Немного быстрее и не требует функтора, однако он не поддерживает порядок.

auto end = std::end(rectArray); 
for(auto it = std::begin(rectArray); it != end; ++it) 
{ 
    if(it->remove_me()))  
     std::swap(*it, *--end); // or even faster *it = std::move(*--end); 
}  
rectArray.erase(end, std::end(rectArray)); 

Answer 6

Если вы делаете много удалений, список, вероятно, путь. Вот несколько примеров кода, которые помогут.

#include <vector> 
#include <list> 
#include <algorithm> 

using namespace std; 

class Widget 
{ 
public: 
    explicit Widget(int someNumber); 
    bool ShouldDelete(); 
    bool ShouldDeleteComplex(int a, int b, int c); 
private: 
    int _someNumber; 
}; 

Widget::Widget(int someNumber) : _someNumber(someNumber) 
{ 
} 

bool Widget::ShouldDelete() 
{ 
    if (_someNumber > 2) 
    { 
     return true; 
    } 
    return false; 
} 

bool Widget::ShouldDeleteComplex(int a, int b, int c) 
{ 
    if ((a * b - c) > _someNumber) 
    { 
     return true; 
    } 
    return false; 
} 

int main() 
{ 
    list<Widget> lw; 

    lw.push_back(Widget(1)); 
    lw.push_back(Widget(2)); 
    lw.push_back(Widget(3)); 

    // delete from list using functor 
    lw.remove_if(mem_fun_ref(&Widget::ShouldDelete)); 

    // delete from list using lambda function 
    lw.remove_if([] (Widget& x) { return x.ShouldDeleteComplex(1, 2, 0); } ); 

    vector<Widget> vw; 

    vw.push_back(Widget(1)); 
    vw.push_back(Widget(2)); 
    vw.push_back(Widget(3)); 

    // delete using functor 
    vw.erase(remove_if(vw.begin(), vw.end(), mem_fun_ref(&Widget::ShouldDelete)), vw.end()); 

    // delete using lambda function 
    vw.erase(
     remove_if(vw.begin(), vw.end(), 
     [] (Widget& x) { return x.ShouldDeleteComplex(1, 2, 0); } 
    ), 
     vw.end()); 

    return 0; 
}