By WilliamKF


2019-06-07 20:09:12 8 Comments

I need an STL algorithm that takes a predicate and a collection and returns true if one and only one member of the collection satisfies the predicate, otherwise returns false.

How would I do this using STL algorithms?

E.g., to replace the following with STL algorithm code to express the same return value.

int count = 0;

for( auto itr = c.begin(); itr != c.end(); ++itr ) {
    if ( predicate( *itr ) ) {
      if ( ++count > 1 ) {
        break;
      }
    }
}

return 1 == count;

4 comments

@JeJo 2019-06-07 20:12:46

You can use std::count_if to count and return if it is one.

For example:

#include <iostream>
#include <algorithm> // std::count_if
#include <vector>    // std::vector
#include <ios>       // std::boolalpha

template<class Iterator, class UnaryPredicate>
constexpr bool is_count_one(Iterator begin, const Iterator end, UnaryPredicate pred)
{
    return std::count_if(begin, end, pred) == 1;
}

int main()
{
    std::vector<int> vec{ 2, 4, 3 };
    // true: if only one Odd element present in the container
    std::cout << std::boolalpha
              << is_count_one(vec.cbegin(), vec.cend(),
                  [](const int ele) constexpr noexcept -> bool { return ele & 1; });
    return 0;
}

Update: However, std::count_if counts entire element in the container, which is not good as the algorithm given in the question. The best approach using the standard algorithm collections has been mentioned in @formerlyknownas_463035818 's answer.

That being said, OP's approach is also good as the above mentioned best standard approach, where a short-circuiting happens when count reaches 2. If someone is interested in a non-standard algorithm template function for OP's approach, here is it.

#include <iostream>
#include <vector>    // std::vector
#include <ios>       // std::boolalpha
#include <iterator>  // std::iterator_traits

template<class Iterator, class UnaryPredicate>
bool is_count_one(Iterator begin, const Iterator end, UnaryPredicate pred)
{
    typename std::iterator_traits<Iterator>::difference_type count{ 0 };
    for (; begin != end; ++begin) {
        if (pred(*begin) && ++count > 1) return false;
    }
    return count == 1;
}

int main()
{
    std::vector<int> vec{ 2, 3, 4, 2 };
    // true: if only one Odd element present in the container
    std::cout << std::boolalpha
              << is_count_one(vec.cbegin(), vec.cend(),
                  [](const int ele) constexpr noexcept -> bool { return ele & 1; });
    return 0;
}

Now that can be generalized, by providing one more parameter, the number of N element(s) has/ have to be found in the container.

template<typename Iterator>
using diff_type = typename std::iterator_traits<Iterator>::difference_type;

template<class Iterator, class UnaryPredicate>
bool has_exactly_n(Iterator begin, const Iterator end, UnaryPredicate pred, diff_type<Iterator> N = 1)
{
    diff_type<Iterator> count{ 0 };
    for (; begin != end; ++begin) {
        if (pred(*begin) && ++count > N) return false;
    }
    return count == N;
}

@WilliamKF 2019-06-07 20:38:08

Yes, but that misses the key requirement of not counting past 2.

@WilliamKF 2019-06-07 21:01:51

I mean once count reaches 2, it is unnecessary to continue computing the predicate.

@JeJo 2019-06-07 21:16:48

@WilliamKF Shamefully agree with that. The other answer shows a better alternative. In case, you are interested to convert your shown algorithm to a better version by packing them into a templated function, here is an example:wandbox.org/permlink/zej1d4L0J7RoS5PH which will short circuit as in your code.

@Mark H 2019-06-09 12:02:48

Starting from @formerlyknownas_463035818's answer, this can be generalized to seeing if a container has exactly n items that satisfy a predicate. Why? Because this is C++ and we're not satisfied until we can read email at compile time.

template<typename Iterator, typename Predicate>
bool has_exactly_n(Iterator begin, Iterator end, size_t count, Predicate predicate)
{
    if(count == 0)
    {
        return std::none_of(begin, end, predicate);
    }
    else
    {
        auto iter = std::find_if(begin, end, predicate);
        return (iter != end) && has_exactly_n(std::next(iter), end, count - 1, predicate);
    }
}

@Cody Gray 2019-06-09 19:50:51

I tried your code, but I was unable to read my email. Please let me know what I am doing wrong. Thanks. On a more serious note, why not go one step further and make the n a compile-time value (template non-type parameter) as well?

@Kevin 2019-06-09 23:14:07

@CodyGray: If n = 10000, does the compiler recursively generate 10000 templates, or are modern compilers smart enough to do tail-call elimination in the templating step?

@Mark H 2019-06-10 00:13:08

@CodyGray I believe the std::email_client concept has been pushed back to C++23.

@Mark H 2019-06-10 17:48:07

@CodyGray I've tried your idea here: repl.it/repls/BossyIdealDatawarehouse. The problem is, as mentioned by @Kevin, that a new function is generated for every value of n. If you want to know whether a std::vector<int> has exactly 100,000 zeros in it, the program won't compile.

@Mark H 2019-06-10 17:50:29

@Kevin The compiler can't do tail-call optimization because the functions generated are different. Every value of n gets a new function which calls the function for n-1. This leads to compilation failing. See the link in my previous comment.

@dfri 2019-06-08 18:53:29

Using std::not_fn to negate a predicate

As the core of the algorithm of this question (as has been elegantly covered by combining std::find_if and std::none_of in the accepted answer), with short-circuiting upon failure, is to scan a container for a unary predicate and, when met, continue scanning the rest of the container for the negation of the predicate, I will mention also the negator std::not_fn introduced in C++17, replacing the less useful std::not1 and std::not2 constructs.

We may use std::not_fn to implement the same predicate logic as the accepted answer (std::find_if conditionally followed by std::none_of), but with somewhat different semantics, replacing the latter step (std::none_of) with std::all_of over the negation of the unary predicate used in the first step (std::find_if). E.g.:

// C++17
#include <algorithm>   // std::find_if
#include <functional>  // std::not_fn
#include <ios>         // std::boolalpha
#include <iostream>
#include <iterator>  // std::next
#include <vector>

template <class InputIt, class UnaryPredicate>
constexpr bool one_of(InputIt first, InputIt last, UnaryPredicate p) {
  auto it = std::find_if(first, last, p);
  return (it != last) && std::all_of(std::next(it), last, std::not_fn(p));
}

int main() {
  const std::vector<int> v{1, 3, 5, 6, 7};
  std::cout << std::boolalpha << "Exactly one even number : "
            << one_of(v.begin(), v.end(), [](const int n) {
                 return n % 2 == 0;
               });  // Exactly one even number : true
}

A parameter pack approach for static size containers

As I’ve already limited this answer to C++14 (and beyond), I’ll include an alternative approach for static size containers (here applied for std::array, specifically), making use of std::index_sequence combined with parameter pack expansion:

#include <array>
#include <ios>         // std::boolalpha
#include <iostream>
#include <utility>     // std::(make_)index_sequence

namespace detail {
template <typename Array, typename UnaryPredicate, std::size_t... I>
bool one_of_impl(const Array& arr, const UnaryPredicate& p,
                 std::index_sequence<I...>) {
  bool found = false;
  auto keep_searching = [&](const int n){
      const bool p_res = found != p(n);
      found = found || p_res;
      return !found || p_res;
  };
  return (keep_searching(arr[I]) && ...) && found;
}
}  // namespace detail

template <typename T, typename UnaryPredicate, std::size_t N,
          typename Indices = std::make_index_sequence<N>>
auto one_of(const std::array<T, N>& arr,
            const UnaryPredicate& p) {
  return detail::one_of_impl(arr, p, Indices{});
}

int main() {
  const std::array<int, 5> a{1, 3, 5, 6, 7};
  std::cout << std::boolalpha << "Exactly one even number : "
            << one_of(a, [](const int n) {
                 return n % 2 == 0;
               });  // Exactly one even number : true
}

This will also short-circuit upon early failure (“found more than one”), but will contain a few more simple boolean comparisons than in the approach above.

@Peter Cordes 2019-06-08 21:38:58

Just because the size is static doesn't mean that fully unrolling the loop with templates is a good idea. In the resulting asm, this needs a branch every iteration anyway to stop on found, so that might as well be a loop-branch. CPUs are good at running loops (code caches, loopback buffers). Compilers will fully unroll static-sized loops based on heuristics, but probably won't roll this back up if a is huge. So your first one_of implementation has the best of both worlds already, assuming a normal modern compiler like gcc or clang, or maybe MSVC.

@dfri 2019-06-08 21:45:05

@PeterCordes thanks for the feedback, good point(s)! As I currently don’t get to use modern C++ features in my work, I fear some of my answers might become blindly biased to using particular “new” (non-legacy ...) core language features I find interesting to practice on. I’ll add your comment as a quote at the end of my answer, if it’s ok? As comments may not persist over time.

@formerlyknownas_463035818 2019-06-07 20:14:25

Two things come to my mind:

std::count_if and then compare the result to 1.

To avoid traversing the whole container in case eg the first two elements already match the predicate I would use two calls looking for matching elements. Something along the line of

auto it = std::find_if(begin,end,predicate);
if (it == end) return false;
++it;
return std::none_of(it,end,predicate);

Or if you prefer it more compact:

auto it = std::find_if(begin,end,predicate); 
return (it != end) && std::none_of(std::next(it),end,predicate);

Credits goes to Remy Lebeau for compacting, Deduplicator for debracketing and Blastfurnance for realizing that we can also use none_of the std algorithms.

@NathanOliver 2019-06-07 20:23:09

I like the short-circuiting of the second option.

@formerlyknownas_463035818 2019-06-07 20:26:33

@NathanOliver I always strive to be as explicit as possible about what I actually want to do in the code, actually not that much for efficiency but mainly for clarity of the code. Nobody asked for the count over the whole container, so why make the code lie about it. unfortunately its not always as easy as in this example

@StoryTeller 2019-06-07 20:50:06

Someone will probably disagree with me on this, vocally, but I just feel compelled to say it. It's answers like this that remind me about the beauty that can sometimes be found in the standard algorithm library.

Related Questions

Sponsored Content

24 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

3 Answered Questions

Does a standard algorithm for sorting and partitioning two ranges in the following way exist?

  • 2019-04-15 11:21:34
  • Ton van den Heuvel
  • 115 View
  • 1 Score
  • 3 Answer
  • Tags:   c++ algorithm stl

1 Answered Questions

[SOLVED] Can't use the lambda function inside function template

2 Answered Questions

[SOLVED] is_partitioned behavior when no elements satisfy predicate

1 Answered Questions

2 Answered Questions

[SOLVED] Does zero match always "matches" when regex_search returns true?

  • 2014-08-01 17:29:55
  • PowerGamer
  • 447 View
  • 4 Score
  • 2 Answer
  • Tags:   c++ regex c++11

38 Answered Questions

[SOLVED] Algorithm to determine if array contains n...n+m?

1 Answered Questions

[SOLVED] Implementations of count_until and accumulate_until?

12 Answered Questions

[SOLVED] Determining if two vectors contain two adjacent items the same

Sponsored Content