inicio GeNeura cursos

Algoritmos no alteradores de secuencia


Los algoritmos no alteradors de secuencia realizan una operación sobre un rango definido por un par de iteradores. El algoritmo empieza su trabajo en la dirección a la que apunta el primer iterador y continua hasta alcanzar una condición de parada o el elemento final.

Se llaman así porque no modifican el contenedor que contienen los elementos a los que se les aplica el algoritmo.

El código de la mayoría de ellos es extremadamente simple. Se puede encontrar en los ficheros algo.h y algobase.h (o en stl_algo.h y stl_algobase.h en las nuevas implementaciones). Para utilizarlos podemos usar #include <algoritm>.

De algunos de estos algoritmos existen versiones especiales que utilizan un objeto función para determinar cual es la condición de parada. Estos algoritmos utilizan el sufijo _if.

Tipos de algoritmos no alteradores de secuncia:


for_each()

Función

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, 
                  Function f) 
{
  for ( ; first != last; ++first)
    f(*first);

  return f;
}

Descripción

for_each() aplica una función a cada uno de los objetos de una secuencia. La secuencia de entrada normalmente es un contenedor o un array, pero también puede ser cualquier otro tipo de iterador de entrada.


find()

Función

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, 
                   const T& value) 
{
  while (first != last && *first != value) 
    ++first;

  return first;
}

template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
                      Predicate pred) {
  while (first != last && !pred(*first)) 
    ++first;

  return first;
}

Descripción

find() busca a través de un rango de entrada un objeto que cumpla la condición de terminación. En la primera versión del algoritmo simplemente se busca un elemento igual al recibido como argumento. En la segunda se finaliza cuando la función de búsqueda devuelve true para un cierto argumento.


find_end()

Función

template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1 
find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
         ForwardIterator2 first2, ForwardIterator2 last2)

template <class ForwardIterator1, class ForwardIterator2, 
          class BinaryPredicate>
inline ForwardIterator1 
find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
         ForwardIterator2 first2, ForwardIterator2 last2,
         BinaryPredicate comp)

Descripción

find_end() busca [first2, last2) como una subsecuencia dentro de [first1, last1). En caso de encontrarla devuelve un iterador que apunta al final de secuencia dentro del rango de entrada [first1, last1). En caso de no encontrarla devuelve last1.


find_first_of()

Función

template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
                            ForwardIterator first2, ForwardIterator last2)
{
  for ( ; first1 != last1; ++first1) 
    for (ForwardIterator iter = first2; iter != last2; ++iter)
      if (*first1 == *iter)
        return first1;
  return last1;
}

template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
                            ForwardIterator first2, ForwardIterator last2,
                            BinaryPredicate comp)
{
  for ( ; first1 != last1; ++first1) 
    for (ForwardIterator iter = first2; iter != last2; ++iter)
      if (comp(*first1, *iter))
        return first1;
  return last1;
}

Descripción

find_first_of() busca en el rango de entrada [first1, last1) la secuencia [first2, last2). Si la encuentra devuelve un iterador al primer elemento de la secuencia comun dentro de [first1, last1), en otro caso devuelve last1. La igualdad se comprueba mediante el operator==() o bien mediante la funcion comp.


adjacent_find()

Función

template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) 
{
  if (first == last) return last;
  ForwardIterator next = first;
  while(++next != last) 
  {
    if (*first == *next) return first;
    first = next;
  }
  return last;
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                              BinaryPredicate binary_pred) 
{
  if (first == last) return last;
  ForwardIterator next = first;
  while(++next != last) 
  {
    if (binary_pred(*first, *next)) return first;
    first = next;
  }
  return last;
}

Descripción

adjacent_find() localiza pares de objetos iguales dentro de un contenedor. Si se encuentra un par de elementos iguales, devuelve un iterador que apunta al primero de ellos, sino devuelve last


count()

Función

template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value,
           Size& n) 
{
  for ( ; first != last; ++first)
    if (*first == value)
      ++n;
}

template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred,
              Size& n) 
{
  for ( ; first != last; ++first)
    if (pred(*first))
      ++n;
}

Descripción

count() cuenta el numero de veces que aparece un valor dentro de una secuencia (o el numero de veces que los elementos de la secuencia hacen cierta una cierta funcion). Ninguna de las dos versiones inicializa el contador con los cual deberemos inicializarlo nosotros si deseamos empezar desde 0.


mismatch()

Función

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
					      InputIterator1 last1,
					      InputIterator2 first2) 
{
  while (first1 != last1 && *first1 == *first2) 
  {
    ++first1;
    ++first2;
  }
  return pair<InputIterator1, InputIterator2>(first1, first2);
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
					      InputIterator1 last1,
					      InputIterator2 first2,
					      BinaryPredicate binary_pred) 
{
  while (first1 != last1 && binary_pred(*first1, *first2)) 
  {
    ++first1;
    ++first2;
  }
  return pair<InputIterator1, InputIterator2>(first1, first2);
}

Descripción

mismatch() recorre dos secuencias comprobando la igualdad de cada par de elementos. Si se encuentra un par diferente se devuelve como resultado, sino devuelve un par formado por los los dos ultimos elementos.


equal()

Función

template <class InputIterator1, class InputIterator2>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
		  InputIterator2 first2) {
  for ( ; first1 != last1; ++first1, ++first2)
    if (*first1 != *first2)
      return false;
  return true;
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
		  InputIterator2 first2, BinaryPredicate binary_pred) {
  for ( ; first1 != last1; ++first1, ++first2)
    if (!binary_pred(*first1, *first2))
      return false;
  return true;

Descripción

equal() devuelve true si las dos secuencias son iguales y false en otro caso.


search()

Función

template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                               ForwardIterator2 first2, ForwardIterator2 last2)

Descripción

search() localiza la primera aparicion de la segunda secuencia dentro de la primera. El iterador que devuelve la funcion apunta a la localizacion de esta dentro de la primera secuncia. En caso de no encontrarla devuelve last1.