如何統計向量中相等的相鄰元素？

Question

可以說我有一個vector<int> { 1, 1, 2, 3, 3, 3, 1, 1 }，我想這個轉換成「相鄰元素計數」的vector<std::pair<int, int>> { {1, 2}, {2, 1}, {3, 3}, {1, 2} }：

我可能會遍歷向量與指示新「鄰居盤開始的標誌'和一個計數連續元素數量的計數器。我只是想知道STL中是否還有一個更抽象和優雅的解決方案，因爲這似乎是一個非常常見的用例。諸如unique，adjacent_find或equal_range的算法看起來與我正在尋找的非常接近，但僅僅是不太正確的事情，並且可能無法從頭開始自己實現它。

Answer 1

Eric Niebler's range library，其中，AFAIU is in the process of becoming part of the standard library，有一個group_by這是非常類似於Python's itertools.groupby，並組連續等效的元素，就像你需要。

，以便將向量，你會用

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

這意味着x就是相鄰整數屬於一個組，如果整數是相等的視圖開始。

現在要迭代打印每個連續的組及其大小，可以執行以下操作（我確信您可以做得比以下更好，但這是我使用此庫的限制） ：

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

---

例

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

此打印出

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

Answer 2

據我所知，沒有這樣的C++庫會自動執行你所要求的。
無論如何，這是很容易實現這一點，雖然。以下是一種方法：

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

請參閱ideone。

Answer 3

從算法的角度來看最接近的是run-length encoding我會說。我不認爲這是一個現成的算法來做到這一點，但代碼應該是微不足道的：

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

隨着std，你可以這樣做：

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

或

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