logo
Contato | Sobre...        
rebarba rebarba

Rodrigo Strauss :: Blog

follow us in feedly

Tutorial de STL, parte 5: algoritmos

Hoje vamos falar sobre os algoritmos da STL (algorithms), que nada mais são que as funções template que efetuam algum tipo de operação sobre os itens de um container. Isso mesmo, os tais algorithms nada mais são do que funções. O que os faz especiais é a programação genérica, que permite que um mesmo algoritmo possa ser aplicado a diversos tipos de containers, sem distinção. Dessa forma, ao invés de cada container prover métodos com o algoritmos necessários, todos eles ficam separados e pode ser aplicados a maioria deles.

Para tornar os algoritmos genéricos, precisamos primeiro abstrair os containers. Existem duas formas básicas para resolver isso em C++: usando interfaces e funções virtuais, ou fazendo o chamado "polimorfismo em tempo de compilação", usando templates e concepts, onde ter os métodos das classes com os mesmos nomes já é suficiente. A primeira opção não se enquadra no conceito C++ de "generic programming", e apesar da segunda se enquadrar, não é possível usá-la com os containers STL. Por exemplo, apesar da maioria dos containers oferecer o método push_back, alguns não o fazem (como o std::map).

Como dito na parte 4 dessa série sobre STL, o conceito de iterators existe para abstrair as particularidades do armazenamento de cada container. Dessa forma, a ação de acessar e percorrer os itens de um container se torna igual para a maioria dos containers. Apesar de não ser possível abstrair todas as características de um container, a abstração da forma de acesso aos itens já é suficiente para que os algortimos funcionem. Além disso, isso torna tudo mais flexível, já que permite que você aplique um algoritmos somente em determinados itens de um container.

Como um trecho de código vale muito mais do que uma lei estúpida feita por alguém mal informado, vamos lá:

#include <vector>
#include <algorithm>
#include <assert.h>
 
//
// esse é o nosso algoritmo que soma um número a
// cada item de um container. Note que durante a execução
// o tipo T será o tipo do iterator, e não do container
//
template<typename T >
void soma_num(T begin, T end, int num)
{
  for(T i = begin; i != end ; ++i)
    *i += num;
}
 
 
int main()
{
  std::vector<int> v;
  std::vector<int> l;
  int arr[10];

  for(int a = 0 ; a < 10 ; ++a)
  {
    v.push_back(a);
    l.push_back(a);
    arr[a] = a;
  }
 
  //
  // vamos somar 10 aos número de todos os containers
  //
  soma_num(v.begin(), v.end(), 10);
  soma_num(l.begin(), l.end(), 10);
 
  //
  // somando 10 somente aos 5 primeiros itens do array
  //
  soma_num(arr, arr + 5, 10);
}

Para maioria dos algoritmos, o acesso a todos os itens do container já á mais do que suficiente. A STL contém diversos algoritmos em várias áreas, entre eles:

  • procurar itens dentro de um container (find, find_if)
  • contar itens que atendem a uma determinada condição (count, count_if)
  • cópia de itens entre containers e trechos de containers (copy, copy_n)
  • o famoso map reduce (transform, accumulate)
  • troca de itens (reverse, swap, rotate)
  • operações com std::set, conjuntos (set_union, set_intersection, set_difference)
  • e muitos outros (min, max, random_shuffle, fill generate)

A lista e documentação dos algoritmos pode ser encontrada na página da SGI ou na MSDN. Segue um exemplo de uso dos algoritmos:

int main()
{
  std::vector<int> v1, v2;
 
  for(int a = 0 ; a < 100 ; ++a)
    v1.push_back(a);
 
  //
  // cria um iterator especial que insere um novo
  // items em um container toda vez que houver 
  // uma atribuição. 
  //
  std::back_insert_iterator<std::vector<int>> bi(v2);
 
  //
  // isso faria um v2.push_back(10);
  // *bi = 10;  
  //
 
  //
  // vamos copiar os itens de um container para outro.
  // o algoritmo copy tem duas linhas: é um loop for
  // que copia todos os itens em sequência. Veja os fontes
  // em stl_algo.h
  //
  std::copy(v1.begin(), v1.end(), bi);
 
  //
  // embaralha o v1
  //
  std::random_shuffle(v1.begin(), v1.end());
 
  //
  // ordena v1
  //
  std::sort(v1.begin(), v1.end());
 
  for(int x = 0 ; x < 100 ; ++x)
  {
    assert(v1[x] == v2[x]);
  }
}

Em 13/02/2007 16:26, por Rodrigo Strauss


  
 
 
Comentários
Algo a dizer?
Nome:


Site:


E-mail:


Escreva o número vinte e seis:


 Não mostre meu e-mail no site, não serve pra nada mesmo...

Comentário





Os comentários devem ser sobre assuntos relativos ao post, eu provavelmente apagarei comentários totalmente offtopic. Se quiser me enviar uma mensagem, use o formulário de contato. E não esqueça: isso é um site pessoal e eu me reservo o direito de apagar qualquer comentário ofensivo ou inapropriado.
rebarba rebarba
  ::::