logo
Contato | Sobre...        
rebarba rebarba

Rodrigo Strauss :: Blog

follow us in feedly

Tutorial de STL, parte 4: iterators

Apesar de existir muito mais coisas para falar sobre containers, vamos ver hoje o que são e para que servem os iterators. Mesmo porque, muitas das diferenças entre os containers só podem ser demonstradas usando iterators.

Os iterators são um abstração da forma de acesso aos itens de um container. Eles foram criados para que os itens dos mais diversos containers possam ser acessados de uma mesma forma. Isso constitui o pilar da programação genérica, já que o código que manipula os itens de um container fica independente dos detalhes da implementação do container.

Já vimos o std::vector, e sabemos que ele armazena os itens de forma sequencial. Da mesma forma, sabemos que o std::list armazena os itens em forma de uma lista ligada. Sendo assim, o método de acesso para itens dos dois containers é diferente. No caso do std::vector, para pegar o próximo item devemos pegar o ponteiro do item atual e somar um. No caso do list, devemos pegar o ponteiro para o próximo item diretamente na struct que controla o item, e derreferenciá-lo. No caso de uma red-black tree, como é comumente implementado o std::map, o acesso fica ainda mais complicado.

O iterators são análogos aos ponteiros. São variáveis que quando derreferenciadas, pegam o conteúdo de uma varíavel. Como um trecho de código com comentários vale bem mais do que um trecho de código sem comentários, vamos ao que interessa:

#include <iostream>
#include <vector>

#include <list>
#include <map>
#include <string>
#include <sstream>
 
 

int main()
{
   static const unsigned int n = 10;
   int array[n];
   std::vector<int> v;
   std::list<int> l;
   std::map<int, std::string> m;

   //
   // preenchedo o array
   //
   for(int a = 0 ; a < n ; ++a)
   {
      //
      // vamos colocar itens não sequenciais, usando o 
      // dobro da nossa variável de controle
      //
      int x = a * 2;

      //
      // vou usar um stringbuffer para converter de int
      // para string. Nada de itoa, isso é C++ :-)
      //
      std::stringstream buffer;
      buffer << a;
 
      array[a] = x;
      v.push_back(x);
      l.push_back(x);
      m[x] = buffer.str();
   }
 
   //
   // pronto, agora temos todos os containers (sim, um array C
   // também é um container) preenchidos. Vamos à nossa primeira
   // tentativa (inútil) de acessar os itens da mesma forma
   //
   for(int a = 0 ; a < n ; ++a)
   {
      int x;
 
      x = array[a];
      x = v[a];

      // isso não funciona, o list não suporta acesso por índice
      // x = l[a];

      // também não funciona, essa sintaxe procura pela chave do map
      // e não pelo índice no map. Além disso, o retorno dessa expressão
      // é do tipo string, veja a declaração do map
      // x = m[a];
 
   }
 
   //
   // agora vou acessar os itens do array via ponteiro.
   // incrementamos o ponteiro até o fim do array
   //
   std::stringstream buffer;
   buffer << "array: ";
 
   for(int* i = array ; i != array + n ; ++i)
   {
      buffer << *i << ", ";
   }

 
   std::cout << buffer.str() << std::endl;
 
   //
   // veja como o acesso ao vector funcionará quase da mesma forma,
   // só muda a inicialização.
   //
   buffer.str(""); buffer.clear(); 
   buffer << "std::vector: ";
   for(std::vector<int>::iterator i = v.begin() ; i != v.end() ; ++i)
   {
      buffer << *i << ", ";
   }
   std::cout << buffer.str() << std::endl;

 
   //
   // Mais uma vez. O acesso ao std::list funciona da mesma forma que
   // para o array e para o std::vector
   //
   buffer.str(""); buffer.clear();
   buffer << "std::list: ";
   for(std::list<int>::iterator i = l.begin() ; i != l.end() ; ++i)
   {
      buffer << *i << ", ";
   }
   std::cout << buffer.str() << std::endl;

 
   //
   // O acesso ao map é um pouco diferente porque temos chave e
   // valor, mas o conceito continua o mesmo
   //
   buffer.str(""); buffer.clear();
   buffer << "std::map: ";
   for(std::map<int, std::string>::iterator i = m.begin() ; i != m.end() ; ++i)
   {
      buffer << "(" << i->first << "," << i->second << ") ";
   }
   std::cout << buffer.str() << std::endl;

 
   return 0;
}

O que deve ser notado no exemplo acima é que, independente do container, a forma de acesso é a mesma. O método begin() retorna um iterator para o primeiro item do container (por exemplo, a expressão *v.begin() retorna o conteúdo do primeiro item). O método end() retorna um item APÓS o último, e não pode ser derreferenciado, pois ele deve ser usado para testar se o iterator já passou do final. Mais código:

#include <vector>
#include <assert.h>

int main()
{

   std::vector<int> v;
   // 
   // Esse é o tipo do iterator para um vetor de int. 
   // Todos os containers da STL seguem esse padrão, o tipo do iterator
   // é definido por um typedef dentro do próprio container
   //
   std::vector<int>::iterator i;

   //
   // container vazio, begin() é igual a end()
   //
   assert(v.begin() == v.end());

   v.push_back(10);
   v.push_back(20);

   i = v.begin();
   assert(*i == v[0]);

   assert(v.begin() != v.end());

   // o primeiro item é igual a 10
   assert(v[0] == 10);

   // o begin() aponta para o item de índice 0
   assert(v[0] == *v.begin());

   // posso somar iterator como somo ponteiros.
   // begin() + 1 aponta para o segundo item.
   assert(*(v.begin() + 1) == 20);

   // temos somente dois itens. O item depois do último é o end()
   assert(v.begin() + 2 == v.end());

   return 0;
}

Mais informações no tópico sobre iterators na página da SGI.


Em 22/11/2006 15:17, por Rodrigo Strauss


  
 
 
Comentários
Thiago | website | em 23/11/2006 | #
Olá,

Engraçado, ontem mesmo (dia 22 de novembro) tivemos uma palestra na empresa que eu trabalho sobre iterators, ele é um padrão de projeto muito interessante e que usamos no nosso dia a dia aqui, só não usamos (ou usávamos) com o STL. :-)

Parabens pelos artigos, eles são bastante interessantes.
Diego Rocha | website | e-mail | em 05/08/2007 | #
Só para quem é curioso e esta pensando " é possivel ter um mapa de vetores ??", a resposta é sim, aqui vai um exemplo bem basico de uso de mapas de vetores,

#include <vector>
#include <string>
#include <iostream>
#include <map>

int main()
{
// usar > > com espaço para o confundir não confundir com o operator >>
typedef std::map<std::string,std::vector<std::string> > MyMapVectors;
MyMapVectors MyMap;
MyMapVectors::iterator IterMap;
//aqui o iterator para o vector
std::vector<std::string>::iterator IterVector;
MyMap["teste1"].push_back("teste1::teste1"); //populamos os vetores
MyMap["teste1"].push_back("teste1::teste2");
MyMap["teste1"].push_back("teste1::teste3");
MyMap["teste2"].push_back("teste2::teste1");
MyMap["teste2"].push_back("teste2::teste2");
MyMap["teste2"].push_back("teste2::teste3");

IterMap = MyMap.begin();
while( IterMap != MyMap.end() )
{
std::string valor = (*IterMap).first; //aqui pegamos o Key do Map
IterVector = MyMap[valor].begin();
while( IterVector != MyMap[valor].end() )
{
std::cout << *IterVector<<std::endl;
IterVector++;
}
IterMap++;
}
return 0;
}

Bom é isso espero que ajude alguem, :)
Filipe | e-mail | em 04/04/2008 | #
Tenho uma dúvida,
Eu tenho uma
Class A
{
public:
void ChangeName (std::string newName);
....
..

private:
std::string mName;
....
...
}

e faço um std::map <std::string, A> namesHashMap;
std::map <std::string, A>::iterator it;

namesHashMap.insert(pair.... A.GetName(),&A);
agora kero mudar nome de um qualquer
it = namesHashMap.begin();

it->second.ChangeName("NovoNome");

Mas agora quero actualizar o it.first;

mas Não quero ter de fazer o erase(old) e depois insert do novo.


Como posso fazer isso?

it->second.MudaNome("NovoNome");
Rodrigo Strauss | website | e-mail | em 06/04/2008 | #
Filipe, só com erase mesmo. Outra opção é definir o operador < comparando o atributo nome de duas instâncias e usar um std::set ao invés do sdt::map. Ah, e o std::map não é hash map, é uma red black tree.
Daniel | e-mail | em 06/06/2008 | #
Rodrigo,

existe algum motivo para vc nao usar "using"? vi códigos seus no seminário sempre com "boost::" e agora todos com "std::"..... é para manter o controle sobre os namespaces? vc usa muitos namespaces em programas que faz?
Rodrigo Strauss | website | em 21/06/2008 | #
Daniel, depende muito. Eu gosto de usar namespaces quando não torna o nome muito grande e deixa o código mais legível.
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
  ::::