Convert sequence of number into display string

My requirement is to convert a sequence of numbers into a display string as below.

Example


Input


1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86


Output


1-5,7-8,10-12,15,86-88

void makeDisplayString(std::vector& vector, std::wstring& string)
{
    if(vector.empty()) return; // If empty do nothing

    std::sort(vector.begin(),vector.end()); // Sort vector first

    int& preValue =vector.at(0);
    string.append(std::to_wstring(preValue));

    bool continueFlag = false; // Flag to check if continuation of value

    for(auto const & num : vector)
    {
        if(preValue ==num)  continue; // if same number as previous , Skip it

        if(preValue+1 == num) // If number is one more than privious value
        {
            preValue = num;
            continueFlag=true; // set continuation flag and continue rest part
            continue;
        }

        if(continueFlag) 
        {
            // We reach here only if neither number is save as previous nor it is continous of numbering
            // But befor this number there was a continous numbering
            string.push_back(L'-');
            string.append(std::to_wstring(preValue));
            string.push_back(L',');
            preValue=num;

            string.append(std::to_wstring(num));
            continueFlag = false;
            continue;
        }
        // We reach here only if neither number is save as previous nor it is continous of numbering
        // Also befor this number there was no continous numbering
        preValue = num; 
        string.push_back(L',');
        string.append(std::to_wstring(num));
    }
    // This is to handle a sequence ending with continous number
    if(continueFlag) 
    {
        string.push_back(L'-');
        string.append(std::to_wstring(*vector.rbegin()));
    }
}

1. Separate data representation from actual output, using standard algorithms where possible.

make_ranges below takes input sequence array and returns limits of all ranges found, in two different sequences from, to:

template
void make_ranges(F& from, T& to, A array)
{
    auto diff = array;
    std::sort(array.begin(), array.end());
    std::adjacent_difference(array.begin(), array.end(), diff.begin());

    std::vector idx(array.size());
    std::iota(idx.begin(), idx.end(), 0);
    auto sep = [&diff] (size_t i) { return diff[i] > 1; };
    for(auto p = idx.begin(); p != idx.end();)
    {
        from.push_back(array[*p]);
        p = std::find_if(++p, idx.end(), sep);
        to.push_back(array[*(p - 1)]);
    }
}

1. For most generic use, use a stream for output:

template
void print_range(S& stream, I i, J j)
{
    stream 
void print_ranges(S& stream, const F& from, const T& to)
{
    auto i = from.begin();
    auto j = to.begin();
    if (i != from.end())
        print_range(stream, i++, j++);
    while (i != from.end())
    {
        stream << ",";
        print_range(stream, i++, j++);
    }
}

1. For convenient use, provide a streaming operator interface:

template
S& operator& ranges)
{
    typename std::decay::type from, to;
    make_ranges(from, to, std::get(ranges));
    print_ranges(stream, from, to);
    return stream;
}

where array_ranges is a helper struct holding a sequence and indicating that its ranges should be streamed out instead of the sequence itself. Given a sequence, an array_ranges instance is made easily via helper function ranges:

template
struct array_ranges : std::tuple { using std::tuple::tuple; };

template
array_ranges ranges(A&& a) { return array_ranges{std::forward(a)}; }

Example

Now the above can be used as

std::vector arr{1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86};
std::cout << arr << std::endl;
std::cout << ranges(arr) << std::endl;

See live example.

If you want to print the ranges into a string, just use an std::ostringstream.

Discussion

With the above separation, you can do more advanced tasks like extracting ranges from arbitrary sequences, processing them (e.g. filtering or merging two sets of ranges), and finally printing them.

If you don't need any extra processing, this separation is more costly than direct printing since it stores intermediate results in arrays from, to. Using std::adjacent_difference introduces another intermediate result.

It is possible to save the extra cost of "intermediate results" while keeping the same design by more advanced techniques like expression templates, but this goes way beyond this simple task.

I would personally prefer a clean design to optimal performance for this task. This makes code more readable and maintainable. Also, with a bit more abstraction, you may find that parts of the code above can be reused elsewhere (especially print_ranges, but I don't want to go too far).

Another choice you could follow is to have an std::pair or (better) a dedicated data structure representing one range. A single sequence would then be enough instead of two sequences from, to, but processing such a sequence would be a bit more involved.

Of course, you are free to flat everything into a single call without intermediates if you prefer.

StackExchange Code Review Q#47845, answer score: 8