Determina se un predicato vale per nessuno, alcuni o tutti gli elementi di un intervallo

Question

Dopo C++ 11, nella libreria degli algoritmi abbiamo all_of, any_of and none_of per determinare se un predicato vale per tutti, nessuno o nessuno degli elementi di un intervallo. Una singola chiamata a uno di questi algoritmi restituisce 1 bit di informazione, mentre per un determinato intervallo e predicato ci sono 4 possibilità:

• Il predicato trattiene tutti gli elementi e senza elementi: l'intervallo è vuota;
• Il predicato vale su tutti gli elementi (e l'intervallo non è vuoto);
• Il predicato non contiene elementi (e l'intervallo non è vuoto);
• Il predicato vale per alcuni ma non per tutti gli elementi.

Esiste un modo sintetico ed efficace per trovare queste informazioni? Chiamare all_of seguito da none_of è una possibilità, ma (a) non riesce a funzionare su intervalli a passaggio singolo e (b) valuta il predicato esattamente una volta più del necessario. Boost sarebbe accettabile.

Answer 1

È possibile eliminare entrambi (a) i problemi (b) se si esamina il primo elemento manualmente e si sceglie tra all_of o none_of a seconda del risultato.

Codice (preso in prestito il enum da @Angew):

enum class Result { 
    empty, all, none, some 
}; 

template <class FwIt, class Pred> 
Result examine_range(FwIt from, FwIt to, Pred pred) 
{ 
    if (from == to) return Result::empty; 
    if (pred(*from)) { 
    ++from; 
    return all_of(from,to,pred) ? Result::all : Result::some; 
    } else { 
    ++from; 
    return none_of(from,to,pred) ? Result::none : Result::some; 
    } 
} 

Answer 2

Perchè sono la comprensione questa domanda a torto, o si tratta di qualcosa che si potrebbe fare tramite std::accumulate?

using eana = std::tuple<bool, bool, bool, bool>; 

template <typename T, typename FwdIt, typename Pred> 
auto empty_all_none_any(FwdIt begin, FwdIt end, Pred predicate) -> eana { 
    auto result = eana{begin == end, begin != end, begin != end, false}; 
    result = std::accumulate(begin, end, result, [&](eana& res, T& val) { 
    if (predicate(val)) { 
     std::get<2>(res) = false; 
     std::get<3>(res) = true; 
    } 
    else { 
     std::get<1>(res) = false; 
    } 
    return res; 
    }); 
    return result; 
} 

Answer 3

Questo è il mio preferito algoritmo (enum da @Angew):

enum class Result { 
    empty, all, none, some 
}; 
template<class InputIt, class UnaryPredicate> 
Result examine_range(InputIt first, InputIt last, UnaryPredicate p) 
{ 
    bool all = true, none = true; 
    for (; first != last && (all || none); ++first) 
     (p(*first) ? none : all) = false; 
    return all ? (none ? Result::empty : Result::all) 
     : (none ? Result::none : Result::some); 
} 

Answer 4

È possibile farlo con le funzioni della libreria standard che descrivi. Prova entrambi se eventuali elementi sono vere, e se tutti gli elementi sono false, quindi combinare i risultati in base a questa tabella:

   any true | none true 
      ====================== 
any false | mixed | all false | 
none false | all true | empty |