CopperSpice API
1.7.3

The study of Time Complexity examines how long it will take for a operation to complete given a input size of n. For example, inserting an item in the middle of a QLinkedList takes the same amount of time, regardless of the size of the list. However, inserting an item in the middle of a QVector can be very slow if the QVector contains many items.
To describe algorithmic complexity the following terminology is used and is based on the "big O" notation.
The following table summarizes the algorithmic complexity of the sequential container classes. The notation of amortized behavior O(1) means if you call the function only once you might get O(n) behavior, however if you call it multiple times (e.g., n times) the average behavior will be O(1).
Index lookup  Insertion  Prepending  Appending  

QLinkedList  O(n)  O(1)  O(1)  O(1) 
QList  O(1)  O(n)  amortized O(1)  amortized O(1) 
QVector  O(1)  O(n)  O(n)  amortized O(1) 
The following table summarizes the algorithmic complexity of the associative container classes.
Key lookup  Insertion  

Average  Worst case  Average  Worst case  
QMap  O(log n)  O(log n)  O(log n)  O(log n) 
QMultiMap  O(log n)  O(log n)  O(log n)  O(log n) 
QHash  amortized O(1)  O(n)  amortized O(1)  O(n) 
QSet  amortized O(1)  O(n)  amortized O(1)  O(n) 
With QVector, QHash, and QSet, the performance of appending items is amortized O(log n). It can be brought down to O(1) by calling QVector::reserve(), QHash::reserve(), or QSet::reserve() with the expected number of items before inserting the items.
QVector<T>, QString, and QByteArray store their items contiguously in memory. QHash<Key, Val, Hash, KeyEqual> maintains a hash table whose size is proportional to the number of items in the hash. To avoid reallocating the data every time an item is added at the end of a container, these classes allocate extra memory each time the container needs to grow.
For most applications the default growing algorithm will be enough. If you need more control QVector<T>, QHash<Key, Val, Hash, KeyEqual>, QSet<T>, and QByteArray provide three methods which allow checking and specifying how much memory to allocate.
If you know the approximate number of items stored in a container, start by calling reserve(). When you are done populating the container call squeeze() to release the extra preallocated memory.