Introdução ao STL em C++ (Standard template Library)

Dezembro 2016



Introdução


Uma das dificuldades da linguagem C consiste em implementar contêineres (vetores, listas relacionadas, conjuntos ordenados) genéricos, fáceis de usar e eficazes. Para ser genérico é, muitas vezes, forçado a usar ponteiros genéricos (void*) e operadores de cast. Além disso, quando esses recipientes são aninhados uns dentro dos outros (por exemplo, um conjunto de vetores), o código torna-se rapidamente difícil de usar.

Para atender a essa necessidade, a STL (Standard Template Library) implementa um grande número de classes template descrevendo contêineres genéricos para C++. Além disso, a STL fornece algoritmos para manipular facilmente estes contêineres (para inicializá-los, encontrar valores, etc...). A STL também introduz o conceito de iterador para percorrer facilmente um contêiner se liberando completamente da forma como ele foi implementado.

Os conceitos desenvolvidos na STL são agora estendidos pela biblioteca boost, que permite a manipulação de estruturas do gráfico genérico.

O objetivo desta introdução não é fazer um inventário exaustivo das possibilidades oferecidas pela STL, mas dar exemplos comuns de uso. Podemos encontrar uma visão mais detalhada das classes da STL aqui:
http://www.sgi.com/tech/stl/table_of_contents.html

A seguir, apresentamos as classes da STL com parâmetros templates "simples". Na prática, temos que ver as classes da STL como legos (ou duplos para não ficar com ciúmes) que podem ser encaixados uns nos outros. Assim, podemos manipular um vetor de conjunto da lista do inteiro (std::vector<std::set<std::list<int> > >).

Principais classes da STL


É particularmente importante escolher uma classe fornecida pela STL coerente com suas necessidades. Algumas estruturas são realmente, mais ou menos eficazes, para acessar uma memória ou, em termos de realocação de memória, quando elas se tornam importantes. O objetivo desta parte é apresentar as vantagens e as desvantagens de cada uma delas.

Em primeiro lugar, é necessário ter algumas noções de complexidade. Seja n o tamanho de um contêiner. Um algoritmo é chamado linear (O(n)) se o seu tempo de cálculo é proporcional a n. Da mesma forma, um algoritmo pode ser instantâneo (O(1)), logarítmica O(log(n)), polinomial O(n^k), exponencial O(e(n)), etc...

Para resumir, veja a lista das complexidades em ordem crescente de proporções de tempo de cálculo (quanto mais descemos, mais violento):
  • O(1)
  • O(log(n))
  • O(n)
  • O(n^k)
  • O(e(n))


Aqui vamos nos concentrar principalmente sobre a complexidade de acesso (pesquisa) a um dado armazenado em um conteiner e sobre a complexidade para inserir um dado.

std::pair<T1,T2>


Um "pair" é uma estrutura com dois elementos, possivelmente, de tipos diferentes. Alguns algoritmos da STL (find, por exemplo) retornam pares (posição do elemento encontrado e um booleano indicando se ele foi encontrado).


Complexidade: inserção e acesso em O(1)
#include <pair> // na prática este include é subentendido pois feito implicitamente quando utilizamos <vector>, <set> ... 
#include <iostream> 
#include <string> 

int main(){ 
  std::pair<int,std::string> p = std::make_pair(5,"pouet"); 
  std::cout << p.first << ' ' << p.second << std::endl; 
  return 0; 
} 

std::list<T,...>


A classe "list" fornece uma estrutur genérica de listas ligadas que podem, eventualmente, conter duplicatas.

Complexidade
  • Inserção (no início ou no fim da lista) : O(1)
  • Pesquisa: O(n) em geral, O(1) para o primeiro e o ultimo elo


Este exemplo mostra como inserir os valores 4,5,4,1 em uma lista e como exibir seu conteúdo:
#include <list> 
#include <iostream> 

int main(){ 
  std::list<int> ma_liste; 
  minha_lista.push_back(4); 
  minha_lista.push_back(5); 
  minha_lista.push_back(4); 
  minha_lista.push_back(1); 
  std::list<int>::const_iterator 
    lit (minha_lista.begin()), 
    lend(minha_lista.end()); 
  for(;lit!=lend;++lit) std::cout << *lit << ' '; 
  std::cout << std::endl;  
  return 0; 
} 

std::vector<T,...>


A classe vetor é parecida com a tabela do C. Todos os elementos do vetor são adjacentes na memória, o que permite o acesso imediato a qualquer elemento. A vantagem do vetor comparado à tabela do C é a sua capacidade de realocar, automaticamente, em caso de necessidade, durante um push_back, por exemplo. No entanto, como uma tabela clássica, uma casa só pode ser acessada por um operador [ ] se ela foi alocada com antecedência (se não, um erro de segmentação é acionado).


Complexidade:
  • Acesso O(1)
  • Inserção: O(n) no começo do vetor (pop_back), O(1) no final do vetor (push_back). Nos dois casos as realocações podem ocorrer.


Não devemos esquecer que a realocação de memória é cara em termos de tempo de cálculo. Portanto, se o tamanho de um vetor é conhecido de antemão, você deve criá-lo desse tamanho, tanto quanto for possível.

Exemplo :
#include <vector> 
#include <iostream> 

int main(){ 
  std::vector<int> meu_vetor; 
  meu_vetor.push_back(4); 
  meu_vetor.push_back(2); 
  meu_vetor.push_back(5); 
  // para percorrer um vetor (mesma const) podemos utilizar os iterators ou os indexes 
  for(std::size_t i=0;i<meu_vetor.size();++i) std::cout << meu_vetor[i] << ' ' 
  std::cout << std::endl; 

  std::vector<int> meu_vetor(5,69); // criado o vetor 69,69,69,69,69 
  v[0] = 5; 
  v[1] = 3; 
  v[2] = 7; 
  v[3] = 4; 
  v[4] = 8; 
  return 0; 
} 

std::set<T,...>


A classe set é para descrever um conjunto ordenado, e sem duplicatas, de elementos. Em principio, devemos passar esta ordem em parâmetro template (mais precisamente, de um functor). Por padrão, o functor std::less (baseado no operador <) é utilizado, o que significa ter um conjunto de elementos ordenados do menor ao maior. Concretamente, basta implementar o operador < de uma classe ou de uma estrutura do tipo T para poder definir um std::set <T>. Além disso, o tipo T deve ter um construtor vazio T().


Complexidade:
  • O(log(n)) para a pesquisa e a inserção. Na verdade, a estrutura std::set se aproveita da ordem para o T para construir uma estrutura de árvore vermelha e preta, permitindo uma busca logarítmica de um elemento.

#include <set> 
#include <iostream> 

int main(){ 
  std::set<int> s; // equivale à std::set<int,std::less<int> > 
  s.insert(2); // s contém 2 
  s.insert(5); // s contém 2 5 
  s.insert(2); // a duplicata não foi inserida 
  s.insert(1); // s contém 1 2 5 
  std::set<int>::const_iterator 
    sit (s.begin()), 
    send(s.end()); 
  for(;sit!=send;++sit) std::cout << *sit << ' '; 
  std::cout << std::endl; 
  return 0; 
}


Atenção: O fato de remover ou adicionar um elemento em uma std:: set torna os seus iteradores inválidos. Não é preciso modificar um std::set em um "loop for" baseado nos seus iteradores.

std::map<K,T,...>


Um "map" (mapa) associa uma chave (identificador) a um dado (tabela associativa).

O mapa utiliza, pelo menos, dois parâmetros templates:
  • O tipo da chave K
  • O tipo de dado T


Como o std::set, o tipo K deve ser ordnado (esta ordem pode ser dada como 3° parâmetro template, std::less <K> por padrão). O tipo T só exige um construtor vazio.

Complexidade:
  • O (log (n)) para a pesquisa e a inserção. Na verdade, a estrutura std::map aproveita a ordem sobre o T para construir uma estrutura de árvore vermelha e preta, permitindo a busca logarítmica de um elemento.


Atenção: o fato de remover ou adicionar um elemento em uma std::map torna os seus iteradores inválidos. Não é preciso modificar um std::map em um "loop for" baseado em seus iteradores

Atenção: o fato de acessar uma chave através do operador [ ] insere esta chave (com o dado T()) no mapa. Assim, o operador [ ] não é adequado para verificar se uma chave está presente no mapa, é preciso utilizar o método "find". Além disso, ele não garante a constância do mapa (por causa das inserções potenciais) e, portanto, não pode ser usado em const std::map .

Exemplo:
#include <map> 
#include <string> 
#include <iostream> 

int main(){ 
  std::map<std::string,unsigned> map_mês_idx; 
  map_mês_idx["janeiro"] = 1; 
  map_mê_idx["fevereiro"] = 2; 
  //... 
  std::map<std::string,unsigned>::const_iterator 
    mit (map_mês_idx.begin()), 
    mend(map_mêis_idx.end()); 
  for(;mit!=mend;++mit) std::cout << mit->first << '\t' << mit->second << std::endl; 
  return 0; 
}

Iterators


Vimos na seção anterior que os iterators permitem percorrer facilmente uma estrutura da STL de um extremo a outro. Um iterator lembra um pouco a noção de ponteiro, mas não é um endereço. Agora, vamos ver quatro iterators clássicos da STL.

Eles são definidos para todas as classes da STL mencionados acima (exceto, é claro, a std::pair)

Iterator e const_iterator


Um iterador (e um const_iterator) permite percorrer um contêiner do começo ao fim. Um const_iterator, ao contrário de um iterador, dá acesso apenas em leitura para o elemento "apontado". Assim, um percurso com const_iterator mantém a constância do contêiner. É por isso que um contêiner "const" pode ser percorrido por const_iterators mas não por iterators.

Em geral, quando você pode escolher entre iterators ou const_iterators, é sempre melhor escolher os const_iterators pois eles devolvem a seção de código à qual eles servem mais genérico (aplicável aos contêineres const ou não const).
  • begin(): retorna um iterador que aponta para o primeiro elemento
  • end(): retorna um iterador que aponta logo "depois" do último elemento
  • ++ : para incrementar o iterador passando-o para o próximo elemento.


Exemplo:
#include <list> 
#include <iostream> 

const std::list<int> criar_lista(){ 
  std::list<int> l; 
  l.push_back(3); 
  l.push_back(4); 
  return l; 
} 

int main(){ 
  const std::list<int> minha_lista(criar_lista()); 
  // não compila pois é const 
  // std::list<int>::iterator 
  //  lit1 (l.begin()), 
  //  lend(l.end()); 
  //for(;lit1!=lend1;++lit1) std::cout << *lit1 << ' '; 
  //std::cout << std::endl; 
  std::list<int>::const_iterator 
    lit2 (l.begin()), 
    lend2(l.end()); 
  for(;lit2!=lend2;++lit2) std::cout << *lit2 << ' '; 
  std::cout << std::endl;  
  return 0; 
}

reverse_iterator e const_reverse_iterator


O princípio dos reverse_iterator e const_reverse_iterator é semelhante aos iterators e const_iterator exceto que o percurso é feito na direção oposta.


Utilizamos então:
  • rbegin(): retorna um iterador que aponta para o último elemento
  • rend(): retorna um iterador que aponta para logo "antes" do primeiro elemento
  • ++ : permite incrementar o reverse_iterator passando-o para o elemento seguinte. Exemplo:

#include <set> 
#include <iostream> 

int main(){ 
  std::set<unsigned> s; 
  s.insert(1); // s = {1} 
  s.insert(4); // s = {1, 4} 
  s.insert(3); // s = {1, 3, 4} 
  std::set<unsigned>::const_reverse_iterator 
    sit (s.rbegin()), 
    send(s.rend()); 
  for(;sit!=send;++sit) std::cout << *sit << std::endl; 
  return 0; 
}

... affiche :
4 
3 
1

Os algoritmos


Se o conceito de iterator foi dominado, basta consultar
http://www.sgi.com/tech/stl/table_of_contents.html

Vamos memorizar alguns métodos bem práticos como o "find" (para os std::set e os std::map) para buscar um elemento, std:fill para (re)inicializar um std::vector, algoritmos de ordenação, de pesquisa, de mínimo ou de máximo.



Tradução feita por Lucia Maurity y Nouira

Veja também

Artigo original publicado por . Tradução feita por pintuda. Última modificação: 19 de outubro de 2011 às 18:28 por pintuda.
Este documento, intitulado 'Introdução ao STL em C++ (Standard template Library)', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.