Making sequence unique with removal records I'm working on a tool to detect all exact tandem repeats in a DNA/RNA sequence. Part of the algorithm requires finding Longest Common Extension (LCE) values, which although can be computed in constant time, in practice it is (usually) better to use a naive \$O(n^2)\$ solution. The problem is that DNA sequences can contain long contiguous sequences of N's (unknown base). This can completely destroy the performance of the algorithm as it doesn't play nice with the \$O(n^2)\$ LCE algorithm. Solution: collapse all stretches of N's into a single N, no other repeats are missed (other than N's).

The problem is that then the repeats reported by the algorithm are in respect to the modified sequence, so I need to record how many N's have been removed before that position in the original sequence to get the correct position.

More generally: The algorithm should take as input a sequence sequence and a character c, collapse all contiguous sub-sequences of c into a single c (in-place), and record how many cs have been removed up until the next non-c character past the last removed c.

Here is my current attempt at this algorithm:

#include &lt;map&gt;
#include &lt;cstddef&gt;   // std::size_t
#include &lt;algorithm&gt; // std::adjacent_find, std::find_if_not, std::unique
#include &lt;iterator&gt;  // std::begin, std::end, std::distance, std::next

template &lt;typename SequenceType&gt;
std::map&lt;std::size_t, std::size_t&gt; collapse(SequenceType&amp; sequence, char c)
{
    std::map&lt;std::size_t, std::size_t&gt; result {};

    auto first = std::begin(sequence);
    auto last  = std::end(sequence);

    std::size_t position {}, num_removed {};

    while (first != last) {
        auto it1 = std::adjacent_find(first, last, [c] (char lhs, char rhs) { return lhs == c &amp;&amp; lhs == rhs; });

        if (it1 == last) break;

        auto it2 = std::find_if_not(it1, last, [c] (char b) { return b == c; });

        position    += std::distance(first, it1);
        num_removed += std::distance(it1, it2) - 1;

        result.emplace(position, num_removed);

        first = it2;
    }

    if (!result.empty()) {
        sequence.erase(std::unique(std::next(std::begin(sequence), result.cbegin()-&gt;first), last,
                                   [c] (char lhs, char rhs) { return lhs == c &amp;&amp; lhs == rhs; }), last);
    }

    return result;
}


I'm wondering if there's a better way that would avoid having to potentially scan the entire sequence twice (note the last call to std::unique)?
Generally, this seems to be readable code.  I would just note a few possible improvements:

Use a std::vector instead of a std::map

The std::map may be appropriate if you plan on doing frequent lookups of the key values, but a std::vector might be a less expensive storage mechanism than std::map otherwise.

Prefer for to while loop

The while loop may be more intuitively written as a for loop, as shown in the code below the next suggestion.

Consolidate loops

As you've asked in your question, yes, the separate loop can be eliminated.  Once the pair of iterators (it1 and it2) are found, simply use erase with those as parameters:

template &lt;typename SequenceType&gt;
std::map&lt;std::size_t, std::size_t&gt; collapse(SequenceType&amp; sequence, char c)
{
    std::map&lt;std::size_t, std::size_t&gt; result {};

    std::size_t position {}, num_removed {};
    auto last = std::end(sequence);

    for(auto first = std::begin(sequence); first != last; last = std::end(sequence) ) {
        auto it1 = std::adjacent_find(first, last, [c] (char lhs, char rhs) { return lhs == c &amp;&amp; lhs == rhs; });

        if (it1 == last) break;

        auto it2 = std::find_if_not(it1, last, [c] (char b) { return b == c; });

        position    += std::distance(first, it1);
        num_removed += std::distance(++it1, it2);

        result.emplace(position, num_removed);
        first = sequence.erase(it1, it2);
    }

    return result;
}


Because std::erase returns an iterator following the last erased value, this also provides a handy way to update first.  Also, by incrementing it1 within the num_removed update, we eliminate the need to subtract one and automatically correct the first iterator so that we eliminate only duplicate Ns and not all of them.

Consider the use of std::regex

It occurs to me that rather than use compress at all, perhaps std::regex might be better suited to solving this particular problem by eliminating the need to do preprocessing at all.  That is, with the proper regex, the notion of "one or more N's" is very quickly and easily represented.  Naturally, this assumes a more restrictive possibility range than a generic sequence object, but if your sequences are already std::string types, this may work very well.