循环在std :: list上的循环std :: erase挂起

Question

我正在尝试使用哈希表删除存储在列表中的整数矢量的重复组合。遍历列表中的每个整数向量，I：

1. 计算hash_value（thash）
2. 查看哈希值是否已经在哈希表中（pids）
3. [如果在哈希表中，请从列表中删除该向量。否则，将该值添加到hash_table并增加列表迭代器

打印语句似乎证实了我的逻辑，但是循环挂在迭代的第四步。我已经注释了导致问题的it++和vz.remove(it)，仅在下面的代码中显示了逻辑。该代码也可以通过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

问题是这行代码：

vz.erase(it);

将迭代器保留在原处，即使其无效。应该是：

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()，您的代码可以简化：

remove_if()

而不是整个循环。

Answer 2

如果已经看到该元素，则擦除（）

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

节点，然后在循环末尾递增it：未定义的行为。请尝试擦除（it ++）。

[如果未看到该元素，则使it递增，然后在it的末尾再次进行，如果for越过末尾，则如果it为end() - 1，则产生UB。