1.02
Explanation of the contents of a topic page @ Week 1 Topic 1
Objectives: Adding, iterating, manipulating data in item containers
Comment: Attendees should realise it's totally ok to use standard containers. There are conversion functions between the standard and Qt item containers. The added-value of Qt containers is implicit sharing. It's efficient to take copies of huge containers, as long as the items are not changed, which will result to deep copy. Important learning objective is to do the iteration in the right way: non-mutable with simple range loop for (const ¬eConstRefToMyItem : container) and QMutableXXIterator for mutable iterating. These are typically the fastest ones.
- What are Containers?
- What are the Container classes?
- Is it OK to use standard containers?
- What is the added-value of Qt containers?
- How do I iterate the right way?
- What are assignable types?
- How to iterate containers efficiently (for-range loop + Java-like iterators)?
- How to use algorithms in container manipulation (because Qt algorithms are mostly depicted)?
!NB: The doc.qt.io Container page is pretty exhaustive. We may not need much more than a shorter introductory presentation here.
Qt Containers (vs standard Containers?)
http://doc.qt.io/qt-5/containers.html
The Qt library provides a set of general purpose template-based container classes. These classes can be used to store items of a specified type. For example, if you need a resizable array of QStrings, use QVector<QString>.
These container classes are designed to be lighter, safer, and easier to use than the STL containers. If you are unfamiliar with the STL, or prefer to do things the "Qt way", you can use these classes instead of the STL classes.
The container classes are implicitly shared, they are reentrant, and they are optimized for speed, low memory consumption, and minimal inline code expansion, resulting in smaller executables. In addition, they are thread-safe in situations where they are used as read-only containers by all threads used to access them.
For traversing the items stored in a container, you can use one of two types of iterators: Java-style iterators and STL-style iterators. The Java-style iterators are easier to use and provide high-level functionality, whereas the STL-style iterators are slightly more efficient and can be used together with Qt's and STL's generic algorithms.
Qt also offers a foreach keyword that make it very easy to iterate over all the items stored in a container.
Container classes
http://doc.qt.io/qt-5/containers.html#the-container-classes
Qt provides the following sequential containers: QList, QLinkedList, QVector, QStack, and QQueue. For most applications, QList is the best type to use. Although it is implemented as an array-list, it provides very fast prepends and appends. If you really need a linked-list, use QLinkedList; if you want your items to occupy consecutive memory locations, use QVector. QStack and QQueue are convenience classes that provide LIFO and FIFO semantics.
Qt also provides these associative containers: QMap, QMultiMap, QHash, QMultiHash, and QSet. The "Multi" containers conveniently support multiple values associated with a single key. The "Hash" containers provide faster lookup by using a hash function instead of a binary search on a sorted set.
As special cases, the QCache and QContiguousCache classes provide efficient hash-lookup of objects in a limited cache storage.
Containers can be nested. For example, it is perfectly possible to use a QMap<QString, QList<int>>, where the key type is QString and the value type QList<int>.
The containers are defined in individual header files with the same name as the container (e.g., <QLinkedList>). For convenience, the containers are forward declared in <QtContainerFwd>.
The values stored in the various containers can be of any assignable data type. To qualify, a type must provide a default constructor, a copy constructor, and an assignment operator. This covers most data types you are likely to want to store in a container, including basic types such as int and double, pointer types, and Qt data types such as QString, QDate, and QTime, but it doesn't cover QObject or any QObject subclass (QWidget, QDialog, QTimer, etc.). If you attempt to instantiate a QList<\QWidget>, the compiler will complain that QWidget's copy constructor and assignment operators are disabled. If you want to store these kinds of objects in a container, store them as pointers, for example as QList<QWidget *>.
Here's an example custom data type that meets the requirement of an assignable data type:
class Employee
{
public:
Employee() {}
Employee(const Employee &other);
Employee &operator=(const Employee &other);
private:
QString myName;
QDate myDateOfBirth;
};
If we don't provide a copy constructor or an assignment operator, C++ provides a default implementation that performs a member-by-member copy. In the example above, that would have been sufficient. Also, if you don't provide any constructors, C++ provides a default constructor that initializes its member using default constructors. Although it doesn't provide any explicit constructors or assignment operator, the following data type can be stored in a container:
struct Movie
{
int id;
QString title;
QDate releaseDate;
};
Some containers have additional requirements for the data types they can store. For example, the Key type of a QMap<Key, T> must provide operator<(). Such special requirements are documented in a class's detailed description. In some cases, specific functions have special requirements; these are described on a per-function basis. The compiler will always emit an error if a requirement isn't met.
Qt's containers provide operator<<() and operator>>() so that they can easily be read and written using a QDataStream. This means that the data types stored in the container must also support operator<<() and operator>>(). Providing such support is straightforward; here's how we could do it for the Movie struct above:
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;
}
The documentation of certain container class functions refer to default-constructed values; for example, QVector automatically initializes its items with default-constructed values, and QMap::value() returns a default-constructed value if the specified key isn't in the map. For most value types, this simply means that a value is created using the default constructor (e.g. an empty string for QString). But for primitive types like int and double, as well as for pointer types, the C++ language doesn't specify any initialization; in those cases, Qt's containers automatically initialize the value to 0.
Using standard containers
It's totally ok to use standard containers \:D/
Iterating correctly and efficiently
http://doc.qt.io/qt-5/containers.html#the-iterator-classes
http://doc.qt.io/qt-5/qtalgorithms.html#details
Assignable types
Algorithms in container manipulation
http://doc.qt.io/qt-5/containers.html#algorithmic-complexity