cycle and erase elments from std::set

Question

I have a std::set and I need to erase similar adjacet elements:

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;
}

sometimes the program can't exit from the main loop, I think the problem happens when I erase the last element in the dna_list. What's the correct way to do this task?

Answer 1

Use actual = next rather than ++actual.

Once you erase actual, it is an invalid iterator, so ++actual will behave strangely. next should remain intact, so assigning actual to next should work.

Answer 2

Your best option is to create a comparison functor that uses the similar() predicate. Then all you need to do is construct the set with that comparison functor and you're done. The set itself will see two similar elements as identical and will only let the first one in.

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());

You can work with set s: insert elements, remove elements, modify elements -- and the set itself will make sure no two similar elements exist in the set.

That said, you can also write an algorithm yourself, if only for an alternative choice. Take a look at std::adjacent_find() from <algorithm>. It will find the first occurrence of two consecutive identical elements; hold on to that position. With that found, find the first element from that point that is different from these elements. You end up with two iterators that denote a range of consecutive, similar elements. You can use the set's erase() method to remove them, as it has an overload that takes two iterators.

Lather, rinse, repeat for the entire set.