inicio GeNeura cursos

Algoritmos alteradores de secuencia


Los algoritmos alteradores de secuencias comparte con los no alteradores su modo de funcionar. Todos ellos realizan operaciones a lo largo de rangos de elementos definidos a traves de un par de iteradores.

El nombre de estos algoritmos proviene de su capacidad de alterar los valores de los elementos apuntados mediante iteradores o de alterar el orden de las secuencias.

Para algunos de estos algoritmos existen variaciones que copian en vez de sobreescribir (variaciones con *_copy()) o que realizan la operacion solo si se cumple cierta condicion (variaciones con *_if()).

Lista de algoritmos alteradores de secuencia:


copy()

Función

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result)

template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, 
                                     BidirectionalIterator1 last, 
                                     BidirectionalIterator2 result)

Descripción

copy() copia el rango de entrada [first1, last) en el rango apuntado por result. copy_backward() hace lo mismo pero empieza copiando por el final. En ambos casos hemos de tener cuidado para no solapar los rangos origen y destino.


swap()

Función

template <class T>
inline void swap(T& a, T& b) 
{
  T tmp = a;
  a = b;
  b = tmp;
}

template <class ForwardIterator1, class ForwardIterator2, class T>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
  T tmp = *a;
  *a = *b;
  *b = tmp;
}

template <class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  __iter_swap(a, b, value_type(a));
}

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2) {
  for ( ; first1 != last1; ++first1, ++first2)
    iter_swap(first1, first2);
  return first2;
}

Descripción

swap() intercambia dos objetos. iter_swap() intercambia el valor de dos objetos a traves de iteradores. swap_ranges() intercambia dos secuencias de elementos.


transform()

Función

template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryOperation op) 
{
  for ( ; first != last; ++first, ++result)
    *result = op(*first);
  return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, OutputIterator result,
                         BinaryOperation binary_op) 
{
  for ( ; first1 != last1; ++first1, ++first2, ++result)
    *result = binary_op(*first1, *first2);
  return result;
}

Descripción

transform() aplica un funcion a una o dos secuencias de elementos y almacena el valor en un tercera. La primera version funciona aplicando un operador unario, la segunda, uno binario.


replace()

Función

template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
             const T& new_value) 
{
  for ( ; first != last; ++first)
    if (*first == old_value) *first = new_value;
}

template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
                const T& new_value) 
{
  for ( ; first != last; ++first)
    if (pred(*first)) *first = new_value;
}

template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
                            OutputIterator result, const T& old_value,
                            const T& new_value) 
{
  for ( ; first != last; ++first, ++result)
    *result = *first == old_value ? new_value : *first;
  return result;
}

template <class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
                               OutputIterator result, Predicate pred,
                               const T& new_value) 
{
  for ( ; first != last; ++first, ++result)
    *result = pred(*first) ? new_value : *first;
  return result;
}

Descripción

replace() recorre una secuencia de elementos y reemplaza los que coincidan con old_value por new_value. En la variante con if(), el reemplazo tendra lugar si la funcion devuelve true. En la version de copia, lo que se hace es realizar el reemplazo sobre una nueva copia de la secuencia que se va almacenando sobre otro iterador, result. La ultima version funciona igual que la version de copia, pero ejecutando el reemplazo solo cuando asi lo indique la funcion de comparacion.


fill()

Función

template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) 
{
  for ( ; first != last; ++first)
    *first = value;
}

template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) 
{
  for ( ; n > 0; --n, ++first)
    *first = value;
  return first;
}

Descripción

fill() cambia un rango de valores a un valor predefinido apuntado por dos iteradores. fill_n() hace lo mismo pero utilizando un iterador al primer elemento y un contador.


generate()

Función

template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen) 
{
  for ( ; first != last; ++first)
    *first = gen();
}

template <class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen) 
{
  for ( ; n > 0; --n, ++first)
    *first = gen();
  return first;
}

Descripción

generate() recorre una secuencia asignando un nuevo valor a cada elemento. En este caso, el nuevo valor es proporcionado por la funcion que se pasa como ultimo parametro, gen. Existe otra version que hace lo mismo pero recorre la secuencia utilizando un iterador y un contador, generate_n().


remove()

Función

template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
                           OutputIterator result, const T& value) 
{
  for ( ; first != last; ++first)
    if (*first != value) {
      *result = *first;
      ++result;
    }
  return result;
}

template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
                              OutputIterator result, Predicate pred) 
{
  for ( ; first != last; ++first)
    if (!pred(*first)) {
      *result = *first;
      ++result;
    }
  return result;
}

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                       const T& value) 
{
  first = find(first, last, value);
  ForwardIterator next = first;
  return first == last ? first : remove_copy(++next, last, first, value);
}

template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                          Predicate pred) 
{
  first = find_if(first, last, pred);
  ForwardIterator next = first;
  return first == last ? first : remove_copy_if(++next, last, first, pred);
}

Descripción

Estas cuatro funciones borran elementos de un contenedor. Lo hacen utilizando dos pares de criterios:

Ademas, estas funciones utilizan dos formas de almacenar los resultados>


unique()

Función

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last) 
{
  first = adjacent_find(first, last);
  return unique_copy(first, last, first);
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                       BinaryPredicate binary_pred) 
{
  first = adjacent_find(first, last, binary_pred);
  return unique_copy(first, last, first, binary_pred);
}

template <class InputIterator, class OutputIterator>
inline OutputIterator unique_copy(InputIterator first, InputIterator last,
                                  OutputIterator result)

template <class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator unique_copy(InputIterator first, InputIterator last,
                                  OutputIterator result,
                                  BinaryPredicate binary_pred)

Descripción

Este algoritmo se aplica a secuencias ordenadas, las cuales recorre seleccionando los elementos que son unicos. unique() almacena su seleccion sobre el propio rango de entrada, con lo cual, igual que en el caso de remove, nos quedaran elementos que deberemos borrar al final del contenedor unique_copy() realiza la seleccion sobre un nuevo contenedor. Ambas versiones devuelven un iterador tras las ultima posicion valida.


reverse()

Función

template <class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last)

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
                            BidirectionalIterator last,
                            OutputIterator result) 
{
  while (first != last) 
  {
    --last;
    *result = *last;
    ++result;
  }
  return result;
}

Descripción

reverse() invierte el orden de los elementos dentro de una secuencia.reverse_copy() no modifica la secuencia de entrada y copia la secuencia invertida en un nuevo contenedor.


rotate()

Función

template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle,
                   ForwardIterator last)

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
                           ForwardIterator last, OutputIterator result) {
  return copy(first, middle, copy(middle, last, result));
}

Descripción

rotate() realiza una rotacion circular de los elementos de una secuencia. El objeto apuntado por middle se convertira en el primer elemento de la nueva secuencia. rotate() realiza la rotacion sobre una nueva secuencia.


random_shuffle()

Función

template <class RandomAccessIterator>
inline void random_shuffle(RandomAccessIterator first,
                           RandomAccessIterator last)

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rand) 
{
  if (first == last) return;
  for (RandomAccessIterator i = first + 1; i != last; ++i)
    iter_swap(i, first + rand((i - first) + 1));
}

Descripción

random_shuffle() realiza un barajado de los elementos de una secuencia. El efecto global es desordenar aleatoriamente los elementos de la secuencia. En la segunda version podemos proporcionar nosotros el generador de numeros aletorios. Este aceptara un unico parametro entero n y debera devolver valores aleatorios entre 0 y n-1.


partition()

Función

template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
                                BidirectionalIterator last, Predicate pred)

template <class ForwardIterator, class Predicate>
inline ForwardIterator stable_partition(ForwardIterator first,
                                        ForwardIterator last, 
                                        Predicate pred)

Descripción

partition() y stable_partition() dividen una sequencia en dos grupos: el primero, de elementos que cumplen la funcion pred y el segundo, de elementos que no la cumplen. stable_partition() ademas garantiza que los elementos no perderan su orden relativo entre si despues de efectuar la particion.