19.01
2025
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.