c++ 7種非修改性的range查詢算法

std::range算法簡介。

• range算法被定義在<algorithm>頭中，而range的基礎結構和核心類型被定義在<ranges>頭中。
• 通常，range算法至少有兩個重載：帶有一對疊代器的重載和帶有單一範圍參數的重載。
• range版本采取 "投影"，這有時允許更多的靈活性；例如，你可以針對一些標明的成員進行排序，或者在比較之前執行額外的轉換。
• range版本沒有并行執行選項（你不能傳遞std::執行政策）。
• range算法，與C++20的标準算法類似，也是constexpr。
• 從C++20開始，沒有對應于<numeric>頭的range數值算法。

下面，你可以找到顯示标準算法和帶有range的替代版本的例子。它們說明了一些基本概念，并盡量不使用進階的range組成或視圖。我們将按照在cppreference/algorithms找到的順序進行，在這一部分，我們将介紹 "非修改序列操作"。

1. all_of, any_of, none_of

标準算法

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

int main() {

const std::vector nums = {1, 2, 3, -4, 5, 6, 7, 8 };

auto is_positive = [](const auto& v) { return v > 0; };

// standard version:

auto res = std::all_of(begin(nums), end(nums), is_positive);

std::cout << "std::all_of: " << res << '\n';

res = std::any_of(begin(nums), end(nums), is_positive);

std::cout << "std::any_of: " << res << '\n';

}

range版本

// ranges version:

res = std::ranges::all_of(nums, is_positive);

std::cout << "std::ranges::all_of: " << res << '\n';

res = std::ranges::any_of(nums, is_positive);

std::cout << "std::ranges::any_of: " << res << '\n';

我們還可以寫一個更複雜的例子，掃描一個自定義類型的容器。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

struct Product {

std::string name_;

double value_ { 0.0 };

};

int main() {

const std::vector<Product> prods {

{ "box", 10.0 }, {"tv", 100.0}, {"none", -1.0}

};

auto is_positive = [](const auto& v) { return v > 0; };

auto is_positive_val = [](const Product& p) {

return p.value_ > 0;

};

// standard version:

auto res = std::all_of(begin(prods), end(prods), is_positive_val);

std::cout << "std::all_of: " << res << '\n';

res = std::any_of(begin(prods), end(prods), is_positive_val);

std::cout << "std::any_of: " << res << '\n';

// ranges version:

res = std::ranges::all_of(prods, is_positive, &Product::value_);

std::cout << "std::ranges::all_of: " << res << '\n';

res = std::ranges::any_of(prods, is_positive, &Product::value_);

std::cout << "std::ranges::any_of: " << res << '\n';

}

在range版本中，我們仍然可以使用is_positive，一個通用的謂詞，但我使用了一個投影，它隻 "接受 "Product::value_并将其傳入謂詞。在标準情況下，我不得不寫一個自定義的lambda來識别Product的類型。

2. for_each

一個基于範圍的for循環的替代方案。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

struct Product {

std::string name_;

double value_ { 0.0 };

};

int main() {

const std::vector<Product> prods {

{ "box", 10.0 }, {"tv", 100.0}, {"none", -1.0}

};

auto out = [](const auto& v) { std::cout << v << ", "; };

// standard version:

std::cout << "std::for_each: \n";

std::for_each(begin(prods), end(prods), [](const Product& p){

std::cout << p.name_ << ", " << p.value_ << '\n';

});

std::cout << "std::for_each only names reverse: \n";

std::for_each(rbegin(prods), rend(prods), [](const Product& p){

std::cout << p.name_ << '\n';

});

// ranges version:

std::cout << "std::ranges::for_each: \n";

std::ranges::for_each(prods, [](const Product& p) {

std::cout << p.name_ << ", " << p.value_ << '\n';

});

std::cout << "std::ranges::for_each only names in reverse: \n";

std::ranges::for_each(prods | std::views::reverse,

out, &Product::name_);

}

令人振奮的是，在标準版本中以反向順序列印需要使用rbegin/rend疊代器，然後使用一個自定義的單選函數來列印來自Product類的确切資料成員。而對于range，我們可以應用views::reverse，使用一個簡單的輸出函數，然後是一個投影。

缺少的是range算法的并行版本。

// standard:

std::for_each(std::execution::par, begin(prods), end(prods), /*...*/);

// no ranges version...

// std::ranges::for_each(std::execution::par, prods, /*... */); // doesn't compile...

所有的range算法都缺少并行版本，而不僅僅是for_each。

3. count_if

在下面的例子中，我們将計算名稱以 "no "開頭的Product。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

struct Product {

std::string name_;

double value_ { 0.0 };

};

int main() {

const std::vector<Product> prods {

{ "box", 10.0 }, {"tv", 100.0}, {"none", -1.0},

{ "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}

};

// standard version:

auto res = std::count_if(begin(prods), end(prods), [](const Product& p){

return p.name_.starts_with("no");

});

std::cout << "std::count_if: " << res << '\n';

// ranges version:

res = std::ranges::count_if(prods, [](const Product& p) {

return p.name_.starts_with("no");

});

std::cout << "std::ranges::count_if: " << res << '\n';

// alternative version for "none":

res = std::ranges::count(prods, std::string{"none"}, &Product::name_);

std::cout << "std::ranges::count: " << res << '\n';

}

這個例子顯示了三種方法，最後一種使用了一個投影，隻檢查Product::name_資料成員。在這個方法中，我們精确地搜尋 "none"，是以它比starts_with更嚴格。

4. find_if

到目前為止，我們的文本算法都是傳回布爾值或積分值，但有了find*函數，我們就有了顯示更多内容的疊代器（或子range）。

請看這個例子。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

struct Product {

std::string name_;

double value_ { 0.0 };

};

int main() {

const std::vector<Product> prods {

{ "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},

{ "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}

};

// standard version:

auto it = std::find_if(begin(prods), end(prods), [](const Product& p){

return p.name_.starts_with("ro");

});

if (it != end(prods))

std::cout << "std::find_if: " << it->name_ << '\n';

// ranges version:

auto res = std::ranges::find_if(prods, [](const Product& p) {

return p.name_.starts_with("ro");

});

if (res != end(prods))

std::cout << "std::ranges::find_if: " << res->name_ << '\n';

}

像其他算法一樣，也有一個 "正常 "版本，你可以傳遞兩個疊代器。

it = std::ranges::find_if(begin(prods), end(prods), [](const Product& p) {

return p.name_.starts_with("ro");

});

采取單一範圍的版本是特殊的，因為它傳回一個借用的疊代器。這種特殊類型允許檢查臨時/生命期對象的問題。當你傳遞兩個疊代器時，這是不可能的（因為容器在某處存在），但用一個臨時範圍就可以。

struct Product {

std::string name_;

double value_ { 0.0 };

};

std::vector<Product> GetProds() {

return {

{ "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},

{ "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}

};

}

int main() {

auto it = std::ranges::find_if(GetProds(), [](const Product& p) {

return p.name_.starts_with("ro");

});

std::cout << "std::ranges::find_if: " << it->name_ << '\n';

}

這不能編譯，你會看到以下錯誤。

error: base operand of '->' has non-pointer type 'std::ranges::dangling'

22 | std::cout << "std::ranges::find_if: " << it->name_ << '\n';

| ^~

正如你所看到的，編譯器檢查了GetProds()傳回一個臨時的值，而我們會發現的疊代器是懸空的。

5. find_first_of

讓我們來看看另一個find*函數的替代方案，它可以一次搜尋多個元素。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

struct Product {

std::string name_;

double value_ { 0.0 };

friend bool operator==(const Product& a, const Product& b) {

return a.name_ == b.name_ && abs(a.value_ - b.value_) < 0.0001;

}

};

int main() {

const std::vector<Product> prods {

{ "box", 10.0 }, {"default", 0.0 }, {"tv", 100.0}, {"rocket", 10000.0},

{ "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0 }, { "ball", 40.0 }

};

const std::vector<Product> invalids {

{"default", 0.0 }, {"none", 0.0 }

};

// standard version:

auto it = std::find_first_of(begin(prods), end(prods), begin(invalids), end(invalids));

if (it != end(prods)) {

std::cout << "std::find_first_of: " << it->name_ << " at: "

<< std::distance(begin(prods), it) <<'\n';

auto it2 = std::find_first_of(std::next(it), end(prods), begin(invalids), end(invalids));

if (it2 != end(prods))

std::cout << "std::find_first_of: " << it2->name_ << " at: "

<< std::distance(begin(prods), it2) <<'\n';

}

// ranges version:

const std::array<std::string, 2> arrInvalids{"default", "none"};

auto res = std::ranges::find_first_of(prods, arrInvalids,

std::ranges::equal_to{}, &Product::name_);

if (res != end(prods)) {

const auto pos = std::distance(begin(prods), res);

std::cout << "std::ranges::find_first_of: " << res->name_

<< " at: " << pos <<'\n';

auto res2 = std::ranges::find_first_of(prods | std::views::drop(pos+1), arrInvalids,

std::ranges::equal_to{}, &Product::name_);

if (res2 != end(prods)) {

std::cout << "std::ranges::find_first_of: " << res2->name_

<< " at: " << std::distance(begin(prods), res2) <<'\n';

}

}

}

std::find_first_of需要兩對疊代器。我想在例子中的prod序列中找到 "無效的 "product。因為我在比較product，是以我必須為我的結構定義operator==。另外，我可以提供一個二進制操作，然後隻比較名稱。

auto cmpNames = [](const Product& a, const Product& b) {

return a.name_ == b.name_;

};

auto it = std::find_first_of(begin(prods), end(prods),

begin(invalids), end(invalids), cmpNames);

if (it != end(prods)) {

// ...

}

在range版中，我可以使用預測和預設比較器來達到類似的效果。

const std::array<std::string, 2> arrInvalids{"default", "none"};

auto res = std::ranges::find_first_of(prods, arrInvalids,

std::ranges::equal_to{}, &Product::name_);

後來有趣的部分是，對于第二次搜尋，我可以使用drop來跳過範圍中的前N個元素。

auto res2 = std::ranges::find_first_of(prods | std::views::drop(pos+1),

arrInvalids, std::ranges::equal_to{}, &Product::name_);

另外，你也可以使用一個有兩對疊代器的版本。

auto res2 = std::ranges::find_first_of(std::next(res), end(prods),

begin(arrInvalids), end(arrInvalids),

std::ranges::equal_to{}, &Product::name_);

6. mismatch

通過不比對算法，我們可以找到兩個範圍不同的第一個地方。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

#include <iomanip> // quoted

int main() {

const std::string firstStr = "Hello Super World";

const std::string secondStr = "Hello Amazing World";

std::cout << "mismatch for " << std::quoted(firstStr)

<< " and " << std::quoted(secondStr) << '\n';

// standard version:

auto [first, second] = std::mismatch(begin(firstStr), end(firstStr), begin(secondStr));

{

const auto pos = std::distance(begin(firstStr), first);

std::cout << "std::mismatch: at pos " << pos << '\n';

}

// ranges version:

auto res = std::ranges::mismatch(firstStr, secondStr);

{

const auto pos = std::distance(begin(firstStr), res.in1);

std::cout << "std::ranges::mismatch: at pos " << pos << '\n';

}

}

range版本傳回：

template<class I1, class I2>

using mismatch_result = ranges::in_in_result<I1, I2>;

這是一對兩個疊代器，但我們可以通過.in1和.in2通路它們。

為什麼不是一個簡單的範圍呢？在cpp參考中我們可以看到下面這句話。

Unlike std::pair and std::tuple, this class template has data members of meaningful names.

其結果在結構化綁定時表現不錯，是以你可以寫。

auto [n1, n2] = std::ranges::mismatch(firstStr, secondStr);

const auto pos = std::distance(begin(firstStr), n1);

std::cout << "std::ranges::mismatch: at pos " << pos << '\n';

代碼幾乎與标準版相同。

7. search

在另一個範圍/容器中搜尋模式。

#include <algorithm>

#include <vector>

#include <iostream>

#include <ranges>

#include <functional> // searchers

#include <iomanip>

int main() {

const std::string testString = "Hello Super World";

const std::string needle = "Super";

std::cout << "looking for " << std::quoted(needle)

<< " in " << std::quoted(testString) << '\n';

// standard version:

auto it = std::search(testString.begin(), testString.end(),

std::boyer_moore_searcher(needle.begin(), needle.end()));

if (it != testString.end()) {

const auto pos = std::distance(testString.begin(), it);

std::cout << "std::search: found at pos " << pos << '\n';

}

// ranges version:

auto res = std::ranges::search(testString, needle);

if (!res.empty()) {

const auto first = std::distance(testString.begin(), res.begin());

const auto last = std::distance(testString.begin(), res.end());

std::cout << "std::ranges::search: found between "

<< first << " and " << last << '\n';

}

}

标準版本傳回第二個字元串開始的第一個字元串的疊代器（如果不在那裡，則傳回end()）。而range版本則傳回一個子range（或一個借用的子range）。

我們也可以使用投影以不區分大小寫的方式進行檢查。

// ranges version:

const std::string testString2 = "hello abc world";

const std::string needle2 = "ABC";

std::cout << "looking for " << std::quoted(needle2) << " in "

<< std::quoted(testString2) << '\n';

res = std::ranges::search(testString2, needle2,

std::ranges::equal_to{}, ::toupper, ::toupper);

if (!res.empty())

{

const auto first = std::distance(testString2.begin(), res.begin());

const auto last = std::distance(testString2.begin(), res.end());

std::cout << "std::ranges::search: found between "

<< first << " and " << last << '\n';

}

另一個函數 ranges::search_n可以友善地在輸入範圍内找到一個給定值的N個出現次數。

#include <algorithm>

#include <iostream>

#include <ranges>

#include <iomanip>

int main() {

const std::string sequence = "CTGCCCAGGGTTT";

const char letter = 'C';

const size_t count = 3;

std::cout << "looking for " << count << " "

<< letter << "'s in " << std::quoted(sequence) << '\n';

// standard version:

auto it = std::search_n(begin(sequence), end(sequence), count, letter);

if (it != end(sequence))

{

const auto pos = std::distance(begin(sequence), it);

std::cout << "std::search_n: found at pos " << pos << '\n';

}

// ranges version:

auto res = std::ranges::search_n(sequence, count, letter);

if (!res.empty())

{

const auto first = std::distance(begin(sequence), res.begin());

const auto last = std::distance(begin(sequence), res.end());

std::cout << "std::ranges::search_n: found between "

<< first << " and " << last << '\n';

}

}

在标準版本中，沒有特殊的搜尋器；你隻能使用并行算法來調用它。

總結

在這篇文章中，我們涵蓋了非修改性操作類别中的七種不同的算法 "類型"：檢查所有/無/部分元素的一些謂詞，搜尋，查找，一般疊代。總共有超過10個不同的例子。

ranges算法提供了一種更簡單的方法來傳遞 "整個 "容器--隻有一個參數，而不是傳遞給疊代器。它們也允許投影，并且有辦法檢測到臨時範圍的疊代器。它們也有局限性，比如缺乏進階搜尋器或并行執行模式。