时间戳

首页 > 解决方案 > STL 或范围算法可有效地找到满足谓词的 n 个连续元素

c++ - STL 或范围算法可有效地找到满足谓词的 n 个连续元素

问题描述

我有以下功能（玩具示例，但适合演示）：

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

我正在寻找一种更好、更有效的方法来完成同样的事情。

我的问题：

  1. 我不能使用手动迭代 + std::all_of(从当前元素到前面的 n 个元素)，因为它太慢了(理论上对于我最多 n 个谓词应用程序所做的每个元素)。

  2. 我的解决方案为每个元素分配内存并计算谓词，尽管我们可能会在前 1% 的元素中找到结果。

完整代码在这里：https ://wandbox.org/permlink/rBVFS64IcOI6gKe6

标签： c++stlc++20range-v3

解决方案

正如 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      |         |         |                |
|  …      |         |         |                |
|---------|---------|---------|----------------|

推荐阅读