Cadeias de caracteres (strings)

Livro de Sedgewick e Wayne: sec.1.2, p.74, p.80.  Também a introdução do capítulo 5.  Website do livro: resumo sec.1.2.

Cadeias de caracteres são um ADT básico (que já usamos em muitas das aulas anteriores). Em Java, cadeias de caracteres são representadas pela classe String.  Esta página discute a API da classe String (mas evita tratar das implementações).

String

• A classe String está embutida na linguagem Java e portanto pode ser usada sem qualquer import.
• A API completa da classe String pode ser vista no website da Oracle.  Aqui exibiremos apenas algumas das operações mais importantes:

  public class String
  	String()	construtor: cria uma string vazia
  boolean	isEmpty()	esta string é vazia?
  int	length()	número de caracteres desta string
  char	charAt(int i)	caractere na posição i desta string     (supõe 0 ≤ i < length())
  boolean	equals(String t)	o valor desta string é igual ao valor de t?
  String	substring(int i, int j)	segmento formada pelos caracteres nas posições     i até j-1 desta string (supõe i ≤ j)
  String	substring(int i)	sufixo que começa com o caractere na posição i     desta string
  String	concat(String t)	resultado da concatenação desta string     com a string t

• Os caracteres de uma string ocupam posições:  o primeiro caractere ocupa a posição 0, o segundo ocupa a posição 1, etc.
• Uma string s é vazia se e só se s.length() == 0.  A string vazia é denotada por  ""  e ocasionalmente pela letra epsilon (ε) do alfabeto grego.
• O método substring() com dois argumentos extrai um segmento da string:  se s é uma string e i e j são inteiros tais que  0  ≤  i  ≤  j  ≤  s.length()  então a string s.substring(i,j) começa com o caractere que está na posição i de s e vai até o caractere na posição j-1.  Se i > j então s.substring(i,j) dá pau, ou seja, lança uma exceção Java.  (Acho que seria mais útil se devolvesse null nesse caso.)
• Exemplos:
  • "ABCDE".substring(1,3)  devolve  "BC",
  • "ABCDE".substring(0,5)  devolve  "ABCDE",
  • "ABCDE".substring(2,2)  devolve  "".
• O método substring() com um só argumento devolve um sufixo da string:  se s é uma string e i é um inteiro tal que  0  ≤  i  ≤  s.length()  então s.substring(i) começa com o caractere que está na posição i de s e vai até o fim da string.  Se i  >  s.length() então s.substring(i) dá pau, ou seja, lança uma exceção Java.  (Acho que seria mais útil se devolvesse null nesse caso.)
• Exemplos:
  • "ABCD".substring(2)  devolve  "CD",
  • "ABCD".substring(4)  devolve  "".
• Exemplo de operações sobre strings:

  

• A concatenação de duas strings s e t consiste na string s seguida da string t.  A concatenação de s e t também pode ser indicada pela expressão  s + t.

Exercícios 1

1. Qual a diferença entre null e a string ""?
2. Suponha que s é uma String.  Qual o valor de s.substring(0,-1)?
3. É verdade que s.substring(i) é igual a s.substring(i, s.length())?

Imutabilidade

• Objetos da classe String são imutáveis:  o valor de uma string não pode ser alterado depois que a string foi criada ou construída.

Exercícios 2

1. (SW 1.2.4)  O que imprime o seguinte fragmento de código?

      String string1 = "hello";
      String string2 = string1;
      tring1 = "world";
      StdOut.println(string1);
      StdOut.println(string2);
   

2. (SW 1.2.5)  O que imprime o seguinte fragmento de código?

      String s = "Hello World";
      s.toUpperCase();
      s.substring(6, 11);
      StdOut.println(s);
   

Implementações

• A maneira mais básica de implementar String é um simples vetor de caracteres (embora nessa implementação String deixaria, tipicamente, de ser imutável).
• Cada implementação da classe tem suas características de desempenho.  Antes da versão 7 de Java, a implementação da classe String era tal que o método substring() consumia tempo constante. Na versão 7, isso deixou de ser verdade.

Exercícios 3

1. Implemente a classe String em um vetor de caracteres (é necessário tomar providências para que String seja imutável, como desejado). Qual o desempenho dos diversos métodos dessa implementação?