Módulo 02
Estruturas Sequenciais
Strings e Estruturas de Caracteres
Uma string é uma sequência de caracteres. Por isso, muitos dos conceitos estudados em vetores reaparecem aqui: índices, memória contígua, percursos, busca e deslocamentos. Nesta aula vamos estudar str, Unicode e sequências de bytes, além de entender por que UTF-8 torna a relação entre caractere e byte mais interessante.
Um vetor especializado em texto
O Que é uma String?
Uma string representa uma sequência ordenada de símbolos. Em situações simples, podemos imaginá-la como um vetor de caracteres: cada posição possui um índice e pode ser percorrida sequencialmente.
Caractere
Em C++, char ocupa um byte. Em UTF-8, um caractere visual pode utilizar vários char.
Sequência
Os caracteres possuem ordem e podem ser acessados por índice.
bytes
Sequência imutável de valores entre 0 e 255, usada para dados codificados.
std::string
Sequência mutável de bytes com memória administrada pela biblioteca padrão do C++.
Conexão com vetores: se
texto = "DADOS", podemos pensar em
texto[0] = 'D', texto[1] = 'A', texto[2] = 'D' e assim por diante.
Cuidado com a palavra “caractere”: quando trabalhamos apenas com ASCII, é tentador dizer
que “um caractere ocupa um byte”. Isso funciona para letras como
A, B e
7, mas deixa de ser verdade para textos Unicode. Em uma string UTF-8 devemos distinguir
byte, ponto de código Unicode e caractere visual.
Caractere não é string
Um caractere representa uma unidade, como 'A'. Uma string representa uma sequência, como "ALGORITMO".
Strings também têm índices
Assim como vetores, strings permitem acessar posições. Em "DADOS", o caractere inicial está no índice 0.
Do texto para sua representação binária
Codificando uma String em Bytes UTF-8
C++ não impõe uma codificação para std::string. Quando adotamos UTF-8,
a string armazena diretamente os bytes que codificam o texto.
A expressão
std::string texto = "DADOS"; armazena 5 bytes.
Caracteres acentuados em UTF-8 podem precisar de mais de um byte.
Cada célula representa um byte da sequência didática. Clique para observar o símbolo e o valor numérico.
Selecione uma posição da string.
texto.size() conta bytes?
Sim. Em std::string, size() informa a quantidade de bytes armazenados, não necessariamente a quantidade de caracteres visuais.
Como interpretar os bytes como texto?
O programa e o ambiente precisam concordar sobre a codificação. Um literal u8"..." explicita UTF-8 em C++17.
Strings também são sequências
Acesso, Busca, Inserção e Remoção
As operações sobre strings lembram as operações sobre vetores. Acessar uma posição é direto; procurar um caractere pode exigir percurso; inserir ou remover internamente pode deslocar caracteres.
A string inicial é ESTRUTURA. Observe comparações e deslocamentos.
Escolha uma operação.
Acesso por índice
Em uma representação contígua, acessar uma posição conhecida é O(1).
Buscar um caractere
Uma busca linear pode precisar examinar toda a string: O(n) no pior caso.
Inserção e remoção internas
Para manter a sequência, posições posteriores podem precisar ser deslocadas: O(n) no pior caso.
Byte, código e símbolo visual são coisas diferentes
ASCII, Unicode e UTF-8
Para entender strings modernas, precisamos separar conceitos que parecem iguais quando usamos apenas letras simples. Um computador armazena bytes; Unicode atribui números aos símbolos chamados pontos de código; e uma codificação como UTF-8 transforma esses pontos de código em uma sequência de bytes.
Byte é uma unidade de armazenamento, normalmente com 8 bits. Em C++, uma std::string UTF-8 pode usar um ou mais bytes para representar um caractere visual.
É um número atribuído pelo Unicode, escrito como U+XXXX. Por exemplo, A = U+0041 e á = U+00E1.
É a regra que converte cada ponto de código em 1 a 4 bytes. Por isso um único ponto de código pode ocupar vários elementos char em uma std::string.
É, aproximadamente, um “caractere visual”. Um grafema pode ser formado por um único ponto de código ou pela combinação de vários pontos de código.
Então “1 caractere = 1 byte” está errado?
Como regra geral, sim. A frase só funciona em conjuntos simples de um byte, como a parte ASCII do UTF-8.
Em UTF-8,
A usa 1 byte, á usa 2, € usa 3 e
😀 usa 4. E ainda existe um caso mais interessante: um único símbolo visual pode ser
composto por vários pontos de código.
| Texto exibido | Grafemas visuais | Pontos de código | UTF-8 (hex) | Bytes |
|---|---|---|---|---|
| A | 1 | U+0041 |
41 |
1 |
| á | 1 | U+00E1 |
C3 A1 |
2 |
| € | 1 | U+20AC |
E2 82 AC |
3 |
| 😀 | 1 | U+1F600 |
F0 9F 98 80 |
4 |
| é (e + acento combinante) | 1 | U+0065 U+0301 |
65 CC 81 |
3 |
O exemplo “é” é o mais importante: visualmente enxergamos uma única letra acentuada,
mas internamente ela pode ser formada por dois pontos de código:
e + acento agudo combinante.
Portanto até “1 símbolo visual = 1 ponto de código” pode ser falso.
Tabela ASCII padrão — 0 a 127
ASCII é uma codificação histórica de 7 bits, portanto possui exatamente 128 valores (0 a 127). Os códigos 0–31 e 127 são caracteres de controle; 32–126 são os caracteres imprimíveis. A parte ASCII é preservada pelo UTF-8: para esses valores, o byte UTF-8 é exatamente o mesmo código.
128 códigos
| Decimal | Hex | Binário | Caractere / nome | Descrição |
|---|
Exemplo: a letra
A é ASCII decimal 65, hexadecimal
0x41 e binário 01000001. Em UTF-8 ela continua sendo codificada pelo
único byte 41. Já á não pertence ao ASCII padrão e precisa de dois
bytes em UTF-8: C3 A1.
Visualizador: do símbolo aos bytes UTF-8
Bytes UTF-8 completos
Separação por ponto de código
Digite um texto ou escolha um exemplo.
ASCII
ASCII possui 128 códigos, de 0 a 127. Como esses códigos cabem em 7 bits, todos eles são representados por um único byte em UTF-8. Não confunda ASCII padrão com antigas tabelas chamadas informalmente de “ASCII estendido”, que variam conforme a página de código.
Unicode não é UTF-8
Unicode define o repertório e os pontos de código. UTF-8 é uma das codificações utilizadas para transformar esses pontos em bytes. UTF-16 e UTF-32 são outras codificações possíveis.
E em std::string?
std::string é uma sequência de elementos char. Se o conteúdo estiver
codificado em UTF-8, cada char corresponde a um byte da codificação, e não
necessariamente a um caractere visual. Assim, size() informa bytes armazenados,
não “letras na tela”.
Exemplo prático: "ação"
A palavra possui 4 letras visuais e 4 pontos de código, mas em UTF-8 ocupa 6 bytes:
a = 1, ç = 2, ã = 2 e o = 1.
Portanto uma str contendo esses bytes terá size() == 6.
Custos básicos
Complexidade das Operações em Strings
| Operação | Complexidade típica | Observação |
|---|---|---|
Acessar s[i] | O(1) | Acesso direto à posição armazenada. |
Alterar s[i] | O(1) | Quando a posição é conhecida e válida. |
| Buscar um caractere | O(n) | No pior caso, percorre toda a sequência. |
| Comparar duas strings | O(n) | Pode exigir comparar vários caracteres. |
| Inserir no meio | O(n) | Pode deslocar caracteres posteriores. |
| Remover do meio | O(n) | Pode deslocar a parte restante. |
| Concatenar | O(n + m) | Depende dos tamanhos envolvidos e da capacidade disponível. |
Aplicação prática
Strings em C++17
str com um ou vários caracteres
char letra = 'A';
char quebra_de_linha = '\n';str
#include <string>
std::string texto = "Estrutura de Dados";
std::cout << texto.size() << '\n';
std::cout << texto[0] << '\n';
std::cout << texto.substr(0, 9) << '\n';str e UTF-8: size() conta bytes
#include <iomanip>
#include <string>
std::string texto = u8"ação";
for (unsigned char byte : texto) {
std::cout << std::hex
<< std::setw(2)
<< std::setfill('0')
<< static_cast<int>(byte) << ' ';
}Inserção, remoção e concatenação
std::string texto = "DADOS";
std::cout << texto[0] << '\n'; // D
std::cout << texto.at(4) << '\n'; // S
for (char caractere : texto) {
std::cout << caractere << ' ';
}Procurando texto
std::string texto = "ESTRUTURAS DE DADOS";
std::string termo = "DADOS";
std::size_t posicao = texto.find(termo);
if (posicao != std::string::npos)
std::cout << "Encontrado em " << posicao;
else
std::cout << "Não encontrado";size()
Retorna a quantidade de bytes armazenados pela std::string. Em UTF-8, isso não deve ser interpretado automaticamente como quantidade de caracteres visuais.
u8"..."
Cria um literal codificado em UTF-8. Em C++17 ele pode inicializar uma std::string.
std::string::find()
Procura uma substring ou caractere. Quando não encontra, retorna std::string::npos.
Modelo mental
O Que Você Precisa Guardar
Resumo: strings reutilizam muitos conceitos de vetores, mas adicionam uma preocupação essencial:
como os caracteres são codificados.