哪种STL算法可以确定容器中的某一项是否完全满足谓词?

我需要一个带谓词和集合的STL算法,如果集合中只有一个成员满足该谓词,则返回true,否则返回false

我将如何使用STL算法做到这一点?

例如,用STL算法代码替换以下内容以表示相同的返回值。

int count = 0;

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

return 1 == count;
4个解决方案
77 votes

我想到两件事:

none_of,然后将结果与none_of进行比较。

为了避免在例如前两个元素已经匹配谓词的情况下遍历整个容器,我将使用两个调用来寻找匹配的元素。 沿线的东西

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进行了分括号,Blastfurnance意识到我们也可以使用std算法none_of

formerlyknownas_463035818 answered 2020-06-30T00:46:06Z
14 votes

您可以使用N†计数并返回(如果为1)。

例如:

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

†更新:但是,N对容器中的整个元素进行计数,这不像问题中给出的算法那样好。 @ formerlyknownas_463035818的答案中提到了使用标准算法集合的最佳方法。

话虽这么说,OP的方法还是上面提到的最佳标准方法一样好,当29450772252317460460到达2时会发生短路。如果有人对OP的方法的非标准算法模板功能感兴趣,就是这样。

#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;
}
JeJo answered 2020-06-30T00:46:44Z
10 votes

从@ formerlyknownas_463035818的答案开始,可以将其推广为查看容器是否恰好具有满足谓词的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);
    }
}
Mark H answered 2020-06-30T00:47:05Z
8 votes

使用std::array否定谓词

作为此问题的算法的核心(如已通过在接受的答案中组合std::arraystd::array很好地涵盖了该问题),并且在发生故障时发生短路,它是扫描容器中的一元谓词,并在遇到该条件时继续扫描 对于谓词的否定,在容器的其余部分中,我还将提到C ++ 17中引入的否定器std::array,它代替了不太有用的std::index_sequencestd::none_of构造。

我们可以使用std::array来实现与接受的答案(std::index_sequence有条件地跟在后面的std::none_of)相同的谓词逻辑,但是语义有所不同,在第一步中使用的一元谓词的否定之后,用std::array替换后一步(std::none_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
}

这也将在早期故障时短路(“发现多个”),但是将包含比上述方法更简单的布尔比较。

dfri answered 2020-06-30T00:47:48Z
translate from https://stackoverflow.com:/questions/56500676/what-stl-algorithm-can-determine-if-exactly-one-item-in-a-container-satisfies-a