11. Classes Container

Containers Sequenciais

Containers Associativos

Algoritmos Genéricos

Strings, Byte Arrays e Variantes Classes Container são classes de propósito geral que armazenam itens de um dado tipo em memória. C++ oferece

vários containers como parte da Biblioteca Template Padrão (STL), que está incluída na biblioteca C++ padrão.

Qt possui seu próprio conjunto de classes container, então para programadores Qt podemos usar ambos containers

Qt e STL. As principais vantagens dos containers Qt são que eles se comportam da mesma maneira em todas as

plataformas e que eles são compartilhados implicitamente. Compartilhamento implícito, ou “cópia na escrita”, é

uma otimização que torna possível passar containers inteiros como valores sem custo significativo de performance.

Os containers Qt possuem também classes iterator fáceis de serem usadas inspiradas no Java, podem ser

transmitidas usando QDataStream, e eles geralmente resultam em menos código executável do que os

containers STL. Por último, em algumas plataformas de hardware suportados por Linux baseado em Qt, os

containres Qt são os únicos disponíveis.

Qt oferece containers sequenciais, como QVector<T> , QLinkedList<T>, e QList<T>, e também

containers associativos como QMap<K, T> e QHash<K, T>. Conceitualmente, os containers sequenciais

armazenam itens um após o outro, enquanto os containers associativos armazenam pares chave-valor.

Qt também possui algoritmos genéricos que realizam operações em containers arbitrários. Por exemplo, o algoritmo

qSort()ordena um container sequencial, e qBinaryFind()realiza uma busca binária em um container

sequencial ordenado. Esses algoritmos são similares aos oferecidos pela STL.

Se você está familiarizado com os containers STL e possui STL disponível na plataforma, você pode preferir a usá-los

ao invés dos containers Qt, ou usá-los adicionalmente. Para mais informações sobre as classes e funções STL, um

bom lugar para começar é a sessão STL do site da SGI: http://www.sgi.com/tech/stl/.

Neste capítulo, veremos também QString, QByteArray, e QVariant, já que eles têm muito em comum

com containers. QString é uma string 16-Bit Unicode usada na API do Qt. QByteArray é um array de chars

de 8 Bits útil para armazenamento de dados binários brutos. QVariant é um tipo que pode armazenar a maioria

dos tipos de valores C++ e Qt.

Containers Sequenciais

Um vetor QVector<T> é uma estrutura de dados no formato array que armazena seus itens em posições adjacentes

na memória, como mostra a Figura 11.1. A diferença entre um vetor e um array C++ é que o vetor sabe seu próprio

tamanho e pode ser redimensionado. Incluir itens adicionais no final de um vetor é eficiente, porém adicionar

valores no início ou no meio do vetor pode ser custoso.

Figura 11.1. Um vetor de doubles

Se soubermos com antecedência de quantos itens vamos precisar, podemos dar ao vetor um valor inicial ao o

definir, e usar o operador [] para atribuir um valor para os itens; do contrário, devemos ou redimensionar o vetor

mais tarde ou adicionar itens. Aqui um exemplo onde especificamos o valor inicial:

QVector<double> vect(3);

vect[0] = 1.0;

vect[1] = 0.540302;

vect[2] = -0.416147;

Aqui temos o mesmo exemplo, dessa vez iniciando com um vetor vazio e usando a função append() para

adicionar itens no final:

QVector<double> vect;

vect. Append(1.0);

vect.append(0.540302);

vect.append(-0.416147);

Podemos usar também o operador << ao invés de append():

double sum = 0.0;

for (int i = 0; i < vect.count(); ++i)

sum += vect[i];

Entradas de vetores que são criadas sem nenhum valor explícito atribuído são inicializadas usando o construtor

padrão da classe do item. Tipos básicos e ponteiros são inicializados com zero.

Adicionar itens ao início ou no meio de um QVector<T>, ou remover itens dessas posições, pode ser ineficiente

para vetores grandes. Por essa razão, Qt também oferece QLinkedList<T>, uma estrutura de dados que

armazena seus itens em posições não adjacentes da memória, como ilustra a Figura 11.2. Diferente de vetores,

listas ligadas não oferecem suporte a acesso aleatório, mas elas possuem inserções e remoções em “tempo

constante”.

Figura 11.2. Um lista ligada de doubles

Listas ligadas não possuem o operador [], assim faz-se necessário o uso de iteradores para permutar os items.

Iteradores são também usados para especificar a posição de itens. Por exemplo, o código a seguir insere a string

“Tote Hosen” entre “Clash” e “Ramones”:

QLinkedList<QString> list;

list.append(“Clash”);

list.append(“Ramones”);

QLinkedList<QString>::iterator i = list.find(“Ramones”);

list.insert(i, “Tote Hosen”);

Vamos analisar iteradores com mais detalhadamente mais tarde nessa seção,

O container sequencial QList<T> é um “array-lista” que combina os mais importantes benefícios de

QVector<T> e QLinkedList<T> em uma única classe. Suporta acesso randômico, e sua interface é

baseada em endereço como a do QVector. Inserir ou remover um item no final ou início de uma QList<T> é

muito rápido, enquanto que inserir no meio é rápido para listas com até mil elementos. A não ser que queiramos

realizar inserções no meio de listas enormes ou precisemos dos itens da lista para ocupar endereços consecutivos

da memória, QList<T> é geralmente a classe container mais apropriada para usos gerais.

A classe QStringList é uma subclasse de QList<QString> que é amplamente usada na API do Qt. Além

das funções que herda de suas classes base, ela oferece algumas funções extra que tornam a classe mais versátil

para controle de string. Vamos discutir QStringList na última sessão deste capítulo.

QStack<T> e QQueue<T> são mais dois exemplos de subclasses convenientes. QStack<T> é um vetor que

possui push(), pop() e top(). QQueue<T> é uma lista que fornece enqueue(), dequeue() e

head().

Para todas as classes container vistas até agora, o valor T pode ser um tipo básico como int ou double, um

ponteiro, ou uma classe com construtor padrão (um construtor sem argumentos), um construtor cópia, e um

operador de atribuição. Entre as classes que se qualificam podemos citar QByteArray, QDateTime,

QRegExp, QString, e QVariant. Classes Qt que são derivadas de QObject não se qualificam, pois elas

não possuem um construtor cópia e um operador de atribuição. Isto não é um problema na prática, já que podemos

simplesmente armazenar ponteiros para tipos QObject ao invés dos objetos em si.

O tipo valor T pode também ser um container, e neste caso é necessário separar colchetes com espaços, do contrário

o compilador fará uma interpretação errada no que pensa ser um operador >>. Por exemplo:

QList<QVector<double> > list;

Além dos tipos mencionados, o tipo valor de um container pode ser qualquer classe personalizada que preenche os

requisitos descritos acima. Aqui um exemplo de uma classe:

class Movie

{

public:

Movie(const QString &title = “”, int duration = 0);

void setTitle(const QString &title) { myTitle = title; }

QString title() const { return myTitle; }

void setDuration(int duration) { myDuration = duration; }

QString duration() const { return myDuration; }

private:

QString myTitle;

int myDuration;

};

A classe tem um construtor que não requer argumentos( embora pode-se incluir até dois). Ela também um construtor

cópia e um operador de atribuição, ambos fornecidos implicitamente pelo C++. Para essa classe, uma cópia

membro-a-membro é suficiente, então não há necessidade de implementar nosso próprio construtor cópia e

operador de atribuição.

Qt oferece duas categorias de iteradores para permutar os itens armazenados em um container: iteradores baseados

em Java e baseados em STL. Os iteradores baseados em Java são mais fáceis de usar, enquanto que os iteradores

STL podem ser combinados com algoritmos genéricos do STL e do Qt e são mais poderosos.

Para cada classe container, há dois tipos de iterador baseados em Java: um iterador somente leitura e um somente

escrita. Suas posições válidas são mostradas na Figura 11.3. As classes do iterador somente leitura são

QvectorIterator<T>, QLinkedListIterator<T>, e QListIterator<T>. Os iteradores

somente escrita correspondentes têm Mutable em seus nomes (i.e, QMutableVectorIterator<T>).

Vamos nos concentrar nos iteradores de QList. Os iterators de listas ligadas e vetores possuem a mesma API.

Figura 11.3. Posições válidas para iteradores Java

A primeira coisa a ser lembrada ao usar iteradores baseados em Java é que eles não apontam diretamente para os

itens. Ao invés, eles podem ser localizados antes do primeiro item, após o último item, ou entre dois itens. Uma

iteração de loop típica é algo como:

QList<double> list;

...

QListIterator<double> i(list);

while (i.hasNext()) {

do_something(i.next);

}

O iterador é inicializado com o container a ser permutado. Neste ponto, o iterador está localizado logo antes do

primeiro item. A chamada a hasNext() retorna true se existe um item à direita do iterador. A função next()

retorna p item à direita do iterador e avança o iterador até a próxima posição válida.

Iterações de frente para trás são similares, exceto que devemos primeiro chamar toBack() para posicionar o

iterador após o último item:

QListIterator<double> i(list);

i.toBack();

while (i.hasPrevious()) {

do_something(i.previous());

}

A função hasPrevious() retorna true se existe um item à esquerda do iterador; previous() retorna o

item à esquerda do iterador e move o iterador para trás 1 posição. Outra forma de definir os iteradores next() e

previous() é que eles retornam o item o qual o iterador acaba de pular, como mostra a figura 11.4.

Figura 11.4. Efeito de previous() e next() em um iterador baseado em Java

Iteradores mutáveis fornecem funções para inserir, modificar e remover itens durante permutação. O loop a seguir

remove todos os números negativos de uma lista:

QMutableListIterator<double> i(list);

while (i.hasNext()) {

if (i.next() < 0.0)

i.remove();

}

A função remove() sempre opera no último item que foi pulado. Também funciona quando iteramos de frente para

trás:

QMutableListIterator<double> i(list);

i.toBack();

while (i.hasPrevious()) {

if (i.previous() < 0.0)

i.remove();

}

Similarmente, os iteradores mutáveis baseados em Java fornecem uma função setValue() que modifica o

último item que foi pulado. Aqui podemos ver como poderíamos substituir números negativos por seus valores

absolutos:

QMutableListIterator<double> i(list);

while (i.hasNext()) {

int val = i.next();

if (val < 0.0)

i.setValue(-val);

}

Também é possível inserir um item na posição atual do iterador fazendo uma chamada a insert(). O iterador é

então avançado ao ponto entre o novo item e o item seguinte.

Em adição aos iteradores baseados em Java, todas classe de container sequencial C<T> tem dois tipos de

iteradores baseados em STL: C<T>::iterator e C<T>::const_iterator. A diferença entre os dois é

que const_iterator não nos deixa modificar os dados.

A função begin() de um container retorna um iterador baseado em STL que se refere ao primeiro item do

container (ex, list[10]), enquanto que end() retorna um iterador para o “elemento depois do último” (ex,

list[5] para uma lista de tamanho 5). A Figura 11.5 mostra as posições válidas para iteradores baseados em STL. Se

um container está vazio, begin() é igual a end(). Isto pode ser usado para verificar se o container possui

algum item, embora seja normalmente mais conveniente chamar isEmpty() para este propósito.

Figura 11.5. Posições válidas para iteradores baseados em STL

A sintaxe do iterador beaseado em STL é modelada depois da sintaxe dos ponteiros C++ em um array. Podemos

usar os operadores ++ e –- para mover para o próximo item ou anterior, e o operador unário * para obter o item

atual. Para QVector<T>, os tipos iterator e const_iterator são meramente typedefs para T * e

const T *. (Isto é possível porque QVector<T> armazena seus próprios itens em posições consecutivas da

memória).

O seguinte exemplo substitui cada valor em uma QList<double> com seus valores absolutos:

QList<double>::iterator i = list.begin();

while (i != list.end()) {

*I = qAbs(*i);

++i;

}

Apenas algumas funções Qt retornam um container. Se queremos iterar sobre o valor de retorno de uma função

usando um iterador baseado em STL, devemos gerar uma cópia do container e iterar sobre a cópia. Por exemplo, o

código a seguir é a forma correta de iterar sobre a QList<int> retornada por QSplitter::sizes():

QList<int> list = splitter->sizes();

QList<int>::const_iterator i = list.begin();

while (i != list.end()) {

do_something(*i);

++i:

}

O código seguinte está errado:

// ERRADO

QList<int>>::const_iterator i = splitter->sizes().begin();

while (I != splitter->sizes().end()) {

do_something;

++i:

}

Isto porque QSplitter::sizes() retorna um novo QList<int> por valor toda vez que a função é

chamada. Se não armazenarmos o valor de retorno, C++ automaticamente o destrói antes mesmo de começar a

iteração, nos deixando com um problema no iterador. Para tornar as coisas piores, cada vez que o loop roda,

QSplitter::sizes() deve gerar uma nova cópia da lista devido a chamada de splitter->sizes()

.end(). Em suma: Ao usar iteradores baseados em STL, sempre faça a iteração em uma cópia do container

retornado por valor.

Com iteradores somente escrita baseados em Java, não precisamos levar uma cópia. O iterador tira a cópia para nós

por trás da cena, garantindo que sempre iteraremos sobre a data cuja função retornou primeiro. Por exemplo:

QListIterator<int> i(splitter->sizes());

while(i.hasNext()) {

do_something(i.next());

}

Copiar um container como este parece caro, mas não é, graças a uma optimização chamada Compartilhamento

Implícito (implicit sharing). Isto significa que copiar um container Qt é tão rápido quanto copiar um ponteiro singular.

Os dados são apenas copiados se uma das cópias é modificada – e tudo isso é controlado automaticamente por trás

da cena. Por essa razão, compartilhamento implícito é às vezes chamado de “cópia na escrita”.

A beleza de compartilhamento implícito está no fato de que é uma otimização sobre a qual não precisamos nos

preocupar; ela simplesmente funciona, sem requerer nenhuma intervenção do programador. Ao mesmo tempo,

compartilhamento implícito motiva a um estilo de programação limpo onde os objetos são retornados por valor.

Considere a seguinte função:

QVector<double> sineTable()

{

QVector<double> vect(360);

For (int i = 0; i < 360; i++)

vect[i] = std::sin(i / (2 * M_PI));

return vect;

}

A chamada para a função parece algo como:

QVector<double> table = sineTable();

STL, em comparação, encoraja-nos a passar o vetor como uma referência não-const para evitar a cópia que toma

lugar quando o valor de retorno da função é armazenado em uma variável:

void sineTable (std::vector<double> &vect)

{

vect.resize(360);

for (int i=0; I < 360; ++i)

vect[i] = std::sin(i / (2 * M_PI));

}

A chamada se torna, então, mais tediosa de escrever e menos clara de se ler:

std::vector<double> table;

sineTable (table);

Qt usa compartilhamento implícito para todos os seus containers e para diversas outras classes, incluindo

QByteArray, QBrush, QFont, QImage, QPixmap, e QString. Isto torna a passagem por valor dessas

classes muito eficiente, tanto como parâmetros de função quando como valores de retorno.

Compartilhamento implícito é uma garantia do Qt que a data não será copiada se não a modificarmos. Para tirar o

melhor do compartilhamento implícito, podemos adotar uma série de novos hábitos de programação. Um deles é o

uso da função at() ao invés do operador [] para acesso somente leitura em um (não const) vector ou lista. Já que

os containers não podem dizer se [] aparece no lado esquerdo de uma atribuição ou não, eles assumem o pior

caso e forçam a ocorrência de uma cópia profunda-enquanto que at() não está autorizado no lado esquerdo de

uma atribuição.

Uma medida similar ocorre quando iteramos sobre um container com iteradores baseados em STL. Sempre que

chamamos begin() ou end() em um não-const container, Qt força a existência de uma cópia profunda se os

dados são compartilhados. Para prevenir essa ineficiência, a solução é usar const_iterator,

constBegin(), e constEnd() sempre que possível.

Qt fornece um último método para iterar sobre itens em um container sequencial: o loop foreach. É algo similar a

isto:

QLinkedList<Movie> list;

...

foreach (Movie movie, list) {

if (movie.title() == “Citizen Kane”) {

std::cout << “Found Citizen Kane” << std::endl;

break;

}

}

A pseudo-palavra-chave foreach é implementada nos termos do loop for padrão. A cada iteração do loop, a

variável de iteração (movie) é setada para um novo item, começando do primeiro item no container e progredindo

avante. O loop foreach automaticamente tira uma cópia do container quando o loop é iniciado, e por essa razão

o loop não é afetado se o container for modificado durante a iteração.

Como funciona Compartilhamento Emplícito

Compartilhamento Implícito funciona automaticamente por trás das cenas, então não temos que fazer nada em

nosso código para fazer essa otimização acontecer. Mas já que é sempre bom saber como as coisas funcionam,

estudaremos um exemplo analisando o que acontece por trás da cena. O exemplo usa QString, uma das várias

classes de compartilhamento implícito do Qt.

QString str1 = “Humpty”;

QString str2 = str1;

Setamos str1 para “Humpty” e str2 para ser igual a str1. Neste ponto, ambos objetos QString apontam para

a mesma estrutura de dados interna na memória. Além dos dados de caracteres, a estrutura de dados carrega um

contador de referência que indica quantos QStrings apontam para a mesma estrutura de dados. Já que ambos

str1 e str2 apontam para os mesmos dados, o contador de referência vale 2.

str2[0] = ‘D’;

Quando modificamos str2, é feito primeiro uma cópia profunda dos dados, para assegurar que str1 e str2

apontem para estruturas de dados diferentes, e isso então faz com que eles mudem suas próprias cópias de dados.

O contador de referência dos dados de str1 (“Humpty”) se torna 1, e o contador de referência dos dados de

str2(“Dumpty”) é setado com 1. Um valor de referência 1 significa que os dados não estão compartilhados.

str2.truncate(4);

Se modificarmos str2 novamente, nenhuma cópia surgirá porque o contador de referência dos dados de str2 é

1. A função truncate() opera diretamente nos dados de str2, resultando na string “Dump”. O contador de

referência permanece em 1.

str1 = str2;

Quando atribuímos str2 para str1, o contador de referência para os dados de str1 vai para 0, o que significa

que nenhum QString está usando mais o valor “Humpty”. Os dados são então liberados da memória. Ambos

QString apontam para “Dump”, que agora tem contador de referência 2.

Compartilhamento de dados é geralmente desconsiderado como uma opção em programas multithread, devido a

condições de corrida na contagem de referência. Com Qt, isto não é um problema. Internamente, as classes

container usam instruções em linguagem assembly para realizar contagem de referência atômica. Essa tecnologia

está disponível para usuários de Qt através das classes QSharedData e QSharedDataPointer.

Os comandos de loop break e continue são suportados. Se o corpo consiste de uma única chamada, as

chaves são desnecessárias. Assim como uma chamada for, a variável de iteração pode ser definida fora do loop,

como em:

QLinkedList<Movie> list;

Movie movie;

…

foreach (movie, list) {

if(movie.title() == “Citizen Kane”) {

std::cout << “Found Citizen Kane” << std::end1;

break;

}

}

Definir a variável de iteração fora do loop é a única opção para containers que armazenam tipos de dados que

contém uma vírgula (ex., QPair<QString, int>).