CODEWITHSUNDEEP
c++algorithm
ecatmur
ecatmur

Reputation: 157374

Determine whether a predicate holds for none, some or all elements of a range

Since C++11, in the algorithms library we have all_of, any_of and none_of to determine whether a predicate holds on all, any or none of the elements of a range. A single call to one of these algorithms returns 1 bit of information, whereas for a particular range and predicate there are 4 possibilities:

Is there a concise and efficient way to find this information? Calling all_of followed by none_of is a possibility, but (a) fails to work on single-pass ranges, and (b) evaluates the predicate exactly once more than necessary. Boost would be acceptable.

Upvotes: 8

Views: 683

Answers (4)

Colonel Panic
Colonel Panic

Reputation: 137622

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

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

Upvotes: 0

ecatmur
ecatmur

Reputation: 157374

This is my preferred algorithm (enum 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);
}

Upvotes: 0

Kolja
Kolja

Reputation: 1247

Am I understanding this question wrongly, or is this something you could do via 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;
}

Upvotes: 1

Csq
Csq

Reputation: 5855

You can eliminate both (a) the (b) problems if you examine the first element manually and choose between all_of or none_of depending on the result.

Code (borrowed the 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;
  }
}

Upvotes: 10

Related Questions