CODEWITHSUNDEEP
c++algorithmvectorstl
user1709708
user1709708

Reputation: 1577

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.

Upvotes: 2

Views: 2124

Answers (4)

midor
midor

Reputation: 5557

From an algorithmic point of view the closest thing is run-length encoding I would say. I don't think there is a ready made algorithm to do that, but the code should be trivial:

std::vector<std::pair<int, int>> out; 
for (int i: in)
{
     if (out.empty() || out.back().first != i)
     {
         out.emplace_back(i, 1);
     }
     else
     {
         ++out.back().second;
     }
}

Live-example.

Upvotes: 4

Jarod42
Jarod42

Reputation: 217870

With std, you may do:

template <typename T>
std::vector<std::pair<T, std::size_t>>
adjacent_count(const std::vector<T>& v)
{
    std::vector<std::pair<T, std::size_t>> res;

    for (auto it = v.begin(), e = v.end(); it != e; /*Empty*/) {
        auto it2 = std::adjacent_find(it, e, std::not_equal_to<>{});
        if (it2 != e) {
            ++it2;
        }
        res.emplace_back(*it, std::distance(it, it2));
        it = it2;
    }
    return res;
}

Demo

or

template <typename T>
std::vector<std::pair<T, std::size_t>>
adjacent_count(const std::vector<T>& v)
{
    std::vector<std::pair<T, std::size_t>> res;

    for (auto it = v.begin(), e = v.end(); it != e; /*Empty*/) {
        const auto it2 = std::find_if(it, e, [&](const auto&x) { return x != *it; });
        res.emplace_back(*it, std::distance(it, it2));
        it = it2;
    }
    return res;
}

Demo

Upvotes: 1

A. Sarid
A. Sarid

Reputation: 3996

As far as I know there is no such C++ library that will automatically do what you are asking.
Anyway, it is very simple to implement this though. Here is one way:

#include <iostream>
#include <vector>

using namespace std;

void count_equal_elements(vector<int>& vec, vector<pair<int,int> >& result){
    if (vec.empty())
        return;
    int curr = vec[0];
    int count = 1;
    for (vector<int>::iterator it = vec.begin()+1; it != vec.end(); ++it){
        if (curr == *it){
            count++;
        }
        else{
            result.push_back(make_pair(curr,count));
            curr = *it;
            count = 1;
        }
    }
    result.push_back(make_pair(curr,count));
}

See it in ideone.

Upvotes: 0

Ami Tavory
Ami Tavory

Reputation: 76346

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

Upvotes: 3

Related Questions