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

Question

In comments to this question is-there-a-way-to-iterate-over-at-most-n-elements-using-range-based-for-loop there was additional question - is this possible to have "index view" on a container, i.e. to have subrange with some indexes filtered out.

Additionally I encountered a problem to find minimum value from a range with some indexes filtered out.

I.e. is it possible to replace such code as below with std and/or boost algorithms, filters - to make it more readable and maintainable:

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

Just to be used like this:

#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

Start with this answer to the earlier question. Optionally do the described tasks in that question augments.

Augment indexT to support a stride template argument size_t stride=1: Replace ++t; with std::advance(t,stride);

Add ItB base() const { return b+**a(); } to indexing_iterator (this is for later).

Add template<size_t stride> using index_stride_range=range<indexT<size_t, stride>>; This is an indexing range with a compile time stride.

Write intersect that works on two index_stride_ranges. The output is an index_stride_range of stride gcd(lhs_stride, rhs_stride). Working out where it starts is another bit of work, but only high-school math. Note that an index_range is a type of index_stride_range with stride=1, so this upgrade will work with index_ranges as well.

Upgrade index_filter to take a index_stride_range as the first argument. The implementation is the same (other than relying on upgraded intersect).

Write every_nth_index<N>(offset), which is an index_stride_range that goes from offset to size_t(-(1+(abs(offset))%stride) - (size_t(-(1+(abs(offset)%stride)))%stride) or some such (basically 0 to infinity in the simple case -- the extra math is to find the biggest number that is equal to offset+k*stride that fits in a size_t.

Now we get:

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

and we have an iterator. it.base() will return the iterator into the container that contains the element if it!=filtered.end(); (not it.base()!=container.end(), which is different).

Answer 2

Using the recently Standard 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. Note that the syntax is roughly similar to Boost.Range, but fully revamped to take advantage of C++14 (generalized lambdas, auto return type deduction etc.)

Answer 3

The solution to this is to think beyond the natural way of filtering ranges in C++. I mean - we need to filter the range of indexes, not the range of values. But from where we got the range of indexes? There is way to get the range of indexes - boost::irange. So - see this:

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

One drawback of using boost ranges is that they have problems to use raw lambdas - so that is why I need to use std::function.

Nest step is as easy as using boost::min_element - the only thing to remember is that you should compare values. not just indexes:

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

And the final steps:

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