l oop зависает для повторного std :: erase в std :: list

Question

Я пытаюсь удалить повторяющиеся комбинации целочисленных векторов, хранящихся в списке, используя таблицу ha sh. Итерируя по каждому целочисленному вектору в списке, I:

1. Вычислить значение hash_value (tha sh)
2. Проверьте, есть ли значение ha sh уже в ha sh table (pids)
3. Если он находится в таблице ha sh, удалите этот вектор из списка. В противном случае, добавьте это значение в hash_table и увеличьте итератор списка

. Кажется, операторы Print подтверждают мою логику c, но l oop зависает на четвертом шаге итерации. Я прокомментировал it++ и vz.remove(it), которые вызывают проблему, и показывает только logi c в коде ниже. Код также доступен через ideone: https://ideone.com/JLGA0f

    #include<iostream>
    #include<vector>
    #include<list>
    #include<cmath>
    #include<unordered_set>
    using namespace std;

    double hash_cz(std::vector<int> &cz, std::vector<double> &lprimes) {
      double pid = 0;
      for(auto it = cz.begin(); it != cz.end(); it++) {
        pid += lprimes[*it];
      }
      return pid;
    }

    int main(){
      // create list of vectors
      std::list<std::vector<int>> vz;
      vz.push_back({2,1});
      vz.push_back({1,2});
      vz.push_back({1,3});
      vz.push_back({1,2,3});
      vz.push_back({2, 1});

      // vector of log of prime numbers
      std::vector<double> lprimes {2, 3, 5, 7};
      for (auto it = lprimes.begin(); it != lprimes.end(); it++) {
        *it = std::log(*it);
      }

      std::unordered_set<double> pids;
      double thash;
      for (auto it = vz.begin(); it != vz.end(); ) {
        thash = hash_cz(*it, lprimes);
        std::cout << thash << std::endl;
        // delete element if its already been seen
        if (pids.find(thash) != pids.end()) {
           std::cout << "already present. should remove from list" << std::endl;
           // vz.erase(it);
        }
        else {
          // otherwise add it to hash_table and increment pointer
          std::cout << "not present. add to hash. keep in list." << std::endl;
          pids.insert(thash);
          // it++;
        }
        it++;
      }

      for (auto it = vz.begin(); it != vz.end(); it++) {
        for (auto j = it -> begin(); j != it -> end(); j++) {
          std::cout << *j << ' ';
        }
        std::cout << std::endl;
      }
      return 0;
    }

Answer 1

Если элемент уже был просмотрен, вы стираете () узел it, а затем увеличиваете it в конце поведения l oop: undefined. Вместо этого попробуйте стереть (it ++).

Если элемент не был просмотрен, вы увеличиваете it, а затем делаете это снова в конце for, получая UB, если it было end() - 1 как он движется мимо конца.

Answer 2

Проблема в этой строке кода:

vz.erase(it);

Он сохраняет итератор там, где он был ie, и оставляет его недействительным. Это должно быть либо:

vz.erase(it++);

или

it = vz.erase( it );

Примечание: std::unoredered_set::insert() возвращаемое значение сообщает вам, была ли вставка успешной или нет (если такой же элемент значения уже существует), Вы должны позвонить и проверить результат. В вашем коде вы выполняете поиск дважды:

if (pids.insert(thash).second ) { 
    // new element added
    ++it;
} else { 
    // insertion failed, remove 
    it = vz.erase( it );
}

Поскольку std::list обеспечивает remove_if(), ваш код может быть упрощен:

vz.remove_if( [&pids,&lprimes]( auto &v ) { 
   return !pids.insert( hash_cz(v, lprimes) ).second );
} );

вместо целого l oop.