Rodrigo Strauss :: Blog
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
Estou curioso demais pra esperar: se "PessoasPorID.find(400) != PessoasPorID.end()" não é a forma mais eficiente, qual seria? =)