C++「group where」算法

STL中是否有函數將一個序列劃分爲連續的子序列，其中某些謂詞是有效的？C++「group where」算法

例如以下序列：

1 1 1 0 1 1 0 0 1 1 1 1

給定一個謂詞 v == 1，應該返回三個子序列

：那些組中

1 1 1 
1 1 
1 1 1 1

組的順序，和元素，應予以保留。

我可以在O（N）中編寫一個循環來做到這一點，但我想了解更多關於STL並避免這種事情的循環。肖恩家長的精彩演講，C++ Seasoning，是我的動力。

翻閱<algorithm>，沒有什麼東西跳到我身上。

來源

2014-03-02 Drew Noakes

也許這個問題也可以表示爲更一般形式的標記化？在你的例子中，分隔符滿足v！= 1。 – user2672165

可能是'std :: partition_point'和'std :: stable_partition'可能的東西嗎？ – P0W

我不清楚：*「應該返回三個子序列」*子序列應該如何返回？數組視圖的向量？迭代器？迭代器在容器中？範圍矢量？ – Ali

有沒有這樣的算法已經是標準資源庫中您可以使用std::find_if和std::find_if_not來手動編寫一個查找每個發生序列的開始和結束迭代器。我認爲輸出應該是std::pair<FwdIt, FwdIt>的範圍。該算法在其輸入上具有O(N)的複雜性。

#include <algorithm> 
#include <iostream> 
#include <iterator> 
#include <vector> 
#include <utility> 

template<class FwdIt, class OutIt, class UnaryPred> 
auto find_all_if(FwdIt first, FwdIt last, OutIt dst, UnaryPred pred) 
{ 
    while (first != last) { 
     // start of next occurance 
     auto next_b = std::find_if(first, last, pred); 
     if (next_b == last) break; 

     // end of next occurance 
     auto next_e = std::find_if_not(next_b, last, pred); 
     *dst++ = make_pair(next_b, next_e); 

     first = next_e; 
    } 
    return dst; 
} 

int main() 
{ 
    auto const v = std::vector<int> { 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1 }; 
    using It = decltype(v.begin()); 
    std::vector<std::pair<It, It>> r; // "range of ranges" 

    find_all_if(begin(v), end(v), std::back_inserter(r), 
     [](auto e) { return e == 1; } 
    ); 

    for (auto&& e : r) { 
     std::cout << "["; 
     std::cout << std::distance(begin(v), e.first) << ", "; 
     std::cout << std::distance(begin(v), e.second) << "), "; 
    } 
}

Live Example在C++ 14式（使用的良好的OLE C++ 98手動類型定義和功能對象）打印[0, 3), [4, 6), [8, 12)您的輸入。

來源

2014-03-02 21:20:54 TemplateRex

我想這是一樣好，因爲它可以得到。有沒有從中得到多個範圍的算法？ – user2672165

@ user2672165否，當前的標準算法和容器成員函數不返回任何數據，計數，迭代器或一對迭代器和布爾（例如'map :: insert'）。當然，將迭代器返回到迭代器對的輸出範圍內將模擬您請求的範圍範圍。 – TemplateRex

好的。感謝您的信息。也可以反思一下這樣一個事實，即雖然範圍對於STL來說非常重要，但對於一個範圍來說沒有官方類型（def）。在你的情況下，你必須做一對。 – user2672165

應該返回的算法是什麼？範圍向量（迭代器對）？還是應該留下一個修改後的容器，其元素不符合標準要刪除？

對於第一種情況，您可以「半手工」操作：交替使用std::find_if() and std::find_if_not()，直到達到容器的末端。

對於第二種情況適用remove-erase-idiom。

container.erase(std::remove_if(
     std::begin(container), std::end(container), 
     [](int i){ return i != 1; }), 
    std::end(container));

來源

2014-03-02 21:13:04

第二種解決方案不符合要求。 – user2672165

@ user2672165爲什麼不呢？ –

晚上對我來說可能已經太晚了，但是你難道不會只從中得到一個範圍嗎？ – user2672165

C++「group where」算法

回答

相關問題