Tìm phần tử thứ n thỏa mãn điều kiện?

Question

Có một vài số std::algorithm/lambda function để truy cập phần tử nth thỏa mãn điều kiện nhất định không. Bởi vì std::find_if sẽ truy cập vào cái đầu tiên, vậy có tương đương để tìm số nth không?

Answer 1

Bạn cần phải tạo một biến vị ngữ trạng thái sẽ đếm số lượng cá thể và sau đó hoàn thành khi đạt đến số lượng mong đợi. Bây giờ vấn đề là không có sự đảm bảo về số lần vị từ sẽ được sao chép trong quá trình đánh giá thuật toán, vì vậy bạn cần duy trì trạng thái đó bên ngoài chính biến vị ngữ, điều này làm cho nó hơi xấu xí, nhưng bạn có thể làm :

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

Nếu điều này xuất hiện thường xuyên và bạn không quan tâm đến hiệu suất, bạn có thể viết bộ điều hợp biến vị ngữ đã tạo shared_ptr cho số nội bộ và cập nhật. Nhiều bản sao của cùng một bộ điều hợp sẽ chia sẻ cùng một đối tượng đếm thực tế.

Một giải pháp thay thế khác là triển khai find_nth_if, điều này có thể đơn giản hơn.

#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

câu trả lời của David là tốt vì nó là. Hãy để tôi chỉ ra rằng biến vị ngữ có thể được trừu tượng hóa thành các trình vòng lặp bằng cách sử dụng thư viện Boost.Iterator, cụ thể là bộ điều hợp boost::filter_iterator, có lợi thế là nó có thể được sử dụng cho nhiều thuật toán hơn nữa (đếm ví dụ):

#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. Điều này sẽ in 2 (yếu tố thứ 2> 0, đếm bắt đầu từ 1, do đó find_if trận find_if_nth với n==1. Nếu vị được thay đổi để i > 10 hoặc nếu các yếu tố thứ n được thay đổi để n = 6, nó sẽ trả lại lặp kết thúc.

Answer 3

Một STL-như hàm mẫu sẽ là:

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

Và nếu bạn hoàn toàn muốn sử dụng std::find_if, bạn có thể có một cái gì đó như:

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