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

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

46 голосов
/ 07 июня 2019

Мне нужен алгоритм 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 голосов
/ 07 июня 2019

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

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 стандартные алгоритмы.

13 голосов
/ 07 июня 2019

Вы можете использовать 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. Если кого-то интересует нестандартная функция шаблона алгоритма для подхода ОП, вот оно. 

#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;
}
9 голосов
/ 09 июня 2019

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

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

В качестве ядра алгоритма этого вопроса (как было элегантно описано путем объединения std::find_if и std::none_of в принятый ответ ) с коротким замыканием при сбое - это сканирование контейнера на наличие унарного предиката и, если оно выполнено, продолжение сканирования остальной части контейнера на предмет отрицания предиката, я также упомяну отрицатель std::not_fn введено в C ++ 17, заменяя менее полезные конструкции std::not1 и std::not2.

Мы можем использовать std::not_fn для реализации той же логики предиката, что и принятый ответ (std::find_if условно сопровождается std::none_of), но с несколько иной семантикой, заменив последний шаг (std::none_of) на std::all_of сверх отрицания унарного предиката, использованного на первом шаге (std::find_if). E.g.:

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

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

...