Wie werden gleiche, benachbarte Elemente in einem Vektor gezählt?

Question

Lets sagen, dass ich ein vector<int> { 1, 1, 2, 3, 3, 3, 1, 1 } haben und ich möchte dies in einem ‚benachbarten Element zählt‘ vector<std::pair<int, int>> { {1, 2}, {2, 1}, {3, 3}, {1, 2} } von konvertieren:

ich wahrscheinlich über den Vektor mit einer Fahne, die den Beginn eines neuen ‚Nachbarschaftssatz iterieren würde 'und ein Zähler, der die Anzahl der aufeinanderfolgenden Elemente zählt. Ich habe mich gefragt, ob es nicht bereits eine abstraktere und elegantere Lösung in der STL gibt, da dies ein sehr verbreiteter Anwendungsfall ist. Algorithmen wie unique, boundary_find oder equal_range scheinen ziemlich nah an dem zu sein, wonach ich suche, aber nicht ganz das Richtige und wahrscheinlich auch keinen Gewinn, es von Grund auf selbst zu implementieren.

Answer 1

Eric Niebler's range library, die, AFAIU is in the process of becoming part of the standard library, eine group_by hat, die Python's itertools.groupby sehr ähnlich ist, und Gruppen aufeinander folgende gleichwertige Elemente, wie Sie benötigen.

Zur Gruppe Ihrer Vektor, dann würden Sie mit

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

beginnen, was bedeutet, dass x eine Ansicht ist, wo benachbarte Zahlen zu einer Gruppe gehören, wenn die ganzen Zahlen gleich sind.

Jetzt iterieren, und sagen, drucken Sie jede aufeinanderfolgende Gruppe und ihre Größe, könnten Sie Folgendes tun (ich bin mir sicher, Sie können es besser als die folgenden, aber das ist die Grenze meiner Verwendung dieser Bibliothek) :

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

---

Beispiel

#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; 
} 

Dies gibt

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

Answer 2

Soweit ich weiß, gibt es keine solche C++ Bibliothek, die automatisch tun wird, was Sie fragen.
Wie auch immer, es ist sehr einfach, dies zu implementieren. Hier ist eine Möglichkeit:

#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)); 
} 

es Siehe in ideone.

Answer 3

Aus einer algorithmischen Sicht ist die nächste Sache run-length encoding würde ich sagen. Ich glaube nicht, dass es ein fertiger Algorithmus ist, das zu tun, aber der Code sollte trivial sein:

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.

Answer 4

Mit std, was Sie tun können:

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

oder

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