std::ranges::search
來自 cppreference.com
| 定義於標頭檔案 <algorithm> |
||
| 呼叫簽名 (Call signature) |
||
| template< std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, |
(1) | (C++20 起) |
| template< ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, |
(2) | (C++20 起) |
1) 在範圍
[first1, last1) 中搜索元素序列 [first2, last2) 的首次出現。元素在使用 proj2 和 proj1 分別投影后，使用二元謂詞 pred 進行比較。2) 同 (1)，但使用 r1 作為第一個源範圍，r2 作為第二個源範圍，如同使用 ranges::begin(r1) 作為 first1，ranges::end(r1) 作為 last1，ranges::begin(r2) 作為 first2，以及 ranges::end(r2) 作為 last2。
本頁描述的類函式實體是 演算法函式物件（非正式地稱為 niebloids），即
目錄 |
[編輯] 引數
| first1, last1 | - | 定義要檢查的元素範圍（又稱乾草堆）的迭代器-哨兵對 |
| first2, last2 | - | 定義要搜尋元素的範圍（亦稱針）的迭代器-哨兵對。 |
| r1 | - | 要檢查的元素範圍（又稱乾草堆） |
| r2 | - | 要搜尋的元素範圍（亦稱針） |
| pred | - | 應用於投影元素的二元謂詞 |
| proj1 | - | 應用於第一個範圍元素的投影。 |
| proj2 | - | 應用於第二個範圍元素的投影。 |
[編輯] 返回值
1) 返回一個 ranges::subrange 值，它是序列
[first2, last2) (亦稱針) 在範圍 [first1, last1) (亦稱乾草堆) 中的首次出現，在分別對兩個序列的元素應用投影 proj1 和 proj2 之後，接著應用二元謂詞 pred 比較投影的元素。如果未找到此類出現，則返回 ranges::subrange{last1, last1}。
如果待搜尋範圍（亦稱針）為空，即 first2 == last2，則返回 ranges::subrange{first1, first1}。[編輯] 複雜度
最多對相應的謂詞和每個投影進行 S * N 次應用，其中
(1) S = ranges::distance(first2, last2) 且 N = ranges::distance(first1, last1)；
(2) S = ranges::distance(r2) 且 N = ranges::distance(r1)。
[編輯] 可能的實現
struct search_fn { template<std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2> constexpr ranges::subrange<I1> operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (;; ++first1) { I1 it1 = first1; for (I2 it2 = first2;; ++it1, ++it2) { if (it2 == last2) return {first1, it1}; if (it1 == last1) return {it1, it1}; if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) break; } } } template<ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2> constexpr ranges::borrowed_subrange_t<R1> operator()(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(pred), std::move(proj1), std::move(proj2)); } }; inline constexpr search_fn search {}; |
[編輯] 示例
執行此程式碼
#include <algorithm> #include <cctype> #include <iostream> #include <iterator> #include <string_view> using namespace std::literals; void print(int id, const auto& haystack, const auto& needle, const auto& found) { std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); "; const auto first = std::distance(haystack.begin(), found.begin()); const auto last = std::distance(haystack.begin(), found.end()); if (found.empty()) std::cout << "not found;"; else { std::cout << "found: \""; for (const auto x : found) std::cout << x; std::cout << "\";"; } std::cout << " subrange: {" << first << ", " << last << "}\n"; } int main() { constexpr auto haystack {"abcd abcd"sv}; constexpr auto needle {"bcd"sv}; // the search uses iterator pairs begin()/end(): constexpr auto found1 = std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // the search uses ranges r1, r2: constexpr auto found2 = std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // 'needle' range is empty: constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' will not be found: constexpr auto awl {"efg"sv}; constexpr auto found4 = std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // the search uses custom comparator and projections: constexpr auto bodkin {"234"sv}; auto found5 = std::ranges::search(haystack, bodkin, [](const int x, const int y) { return x == y; }, // pred [](const int x) { return std::toupper(x); }, // proj1 [](const int y) { return y + 'A' - '1'; }); // proj2 print(5, haystack, bodkin, found5); }
輸出
1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}[編輯] 參閱
| (C++20) |
尋找第一對相等的（或滿足給定謂詞的）相鄰項 (演算法函式物件) |
| (C++20)(C++20)(C++20) |
尋找第一個滿足特定條件的元素 (演算法函式物件) |
| (C++20) |
在特定範圍中尋找最後一次出現的元素序列 (演算法函式物件) |
| (C++20) |
搜尋一組元素中的任何一個 (演算法函式物件) |
| (C++23)(C++23) |
檢查範圍是否包含給定的元素或子範圍 (演算法函式物件) |
| (C++20) |
如果一個序列是另一個序列的子序列，則返回 true (演算法函式物件) |
| (C++20) |
尋找兩個範圍開始不同的第一個位置 (演算法函式物件) |
| (C++20) |
在一個範圍內搜尋一個元素的連續 N 次副本首次出現的位置 (演算法函式物件) |
| 搜尋一個範圍的元素首次出現的位置 (函式模板) |
