user1709708 user1709708 - 2 months ago 8
C++ Question

How to count equal, adjacent elements in a vector?

Lets say I have a

vector<int> { 1, 1, 2, 3, 3, 3, 1, 1 }
and I'd like to convert this into a
vector<std::pair<int, int>> { {1, 2}, {2, 1}, {3, 3}, {1, 2} }
of 'adjacent element counts':

I'd probably iterate over the vector with a flag indicating the start of a new 'adjacency set' and a counter which counts the number of consecutive elements. I was just wondering if there isn't already a more abstract and elegant solution in the STL as this seems like a very common use-case. Algorithms like unique, adjacent_find or equal_range seem pretty close to what I'm looking for but just not quite the right thing and probably no gain to implementing it from scratch myself.

Answer

Eric Niebler's range library, which, AFAIU is in the process of becoming part of the standard library, has a group_by which is very similar to Python's itertools.groupby, and groups consecutive equivalent elements, just as you need.

To group your vector, you'd start with

const vector<int> l{ 1, 1, 2, 3, 3, 3, 1, 1 };
auto x = l | view::group_by(std::equal_to<int>());

which means that x is a view where adjacent integers belong to a group, if the integers are equal.

Now to iterate, and say, print each consecutive group and its size, you could do the following (I'm sure you can do it better than the following, but this is the limit of my use of this library):

for (auto i = x.begin();i != x.end(); ++i) 
    cout <<  *((*i).begin()) << " " << to_vector(*i).size() << endl;

Example

#include <vector>
#include <iostream>
#include <range/v3/all.hpp>

int main(int argc, char **argv) { 
    const std::vector<int> l{ 1, 1, 2, 3, 3, 3, 1, 1 };
    auto x = l | ranges::view::group_by(std::equal_to<int>());

    for (auto i = x.begin();i != x.end(); ++i) 
        std::cout <<  *((*i).begin()) << " " << ranges::to_vector(*i).size() << std::endl;
}

This prints out

$ ./a.out 
1 2
2 1
3 3
1 2
Comments