Contando Ocorrências com std::set

por Fabio A. Mazzarino

A biblioteca STL foi incorporada no C++ em 1994, e veio padronizar um conjunto de estruturas de dados muito úteis. Neste post vamos abordar uma das mais simples: std::set.

std::set é um container para armazenamento único e ordenado. Faz uso de template para ser possível utilizar quaisquer tipos ou classes que possam ser comparadas, o container oferece, inclusive opções para definir métodos de comparação e de alocação.

Listando Palavras

Vamos a um exemplo bem simples, um programa que lista as palavras utilizadas em um arquivo:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <set>

int main(int argc, char* argv[]) {
	if (argc < 2) {
		std::cerr << "Usage: " << std::endl;
		std::cerr << "\twordlist <FILENAME>" << std::endl;
		exit(1);
	}
	
	std::string filename = argv[1];
	std::ifstream file(filename.c_str());
	if (!file.is_open()) {
		std::cerr << "Cannot open file: " << filename << std::endl;
		exit(1);
	}
	
	char buffer[512] = "";
	std::set<std::string> words;
	while (!file.eof()) {
		file.getline(buffer, sizeof(buffer) - 1, ' ');
		std::string word = buffer;
		
		word.erase(std::remove(word.begin(), word.end(), '\n'), word.end());
		word.erase(std::remove(word.begin(), word.end(), '\r'), word.end());
		word.erase(std::remove(word.begin(), word.end(), '\t'), word.end());
		word.erase(std::remove(word.begin(), word.end(), '.'), word.end());
		word.erase(std::remove(word.begin(), word.end(), ','), word.end());
		word.erase(std::remove(word.begin(), word.end(), '!'), word.end());
		word.erase(std::remove(word.begin(), word.end(), '?'), word.end());
		word.erase(std::remove(word.begin(), word.end(), ':'), word.end());
		word.erase(std::remove(word.begin(), word.end(), ';'), word.end());
			
		words.insert(word);
	}
	file.close();	
	cc
}

No exemplo acima o programa lê um arquivo texto e lista as palavras únicas do texto. Dentro do loop utilizamos o algorítmo std::remove para remover cada caracter que não é palavra.

Mas note como é utilizado o std::set, através da simples utilização do método insert(). E depois através da recuperação utilizando o iterator do std::set. As palavras únicas são recuperadas alfabeticamente. Note que não há necessidade de verificar se a palavra já existe no std::set, uma simples chamado ao método insert() já gerencia toda a duplicidade.

Utilizando o seguinte arquivo de entrada:

Nunca e nunca. Acumulada, acumuladas e acumulada. Sempre, sempre e SEMPRE!

Executando:

$ g++ wordlist.cpp -o wordlist
$ ./wordlist sample.txt
Acumulada
Nunca
SEMPRE
Sempre
acumulada
acumuladas
e
nunca
sempre

Comparações Customizadas

Os tipos suportados por std::list necessitam contar com sobrecarga de operadores de comparação, ou é possível simplesmente indicar uma função de comparação.

Pra ilustrar, vamos alterar o exemplo acima para ignorar maiúsculas e minúsculas:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <set>
#include <string>

struct casecmp {
        bool operator()(const std::string &lhs, const std::string &rhs) const {
        std::string s1 = lhs;
        std::string s2 = rhs;
        std::transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
        std::transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
        return s1 < s2;
    }
};

int main(int argc, char* argv[]) {
        if (argc < 2) {
                std::cerr << "Usage: " << std::endl;
                std::cerr << "\twordlist <FILENAME>" << std::endl;
                exit(1);
        }

        std::string filename = argv[1];
        std::ifstream file(filename.c_str());
        if (!file.is_open()) {
                std::cerr << "Cannot open file: " << filename << std::endl;
                exit(1);
        }

        char buffer[512] = "";
        std::set<std::string, casecmp> words;
        while (!file.eof()) {
                file.getline(buffer, sizeof(buffer) - 1, ' ');
                std::string word = buffer;

                word.erase(std::remove(word.begin(), word.end(), '\n'), word.end());
                word.erase(std::remove(word.begin(), word.end(), '\r'), word.end());
                word.erase(std::remove(word.begin(), word.end(), '\t'), word.end());
                word.erase(std::remove(word.begin(), word.end(), '.'), word.end());
                word.erase(std::remove(word.begin(), word.end(), ','), word.end());
                word.erase(std::remove(word.begin(), word.end(), '!'), word.end());
                word.erase(std::remove(word.begin(), word.end(), '?'), word.end());
                word.erase(std::remove(word.begin(), word.end(), ':'), word.end());
                word.erase(std::remove(word.begin(), word.end(), ';'), word.end());
                if (word.size() == 0)
                        continue;
                words.insert(word);
        }
        file.close();
        for (std::set<std::string>::iterator it = words.begin(); it != words.end(); it++) {
                std::cout << (*it) << std::endl;
        }
}

Criamos um tipo para executar a comparação, assim podemos utilizá-lo no template std::set. Esse template contém a função de comparação que faz a conversão das strings para minúsculo, para depois efetuar a comparação.

O resultado:

$ g++ wordlist.cpp -o wordlist
$ ./wordlist sample.txt
Acumulada
acumuladas
e
Nunca
Sempre

Note que são armazenadas somente as primeiras versões que são encontradas, exibindo de forma clara o funcionamento do std::set.

Profissionalmente

A estrutura de dados std::set é amplamente utilizada entre os times de desenvolvimento, não há muita discussão sobre se o time deve ou não utilizar essa estrutura de dados. Caso o time aceite classes STL, dificilmente haverá alguma restrição.

Porém a utilização de métodos alternativos de comparação pode encontrar resistência, já que podem alterar comportamento esperado em tipos já estabelecidos, é possível, inclusive, alterar o método de comparação de tipos básicos como double, ou int. E neste caso, é necessário, de fato definições bem claras sobre limites.