c++ - 找到满足条件的第 n 个元素？

Question

是否有几个std::algorithm/lambda function可以访问nth满足给定条件的元素。因为std::find_if将访问第一个，所以是否有等价的找到那个nth？

Answer 1

您需要创建一个有状态的谓词来计算实例数，然后在达到预期计数时完成。现在的问题是，无法保证在算法评估期间谓词将被复制多少次，因此您需要在谓词本身之外维护该状态，这使它有点难看，但是您可以：

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

如果这经常出现，并且您不关心性能，您可以编写一个谓词适配器，在内部创建一个 shared_ptr 到计数并更新它。同一个适配器的多个副本将共享同一个实际计数对象。

另一种选择是实现find_nth_if，这可能更简单。

#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

一个类似 STL 的函数模板是：

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

如果你绝对想使用std::find_if，你可以有类似的东西：

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

大卫的回答很好。让我指出，谓词可以通过使用Boost.Iterator库抽象为迭代器，特别是boost::filter_iterator适配器，它的优点是它也可以用于更多的算法（计算例如）：

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

活生生的例子。这将打印 2（第 2 个元素 > 0，从 1 开始计数，因此与find_if匹配。如果谓词更改为或如果第 n 个元素更改为，它将返回结束迭代器。find_if_nthn==1i > 10n = 6