什么 STL 算法可以确定容器中的一项是否恰好满足谓词？

Question

我需要一个采用谓词和集合的 STL 算法，如果集合中只有一个成员满足谓词，则 returns true，否则 returns false.

我如何使用 STL 算法来做到这一点？

例如，将下面的代码替换为STL算法代码，表达相同的return值。

int count = 0;

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

return 1 == count;

Answer 1

可以用std::count_if^†来算，如果是1就return

例如：

#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：然而，std::count_if计算容器中的整个元素，这不如给出的算法好在问题中。的回答中提到了使用标准算法集合的最佳方法。

也就是说，OP 的方法与上述最佳标准方法一样好，其中 short-circuiting 发生在 count 达到 2 时。如果有人对OP方法的non-standard算法模板函数感兴趣，就在这里。

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

现在可以泛化，通过再提供一个参数，必须/必须在容器中找到 N 个元素的数量。

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

Answer 2

我想到两件事：

std::count_if 然后将结果与 1.

进行比较

为了避免在前两个元素已经与谓词匹配的情况下遍历整个容器，我将使用两次调用来查找匹配元素。沿着

的方向

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

或者如果你更喜欢它更紧凑：

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

归功于 Remy Lebeau 的压缩，Deduplicator 的 debracketing 和 Blastfurnance 实现了我们也可以使用 none_of std 算法。

Answer 3

使用 `std::not_fn` 否定谓词

作为这个问题算法的核心（已经通过组合 std::find_if and std::none_of in 优雅地涵盖），在失败时 short-circuiting 是扫描容器中的一元谓词，并且，当遇到了，继续扫描容器的其余部分以寻找谓词的否定，我还会提到 C++17 中引入的否定符 std::not_fn，替换不太有用的 std::not1 和 std::not2 结构。

我们可以使用 std::not_fn 来实现与已接受答案相同的谓词逻辑（std::find_if 有条件地后跟 std::none_of），但语义略有不同，替换了后一步（ std::none_of) 与 std::all_of 对第一步中使用的一元谓词 (std::find_if) 的否定。例如：

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

静态大小容器的参数包方法

由于我已经将此答案限制为 C++14（及更高版本），我将包含一种用于静态大小容器的替代方法（此处特别适用于 std::array），利用std::index_sequence结合参数包扩展：

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

这也会 short-circuit 在早期失败时（“发现不止一个”），但将包含比上述方法更简单的布尔比较。

但是，请注意，这种方法可能有其 draw-backs，特别是对于具有许多元素的容器输入的优化代码，正如@PeterCordes 在在下面评论。引用评论（因为评论不能保证随着时间的推移持续存在）：

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

Answer 4

从开始，这可以概括为查看容器是否恰好有 n 项满足谓词。为什么？因为这是 C++，我们不满意，直到我们可以在编译时阅读电子邮件。

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

什么 STL 算法可以确定容器中的一项是否恰好满足谓词？

What STL algorithm can determine if exactly one item in a container satisfies a predicate?

c++

algorithm

counting

c++-standard-library

c++11

使用 `std::not_fn` 否定谓词

静态大小容器的参数包方法

什么 STL 算法可以确定容器中的一项是否恰好满足谓词？

What STL algorithm can determine if exactly one item in a container satisfies a predicate?

c++

algorithm

counting

c++-standard-library

c++11

使用 std::not_fn 否定谓词

静态大小容器的参数包方法

使用 `std::not_fn` 否定谓词