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

Aula de Rogério Júnior

Aqui nós veremos mais estruturas de dados da STL.

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 a 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 e 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 e 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.

O 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.

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.