Determine if a predicate has any, some, or all of the elements of a range

Question

Since C ++ 11, in the library of algorithms we have all_of , any_of and none_of to determine whether the predicate is stored on everyone, any or none of the elements in the range. One call to one of these algorithms returns 1 bit of information, while for a certain range and predicate there are 4 possibilities:

• The predicate is executed for all elements and not a single element: the range is empty;
• The predicate is executed for all elements (and the range is not empty);
• The predicate contains no elements (and the range is not empty);
• The predicate holds for some, but not all, elements.

Is there a short and effective way to find this information? Calling all_of , followed by none_of , is an option, but (a) does not work in single-pass ranges and (b) evaluates the predicate exactly once more than necessary. Boost would be acceptable.

Answer 1

You can fix problems (a) (b) by manually examining the first element and selecting all_of or none_of depending on the result.

Code (borrowed enum from @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

I misunderstand this question, or is it something you could do through 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

This is my preferred algorithm (listing from @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

You can do this with the standard library functions that you describe. Check if any elements are true and if any elements are false, and then combine the results according to this table:

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