一种按索引过滤范围，仅从过滤后的索引中获取 min_element 的方法？

Question

在对该问题的评论中还有一个问题 - 是否可以在容器上使用 "index view"，即过滤掉一些索引的子范围。

此外，我遇到了一个问题，即从过滤掉一些索引的范围中找到最小值。

即是否可以用 std and/or 提升算法、过滤器替换如下代码 - 以使其更具可读性和可维护性：

template <typename Range, typename IndexPredicate>
auto findMin(const Range& range, IndexPredicate ipred) 
     -> boost::optional<typename Range::value_type>
{
    bool found = false;
    typename Range::value_type minValue{};
    for (std::size_t i = 0; i < range.size(); ++i)
    {
        if (not ipred(i))
            continue;
        if (not found)
        {
            minValue = range[i];
            found = true;
        }
        else if (minValue > range[i])
        {
            minValue = range[i];
        }
    }
    if (found)
    {
        return minValue;
    }
    else
    {
        return boost::none;
    }
}

只是这样使用：

#include <iostream>
#include <vector>

int main() {
    std::vector<float> ff = {1.2,-1.2,2.3,-2.3};
    auto onlyEvenIndex = [](auto i){ return (i&1) == 0;};

    auto minValue = findMin(ff, onlyEvenIndex);
    std::cout << *minValue << std::endl;
}

Answer 1

解决这个问题的方法是超越 C++ 中过滤范围的自然方式。我的意思是——我们需要过滤索引的范围，而不是值的范围。但是我们从哪里得到索引的范围呢？有办法获取索引范围 - boost::irange。所以 - 看这个：

#include <boost/range/irange.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/algorithm/min_element.hpp>
#include <functional>

template <typename Range, typename IndexPredicate>
auto findMin(const Range& range, IndexPredicate ipred) -> boost::optional<typename Range::value_type>
{
    using boost::adaptors::filtered;
    using boost::irange;

    auto filtered_indexes = irange(0u, range.size()) | filtered(std::function<bool(std::size_t)>{ipred});

使用提升范围的一个缺点是 they have problems to use raw lambdas - 所以这就是我需要使用 std::function.

的原因

嵌套步骤与使用 boost::min_element 一样简单 - 唯一要记住的是您应该比较值。不只是索引：

auto lessByValue = [&range] (auto lhs, auto rhs) 
{ 
      return range[lhs] < range[rhs]; 
};

最后的步骤：

auto foundMin = boost::min_element(filtered_indexes, lessByValue);
if (foundMin != std::end(filtered_indexes))
    return range[*foundMin];
else 
    return boost::none;

Answer 2

使用最近的标准 range-v3 proposal:

#include <range/v3/all.hpp>
#include <iostream>
#include <vector>

int main() 
{
    std::vector<float> rng = {1.2,-1.2,2.3,-2.3};

    auto even_indices = 
        ranges::view::iota(0ul, rng.size()) | 
        ranges::view::filter([](auto i) { return !(i & 1); })
    ;
    auto min_ind = *ranges::min_element(
        even_indices, [&rng](auto L, auto R) { 
        return rng[L] < rng[R]; 
    });
    std::cout << rng[min_ind];
}

Live Example。请注意，语法与 Boost.Range 大致相似，但经过全面修改以利用 C++14（广义 lambda、自动 return 类型推导等）

Answer 3

从开始回答前面的问题。可选地执行该问题扩充中描述的任务。

增加 indexT 以支持步幅模板参数 size_t stride=1：将 ++t; 替换为 std::advance(t,stride);

将ItB base() const { return b+**a(); }添加到indexing_iterator（这是为了以后）。

添加template<size_t stride> using index_stride_range=range<indexT<size_t, stride>>;这是一个具有编译时跨度的索引范围。

写出适用于两个 index_stride_range 的 intersect。输出是步幅 gcd(lhs_stride, rhs_stride) 的 index_stride_range。找出它从哪里开始是另一项工作，但只是高中数学。请注意，index_range 是 index_stride_range 和 stride=1 的一种类型，因此此升级也适用于 index_range。

升级 index_filter 以将 index_stride_range 作为第一个参数。实现是相同的（除了依赖升级 intersect）。

写 every_nth_index<N>(offset)，这是一个 index_stride_range 从 offset 到 size_t(-(1+(abs(offset))%stride) - (size_t(-(1+(abs(offset)%stride)))%stride) 或类似的东西（在简单的情况下基本上是 0 到无穷大 -- 额外的数学是找到等于 size_t.

的 offset+k*stride 的最大数字

现在我们得到：

auto filtered = index_filter( every_nth_index<2>(), container );
auto it = (std::min)( filtered.begin(), filtered.end() );

我们有一个迭代器。 it.base() 将 return 迭代器放入包含元素 if it!=filtered.end(); 的 container（不是 it.base()!=container.end()，这是不同的）。

一种按索引过滤范围，仅从过滤后的索引中获取 min_element 的方法？

A way to filter range by indices, to get min_element from filtered indices only?

c++

templates

boost

c++11

c++14