Clases contenedoras

Introducción

La biblioteca Qt proporciona un conjunto de clases contenedoras de propósito general basadas en plantillas. Estas clases se pueden utilizar para almacenar elementos de un tipo específico. Por ejemplo, si necesita una matriz redimensionable de QStrings, utilice QList<QString>.

Estas clases contenedoras están diseñadas para ser más ligeras, seguras y fáciles de usar que los contenedores STL. Si no estás familiarizado con la STL, o prefieres hacer las cosas a la "manera Qt", puedes usar estas clases en lugar de las clases STL.

Las clases contenedoras están implícitamente compartidas, son reentrantes, y están optimizadas para velocidad, bajo consumo de memoria, y mínima expansión de código en línea, resultando en ejecutables más pequeños. Además, son seguras para los h ilos en situaciones en las que son utilizadas como contenedores de sólo lectura por todos los hilos que acceden a ellas.

Los contenedores proporcionan iteradores para recorrerlos. Los iteradores de estilo STL son los más eficientes y pueden utilizarse junto con los de Qt y STL generic algorithms. Los iteradores estilo Java se proporcionan por compatibilidad con versiones anteriores.

QList<int> list = {1, 2, 3, 4, 4, 5};
QSet<int> set(list.cbegin(), list.cend());
/*
    Will generate a QSet containing 1, 2, 3, 4, 5.
*/

Las clases contenedoras

Qt proporciona los siguientes contenedores secuenciales: QList, QStack, y QQueue. Para la mayoría de las aplicaciones, QList es la mejor clase a utilizar. Proporciona anexos muy rápidos. Si realmente necesitas una lista enlazada, utiliza std::list. QStack y QQueue son clases de conveniencia que proporcionan semántica LIFO y FIFO.

Qt también proporciona estos contenedores asociativos: QMap, QMultiMap, QHash, QMultiHash, y QSet. Los contenedores "Multi" soportan múltiples valores asociados a una única clave. Los contenedores "Hash" proporcionan una búsqueda más rápida mediante el uso de una función hash en lugar de una búsqueda binaria en un conjunto ordenado.

Como casos especiales, las clases QCache y QContiguousCache proporcionan una búsqueda hash eficiente de objetos en un almacenamiento caché limitado.

Los contenedores pueden anidarse. Por ejemplo, es perfectamente posible utilizar un QMap<QString, QList<int><>, donde el tipo de clave es QString y el tipo de valor QList<int>.

Los contenedores se definen en archivos de cabecera individuales con el mismo nombre que el contenedor (por ejemplo, <QList>). Por comodidad, los contenedores se declaran en <QtContainerFwd>.

Los valores almacenados en los distintos contenedores pueden ser de cualquier tipo de datos asignable. Para calificarse, un tipo debe proporcionar un constructor de copia y un operador de asignación. Para algunas operaciones también se requiere un constructor por defecto. Esto cubre la mayoría de los tipos de datos que probablemente desee almacenar en un contenedor, incluidos tipos básicos como int y double, tipos de puntero y tipos de datos Qt como QString, QDate y QTime, pero no cubre QObject ni ninguna subclase de QObject (QWidget, QDialog, QTimer, etc.). Si intenta instanciar un QList<QWidget>, el compilador se quejará de que el constructor de copia y los operadores de asignación de QWidget'están deshabilitados. Si desea almacenar este tipo de objetos en un contenedor, almacénelos como punteros, por ejemplo como QList<QWidget *>.

He aquí un ejemplo de tipo de datos personalizado que cumple el requisito de ser un tipo de datos asignable:

class Employee
{
public:
    Employee() {}
    Employee(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

Si no proporcionamos un constructor de copia o un operador de asignación, C++ proporciona una implementación por defecto que realiza una copia miembro a miembro. En el ejemplo anterior, eso habría sido suficiente. Además, si no proporcionamos ningún constructor, C++ proporciona un constructor por defecto que inicializa su miembro utilizando constructores por defecto. Aunque no proporciona ningún constructor explícito ni operador de asignación, el siguiente tipo de datos puede almacenarse en un contenedor:

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

Algunos contenedores tienen requisitos adicionales para los tipos de datos que pueden almacenar. Por ejemplo, el tipo Key de un QMap<Key, T> debe proporcionar operator<(). Estos requisitos especiales se documentan en la descripción detallada de una clase. En algunos casos, las funciones específicas tienen requisitos especiales, que se describen para cada función. El compilador siempre emitirá un error si no se cumple un requisito.

Los contenedores de Qt proporcionan operator<<() y operator>>() para que puedan ser leídos y escritos fácilmente usando QDataStream. Esto significa que los tipos de datos almacenados en el contenedor también deben soportar operator<<() y operator>>(). Proporcionar tal soporte es sencillo; así es como podríamos hacerlo para la estructura Movie de arriba:

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

La documentación de ciertas funciones de las clases contenedoras hace referencia a valores construidos por defecto; por ejemplo, QList inicializa automáticamente sus elementos con valores construidos por defecto, y QMap::value() devuelve un valor construido por defecto si la clave especificada no está en el mapa. Para la mayoría de los tipos de valores, esto significa simplemente que se crea un valor utilizando el constructor por defecto (por ejemplo, una cadena vacía para QString). Pero para los tipos primitivos como int y double, así como para los tipos de puntero, el lenguaje C++ no especifica ninguna inicialización; en esos casos, los contenedores de Qt inicializan automáticamente el valor a 0.

Iterando sobre contenedores

Basado en rangos para

Es preferible utilizar for para los contenedores:

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : list) {
//...
}

Tenga en cuenta que cuando se utiliza un contenedor Qt en un contexto no-const, la compartición implícita puede realizar un detach no deseado del contenedor. Para evitarlo, utilice std::as_const():

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : std::as_const(list)) {
    //...
}

Para contenedores asociativos, esto hará un bucle sobre los valores.

Basado en índices

Para los contenedores secuenciales que almacenan sus elementos de forma contigua en la memoria (por ejemplo, QList), se puede utilizar la iteración basada en índices:

QList<QString> list = {"A", "B", "C", "D"};
for (qsizetype i = 0; i < list.size(); ++i) {
    const auto &item = list.at(i);
    //...
}

Las clases de iteradores

Los iteradores proporcionan un medio uniforme para acceder a los elementos de un contenedor. Las clases contenedoras de Qt proporcionan dos tipos de iteradores: iteradores estilo STL e iteradores estilo Java. Los iteradores de ambos tipos se invalidan cuando los datos del contenedor se modifican o se separan de las copias compartidas implícitamente debido a una llamada a una función miembro no-const.

Iteradores de estilo STL

Los iteradores de estilo STL han estado disponibles desde la versión 2.0 de Qt. Son compatibles con Qt y STL's generic algorithms y están optimizados para la velocidad.

Para cada clase contenedora, hay dos tipos de iteradores estilo STL: uno que proporciona acceso de sólo lectura y otro que proporciona acceso de lectura-escritura. Los iteradores de sólo lectura deben utilizarse siempre que sea posible porque son más rápidos que los iteradores de lectura-escritura.

La API de los iteradores STL está modelada sobre punteros en un array. Por ejemplo, el operador ++ avanza el iterador al siguiente elemento, y el operador * devuelve el elemento al que apunta el iterador. De hecho, para QList y QStack, que almacenan sus elementos en posiciones de memoria adyacentes, el tipo iterator es sólo un typedef para T *, y el tipo const_iterator es sólo un typedef para const T *.

En esta discusión, nos concentraremos en QList y QMap. Los tipos iteradores para QSet tienen exactamente la misma interfaz que los iteradores de QList; de forma similar, los tipos iteradores para QHash tienen la misma interfaz que los iteradores de QMap.

He aquí un bucle típico para iterar a través de todos los elementos de un QList<QString> en orden y convertirlos a minúsculas:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.begin(), end = list.end(); i != end; ++i)
    *i = (*i).toLower();

Los iteradores estilo STL apuntan directamente a los elementos. La función begin() de un contenedor devuelve un iterador que apunta al primer elemento del contenedor. La función end() de un contenedor devuelve un iterador al elemento imaginario situado una posición después del último elemento del contenedor. end() marca una posición inválida; nunca debe ser dereferenciada. Se utiliza normalmente en la condición de ruptura de un bucle. Si la lista está vacía, begin() es igual a end(), por lo que nunca ejecutamos el bucle.

El siguiente diagrama muestra las posiciones válidas del iterador como flechas rojas para una lista que contiene cuatro elementos:

Iterar hacia atrás con un iterador estilo STL se hace con iteradores inversos:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.rbegin(), rend = list.rend(); i != rend; ++i)
    *i = i->toLower();

En los fragmentos de código hasta ahora, hemos utilizado el operador unario * para recuperar el elemento (de tipo QString) almacenado en una determinada posición del iterador, y luego hemos llamado a QString::toLower() sobre él.

Para el acceso de sólo lectura, puede utilizar const_iterator, cbegin(), y cend(). Por ejemplo:

for(auto i = list.cbegin(), end = list.cend(); i != end; ++i)    qDebug() << *i;

La siguiente tabla resume la API de los iteradores de estilo STL:

Los operadores ++ y -- están disponibles como operadores prefijo (++i, --i) y postfijo (i++, i--). Las versiones prefijo modifican los iteradores y devuelven una referencia al iterador modificado; las versiones postfijo toman una copia del iterador antes de modificarlo y devuelven esa copia. En las expresiones en las que se ignora el valor de retorno, se recomienda utilizar los operadores prefijos (++i, --i), ya que son ligeramente más rápidos.

Para los tipos de iteradores no-const, el valor de retorno del operador unario * puede utilizarse en el lado izquierdo del operador de asignación.

Para QMap y QHash, el operador * devuelve el componente de valor de un elemento. Si desea recuperar la clave, llame a key() en el iterador. Por simetría, los tipos de iterador también proporcionan una función value() para recuperar el valor. Por ejemplo, así es como imprimiríamos todos los elementos de QMap en la consola:

QMap<int,  int> map;//...for(auto i = map.cbegin(), end = map.cend(); i != end; ++i)    qDebug() << i.key() << ':' << i.value();

Gracias a la compartición implícita, es muy barato que una función devuelva un contenedor por valor. La API de Qt contiene docenas de funciones que devuelven un QList o QStringList por valor (por ejemplo, QSplitter::sizes()). Si quieres iterar sobre estos usando un iterador STL, siempre debes tomar una copia del contenedor e iterar sobre la copia. Por ejemplo:

// RIGHT
const QList<int> sizes = splitter->sizes();
for (auto i = sizes.begin(), end = sizes.end(); i != end; ++i)
    {/*...*/}

// WRONG
for (auto i = splitter->sizes().begin();
        i != splitter->sizes().end(); ++i)
    {/*...*/}

Este problema no ocurre con funciones que devuelven una referencia const o no const a un contenedor.

Problema del iterador de compartición implícita

La compartición implícita tiene otra consecuencia en los iteradores estilo STL: debes evitar copiar un contenedor mientras los iteradores estén activos en ese contenedor. Los iteradores apuntan a una estructura interna, y si copias un contenedor debes tener mucho cuidado con tus iteradores. Ej:

QList<int> a, b;
a.resize(100000); // make a big list filled with 0.

QList<int>::iterator i = a.begin();
// WRONG way of using the iterator i:
b = a;
/*
    Now we should be careful with iterator i since it will point to shared data
    If we do *i = 4 then we would change the shared instance (both vectors)
    The behavior differs from STL containers. Avoid doing such things in Qt.
*/

a[0] = 5;
/*
    Container a is now detached from the shared data,
    and even though i was an iterator from the container a, it now works as an iterator in b.
    Here the situation is that (*i) == 0.
*/

b.clear(); // Now the iterator i is completely invalid.

int j = *i; // Undefined behavior!
/*
    The data from b (which i pointed to) is gone.
    This would be well-defined with STL containers (and (*i) == 5),
    but with QList this is likely to crash.
*/

El ejemplo anterior sólo muestra un problema con QList, pero el problema existe para todos los contenedores Qt implícitamente compartidos.

Iteradores estilo Java

Los iteradoresJava-Style están modelados a partir de las clases iteradoras de Java. El código nuevo debería preferir los iteradores de estilo STL.

Contenedores Qt comparados con contenedores std

Contenedores Qt y algoritmos std

Puedes usar contenedores Qt con funciones de #include <algorithm>.

QList<int> list = {2, 3, 1};

std::sort(list.begin(), list.end());
/*
    Sort the list, now contains { 1, 2, 3 }
*/

std::reverse(list.begin(), list.end());
/*
    Reverse the list, now contains { 3, 2, 1 }
*/

int even_elements =
        std::count_if(list.begin(), list.end(), [](int element) { return (element % 2 == 0); });
/*
    Count how many elements that are even numbers, 1
*/

Otras clases similares a contenedores

Qt incluye otras clases de plantilla que se parecen a los contenedores en algunos aspectos. Estas clases no proporcionan iteradores y no pueden utilizarse con la palabra clave foreach.

• QCache<Key, T> proporciona una caché para almacenar objetos de un determinado tipo T asociados a claves de tipo Key.
• QContiguousCache<T> proporciona una forma eficiente de almacenar en caché datos a los que normalmente se accede de forma contigua.

Otros tipos que no son plantillas y que compiten con los contenedores de plantillas de Qt son QBitArray, QByteArray, QString, y QStringList.

Complejidad algorítmica

La complejidad algorítmica se refiere a la rapidez (o lentitud) de cada función a medida que crece el número de elementos en el contenedor. Por ejemplo, insertar un elemento en medio de una lista std::list es una operación extremadamente rápida, independientemente del número de elementos almacenados en la lista. Por otro lado, insertar un elemento en medio de un QList es potencialmente muy costoso si el QList contiene muchos elementos, ya que la mitad de los elementos deben moverse una posición en la memoria.

Para describir la complejidad algorítmica, utilizamos la siguiente terminología, basada en la notación "big Oh":

• Tiempo constante: O(1). Se dice que una función se ejecuta en tiempo constante si requiere la misma cantidad de tiempo independientemente del número de elementos presentes en el contenedor. Un ejemplo es QList::push_back().
• Tiempo logarítmico: O(log n). Una función que se ejecuta en tiempo logarítmico es una función cuyo tiempo de ejecución es proporcional al logaritmo del número de elementos del contenedor. Un ejemplo es el algoritmo de búsqueda binaria.
• Tiempo lineal: O(n). Una función que se ejecuta en tiempo lineal lo hará en un tiempo directamente proporcional al número de elementos almacenados en el contenedor. Un ejemplo es QList::insert().
• Tiempo lineal-logarítmico: O(n log n). Una función que se ejecuta en tiempo lineal-logarítmico es asintóticamente más lenta que una función en tiempo lineal, pero más rápida que una función en tiempo cuadrático.
• Tiempo cuadrático: O(n²). Una función de tiempo cuadrático se ejecuta en un tiempo que es proporcional al cuadrado del número de elementos almacenados en el contenedor.

La siguiente tabla resume la complejidad algorítmica del contenedor secuencial QList<T>:

En la tabla, "Amort." significa "comportamiento amortizado". Por ejemplo, "Amort. O(1)" significa que si llama a la función una sola vez, puede obtener un comportamiento O(n), pero si la llama varias veces (por ejemplo, n veces), el comportamiento medio será O(1).

La siguiente tabla resume la complejidad algorítmica de los contenedores y conjuntos asociativos de Qt:

Con QList, QHash, y QSet, el rendimiento de añadir elementos se amortiza O(log n). Puede reducirse a O(1) llamando a QList::reserve(), QHash::reserve() o QSet::reserve() con el número esperado de elementos antes de insertarlos. En la siguiente sección se trata este tema con más profundidad.

Optimizaciones para tipos primitivos y reubicables

Los contenedores Qt pueden utilizar rutas de código optimizadas si los elementos almacenados son reubicables o incluso primitivos. Sin embargo, no se puede detectar en todos los casos si los tipos son primitivos o reubicables. Puedes declarar que tus tipos son primitivos o reubicables utilizando la macro Q_DECLARE_TYPEINFO con la bandera Q_PRIMITIVE_TYPE o la bandera Q_RELOCATABLE_TYPE. Consulte la documentación de Q_DECLARE_TYPEINFO para más detalles y ejemplos de uso.

Si no usa Q_DECLARE_TYPEINFO, Qt usará std ::is_trivial_v<T> para identificar tipos primitivos y requerirá tanto std::is_trivially_copyable_v<T> como std::is_trivially_destructible_v<T> para identificar tipos reubicables. Esta es siempre una opción segura, aunque de rendimiento quizá subóptimo.

Estrategias de crecimiento

QList<T>, QString, y QByteArray almacenan sus elementos contiguamente en memoria; QHash<Key, T> mantiene una tabla hash cuyo tamaño es proporcional al número de elementos en el hash. Para evitar reasignar los datos cada vez que se añade un elemento al final del contenedor, estas clases suelen asignar más memoria de la necesaria.

Consideremos el siguiente código, que construye un QString a partir de otro QString:

QString onlyLetters(const QString &in)
{
    QString out;
    for (qsizetype j = 0; j < in.size(); ++j) {
        if (in.at(j).isLetter())
            out += in.at(j);
    }
    return out;
}

Construimos la cadena out dinámicamente añadiéndole un carácter cada vez. Supongamos que añadimos 15.000 caracteres a la cadena QString. Entonces se producen las siguientes 11 reasignaciones (de las 15000 posibles) cuando QString se queda sin espacio: 8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376. Al final, QString tiene 16376 caracteres Unicode asignados, 15000 de los cuales están ocupados.

Los valores anteriores pueden parecer un poco extraños, pero hay un principio rector. Avanza duplicando el tamaño cada vez. Más concretamente, avanza hasta la siguiente potencia de dos, menos 16 bytes. 16 bytes corresponden a ocho caracteres, ya que QString utiliza internamente UTF-16.

QByteArray utiliza el mismo algoritmo que QString, pero 16 bytes corresponden a 16 caracteres.

QList<T> también utiliza ese algoritmo, pero 16 bytes corresponden a 16/elementos sizeof(T).

QHash<Key, T> es un caso totalmente distinto. QHash La tabla hash interna de <T> crece por potencias de dos, y cada vez que crece, los elementos se reubican en un nuevo cubo, calculado como qHash(clave) % QHash::capacity() (el número de cubos). Esta observación se aplica también a QSet<T> y QCache<Key, T>.

Para la mayoría de las aplicaciones, el algoritmo de crecimiento por defecto proporcionado por Qt es suficiente. Si necesitas más control, QList<T>, QHash<Key, T>, QSet<T>, QString, y QByteArray proporcionan un trío de funciones que te permiten comprobar y especificar cuánta memoria utilizar para almacenar los elementos:

• capacity() devuelve el número de elementos para los que se ha asignado memoria (para QHash y QSet, el número de buckets de la tabla hash).
• reserve(tamaño) preasigna explícitamente memoria para elementos de tamaño.
• squeeze() libera la memoria no necesaria para almacenar los elementos.

Si sabes aproximadamente cuántos elementos vas a almacenar en un contenedor, puedes empezar llamando a reserve(), y cuando termines de llenar el contenedor, puedes llamar a squeeze() para liberar la memoria extra preasignada.