# Finding consecutive numbers in a vector

I need to write a program to print the line numbers, in ascending order, of a particular word in a file. Example output of the program would be:

 Hello 1, 3, 5-6, 8, 10-15.
// 5-6 represents 5, 6 (consecutive numbers)


The line numbers are stored in a sorted vector<int> with no duplicates. I have created a solution, but my instincts tell me I can do better. I would appreciate some feedback. Further, the following code only processes the line numbers; the word is found in another method. I will remark that intToString() is a custom method that does as the name implies. It returns a static string.

void IndexPager::createLines(vector<int>& vec, string& line)
{
int start = *vec.begin(), end = -1, offset = 0; // initial offset to start

for (vector<int>::const_iterator itr = vec.begin();
itr != vec.end() + 1; itr++)
{
if (*itr == start + offset && itr != vec.end())
{
end = *itr;
++offset;
} // check if line numbers are consecutive and not reading at end of vector
else // not consecutive
{
if ((end != -1) && (end != start))
{
line.append(intToString(start) + "-");
line.append(intToString(end));
} // if there existed consecutive numbers, display with dash
// must be difference of at least 1
else // else, there were no consecutive numbers
line.append(intToString(start));

if (itr != vec.end()) // check if not at end of vector
line.append(", ");
else // reached end of vector
line.append(".");

start = *itr; // set start to next line number. Soft reset.
offset = 1; // change default offset to 1. 0 for first case.
end = -1;
} // not consecutive
} // Get all line numbers and format for proper output
} // createLines()


1. First use ++it instead it++ with iterators.

2. You can replace this loop:

for (vector<int>::const_iterator itr = vec.begin();
itr != vec.end() + 1; itr++)

for (auto i : v)

3. vec.end() returns iterator representing element after the last element in vector

4. if (itr != vec.end()) loop also does this check

5. I think you can rewrite your code to be clearer and with less ifs

6. also you can use std::to_string instead of intToString

7. also if you want to append . at the end of string you can do it outside of the loop

Here is the code with few things fixed; still I think you can do even better than that if you rethink your conditions.

void createLines(vector<int>& vec, string& line)
{
int start = *vec.begin(), end = -1, offset = 0; // initial offset to start

for (auto i : vec)
{
if (i == start + offset)
{
end = i;
++offset;
} // check if line numbers are consecutive and not reading at end of vector
else // not consecutive
{
if ((end != -1) && (end != start))
{
line.append(to_string(start) + "-");
line.append(to_string(end));
} // if there existed consecutive numbers, display with dash
// must be difference of at least 1
else // else, there were no consecutive numbers
line.append(to_string(start));

line.append(", ");

start = i; // set start to next line number. Soft reset.
offset = 1; // change default offset to 1. 0 for first case.
end = -1;
} // not consecutive
} // Get all line numbers and format for proper output
if ((end != -1) && (end != start))
{
line.append(to_string(start) + "-");
line.append(to_string(end));
}
else
line.append(to_string(start));
line.append(".");
} // createLines()

• I think it would be nice to give a reason for why to prefer prefix to postfix (e.g. postfix creates a copy which can be expensive). More info here
– yuri
Jun 2, 2017 at 9:46
• In this specific case, it is not justified to use ++it rather than it++ Jun 2, 2017 at 12:53
• Can you explain why ? Jun 2, 2017 at 14:58
• This whole pre vs post thing is so immaterial. The compiler does a good job optimizing. Move on. Jun 3, 2017 at 11:46

Update

OK, I decided to give the miscco way a try (his code isn't quite working) and came up with this. I think it's correct.

template<class ForwardIt>
string formatLineNumbers(ForwardIt first, ForwardIt last)
{
string returnValue;
//returnValue.reserve();

while (first != last)
{
auto pos = first;
returnValue.append(to_string(*pos));

auto prev = pos;
while ((++first != last) && (*first == (*prev + 1)))
++prev;

if (prev != pos)
{
returnValue.append("-");
returnValue.append(to_string(*prev));
}

if (first != last)
returnValue.append(",");
}

return returnValue;
}

vector<int> v = {1,2,3};
auto text = formatLineNumbers(v.begin(), v.end());


Tried using adjacent_find in my first attempt, but there was a special case that made it a little clunky.

Original Post

My suggestions:

1) Rename the function/parameters so that they better describe what's happening (maybe it's just me, but createLines sounds like some type of graphics related function)

2) return the string instead of passing by reference

string formatLineNumbers(const vector<int>& lineNumbers)
{
string formattedText;   // 'line'

...

// NOTE: If you're worried about the effiency of this type of thing,
// see move semantics, copy elision, return value optimization
return formattedText;
}

// Now you can do this, which is nicer
some_function(formatLineNumbers(lineNumbers));
auto text = formatLineNumbers(lineNumbers);


3) This branch of code:

if ((end != -1) && (end != start))
{
line.append(to_string(start) + "-");
line.append(to_string(end));
}
else
line.append(to_string(start));


can be rewritten as:

s.append(to_string(start));

if ((end != -1) && (end != start))
s.append("-" + to_string(end));


You could also write it as a lambda since you're using that code twice - once in the loop, once after the loop. That way, if you ever have to change the code, you'll only have to change it in one place, not two. (less maintenance, less chance of error)

// Place the lambda before the for loop:
auto appendRangeToLine = [&line](int start, int end)
{
line.append(to_string(start));
if ((end != -1) && (end != start))
line.append("-" + to_string(end));
};

for (...)
{
//if ((end != -1) && (end != start))
//{
//line.append(to_string(start) + "-");
//line.append(to_string(end));
//}
//else
//line.append(to_string(start));

// Now inside the for loop you can replace the commented code
// above with the lambda
appendRangeToLine(start, end);

line.append(", ");
}

// And after the for loop, you can use it again:
appendRangeToLine(start, end);

line.append(".");


Should note that while I've used code like this in the past (where there's a 'leftover operation' after the loop is completed) and it has worked perfectly fine, I think if I did it again I'd be more inclined to go down the path miscco is attempting. It just seems more in line with the 'standards committee' way of doing things (check out the algorithms library on cppreference for code samples)

There is still allot to improve here:

1. Provide full examples. Your code as your presented it does not compile. It is missing headers, in you case you should add

#include <string>
#include <vector>

2. Use the correct functionality. You get the first element of the vector with

int start = *vec.begin();


However, there is a function for that

    int start = vec.front();

1. The idea with the offset is okish but not really smart. Why store the offset between two iterators, when you can remember the iterators themself? Then you can simply check whether the second is equal to the first. If not print the element and increment. If they are equal, increment the second iterator until they are not.

void createLines(vector<int>& vec, string& line) {
auto current = vec.begin();
auto next = std::next(current, 1);

while (next != vec.end()) {
if (*current+1 != *next) {
line.append(to_string(current));
} else {
while (next != vec.end() && *next+1 == *std::next(next, 1)) {
++next;
}
line.append(to_string(current));
line.append("-");
line.append(to_string(std::prev(next, 1)));
}
current = next;
++next;
if (next != vec.end()) {
line.append(", ");
}
}

2. Now you see, that we allways append current, so we can simplify this further

void createLines(vector<int>& vec, string& line) {
auto current = vec.begin();
auto next = std::next(current, 1);

while (next != vec.end()) {
line.append(to_string(current));
if (*current+1 == *next) {
while (next != vec.end() && *next+1 == *std::next(next, 1)) {
++next;
}
line.append("-");
line.append(to_string(std::prev(next, 1)));
}
current = next;
++next;
if (next != vec.end()) {
line.append(", ");
}
}
}

3. You do not modify the vector in your code, so you should change the signature to

void createLines(const vector<int>& vec, string& line) {

• I may have misunderstood your code, but your implementation does not do what I want. For example, if I had: 27, 28, and 29, your code would not print 27-29. Jun 2, 2017 at 20:52
• Oh there is an error. The condition of the while loop must be *next == *std::next(next, 1). It should also be possible to do *next == *(++next)` and not increment in the body of the while, but i am not really a fan of that Jun 3, 2017 at 7:58