迭代并删除 std::set 中的元素

Question

我有一个 std::set ，我需要删除类似的相邻元素：

DnaSet::const_iterator next = dna_list.begin();
DnaSet::const_iterator actual = next;
++next;

while(next != dna_list.end()) // cycle over pairs, dna_list is the set
{
    if (similar(*actual, *next))
    {
        Dna dna_temp(*actual);  // copy constructor
        dna_list.erase(actual); // erase the old one
        do
        {
           dna_temp.mutate(); // change dna_temp
        } while(!dna_list.insert(dna_temp).second);  // insert dna_temp
    }
    ++actual;
    ++next;
}

有时程序无法从主循环退出。我认为当我删除 dna_list 中的最后一个元素时，就会出现问题。完成这项任务的正确方法是什么？

Answer 1

使用 actual = next 而不是 ++actual。

一旦删除 actual，它就是一个无效的迭代器，因此 ++actual 会表现得很奇怪。 next 应保持不变，因此将 actual 分配给 next 应该可以。

Answer 2

最好的选择是创建一个使用 similar() 谓词的比较函子。然后您需要做的就是使用该比较函子构造集合，然后就完成了。集合本身会将两个相似的元素视为相同，并且只让第一个元素进入。

struct lt_different {
    bool operator()(int a, int b) {
        return a < b && !similar(a, b);
    }

private:
    bool similar(int a, int b)
    {
        // TODO:when are two elements similar?
        const int EPSILON = 2;
        return abs(a - b) < EPSILON;
    }
};

// ...
set<int> o;  // fill this set with your data

// copy your data to a new set that rejects similar elements
set<int,lt_different> s(o.begin(), o.end(), lt_different());

您可以使用集合 s：插入元素、删除元素、修改元素 - 并且集合本身将确保集合中不存在两个相似的元素。

也就是说，您也可以自己编写算法，即使只是为了替代选择。查看 中的 std::adjacent_find()。它将找到两个连续相同元素的第一次出现；坚持这个立场。找到后，找到从该点开始与这些元素不同的第一个元素。您最终会得到两个迭代器，它们表示一系列连续的相似元素。您可以使用集合的 erase() 方法来删​​除它们，因为它有一个需要两个迭代器的重载。

起泡沫，冲洗，重复整套。