Aula 7 - Estruturas de Dados II: Explorando o C++

0 Flares Facebook 0 0 Flares ×

Aula de Rogério Júnior

 

Foi dito no início do curso que usaríamos o C++ como linguagem de programação, mas até agora só usamos uma função própria dele: o sort. É recomendado que você implemente suas próprias estruturas de dados, como foi ensinado com pilhas e filas, mas nem todas são tão fáceis de implementar. Hoje mostraremos algumas estruturas bem mais complicadas de fazer, como a árvore AVL, mas que possuem funções muito simples e eficientes de serem usadas, com implementação já pronta em C++, que no caso da AVL é o set.

Conjunto

Agora imagine o seguinte problema: você começa com um conjunto vazio e serão feitas n operações. Cada operação pode ser adicionar, retirar, ou perguntar se algum elemento está no conjunto, que é formado por inteiros de 1 até 10^9. A entrada terá na primeira linha o valor de n. Cada uma das próximas n linhas terá dois inteiros t e x, que irão descrever uma operação. O primeiro número (t) irá indicar o tipo de operação a ser realizada. Se t=1, devemos adicionar x ao conjunto. Se t=2, devemos retirar x do conjunto. Adicionar um número que já pertence ao conjunto, ou retirar um que não pertence a ele equivale a não fazer nada. Se t=3, então devemos imprimir uma única linha, que terá o caractere 'S', caso x pertença ao conjunto, ou 'N', caso contrário. Segue um exemplo de entrada:

6

1 3

1 4

3 3

2 4

3 4

3 6

Essa entrada descreve as seguintes 6 operações: primeiro adiciono o elemento 3 ao conjunto, depois adiciono o 4. Na terceira linha, pergunto se 3 está no conjunto, e ele está, logo devo imprimir uma linha com o caractere 'S'. Na quarta linha, retiro o elemento 4, deixando o conjunto apenas com o 3. Na quinta, pergunto se o 4 está no conjunto, e, como ele não está, devo imprimir o caractere 'N' em uma linha. Na última operação da entrada, pergunto se o 6 está no conjunto. Ele nunca este e apenas imprimo o caractere 'N'. Logo, a saída esperada é:

S

N

N

Cada linha correspondendo, ordenadamente, a cada uma das perguntas feitas na entrada.

Talvez você lembre que nas primeiras aulas usamos um vetor para implementar um conjunto. Se o elemento i estava no conjunto, então vetor[i] era 1. Se ele não estava, era 0. Para isso, entretanto, é necessário que usemos um vetor do tamanho do maior número possível da entrada, para acessar seu estado (se está ou não no conjunto). Vemos, infelizmente, que o maior número possível nesse caso é 10^9, e um vetor desse tamanho é muito grande para ser declarado, o compilador não deixará que tal programa seja feito. A primeira coisa que pensamos talvez fosse criar um vetor que vai guardando os elementos do conjunto e um inteiro com seu tamanho. Assim, toda vez que adicionamos um elemento, vamos adicionar esse número ao fim do vetor, para retirá-lo, basta percorrer o vetor e colocar um 0 em todas as posições em que o número aparece. Para checar se ele está no vetor, basta percorrê-lo, procurando alguma posição com o número. Segue um código que implementa as funções insert, que insere um número no conjunto, erase, que apaga um número do conjunto e count, que retorna 1 se o número estiver no conjunto e 0 caso contrário, e as usa para resolver o problema. Lembre-se que apenas implemento as funções por motivos didáticos e é mais rápido simplesmente executar seus comandos no código. Lembre que em C++ apenas 0 significa false, qualquer outro valor é visto como condição verdadeira, no if por exemplo.

Apesar de imprimir a resposta certa, esse código é extremamente ineficiente. Observe a complexidade das funções: duas delas percorrem completamente o vetor, que pode até ter tamanho n, o que gera complexidade O(n). Como vamos executar n operações, a complexidade é O(n²) (aproximação bem por cima). Assim, resolveríamos o problema para n próximo de 10^3, mas, e se n fosse 10^5? Para isso, vamos usar o set, uma estrutura já implementada no C++ que simula um conjunto, sem repetição de elementos. Ele está na biblioteca set, do C++. Para declararmos um conjunto com nome conj, de variáveis do tipo tipo1, usamos o comando "set<tipo1> conj;". Logo, para o problema, vamos criar um conjunto de mesmo nome, mas que guardará variáveis inteiras, com o coando "set<int> conj;". Um set tem como membros as funções inserterase e count já implementadas. Ou seja, assim como usamos o nome da estrutura seguido de ponto seguido do nome do membro de uma struct para acessá-lo, usaremos, por exemplo, os comandos "conj.insert(x);" para inserir o elemento x em conj, "conj.erase(x)" para apagar x e "conj.count(x);" para verificar se x pertence ao conjunto. O diferencial do set é que cada uma dessas funções tem complexidade O(\log n), onde n é o tamanho do conjunto. Segue a solução do problema usando set.

Antes de passarmos para o próximo tópico, vamos falar bem rapidamente de ponteiros, visto que até agora já usamos algumas vezes esse nome. Um ponteiro é um tipo de variável como outra qualquer, mas seu valor guarda o endereço de outra variável na memória do computador. Já dissemos, por exemplo, que quando chamamos o nome de uma string, ela retorna um ponteiro para o seu primeiro caractere, ou seja, ela retorna seu endereço. Já vimos também que o sort recebe ponteiros como parâmetros. Enfim, ponteiro é simplesmente o endereço, a localização da variável no meio da memória do computador. Para declararmos um ponteiro, escrevemos o tipo de elemento que ele aponta, seguido de um asterisco, seguido do nome do ponteiro. Para declarar, por exemplo, o ponteiro ptr, que deve guardar o endereço de um int, usamos o comando "int * ptr;". Para vermos o endereço de uma variável já declarada, usamos o operador "&" antes de seu nome. Se quisermos, por exemplo, declarar um int a e fazer com que ptr aponte para ele, usamos o comando "ptr = &a;". Para acessarmos o elemento que um ponteiro está apontando, usamos o operador "*" antes de seu nome. Se quisermos, por exemplo, declarar um outro int b e fazê-lo receber o valor que ptr aponta, usaríamos o comando "int b= *ptr;". Para imprimir esse valor salvo em ptr, usaríamos novamente o "*" no comando "printf("%d", *ptr);".

Todos os elementos de um vetor são salvos lado a lado, por isso quando adicionamos 1 a um ponteiro para algum de seus elementos, estamos apontando para o próximo. Cada tipo de variável consome seu próprio espaço: um int consome 4 bytes, um char 1 byte, o que faz com que, na verdade, um vetor de int posicione seus elementos a 4 bytes de distância um do outro, mas o operador "+" de ponteiros já sabe o tipo que ele aponta e conserta isso, fazendo com que ele sempre avance quantas posições eu queira. O nome de um vetor, inclusive uma string, sempre retorna um ponteiro para a primeira posição. De modo geral, um ponteiro para qualquer variável retorna um ponteiro para seu primeiro byte. Repito ainda que um ponteiro é um tipo de variável como outra qualquer, e pode ser usada, por exemplo como parâmetro e retorno de funções, como será feito a seguir.

Suponha agora que você terá n operações  apenas de inserção e exclusão de um conjunto e, ao final da entrada, seu programa deva imprimir todos os números do conjunto, ordenadamente, um por linha. Como fazemos para acessar todos os elementos de um set? Primeiro, o set consegue fazer todas aquelas operações em tempo tão rápido porque ele guarda seu elementos de maneira "ordenada". Entretanto, a ordem não é como a de um vetor, onde todos os elementos estão um do lado do outro em um espaço de memória, em ordem crescente, mas de uma maneira bem mais complexa. Por isso, o set tem um iterator (iterador). Ele é um tipo de objeto que recebe um ponteiro e "sabe" percorrer os elementos de um set na ordem crescente. Assim, se temos um iterator de nome it e executarmos o comando "it++;", ele agora apontará para o próximo elemento do set, em ordem crescente. Para percorrer todos o set, basta usarmos um for e um iterador que começará apontando para o primeiro elemento do conjunto e, enquanto ele não apontar para o fim do set, iremos para o próximo elemento. Vale ressaltar que para declarar um iterator de nome it, por exemplo, precisamos antes especificar que tipo de iterador ele será, especificando a estrutura de dados structure que ele deve percorrer e o tipo de objeto tipo1 que estará salvo naquela estrutura, com o comando "structure<tipo1>::iterator it;". No caso, precisamos de um que saiba percorrer um set de inteiros, logo escreveremos o comando "set<int>::iterator it;", para criar este tipo de iterador. Além disso, precisamos saber que a função begin(), do set, retorna um ponteiro para o primeiro elemento do conjunto, e a função end() retorna um ponteiro para seu final. Sabendo isso, o programa que resolve o problema enunciado usando um set para guardar os elementos do conjunto seria assim:

Além das 5 funções que já vimos, o set tem muitas outras, dentre elas as mais importantes são:

size() -  retorna um inteiro: a quantidade de elementos no set em O(1)

clear() - apaga todos os elementos do set em O(size)

empty() - retorna true se o set estiver vazio e false caso contrário, em O(1)

find(x) - retorna um ponteiro para um elemento igual a x no set em O(log(size)). Se não houver tal elemento, retorna um ponteiro para o fim do set.

lower_bound(x) - retorna, em O(log(size)), um ponteiro para o primeiro elemento do set, em ordem crescente, que não é menor que x.

upper_bound(x) - retorna, em O(log(size)), um ponteiro para o primeiro elemento do set, em ordem crescente, que é maior que x.

As três últimas funções serão mais utilizadas em algoritmos futuros, e você só precisa se concentrar, agora, nas três primeiras. Para ver uma lista completa dos membros de um set, clique aqui e veja a página dele na referência do Cplusplus.

Sempre é bom lembrar, também, que o multiset está na biblioteca set e faz tudo o que um conjunto normal faz, sendo declarado do mesmo jeito, mas aceita repetição de elementos. Além disso, vale notar que, em problemas que pprecisam de mais de um conjunto, podemos criar um vetor de set assim como criarmos um vetor de qualquer outra estrutura, e acessar os set's em suas posições de maneira análoga a qualquer outro vetor. Para criarmos um vetor de set<int> de 10 posições, com o nome conj, usaríamos o comando "set<int> conj[10];", e para acessar o i-ésimo set, usaríamos "conj[i]". Ou seja, para inserirmos o número 4 no set da posição 6 do vetor conj, usaríamos o comando "conj[6].insert(4);".

Vetor Dinâmico

Outra estrutura já implementada é o vector. Ele está na biblioteca vector e representa um vetor dinâmico, ou seja, não precisamos especificar quantos elementos ele irá guardar. Para declará-lo, usamos um comando semelhante ao do set. Para declararmos um vector de nome vetor que irá guardar elementos do tipo int, por exemplo, uso o comando "vector<int> vetor;". Ele pode ter suas posições acessadas como um vetor normal, com os operadores "[]", mas apenas se a posição desejada já tiver sido inserida. Ele tem uma função importante chamada push_back(x), que insere um elemento no fim do vetor em O(1). Assim, só podemos acessar a posição n do vetor se já tivermos inserido n+1 elementos (pois ele começa da posição 0). Algumas outras funções interessantes do vector são:

pop_back() - apaga o último elemento do vetor

size() - retorna, em O(1), o tamanho do vetor

back() - retorna, em O(1), o último elemento do vetor

front() - retorna, em O(1), o primeiro elemento do vetor

clear() - apaga, em O(size), todos os elementos do vetor

begin() - retorna, em O(1), um ponteiro para o primeiro elemento do vetor

end() - retorna,  em O(1), um ponteiro para o fim do vetor

As duas últimas funções são bem úteis como parâmetros para o sort, por exemplo. Segue, para melhor compreensão, o código de um programa que recebe n inteiros e os imprime ordenadamente, usando um vector e um sort:

Lembre-se que o vetor normal (estático) é sempre mais rápido que um vetor dinâmico, e tem bem menos risco de acessar uma posição inválida (pois no começo declaramos seu tamanho). A vantagem do vector está puramente na organização do código e na implementação de suas funções, mas não fique viciado em usá-lo. Se não for extremamente complicado, use um vetor estático.

Par

Na aula passada foi ensinada a implementação de struct para criarmos objetos que guardam várias variáveis. Uma estrutura semelhante a essa, já implementada no C++ é o pair. Você não precisa declarar bibliotecas para usá-lo (apenas a namespace std) e ele contêm dois membros: o first e o second. Os elementos do pair podem ser de qualquer tipo. Para declarar, por exemplo, um pair de nome par em que o primeiro elemento é um int e o segundo é uma double, usamos o comando: "pair<int,double> par;". Podemos associar valores aos seus membros, podemos usar o operador "=". Se quiséssemos que o primeiro elemento de par receba o valor "3" e o segundo o valor "2.5", podemos usar os comandos "par.first=3; par.second=2.5;". Além disso, poderíamos usar a função make_pair(valor1, valor2), também da algorithm, que recebe dois parâmetros (valor1 valor2) e retorna um pair composto por esses dois elementos. Assim, poderíamos fazer par guardar os valores 3 e 2.5 em seus membros com o comando "par=make_pair(3, 2.5);".

Uma das grandes utilidades do pair é podermos fazer um outro pair ser um de seus membros. Imagine, por exemplo, que preciso guardar pontos em um plano cartesiano. Para isso, vou usar o primeiro membro de um pair chamado ponto para guardar o número de identificação do ponto. Além disso, quero usar seu segundo membro para guardar suas coordenadas. Para isso, usarei um segundo pair de double, cujo primeiro membro será a coordenada x e o segundo será a coordenada y. Para declararmos tal objeto, usaríamos o comando "pair< int, pair<double, double> > ponto;". Assim, para acessarmos o número de identificação do ponto, usamos "ponto.first". Para acessar o pair que guarda suas coordenadas, usamos "ponto.second", logo, acessamos a coordenada x com "(ponto.second).first" e a coordenada y com "(ponto.second).second".  Note que podemos declarar ponto com o primeiro membro "3" e o segundo membro com os números "2.5" e "1.7" com o comando "ponto=make_pair(3, make_pair(2.5, 1.7));". É importante lembrar que ao usarmos qualquer objeto que use os operadores "<>" na sua declaração, devemos usar espaços para garantir que não escrevamos "<<" ou ">>", visto que esse são operadores próprios da linguagem que executam outras funções. Note, na declaração de ponto, que usei "pair< int, pair<double, double> > ponto;", com espaço entre os ">" do final, ao invés de ""pair<int, pair<double, double>> ponto;", que daria errado pelo uso do operador ">>" no final. Dessa maneira, podemos ter quantos elementos quisermos em um pair, mas a partir de certo número, é muito confuso e cansativo escrevermos "first.second.second.first...", sendo recomendado o uso de uma struct.

Outra grande utilidade do pair é que ele já vem com os operadores de comparação declarados ("<", ">", "<=", ">=" e "=="). Dessa maneira, ele compara dando prioridade ao primeiro membro e usando o segundo apenas como critério de desempate, com os operadores de comparação próprios do tipo. Imagine, por exemplo, os pares (2, 3) e (1, 7). Temos que  (2, 3) > (1, 7), pois o primeiro elemento do primeiro par (2) é maior que o primeiro elemento do segundo par (1). Se os pares fossem (2, 3) e (2, 7), teríamos que (2, 7) > (2, 3), pois o primeiro elemento dos dois pares são iguais e, no critério de desempate, o segundo elemento do segundo par (7) é maior que o segundo elemento do primeiro (3). Dois pares são iguais ("==" retorna true) somente se todos os elementos de um par forem iguais aos seus correspondentes no outro par. Desse modo, podemos ordenar um vetor de pair usando apenas a função sort sem declararmos uma função de comparação, sabendo que a ordenação irá priorizar o primeiro membro de cada par, usando o segundo como critério de desempate.

Para melhor entendimento, imagine o seguinte problema de ordenação: há n alunos que devem ser ordenados pelo seu desempenho acadêmico. Cada um deles tem seu número de identificação i, a sua nota e o seu número de faltas. Os alunos devem ser ordenados em ordem decrescente de nota. No caso de empate, deve vir primeiro o aluno com menor número de faltas, e persistindo o empate, o aluno com menor número de identificação deve vir na frente. A primeira linha da entrada contêm um único inteiro o valor de n. As n linhas seguintes contêm a descrição de cada um dos alunos. Dessa maneira, a i-ésima linha contêm dois inteiros e f, a nota e o número de faltas do aluno i, respectivamente. A saída deve conter um única linha, com as n identificações dos alunos, ordenadas.

Cada aluno consiste de três informações: nota, faltas e identificação, sendo essa a prioridade no momento de ordenar. Logo, vamos criar um par de um par de inteiros e um inteiro e chamá-lo de aluno, para exemplo ("pair< pair< int, int >, int > aluno;"). Para mantermos a prioridade na ordenação, o primeiro elemento do primeiro par ("aluno.first.first") deve ser a nota, e o segundo elemento do primeiro par ("aluno.first.second") devem ser as faltas. O segundo elemento ("aluno.second") deve ser a identificação do aluno. Entretanto, a função sort ordena de maneira crescente, mas queremos que o aluno de maior nota venha primeiro. Essa situação ocorre muitas vezes na vida de um programador, mas basta salvarmos a nota como um número negativo. Se as notas de dois alunos forem 5 e 3, o sort iria deixá-los na ordem 3, 5. Se salvássemos as notas como números negativos, deixando-as -3, -5, o sort as deixaria na ordem -5, -3, que é a desejada. Basta que na hora de imprimirmos os números, usemos seus opostos, ou seja, imprimiríamos 5 e 3, nessa ordem.

Desse modo, basta criarmos um vector de pair de nome aluno. Essa estrutura será usada na solução do problema. Quando lermos a descrição do aluno i, com sua respectiva nota e número de faltas (e f), iremos adicionar o par ((-s, f), i) ao vetor. Feito isso basta que o ordenemos com uma chamada do sort, e depois imprimamos, em ordem, sos identificadores de seus elementos, que serão seus membros second. Segue o código para melhor entendimento:

String de C++

Já foi citado nesse curso que string refere-se a uma certa estrutura de C++, que está na biblioteca string, que tenta imitar o vetor de char. Ela é como um vetor dinâmico de char. A partir de agora, no curso, string sempre irá se referir a essa estrutura de C++ e o vetor de char pode ser referido como cstring. O diferencial dessa estrutura em relação à cstring é um conjunto de funções e operadores que facilitam muito nossa vida, com um certo custo de tempo. Primeiro, para declará-la, não preciso informar seu tamanho: para criarmos uma string de nome frase basta o comando "string frase;". A comparação entre duas strings é feita com os operadores "<", ">", "<=", ">=" e "==". Se temos a string frase1 e string frase2, então frase1<frase2 indica que, em ordem alfabética frase1 vem antes de frase2, e todos os outros operadores são definidos de maneira análoga. Podemos também somar duas strings com o operador "+", de modo a concatená-las, ou seja, se somarmos as duas strings "earth" e "quake", com o comando "earth"+"quake", teremos a string "earthquake". Ela também reconhece o operador "+=" de maneira semelhante, ou seja, se declaramos "string frase="earth";" e executarmos o comando "frase+="quake";", então frase estará guardando agora a string "earthquake". O melhor é que podemos somar uma cstring ou um char a uma string também, usando os mesmos operadores, ou até atribuir-lhe o valor de uma cstring ou char com o operador "=". Assim como na cstring, podemos acessar a posição n com os operadores "[]" (se tal posição existir).

Infelizmente, nada é perfeito, e não podemos escanear uma string usando a função scanf, ou imprimir usando a printf. Temos então que usar os objetos cin cout, da biblioteca iostream, do C++. Elas são bem mais simples de usar que as funções que estamos acostumados, mas isso tem o custo de serem bem mais lentos, só devendo serem utilizadas nesse caso (ler uma string), pois podem gerar Time Limit Exceeded em casos de entradas muito grandes. Para ler objetos com cin, basta chamarmos ela e, para cada objeto x que vamos ler, escrever o comando " >> x ", e terminar a função com ";". Se quisermos ler, por exemplo, dois inteiros e salvá-los, respectivamente nas variáveis int a int b, usamos o comando "cin >> a >> b;". Note que não temos que determinar os tipos dos objetos que serão lidos, a função faz isso sozinha, o que a faz gastar mais tempo. Para imprimir, usamos a cout, de maneira análoga, mas agora com o operador "<<". Para imprimirmos, por exemplo, a frase "o valor eh ", seguida de um inteiro salvo em int x, e de uma quebra de linha, usamos o comando "cout << "o valor eh " << x << '\n';". Uma informação adicional é que, no cout, existem os objetos "ends" e "endl", que podem representar os caracteres ' ' (espaço em branco) e '\n' (quebra de linha), respectivamente. Vale lembrar que quando o cin lê uma string, ele lê a entrada até o primeiro espaço ou quebra de linha. Para lermos uma linha completa da entrada (até a quebra de linha) e salvarmos em uma string, usamos função getline, da biblioteca string. Ela tem dois parâmetros, sendo que o primeiro deve ser o objeto "cin", e o segundo a string em que iremos salvar a leitura. Para lermos, por exemplo, uma linha inteira da entrada e salvarmos em uma string de nome frase, usamos o comando "getline(cin, frase);". Segue um exemplo de código que lê uma linha da entrada com getline e depois a imprime com cout, seguida de uma quebra de linha:

Se quisermos usar os truques da scanf para escolhermos o que queremos ler, devemos ler uma cstring e depois salvá-la em uma string. Para lermos uma linha toda por exemplo, e a salvarmos na string frase, primeiro declaramos a string frase, depois um vetor de char auxiliar, "char aux[30];", por exemplo. Feito isso, lemos a linha toda e a salvamos em aux, com o comando visto na primeira aula "scanf(" %[^\n]", aux);" e fazemos frase receber o valor de aux com o comando "frase=aux;". Podemos sempre ler uma cstring e depois atribuir seu valor a uma string, mas é mais simples usar cin.

Além disso, a string tem várias funções interessantes, que podem ser vistas na referência do Cplusplus, mas, dentre elas, as mais importantes são:

size() - retorna o tamanho da string em O(1).

substr(int pos, int tam) - retorna, em O(tam), a substring formada pelos tam caracteres partir da posição pos. Se omitirmos o segundo parâmetro, a função retorna a subtring formada por todos os caracteres da string a partir da posição pos.

Segue de exemplo um código que lê uma string, imprime seu tamanho e depois a imprime sem as duas primeiras letras:

Tal programa, ao receber como entrada o exemplo:

NOIC

deveria gerar a saída:

4 IC

Mapa

Imagine o seguinte problema: dados n pagamentos que Daniboy realizou de algumas contas (ele pode ter dividido algumas contas em mais de um pagamento), imprima quanto foi pago em cada tipo de conta. A primeira linha terá o valor de n e as próximas n linhas terão, cada uma, uma string s, a conta que Daniboy estava pagando, e a double v, o valor que foi pago na conta. A conta a ser paga pode ser repetida em algumas linhas, visto que ele podia não pagar tudo de uma vez, e o valor final que foi pago nessa conta será a soma de todos os pagamentos referentes a ela. O programa deve gerar uma linha para cada tipo de conta, contendo o nome dela e o valor total pago, com uma precisão de duas casas após a vírgula, ordenando-as em ordem alfabética. Exemplo de entrada:

5

imposto 8570.62

cartao 54.50

agua 23.50

cartao 132.20

energia 172.80

Daniboy fez 5 pagamentos em 4 tipos diferentes de contas.Ele dividiu a conta de "cartao" em dois pagamentos, um de R$ 132,20 e outro de R$ 54,50, o que totaliza um pagamento de R$ 186,70. A saída deve ter 4 linhas, uma para cada tipo de conta, em ordem alfabética, contendo o seu nome e o valor total nela pago, separados por um espaço em branco. Exemplo:

agua 23.50

cartao 186.70

energia 172.80

imposto 8570.62

Se as contas fossem identificadas por inteiros, não por nomes, bastaríamos que fizéssemos um vetor de double que guardava quanto foi pago em cada conta e depois imprimíssemos os seus índices seguidos dos valores neles salvos. Para acessar um elemento salvo em um vetor normal, usamos o inteiro que identifica a qual posição estamos nos referindo, ou seja, a chave para uma posição no vetor é um inteiro. Felizmente, existe o map. Ele é uma estrutura de dados já implementada no C++ que simula um vetor em que as posições são identificadas por uma chave que pode ser qualquer tipo de variável, não somente por inteiros. O único custo é que acessar uma posição dele custa O(log n) (onde n é o tamanho do vetor), ao invés do O(1) de um vetor normal. Ele está na biblioteca map, do C++, e é declarado de maneira semelhante às outras estruturas vistas hoje. Se quisermos declarar um map de nome mapa, que simulará um vetor em que as chaves de suas posições são objetos do tipo tipo1 e cada uma delas guardará um um objeto do tipo tipo2, usamos o comando "map<tipo1, tipo2> mapa;". No caso, queremos criar um map de nome mapa que simule um vetor em que as posições são strings, e, como não podemos usar um vetor como tipo, teremos que usar a string ao invés da cstring. Além disso, queremos que cada posição do vetor guarde uma double (o valor total pago naquela conta), logo usaremos o comando "map<string, double> mapa;". Para criarmos ou acessarmos a posição frase (onde frase é uma string) do vetor mapa, usamos "mapa[frase]". Vale ressaltar que, se já existir a posição frase, o comando "mapa[frase]=x;" atribui a ela o valor de x, mas se ela ainda não tiver sido criada, ele a cria e depois atribui a ela tal valor.

map tem uma função importante chamada find. Como estamos em mapa, se chamarmos a função "mapa.find("agua");", ela retornaria um ponteiro para o elemento salvo em mapa na chave "agua". Se não existir tal chave, ela retornará um ponteiro para o fim de mapa.

Assim, para cada pagamento efetuado por Daniboy, vamos escanear o nome da conta e salvá-lo na string conta, e o valor pago, salvando-o na double valor. Depois vamos verificar se a posição de nome conta já existe no vetor simulado por mapa. Para fazer isso, vamos ver se a função "mapa.find(conta)" retorna um ponteiro diferente de fim do mapa. Vale ressaltar que, assim como no set, o map também tem as funções begin() e end(), que retornam ponteiros para o começo e para o fim do map, respectivamente. Assim, verificar se uma chave, já existe é verificar: "if(mapa.find(conta)!=mapa.end())". Se isso ocorrer, adiciono valor ao elemento salvo na chave conta, com o comando "mapa[conta]+=valor;". Caso contrário, crio a chave conta e nela salvo o valor pago, que está em valor, através do comando "mapa[conta]=valor;".

Quando tivermos lido toda a entrada, cada chave do mapa representará o nome de uma conta e terá nela salvo o valor a ser pago. Agora basta que percorramos todo o mapa imprimindo, para cada um de seus elementos, o nome da chave e do valor nela salvo. Para isso, assim como no set, vamos usar um iterador que saiba percorrer um map. Semelhante ao set, essa estrutura ordena seus elementos em ordem crescente de chave. Logo, as posições, que são strings, estarão em ordem alfabética, o que nos permitirá imprimir as contas nessa ordem, como pedido pelo problema. Para declará-lo, fazemos algo semelhante ao que fizemos no set, indicando que tipo de iterador queremos criar e, depois, seu nome. Queremos declarar um iterador de nome it que saiba percorrer um map onde as chaves são strings e que guarda elementos do tipo double, logo usamos o comando "map<string, double>::iterator it;". Vamos fazer um for para que it percorra todos os elementos de mapa. Porém, it aponta para os dois valores: a chave e o elemento nele salvo. Logo, para acessar a chave, o primeiro elemento, chamo o membro first ("(*it).first"), e para ver o segundo elemento, o valor nele salvo, chamo o membro second ("(*it).second"). Assim, dentro do for, vamos imprimir a chave com o comando "cout << (*it).first". Agora teremos que imprimir o valor salvo na posição usando o printf, pois queremos a double com apenas duas casas de precisão, usando o comando "printf(" %.2lf\n", (*it).second);", para também imprimir o espaço em branco entre o nome e o valor e depois a quebra de linha. Segue o código para melhor entendimento:

Além das mostradas nessa aula, o map tem várias outras funções, que podem ser vistas na referência do Cplusplus. Dentre elas, as mais importantes são:

size() - retorna, em O(1), o número de posições no map

erase(x) - apaga, em O(1), a posição determinada pela chave x

clear() - apaga todos os elementos do map em O(size)

Vale lembrar que todas as funções mostradas na aula de hoje são membros de alguma estrutura, ou seja, para chamá-las, precisamos escrever o nome do objeto que declaramos, seguido de um ponto ".", seguido do nome da função e seus parâmetros.

Existem outras estruturas já implementadas no C++, sendo as mostrada hoje apenas as necessárias para PJ e P1 da OBI com implementação já pronta. Para ver todas as estruturas da STL, veja a referência do Cplusplus.

Agora que você já sabe tudo isso, tente resolver os seguintes problemas. Caso você não consiga resolver algum deles ou tenha alguma dúvida em algum assunto teórico desta aula, vá para a página inicial do curso e preencha o formulário para nos enviar sua dúvida!

Problema 1 - Espécies de Madeira

Problema 2 - Open Source

Problema 3 - Bankrupt Baker

Problema 4 - Hoax or what

Problema 5 - Primeiro Dicionário de Andy

Problema 6 - Pontos de Feno

Problema 7 - Gloud Computing

Problema 8 - O Fantástico Jaspion


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: