Un modo per filtrare il range per indici, per ottenere min_element solo dagli indici filtrati?

Question

Nei commenti a questa domanda is-there-a-way-to-iterate-over-at-most-n-elements-using-range-based-for-loop c'era una domanda aggiuntiva - è possibile avere "vista indice" su un contenitore, cioè disporre di un subrange con alcuni indici filtrati.

Inoltre ho riscontrato un problema per trovare il valore minimo da un intervallo con alcuni indici filtrati.

I.e. è possibile sostituire tale codice come di seguito con std e/o algoritmi Boost, filtri - per renderlo più leggibile e gestibile:

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

Giusto per essere utilizzato in questo modo:

#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

Utilizzando il recente 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. Si noti che la sintassi è approssimativamente simile a Boost.Range, ma completamente rinnovata per trarre vantaggio da C++ 14 (generalizzato lambda, deduzione tipo di ritorno automatico ecc.)

Answer 2

La soluzione a questo è pensare oltre il modo naturale di filtrare gli intervalli in C++. Voglio dire - dobbiamo filtrare l'intervallo di indici, non l'intervallo di valori. Ma da dove abbiamo preso la gamma di indici? C'è un modo per ottenere la gamma di indici - boost::irange. Quindi - vedere questo:

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

Uno svantaggio di usare il boost varia è che they have problems to use raw lambdas - così è per questo che ho bisogno di usare std::function.

Il passo Nest è facile come usare boost::min_element - l'unica cosa da ricordare è che devi confrontare i valori. Non solo: gli indici

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

E le fasi finali:

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

Answer 3

Inizia con this answer alla domanda precedente. Facoltativamente, i compiti descritti in questa domanda aumentano.

Augment indexT per sostenere un modello di argomentazione passo size_t stride=1: Sostituire ++t; con std::advance(t,stride);

Aggiungi ItB base() const { return b+**a(); }-indexing_iterator (questo è per dopo).

Aggiungi template<size_t stride> using index_stride_range=range<indexT<size_t, stride>>; Questo è un intervallo di indicizzazione con un passo temporale di compilazione.

Scrivere intersect che funziona su due index_stride_range s. L'uscita è index_stride_range del passo gcd(lhs_stride, rhs_stride). Lavorare dove inizia è un altro po 'di lavoro, ma solo la matematica del liceo. Notare che un index_range è un tipo di index_stride_range con stride=1, quindi questo aggiornamento funzionerà anche con index_range s.

Aggiornamento index_filter per prendere un index_stride_range come primo argomento. L'implementazione è la stessa (a parte affidarsi all'aggiornamento intersect).

Write every_nth_index<N>(offset), che è un index_stride_range che va offset-size_t(-(1+(abs(offset))%stride) - (size_t(-(1+(abs(offset)%stride)))%stride) o qualcosa del genere (sostanzialmente 0 all'infinito nel caso semplice - la matematica in più è quello di trovare il maggior numero che è uguale a compensare + k * falcata che . si inserisce in un size_t

ora otteniamo:.

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

e abbiamo un iteratore it.base() tornerà l'iteratore nella container che contiene l'elemento se it!=filtered.end(); (non it.base()!=container.end(), che è diverso).