Стирание указателей от вектора при повторении другого вектора

Question

Я пробовал много других подобных вопросов, но ни один из них не помог мне. Моя проблема следующая: У меня есть 3 вектора указателей на мою структуру: vector<state*> где state - это мой тип структуры. Я пытаюсь удалить состояния из vectorCheck, если они находятся в vectorOpen или vectorClosed. Дело в том, что иногда это работает нормально, а иногда и нет. Согласно CodeBlocks это кажется проблемой, но я понятия не имею, чтобы это преодолеть. Я отлаживал свою программу шаг за шагом, и в какой-то момент состояние от vectorCheck не удаляется, несмотря на то, что оно находится в vectorClosed.

Итерация проводится 2 для петель:

vector<state*> vectorOpen; 
vector<state*>::iterator itOpen; 
vector<state*> vectorClosed; 
vector<state*>::iterator itClosed; 
vector<state*> vectorCheck; 
vector<state*>::iterator itCheck; 

for(itCheck = vectorCheck.begin(); itCheck != vectorCheck.end(); itCheck++) { 
     for(itOpen = vectorOpen.begin(); itOpen != vectorOpen.end(); itOpen++) { 
      if ((*itCheck)->player->x == (*itOpen)->player->x && 
       (*itCheck)->player->y == (*itOpen)->player->y && 
       (*itCheck)->box[0].x == (*itOpen)->box[0].x && 
       (*itCheck)->box[0].y == (*itOpen)->box[0].y) { 
       cout << "erasing as in open " << (*itCheck)->player->x << " " << (*itCheck)->player->y << " " << (*itCheck)->box[0].x << " " << (*itCheck)->box[0].y << endl; 
       vectorCheck.erase(itCheck); 
      } 
     } 
    } 

    for(itCheck = vectorCheck.begin(); itCheck != vectorCheck.end(); itCheck++) { 
     for(itClosed = vectorClosed.begin(); itClosed != vectorClosed.end(); itClosed++) { 
      if((*itCheck)->player->x == (*itClosed)->player->x && 
       (*itCheck)->player->y == (*itClosed)->player->y && 
       (*itCheck)->box[0].x == (*itClosed)->box[0].x && 
       (*itCheck)->box[0].y == (*itClosed)->box[0].y) { 
       cout << "erasing as in closed " << (*itCheck)->player->x << " " << (*itCheck)->player->y << " " << (*itCheck)->box[0].x << " " << (*itCheck)->box[0].y << endl; 
       vectorCheck.erase(itCheck); 
      } 
     } 
    } 

Где vectorCheck это максимальный размер 3. Для того, чтобы объяснить, что я имею в виду вот picture Где я говорю здесь о состояниях в зеленых прямоугольниками (3 1 2 4). Почему он не удаляется, как состояние в синем прямоугольнике (2 2 2 4)? Он должен быть удален, поскольку это состояние появилось уже в vectorClosed (код выше).

Что я делаю неправильно? Это не первая итерация программы, она происходит в виде 6-го или 7-го цикла.

Кроме того, это, вероятно, приводит к сбою моей программы позже.

Answer 1

Как упоминалось в моем комментарии, проблема в том, что вы продолжаете использовать итератор для стираемого элемента. std::vector::erase(i) аннулирует итератор itCheck.

Мы можем исправить это, воспользовавшись алгоритмами C++, такими как std::remove_if. Это может сделать код более сложным с первого взгляда, но вы обнаружите, что этот стиль кодирования позволяет повторно использовать фрагменты логики, улучшая читаемость и удобство обслуживания вашего кода.

Для начала давайте напишем функтор, который вам нужен.

struct states_are_equal : 
    public std::binary_function<state const *, state const *, bool> 
{ 
    bool operator()(state const * a, state const * b) const { 
     return a->player->x == b->player->x && 
       a->player->y == b->player->y && 
       a->box[0].x == b->box[0].x && 
       a->box[0].y == b->box[0].y; 
    } 
}; 

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

template <typename Iterator, typename Comparer> 
struct is_in_container_func : 
    public std::unary_function< 
     typename std::iterator_traits<Iterator>::value_type const &, 
     bool 
    > 
{ 
    is_in_container_func(Iterator begin, Iterator end, Comparer cmp) 
     : it_begin(begin), it_end(end), comparer(cmp) { } 

    bool operator()(argument_type i) const { 
     return std::find_if(it_begin, it_end, std::bind1st(comparer, i)) != it_end; 
    } 

private: 
    Iterator it_begin; 
    Iterator it_end; 
    Comparer comparer; 
}; 

// This is just a helper to allow template type deduction; its only purpose is to 
// allow us to omit the types for Iterator and Comparer when constructing an 
// is_in_container_func object. 
template <typename Iterator, typename Comparer> 
is_in_container_func<Iterator, Comparer> is_in_container(
    Iterator begin, Iterator end, Comparer cmp) 
{ 
    return is_in_container_func<Iterator, Comparer>(begin, end, cmp); 
} 

Теперь мы можем поставить все эти части вместе с std::remove_if:

std::vector<state*> vectorOpen; 
std::vector<state*> vectorClosed; 
std::vector<state*> vectorCheck; 

// Make one pass, removing elements if they are found in vectorOpen. 
std::vector<state*>::iterator new_end = std::remove_if(
    vectorCheck.begin(), vectorCheck.end(), 
    is_in_container(vectorOpen.begin(), vectorOpen.end(), states_are_equal())); 

// Make another pass, removing elements if they are found in vectorClosed. 
new_end = std::remove_if(
    vectorCheck.begin(), new_end, 
    is_in_container(vectorClosed.begin(), vectorClosed.end(), states_are_equal())); 

// std::remove_if just swaps elements around so that the elements to be removed are 
// all together at the end of the vector, and new_end is an iterator to the first 
// one. So, finally, we just need to remove the range [new_end, end()). 
vectorCheck.erase(new_end, vectorCheck.end()); 

Answer 2

Вызов erase аннулирует итератор, переданный ему. Он сдвигает элементы в векторе на одно место слева и возвращает итератор в элемент после удаленной. Следовательно, вы должны не прирастить итератор, если был выполнен erase. Вроде бы так:

for(itCheck = vectorCheck.begin(); itCheck != vectorCheck.end();) { // no increment 
    bool found = false; 
    for(itOpen = vectorOpen.begin(); itOpen != vectorOpen.end(); itOpen++) { 
     if ((*itCheck)->player->x == (*itOpen)->player->x && 
      (*itCheck)->player->y == (*itOpen)->player->y && 
      (*itCheck)->box[0].x == (*itOpen)->box[0].x && 
      (*itCheck)->box[0].y == (*itOpen)->box[0].y) { 
      cout << "erasing as in open " << (*itCheck)->player->x << " " << (*itCheck)->player->y << " " << (*itCheck)->box[0].x << " " << (*itCheck)->box[0].y << endl; 
      itCheck = vectorCheck.erase(itCheck); 
      found = true; 
      break; // found element and erased it. back to outer loop 
     } 
    } 

    if (!found) ++itCheck; // didn't find it, need to increment 
}