Teoria

E aí galera, aqui é o Juan do Responde Aí, e hoje vamos continuar nossos estudos de C++ aprendendo sobre containers e iterators

A Standard Template Library – STL.

Os templates, uma forma especial de preparar funções e classes para receber tipos de dados variados.

Como você pode imaginar, eles podem ser muito úteis na hora de criar bibliotecas versáteis e cheias de funções legais.

E foi exatamente isso que os criadores do C++ fizeram, eles criaram a Standard Template LibrarySTL, um conjunto gigantesco de templates de classes que contém estruturas de dados muito usados e funções importantes, organizada em forma de algoritmos, funções, containers e iterators.

A STL facilita muito a vida dos programadores, mas devido ao tamanho massivo dessa biblioteca, hoje vamos dar atenção a dois pontos em especial: o container v e c t o r e os iterators.

Os containers

Pra começar, vou te dizer o que é um container (alguns professores traduzem para contêiner): é uma estrutura que consegue armazenar dados de maneira organizada, como uma lista, pilha, conjunto, dicionário, etc.

É como se o container fosse um objeto que consegue armazenar outros objetos.

Você pode pensar nos containers como uma evolução das arrays. Os containers são programados através de templates de classes, e por isso já vêm de fábrica com vários métodos legais que os tornam muito mais poderosos do que as arrays que já estamos acostumados.

O container v e c t o r

O container v e c t o r é um template de classe que existe na STL, e que se comportam como as arrays comuns, guardando dados na memória de forma sequencial. Show de bola. Mas e daí?

Qual é a vantagem de usar esse tal de v e c t o r ao invés das arrays que já estamos acostumados?

A principal vantagem é que os v e c t o r s são alocados dinamicamente por padrão! Isso quer dizer que a gente pode mudar o tamanho de um vector a vontade, sem ter que nos preocupar em fazer alocação dinâmica de memória. A desvantagem é que os v e c t o s consomem mais memória do que as arrays comuns, porém é o preço a ser pago pela facilidade de uso.

Então, sem mais enrolação, vamos lá usar um vector:

Para adicionar um v e c t o r ao nosso programa precisamos incluir o cabeçalho < v e c t o r > :

# i n c l u d e < v e c t o r >

Agora, você deve pensar no v e c t o r como um template de classe (afinal ele é isso mesmo), então quando você for criar um vetor, basta você instanciar um objeto da classe v e c t o r inserindo o tipo entre as chaves:

v e c t o r < t i p o > n o m e V e c t o r ;

E assim você criou um v e c t o r completamente vazio. Para saber o tamanho da array que a gente criou nós podemos usar o método s i z e ( ) :

Para inserir um elemento em um v e c t o r devemos usar o método p u s h _ b a c k ( v a l o r ) , que adiciona um elemento no fim do vector:

Para visualizar os elementos de um vetor podemos usar os colchetes [   ] , que nem nas arrays, para qualquer elemento contido no vetor. Mas também podemos usar o método f r o n t (   ) para ver o primeiro elemento e o método b a c k (   ) para ver o último elemento.

A qualquer momento podemos remover um elemento do nosso v e c t o r . Usando o método p o p _ b a c k (   ) a gente remove o último elemento do v e c t o r

E se for necessário, podemos apagar todos os elementos do v e c t o r com o método c l e a r (   )

Viu só que legal?! Os v e c t o r são que nem as arrays com esteroides!

Outras formas de instanciar um v e c t o r

Na parte anterior a gente criou um v e c t o r e preencheu ele usando o p u s h _ b a c k várias vezes seguidas, e você deve ter notado que essa é uma maneira um pouco cansativa de fazer. Imagina, preencher 15 valores dessa forma...

Mas por sorte, a classe v e c t o r possui um construtor sobrecarregado, e existem várias maneiras de preencher um v e c t o r no momento em que ele é instanciado:

Na linha 02 criamos um v e c t o r   totalmente vazio, como fizemos anteriormente. Na linha 03 criamos um v e c t o r com 5 espaços na memória, mas não definimos os valores que estão armazenados. Essa não é uma boa prática, pois os valores inicialmente contidos em v e c 1 vão variar de acordo com cada compilador. Na linha 04 criamos um v e c t o r com 7 espaços na memória, e todos eles preenchidos com o caractere ' A ' . E na linha 05 criamos um v e c t o r que é uma cópia exata de outro v e c t o r .

Mas e se você quiser um v e c t o r preenchido com diversos valores? A melhor forma é transformar uma array em um v e c t o r . A gente faz isso inserindo os ponteiros para a primeira e para a última posição da array no construtor do v e c t o r :

v e c t o r < t i p o > v e c (   a r r a y , a r r a y + T a m A r r a y   )

É importante que a array e o v e c t o r sejam do mesmo tipo!

Outra vantagem é que criar uma v e c t o r partindo de uma array é que você não é obrigado a passar a array completa. Se quiser, pode passar um ponteiro para uma posição inicial qualquer, e um ponteiro para uma posição final que desejar.

Os iterators

Os iterators (alguns professores traduzem para iteradores) são parecidos com os ponteiros, mas o iterator ajuda a gente a trabalhar com os containers. A vantagem de usar iterators é que eles funcionam com a mesma lógica em todos os containers, o que nem sempre é verdade no caso de usar ponteiros.

Antes de mais nada, para usar um iterator precisamos ter um container em funcionamento, então vamos criar um v e c t o r a partir de uma array:

Os iterators e containers são intimamente relacionados, e por isso devem ser do mesmo tipo então pra declarar um iterator que aponta para um v e c t o r fazemos:

v e c t o r < t i p o > ∷ i t e r a t o r   n o m e I t e r a t o r

Todo container possui ao menos dois métodos especiais que trabalham com os iteradores, o b e g i n (   ) que faz o iterator apontar pro início do container, e o e n d (   ) para apontar pro espaço vazio após final do container.

Isso é especialmente útil quando vamos usar um loop em cima dos v e c t o r . Por exemplo:

Na linha 12 criamos um laço que o iterador começa a contar na posição inicial do v e c t o r e avança de um em um até a última posição final. Na linha 13 a gente imprime o valor apontado pelo iterator: da mesma forma que um ponteiro, usamos o operador * para acessar o conteúdo.

Importante: lembre-se que o valor apontado por e n d (   ) é o “vazio” após o final do container, então quando imprimimos esses valores, encontramos lixo de memória.

Um segundo tipo importante são os r e v e r s e _ i t e r a t o r que nos ajudam andar ao contrário sobre um container. Temos o r b e g i n (   ) aponta para o último elemento, e o r e n d (   ) que aponta para o espaço vazio antes do primeiro elemento:

No caso dos iteradores reversos, o r b e g i n (   ) não faz parte do intervalo. E se você imprimir o valor apontado por ele, vai encontrar lixo de memória:

Erros comuns

  • Tentar inicializar um v e c t o r usando   como se fosse uma array:

  • Tentar ampliar o tamanho do vector usando colchetes ao invés do p u s h _ b a c k (   ) :

  • Usar o operador de decremento - - ao invés de + + com os iteradores reversos também é um erro comum. Mesmo que a gente esteja andando “de trás pra frente” com os iteradores reversos, nós devemos usar o operador + +

Dicas:

Na hora de preencher um vetor usando array precisamos saber o tamanho dessa array. Mas pode haver situações em que o tamanho da array é variável ou então é desconhecido.

Pra contornar isso, podemos usar uma expressão para calcular o tamanho da array automaticamente:

s i z e o f ( n o m e A r r a y ) / s i z e o f ( t i p o )

E vamos poder gerar um vector da seguinte forma:

Resumo do básico sobre o container v e c t o r e seus iterators básicos

E por hoje é isso pessoal. Vamos ver agora uns exercícios de fixação.

Outras formas de instanciar um v e c t o r

Os iterators

Erros comuns

Dicas:

Resumo do básico sobre o container v e c t o r e seus iterators básicos