Какой алгоритм STL может определить, удовлетворяет ли предикат ровно одному элементу в контейнере?

Ответ 1

Две вещи приходят мне на ум:

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

Кредиты отправляются Реми Лебо за сжатие, Дедупликатору за дебракетинг и Blastfurnance за понимание того, что мы также можем использовать none_of std алгоритмов.

Ответ 2

Вы можете использовать std::count_if ^† для подсчета и возврата, если он один.

Например:

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

^†Обновление: однако std::count_if считает весь элемент в контейнере, что не соответствует алгоритму, приведенному в вопросе. Лучший подход с использованием стандартных наборов алгоритмов был упомянут в ответе @ прежней известной_463035818.

При этом подход OP также хорош как упомянутый выше лучший стандартный подход, где короткое замыкание происходит, когда count достигает 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;
}

Ответ 3

Начиная с ответа @прежней известной_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);
    }
}

Ответ 4

Использование std::not_fn для отрицания предиката

В качестве основы алгоритма этого вопроса (как было элегантно рассмотрено объединением std::find_if и std::none_of в принятом ответе) с коротким замыканием при неудаче является сканирование контейнера на наличие унарного предиката и, когда встретитесь, продолжите сканирование остальной части контейнера на предмет отрицания предиката, я упомяну также отрицатель std::not_fn введенный в С++ 17, заменив менее полезные конструкции 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
}

Подход пакета параметров для контейнеров статического размера

Поскольку я уже ограничил этот ответ С++ 14 (и более std::index_sequence альтернативный подход для контейнеров статического размера (здесь применяется, в частности, для 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
}

Это также приведет к короткому замыканию при раннем отказе ("найдено более одного"), но будет содержать несколько более простых логических сравнений, чем в подходе выше.