formatting vector of int to a string

Question

So this is an exercise where I have to format a std::vector<int> into a std::string. The exercise requires us to only use stl algorithms, and we're not allowed to use for loops. std::for_each is allowed since it's part of algorithm too, but they rather not have us use it either.

The inputs are always sorted, and don't contain any duplicates.

Input std::vector<int>	Output std::string
{ 4, 8, 12}	"4, 8, 12"
{ -20, -19, .., .., 10, 11}	"[-20, 11]"
{ -5, 8, 9, 10, 11, 12, 21}	"-5, [8, 12], 21"
{ -2, 5, 6, 7, 10, 11, 12 }	"-2, [5, 7], [10, 12]"

I was already looking into std::search and std::adjacent_find if I could use those, but I don't think they'll do what I need.

This is what I've tried. I also don't think this is a proper approach to solve this, since the complete exercise is meant to be about std algorithms, and I'm not using any here. Any suggestions to what stl algorithm could be handy in this case, would be greatly appreciated.

std::string FormatLine(int lineNumber)
{
    std::vector<int> input = { -2, 5, 6, 7, 9, 11, 12, 13 };
    
    std::stringstream output{};
    int startNumber { input[0] };
    bool isRange{ false };
    
    for (int i{ 1 }; i < input.size(); ++i)
    {
        const int lastNumber = input[i - 1];
        
        // continue if its a incrementing sequence
        if (input[i] - 1 == lastNumber)
        {
            // if no range has been started yet, start one
            if (!isRange)
            {
                output << "[" << startNumber << ", ";
                isRange = true;
            }
            continue;
        }

        output << lastNumber;
        // if a range was started, close it with the last element of the range
        if (isRange)
        {
            output << "],";
            isRange = false;
        }
        // just a number so add a comment
        else
            output << ", ";
        
        startNumber = input[i];
    }
    // dont forget to add the last element
    output << input.back();
    // if it was still in a range, add closing bracket
    if (isRange) 
        output << ']';
    
    return output.str();
}

Answer 1

The solution cannot be a simple single loop, because you need to inspect later elements to know if the current element is prefixed with a [. Hence I propose to do some preprocessing.

The task asks to group numbers in intervals when the numbers are consecutive. To reflect that in code, use a structure:

 struct interval {
      int start;
      int size;          
 };

Also a single number can be represented as interval with size 0. Now you can use a single pass through the vector to populate a std::vector<interval>.

I like the premise of only using standard algorithms, but ruling out loops in favour of std::for_each is a little silly, because in some sense range based loops are the modern for_each when the whole container is iterated.

 std::vector<interval> intervals;
 intervals.emplace_back(input[0],0);
 std::for_each( input.begin()+1,input.end(),[&invervals](int x){
      // check if x == intervals.back().start + intervals.back().size + 1
      // to decide if the last intervals size must be incremented
      // or a new interval be added
 });

Once you got that vector, you just need another loop to build the desired string. When interval.size == 1 no [ is prefixed and else interval.start+interval.size-1 ] is appended too.

There might be some off by one errors, but I hope you get the idea.

Answer 2

I suggest:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string get_string_expression(vector<int> & vec)
{
    int pre_iter = vec[0] - 2;
    vector<vector<int>> inter_result;

    sort(vec.begin(), vec.end());
    for_each(vec.begin(), vec.end(), [&inter_result, &pre_iter](int iter) {     
        if (iter - pre_iter == 1)
        {
            inter_result.rbegin()->push_back(iter);
        }
        else
        {
            vector<int> temp = { iter };
            inter_result.push_back(temp);
        }       
        pre_iter = iter;
    });

    string result = "";
    for_each(inter_result.begin(), inter_result.end(), [&result](vector<int> iter) {
        if (iter.size() == 1)
        {
            result += to_string(iter[0]);
        }
        else
        {
            result += (string("[") + to_string(*iter.begin()) + "," + to_string(*iter.rbegin()) + "]");
        }
        result += ", ";
    });

    return result.substr(0, result.length() - 2);
}

int main()
{
    vector<int> input_1 = { 4, 8, 12 };
    vector<int> input_2(32);
    vector<int> input_3 = { -5, 8, 9, 10, 11, 12, 21 };
    vector<int> input_4 = { -2, 5, 6, 7, 10, 11, 12 };

    //. initialize input_2
    generate(input_2.begin(), input_2.end(), [n = -20]()mutable{ return n++; });

    cout << "input_1: " << get_string_expression(input_1) << endl;
    cout << "input_2: " << get_string_expression(input_2) << endl;
    cout << "input_3: " << get_string_expression(input_3) << endl;
    cout << "input_4: " << get_string_expression(input_4) << endl;

    return 0;
}

Answer 3

What about accumulate? https://godbolt.org/z/xfK8acrT8

    std::array arr{1, 2, 3, 4, 5, 6};
    auto begin = arr.begin(), end = arr.end();
    
    std::string r;
    if (begin != end)
        r = std::to_string(*begin++);
    r = std::accumulate(begin, end, r, [](std::string result, int value) { result += ", " + std::to_string(value); return result; });
    std::printf("%s", r.c_str());```

yields:

1, 2, 3, 4, 5, 6