Znajdź n-ty element spełniający warunek?

Question

Czy jest kilka std::algorithm/lambda function, aby uzyskać dostęp do elementu nth spełniającego dany warunek. Ponieważ std::find_if uzyska dostęp do pierwszego, więc czy istnieje odpowiednik znaleźć numer nth?

Answer 1

Należy utworzyć predykat stanowy, który policzy liczbę wystąpień, a następnie zakończy się po osiągnięciu oczekiwanej liczby. Problem polega na tym, że nie ma gwarancji, ile razy predykat zostanie skopiowany podczas oceny algorytmu, więc musisz zachować ten stan poza samym predykatem, co czyni go nieco brzydkim, ale możesz zrobić :

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) 
    }); 
}; 

Jeśli pojawia się często i nie są zaniepokojeni wydajność, można napisać adapter źródłowe, które stworzył shared_ptr do liczenia wewnętrznie i zaktualizowany. Wiele kopii tego samego adaptera udostępnia ten sam rzeczywisty obiekt zliczania.

Inną alternatywą byłoby wdrożenie find_nth_if, co może być prostsze.

#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

odpowiedź Dawida jest w porządku, jak to jest. Pozwolę sobie tylko zauważyć, że predykat może zostać wyodrębniony do iteratorów przy użyciu biblioteki Boost.Iterator, w szczególności adaptera boost::filter_iterator, który ma tę zaletę, że może być użyty do wielu innych algorytmów (np. Liczenia):

#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. Spowoduje to wydrukowanie 2 (2. element> 0, licząc począwszy od 1 tak, że find_if mecze find_if_nth z n==1. Jeżeli orzeczenie zostanie zmieniony na i > 10 lub jeśli n-ty element jest zmieniany na n = 6, zwróci iteracyjnej końca.

Answer 3

szablon funkcja STL-jak byłoby:

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; 
} 

A jeśli koniecznie chcesz używać std::find_if, można mieć coś takiego:

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; 
}