c++ - ¿Qué algoritmo STL puede determinar si exactamente un elemento en un contenedor satisface un predicado?

algorithm c++11

Question

Necesito un algoritmo STL que tome un predicado y una colección y devuelva true si uno y solo un miembro de la colección satisface el predicado; de lo contrario, devuelve false .

¿Cómo haría esto usando algoritmos STL?

Por ejemplo, para reemplazar lo siguiente con el código de algoritmo STL para expresar el mismo valor de retorno.

int count = 0;

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

return 1 == count;

Answer 1

Usando std::not_fn para negar un predicado

Como el núcleo del algoritmo de esta pregunta (como se ha cubierto elegantemente al combinar none_of y none_of en la respuesta aceptada ), con cortocircuito en caso de falla, es escanear un contenedor en busca de un predicado único y cuando se encuentre, continúe escaneando el resto del contenedor para la negación del predicado, mencionaré también el negador std::not_fn introducido en C ++ 17, reemplazando las construcciones std::not1 y std::not2 std::not1 menos útiles.

Podemos usar std::not_fn para implementar la misma lógica de predicado que la respuesta aceptada ( std::find_if seguido condicionalmente por std::none_of ), pero con una semántica algo diferente, reemplazando el último paso ( std::none_of ) con none_of sobre la negación del predicado unario usado en el primer paso ( std::find_if ). P.ej:

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

Un enfoque de paquete de parámetros para contenedores de tamaño estático

Como ya he limitado esta respuesta a C ++ 14 (y más allá), incluiré un enfoque alternativo para contenedores de tamaño estático (aquí se aplica para std::array , específicamente), haciendo uso de std::index_sequence combinado con paquete de parámetros de expansión:

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

Esto también provocará un cortocircuito si se produce un fallo temprano ("se encontraron más de uno"), pero contendrá algunas comparaciones booleanas más simples que en el enfoque anterior.

Answer 2

A partir de la respuesta de @ formerlyknownas_463035818, esto puede generalizarse para ver si un contenedor tiene exactamente n elementos que satisfacen un predicado. ¿Por qué? Porque esto es C ++ y no estamos satisfechos hasta que podamos leer el correo electrónico en tiempo de compilación.

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 3

Dos cosas vienen a mi mente:

std::count_if y luego compara el resultado con 1 .

Para evitar atravesar todo el contenedor en caso de que, por ejemplo, los dos primeros elementos ya coincidan con el predicado, usaría dos llamadas buscando elementos coincidentes. Algo a lo largo de la linea de

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

O si lo prefieres más compacto:

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

Los créditos se asignan a Remy Lebeau para la compactación, Deduplicator para el desguace y Blastfurnance para darse cuenta de que tampoco podemos utilizar none_of los algoritmos none_of .

Answer 4

Puede usar std::count_if ^† para contar y devolver si es uno.

Por ejemplo:

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

^† Actualización : Sin embargo, std::count_if cuenta con un elemento completo en el contenedor, lo que no es tan bueno como el algoritmo dado en la pregunta. El mejor enfoque utilizando las colecciones de algoritmos estándar se ha mencionado en la respuesta de @formerlyknownas_463035818 .

Dicho esto, el enfoque de OP también es bueno como el mejor enfoque estándar mencionado anteriormente, donde ocurre un cortocircuito cuando el count llega a 2 . Si alguien está interesado en una función de plantilla de algoritmo no estándar para el enfoque de OP, aquí está.

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

Ahora que se puede generalizar , al proporcionar un parámetro más, el número de N elemento (s) tiene / tiene que encontrarse en el contenedor.

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