Find the nth element satisfying a condition?

Question

Is there a couple of std::algorithm/lambda function to access the nth element satisfying a given condition. Because std::find_if will access the first one, so is there an equivalend to find the nth one ?

Answer 1

You need to create a stateful predicate that will count the number of instances and then complete when the expected count is reached. Now the problem is that there are no guarantees as of how many times the predicate will be copied during the evaluation of the algorithm, so you need to maintain that state outside of the predicate itself, which makes it a bit ugly, but you can do:

iterator which;
{  // block to limit the scope of the otherwise unneeded count variable
   int count = 0;
   which = std::find_if(c.begin(), c.end(), [&count](T const & x) {
        return (condition(x) && ++count == 6)
   });
};

If this comes up frequently, and you are not concerned about performance, you could write a predicate adapter that created a shared_ptr to the count internally and updated it. Multiple copies of the same adapter would share the same actual count object.

Another alternative would be to implement find_nth_if, which could be simpler.

#include <iterator>
#include <algorithm>

template<typename Iterator, typename Pred, typename Counter>
Iterator find_if_nth( Iterator first, Iterator last, Pred closure, Counter n ) {
  typedef typename std::iterator_traits<Iterator>::reference Tref;
  return std::find_if(first, last, [&](Tref x) {
    return closure(x) && !(--n);
  });
}

http://ideone.com/EZLLdL

Answer 2

An STL-like function template would be:

template<class InputIterator, class NthOccurence class UnaryPredicate>
InputIterator find_nth_if(InputIterator first, InputIterator last, NthOccurence Nth, UnaryPredicate pred)
{
    if (Nth > 0)
        while (first != last) {
            if (pred(*first))
                if (!--Nth)
                    return first;
            ++first;
        }
    return last;
}

And if you absolutely want to use the std::find_if, you could have something like:

template<class InputIterator, class NthOccurence class UnaryPredicate>
InputIterator find_nth_if(InputIterator first, InputIterator last, NthOccurence Nth, UnaryPredicate pred)
{
    if (Nth > 0) {
        do
            first = std::find_if(first, last, pred);
        while (!--Nth && ++first != last);
        return first;
    }
    else
        return last;
}

Answer 3

David's answer is fine as it is. Let me just point out that the predicate can be abstracted into the iterators by using the Boost.Iterator library, in particular the boost::filter_iterator adaptor, which has the advantage that it can be used for a lot more algorithms as well (counting e.g.):

#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/iterator/filter_iterator.hpp>

template<class ForwardIt, class Predicate, class Size>
ForwardIt find_if_nth(ForwardIt first, ForwardIt last, Predicate pred, Size n)
{
    auto vb = boost::make_filter_iterator(pred, first, last);
    auto const ve = boost::make_filter_iterator(pred, last, last);
    while (vb != ve && --n)
        ++vb;
    return vb.base();
}

int main()
{
    auto const v = std::vector<int>{ 0, 0, 3, 0, 2, 4, 5, 0, 7 };
    auto const n = 2;
    auto const pred = [](int i){ return i > 0; };
    auto const nth_match = find_if_nth(v.begin(), v.end(), pred, n);

    if (nth_match != v.end())
        std::cout << *nth_match << '\n';
    else
        std::cout << "less than n elements in v matched predicate\n";
}

Live example. This will print 2 (the 2nd element > 0, counting starting at 1, so that find_if matches find_if_nth with n==1. If the predicate is changed to i > 10 or if the nth element is changed to n = 6, it will return the end iterator.