Итерация и удаление элементов из 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() из <algorithm>. Он найдет первое вхождение двух последовательных идентичных элементов; держись этой позиции. Найдя это, найдите первый элемент из этой точки, который отличается от этих элементов. В итоге вы получите два итератора, которые обозначают ряд последовательных похожих элементов. Вы можете использовать метод набора erase(), чтобы удалить их, поскольку он имеет перегрузку, которая занимает два итератора.

вспенить, промыть, повторить для всего набора.