Quel algorithme STL peut déterminer si un seul élément d'un conteneur satisfait à un prédicat ?

Question

J'ai besoin d'un algorithme STL qui prend un prédicat et une collection et retourne true si un et un seul membre de la collection satisfait le prédicat, sinon retourne false .

Comment pourrais-je faire cela en utilisant les algorithmes STL ?

Par exemple, remplacer ce qui suit par du code algorithmique STL pour exprimer la même valeur de retour.

int count = 0;

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

return 1 == count;

Answer 1

Deux choses me viennent à l'esprit :

std::count_if puis compare le résultat à 1 .

Pour éviter de parcourir tout le conteneur au cas où, par exemple, les deux premiers éléments correspondent déjà au prédicat, j'utiliserais deux appels pour rechercher les éléments correspondants. Quelque chose du genre

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

Ou si vous le préférez plus compact :

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

Les crédits vont à Remy Lebeau pour le compactage, Deduplicator pour le débracketing et Blastfurnance pour avoir réalisé que nous pouvons également utiliser none_of les algorithmes standard.

Answer 2

Vous pouvez utiliser std::count_if † pour compter et retourner si c'est un.

Par exemple :

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

---

† Mise à jour : Cependant, std::count_if compte l'élément entier dans le conteneur, ce qui n'est pas bon comme l'algorithme donné dans la question. La meilleure approche utilisant les collections d'algorithme standard a été mentionnée dans @formerlyknownas_463035818 La réponse de la Commission.

Ceci étant dit, l'approche de l'OP est aussi bonne que l'approche standard mentionnée ci-dessus, où un court-circuit se produit lorsque count atteint 2 . Si quelqu'un est intéressé par une fonction modèle d'algorithme non standard pour l'approche d'OP, la voici.

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

Maintenant, cela peut être généralisé en fournissant un paramètre supplémentaire, le nombre de N Le ou les éléments doivent se trouver dans le conteneur.

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 3

À partir de formerlyknownas_463035818's answer on peut généraliser cette méthode pour voir si un conteneur possède exactement n les éléments qui satisfont à un prédicat. Pourquoi ? Parce que nous sommes en C++ et que nous ne sommes pas satisfaits tant que nous ne pouvons pas lire le courrier électronique au moment de la compilation.

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

Answer 4

Utilisation de std::not_fn pour nier un prédicat

Comme le cœur de l'algorithme de cette question (comme cela a été élégamment couvert par la combinaison de std::find_if y std::none_of sur la réponse acceptée ), avec court-circuit en cas d'échec, consiste à analyser un conteneur à la recherche d'un prédicat unaire et, lorsqu'il est satisfait, à poursuivre l'analyse du reste du conteneur à la recherche de la négation du prédicat, je mentionnerai aussi le négateur std::not_fn introduit dans C++17, remplaçant le moins utile std::not1 y std::not2 les constructions.

Nous pouvons utiliser std::not_fn pour implémenter la même logique de prédicat que la réponse acceptée ( std::find_if suivi sous condition par std::none_of ), mais avec une sémantique quelque peu différente, en remplaçant la dernière étape ( std::none_of ) avec std::all_of sur le négation du prédicat unaire utilisé dans la première étape ( std::find_if ). Par exemple :

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

---

Une approche de type "parameter pack" pour les conteneurs de taille statique

Comme j'ai déjà limité cette réponse à C++14 (et au-delà), je vais inclure une approche alternative pour les conteneurs de taille statique (ici appliquée pour std::array spécifiquement), en utilisant std::index_sequence combiné à l'expansion du pack de paramètres :

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

Cela court-circuite également les échecs précoces ("trouvé plus d'un"), mais contient quelques comparaisons booléennes plus simples que dans l'approche ci-dessus.

Cependant Dans le cadre de l'utilisation de l'outil de gestion de l'information, notez que cette approche peut avoir des inconvénients, en particulier pour l'optimisation du code pour les entrées de conteneurs avec de nombreux éléments, comme le souligne @PeterCordes dans un commentaire ci-dessous. Citer le commentaire (car les commentaires ne sont pas garantis de persister dans le temps) :

Ce n'est pas parce que la taille est statique que le fait de dérouler entièrement la boucle avec des modèles est une bonne idée. Dans l'asm résultant, cela nécessite une branche à chaque itération de toute façon pour s'arrêter sur found, donc cela pourrait aussi bien être une branche de boucle. Les processeurs sont bons pour exécuter des boucles (caches de code, tampons de bouclage). Les compilateurs dérouleront complètement les boucles de taille statique en se basant sur des heuristiques, mais il est probable qu'ils ne le fassent pas. ne le fera pas Rembobinez si a est énorme. Donc votre première one_of a déjà le meilleur des deux mondes, en supposant qu'un compilateur moderne normal comme gcc ou clang, ou peut-être MSVC