Finding consecutive elements in a vector

Question

I am working on a problem where I have to create subvectors from a bigger vector. If the elements in the vector are consecutive I have to create a vector of those elements. If there are elements which are not consecutive then a vector of that single elements is created. My logic is as below

vector<int> vect;
for (int nCount=0; nCount < 3; nCount++)
    vect.push_back(nCount);

vect.push_back(5);
vect.push_back(8);
vector<int>::iterator itEnd;

itEnd = std::adjacent_find (vect.begin(), vect.end(), NotConsecutive());

The functor NotConsecutiveis as below

return (int first != int second-1);

So I am expecting the std::adjacent_find will give me back the iterators such that I can create vector one{0,1,2,3}, vector two{5} and vector{8}. But I am not sure if there is any simpler way?

Edit:I forgot to mention that I have std::adjacent_find in a loop as

while(itBegin != vect.end())
{
    itEnd = std::adjacent_find (vect.begin(), vect.end(), NotConsecutive());
    vector<int> groupe;
    if( std::distance(itBegin, itEnd) < 1)
    {

        groupe.assign(itBegin, itBegin+1);
    }
    else
    {
        groupe.assign(itBegin, itEnd);
    }

    if(boost::next(itEnd) != vect.end())
    {
       itBegin = ++itEnd;                           
    }
    else
    {
       vector<int> last_element.push_back(itEnd);
    }
}

Does it make any sense?

Answer 1

I think this is what is being requested. It does not use adjacent_find() but manually iterates through the vector populating a vector<vector<int>> containing the extracted sub-vectors. It is pretty simple, IMO.

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

int main()
{
    std::vector<int> vect { 0, 1, 2, 3, 5, 8 };

    // List of subvectors extracted from 'vect'.
    // Initially populated with a single vector containing
    // the first element from 'vect'.
    //
    std::vector<std::vector<int>> sub_vectors(1, std::vector<int>(1, vect[0]));

    // Iterate over the elements of 'vect',
    // skipping the first as it has already been processed.
    //
    std::for_each(vect.begin() + 1,
                  vect.end(),
                  [&](int i)
                  {
                      // It the current int is one more than previous
                      // append to current sub vector.
                      if (sub_vectors.back().back() == i - 1)
                      {
                          sub_vectors.back().push_back(i);
                      }
                      // Otherwise, create a new subvector contain
                      // a single element.
                      else
                      {
                          sub_vectors.push_back(std::vector<int>(1, i));
                      }
                  });

    for (auto const& v: sub_vectors)
    {
        for (auto i: v) std::cout << i << ", ";
        std::cout << std::endl;
    }
}

Output:

0, 1, 2, 3,
5,
8,

See demo at http://ideone.com/ZM9ssk.

Answer 2

Due to the limitations of std::adjacent_find you can't use it quite the way you want to. However it can still be useful.

What you can do is to iterate over the collection, and use std::adjacent_find in a loop, with the last returned iterator (or your outer loop iterator for the first call) until it returns end. Then you will have a complete set of consecutive elements. Then continue the outer loop from where the last call to std::adjacent_find returned a non-end iterator.

Answer 3

Honestly, I don't find any clear disadvantage of using a simple hand-crafted loop instead of standard functions:

void split(const std::vector<int> &origin, vector<vector<int> > &result)
{
  result.clear();
  if(origin.empty()) return;

  result.resize(1);
  result[0].push_back(origin[0]);

  for(size_t i = 1; i < origin.size(); ++i)
  {
    if(origin[i] != origin[i-1] + 1) result.push_back(vector<int>());
    result.back().push_back(origin[i]);
  }
}