logo
Contato | Sobre...        
rebarba rebarba

Rodrigo Strauss :: Blog

follow us in feedly

Tutorial de STL, parte 3: mais containers

Já vimos os conceitos de containers na parte 2, além de brincar um pouco com o funcionamento do std::vector. Vamos aproveitar que estamos familiarizados com os conceitos, para conhecer alguns dos outros containers disponibilizados pela STL.

Como vimos, o vector tem muitas similaridades com o array C, os objetos são mantidos na memória de forma contígua, o que permite os elementos sejam acessados rapidamente de forma aleatória - para encontrar um item só é preciso fazer uma soma. Apesar dessa grande vantagem, o vector tem uma grande desvantagem: quando um item é inserido no meio do container, é necessário mover todos os itens posteriores para haver espaço para o novo elemento. Isso pode ser demorado se o container tem uma grande quantidade de itens. Esse problema ocorre também quando precisamos inserir um item no início, o que é comum.

Quando precisamos guardar dados de uma forma onde a inserção e remoção de itens seja mais eficiente, geralmente usamos uma lista ligada. Como um item tem um ponteiro para o próximo (e o anterior no caso de uma lista duplamente ligada), para inserir um item no meio só precisamos trocar o conteúdo de alguns ponteiros. Na STL a lista ligada é implementada na forma do container std::list. Vamos a alguns exemplos:

#include <list>
#include <string>
#include <iostream>
 
struct Pessoa
{
  std::string _nome;
  unsigned int _idade;

  Pessoa(std::string nome, unsigned int idade):
    _nome(nome), _idade(idade)
  {
  }
};
 
int main()
{
  std::list<Pessoa> pessoas;
 
  //
  // podemos inserir um itens no final..
  //
  pessoas.push_back(Pessoa("José João", 26));
 
  //
  // ... e no início, da mesma forma que com o vetor
  //
  pessoas.push_front(Pessoa("João José", 28));

  std::cout << "Primeira pessoa: "<< pessoas.front()._nome << std::endl;
  std::cout << "Segunda pessoa: " << pessoas.back()._nome << std::endl;

 
  //
  // mas isso não funciona, ao contário do vector
  //
  //pessoas[0];
 
  return 0;
}

Outro container bastante usado é o std::map, que cria um mapa entre chave e valor:

#include <map>
#include <string>
#include <iostream>
#include <sstream>

 
struct Pessoa
{
  std::string _nome;
  unsigned int _idade;
 
  Pessoa(): _idade(0) {}
 
  Pessoa(std::string nome, unsigned int idade):
    _nome(nome), _idade(idade)
  {
  }
};

int main()
{
  std::map<unsigned int /* ID */, Pessoa> PessoasPorID;
 
  //
  // vamos "cadastrar" 100 pessoas
  //
  for(int a  = 0 ; a < 100 ; ++a)
  {
    std::stringstream nome;

    nome << "Pessoa " << a;

    //
    // caso não exista item para essa chave, ela é criada
    //
    PessoasPorID[a] = Pessoa(nome.str(), a);
  }

  Pessoa p;
  //
  // vamos pegar a pessoa com ID 50
  //
  p = PessoasPorID[50];
  std::cout << p._nome << " tem " << p._idade << " anos." << std::endl;

  //
  // Se você não tem certeza que o item existe,
  // não pode usar o operador []. 
  // Diferentemente do std::vector, ELE CRIARA O ITEM
  // 200 AUTOMATICAMENTE.
  // Maravilhas do C++: na dúvida, veja o fonte do operator[]
  // do tipo std::map.
  //
  p = PessoasPorID[200];
  std::cout << p._nome << " tem " << p._idade << " anos." << std::endl;

  //
  // se não tem certeza da existência, faça assim:
  // (eu sei, não é a forma mais eficiente, mas
  //  ainda não vimos iterators nessa série, lembra?)
  //
  if(PessoasPorID.find(400) != PessoasPorID.end())
    p = PessoasPorID[400];
 
  return 0;

 
}

Além desses containers notáveis que já vimos - todos baseados em templates - existem outros containers mais específicos, e outros chamados de adaptadores. O adaptadores criam containers com funcionamentos específicos usando o armazenamento de outros containers. Entre eles estão o std::queue (fila), e o std::stack (stack), que encapsulam outros containers mas disponibilizam somente as operações que fazem sentido para o tipo usado - push e pop para pilha, por exemplo.

Mais informações
MSDN: Standard C++ Library Reference
SGI: Index: The Standard Template Library
Wikipedia: C++ Standard Library


Em 10/11/2006 16:53, por Rodrigo Strauss


  
 
 
Comentários
Wanderley Caloni | website | e-mail | em 10/11/2006 | #
Estou curioso demais pra esperar: se "PessoasPorID.find(400) != PessoasPorID.end()" não é a forma mais eficiente, qual seria? =)
Rodrigo Strauss | website | em 10/11/2006 | #
Não é a busca que é ineficiente, é a operação de ver se existe e depois atribuir. O eficiente seria:

std::map<int,Pessoa>::iterator i = PessoasPorID.find(400);
if(i != PessoasPorID.end())
p = *i;

Já que isso não faz a busca duas vezes (uma no find, e uma no operator[]). Mas se eu colocasse esse iterator eu pedir a sequência :-)
Fábio | em 10/11/2006 | #
O que você usa p/ deixar a formatação do código colorida em seus posts?
Rodrigo Strauss | website | em 10/11/2006 | #
Eu uso o http://www.rafb.net/paste/

Ele define uns estilos CSS (olhe o fonte desse post) que eu defino igual no meu CSS.
Fernando Tamberlini Alves | em 13/11/2006 | #
Por que você usou o termo Lista Ligada, e não Lista Encadeada ? Tem alguma diferença?
Rodrigo Strauss | website | em 13/11/2006 | #
Até onde eu sei, é a mesma coisa. Mas lista ligada parece mais com o inglês linked list, talvez seja por isso minha opção por esse termo.
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
  ::::