Một cách để lọc phạm vi theo chỉ mục, để lấy min_element từ chỉ mục đã lọc?

Question

Trong nhận xét cho câu hỏi này is-there-a-way-to-iterate-over-at-most-n-elements-using-range-based-for-loop có thêm câu hỏi - điều này có thể có "chế độ xem chỉ mục" trên vùng chứa, tức là có sắp xếp lại với một số chỉ mục được lọc ra.

Ngoài ra, tôi gặp phải sự cố khi tìm giá trị tối thiểu từ một phạm vi có một số chỉ mục được lọc ra.

I.e. là nó có thể thay thế mã như dưới đây với std và/hoặc các thuật toán tăng, các bộ lọc - để làm cho nó dễ đọc hơn và dễ bảo trì:

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

Chỉ cần để được sử dụng như thế này:

#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

Sử dụng thời gian gần đây Chuẩn 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. Lưu ý rằng cú pháp là xấp xỉ tương tự như Boost.Range, nhưng tân trang đầy đủ để tận dụng lợi thế của C++ 14 (lambdas khái quát hóa, tự động trở lại loại trừ, vv)

Answer 2

Giải pháp điều này là để suy nghĩ vượt ra ngoài phạm vi tự nhiên của các phạm vi lọc trong C++. Ý tôi là - chúng tôi cần lọc phạm vi chỉ mục, không phải phạm vi giá trị. Nhưng từ đâu chúng ta có nhiều chỉ số? Có cách để có được phạm vi chỉ mục - boost::irange. Vì vậy, - thấy điều này:

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

Một nhược điểm của việc sử dụng tăng dao động là they have problems to use raw lambdas - vì vậy đó là lý do tại sao tôi cần phải sử dụng std::function.

Bước tổ dễ dàng như sử dụng boost::min_element - điều duy nhất cần nhớ là bạn nên so sánh các giá trị. không chỉ là chỉ số:

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

Và bước cuối cùng:

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

Answer 3

Bắt đầu với this answer cho câu hỏi trước đó. Tùy chọn thực hiện các tác vụ được mô tả trong phần bổ sung câu hỏi đó.

tăng indexT để hỗ trợ một mẫu đối số sải chân size_t stride=1: Thay thế ++t; với std::advance(t,stride);

Thêm ItB base() const { return b+**a(); }-indexing_iterator (đây là cho sau này).

Thêm template<size_t stride> using index_stride_range=range<indexT<size_t, stride>>; Đây là phạm vi lập chỉ mục có thời gian biên dịch.

Viết intersect hoạt động trên hai index_stride_range s. Đầu ra là index_stride_range của stride gcd(lhs_stride, rhs_stride). Làm việc ra nơi nó bắt đầu là một chút công việc, nhưng chỉ có toán học trung học. Lưu ý rằng index_range là một loại index_stride_range với stride=1, vì vậy bản nâng cấp này cũng sẽ hoạt động với index_range giây.

Nâng cấp index_filter để tham số index_stride_range làm đối số đầu tiên. Việc thực hiện là như nhau (ngoài việc dựa vào nâng cấp intersect).

Viết every_nth_index<N>(offset), mà là một index_stride_range mà đi offset-size_t(-(1+(abs(offset))%stride) - (size_t(-(1+(abs(offset)%stride)))%stride) hoặc một số ví dụ (về cơ bản từ 0 đến vô cực trong trường hợp đơn giản - toán học thêm là để tìm số lớn nhất đó là bình đẳng để bù đắp + k * sải chân mà . phù hợp trong một size_t

Bây giờ chúng ta nhận được:.

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

và chúng tôi có một iterator it.base() sẽ trả lại iterator vào container có chứa nguyên tố này nếu it!=filtered.end(); (không it.base()!=container.end(), khác nhau).