我有以下功能(玩具示例，但适合演示):
// finds the iterator pointing to the start of n consectuve 47s or return values.end() if not found
auto find_n_47s(const int n, const std::vector<int>& values){
std::vector<bool> predicate_result;
predicate_result.reserve(values.size());
std::transform(values.begin(), values.end(), std::back_inserter(predicate_result), []
(const auto& val){return val==47; });
std::vector<bool> search_pattern(n, true);
auto it= std::search(predicate_result.begin(), predicate_result.end(),
search_pattern.begin(), search_pattern.end());
return values.begin() + std::distance(predicate_result.begin(), it);
}
我正在寻找一种更好、更有效的方法来完成同样的事情。
我的问题:
我不能使用手动迭代+ std::all_of(从当前元素到 前面的 n 个元素)因为它太慢了(理论上对于每个元素 我最多执行 n 个谓词应用程序)。
我的解决方案分配内存并计算每个谓词 元素，尽管我们可能会在前 1% 中找到结果 元素。
最佳答案
正如 Cruz Jean 指出的，您可以使用 search_n:
https://wandbox.org/permlink/ENgEi5ZVPDx1D1GQ
search_n 的 GCC 实现
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h
不检查每个元素:
|---------|---------|---------|----------------|
| Find first occurence of n=7 consecutive 47 |
|---------|---------|---------|----------------|
| vector | step# | count | |
|---------|---------|---------|----------------|
| 47 | | | |
| 47 | | | |
| 47 | | | |
| 0 | 4 | 3 | |
| 47 | 3 | 3 | |
| 47 | 2 | 2 | |
| 47 | 1 | 1 | start |
| 47 | | | |
| 47 | | | |
| 0 | 5 | 0 | |
| 47 | | | |
| 0 | | | |
| 0 | | | |
| 47 | | | |
| 0 | | | |
| 47 | | | |
| 0 | 6 | 0 | |
| 0 | | | |
| 0 | | | |
| 0 | | | |
| 0 | | | |
| 47 | | | |
| 0 | | | |
| 0 | 7 | 0 | |
| 47 | | | |
| 47 | | | |
| 47 | | | |
| 47 | | | |
| 0 | | | |
| 0 | 9 | 1 | |
| 47 | 8 | 1 | |
| 47 | 15 | 7 | success |
| 47 | 14 | 6 | |
| 47 | 13 | 5 | |
| 47 | 12 | 4 | |
| 47 | 11 | 3 | |
| 47 | 10 | 2 | |
| 47 | | | |
| 0 | | | |
| 0 | | | |
| 47 | | | |
| 0 | | | |
| … | | | |
|---------|---------|---------|----------------|
关于c++ - STL或范围算法有效地找到满足谓词的n个连续元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58156754/