Последовательные контейнеры
В Qt имеется несколько последовательных контейнеров. Их внутренняя реализация отличается по скорости выполнения для разных видов действий. По следующей таблице можно примерно оцентить, в каких случаях какой контейнер лучше всего использовать.
Скорость выполнения операций для последовательных контейнеров
|
Контейнер |
Доступ |
Вставка/Удаление |
Добавление
в конец |
Добавление
в начало |
Проверка значения через метод contains() |
|
QList
QQueue |
Быстро
O(1) |
Медленно
O(n) |
Быстро
O(1) |
Быстро
O(1) |
O(n) ? |
|
QVector
QStack |
Быстро
O(1) |
Медленно
O(n) |
Быстро
O(1) |
Медленно
O(n) |
O(n) ? |
|
QLinkedList |
Медленно
O(n) |
Быстро
O(1) |
Быстро
O(1) |
Быстро
O(1) |
O(n) ? |
Примечание: как видно из данной таблицы, популятрый контейнер QList - это совсем не то же самое, что контейнер list в библиотеке STL. Аналогом stl::list в Qt является QLinkedList. А контейнер QList - это нечто среднее между вектором и списком, причем у него быстрый доступ к произвольному элементу (что довольно странно для списка) и при этом медленные вставка/удаление (что тоже довольно странно для списка).
По сути, отличие между QVector и QList в том, что в QList оптимизирована операция добавления в начало списка по сравнению с QVector, а в остальном они схожи.
Существует следующая таблица соответствия последовательных контейнеров библиотеки Qt и STD:
|
Qt |
STL |
|
- |
std::array |
|
QVector |
std::vector |
|
- |
std::deque |
|
QLinkedList |
std::list |
|
QList |
- |
|
- |
std::forward_list |
Ассоциативные контейнеры
Для ассоциативных контейнеров имеется следующая таблица скорости выполнения основных действий:
|
Контейнер |
Доступ по ключу |
Вставка |
|
Среднее |
Самое медленное |
Среднее |
Самое медленное |
|
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 |
Amortised O(1) |
O(n) |
Amortised O(1) |
O(n) |
|
QSet |
Amortised O(1) |
O(n) |
Amortised O(1) |
O(n) |
Что такое Amortised O(1) ? Это ожидаемая сложность, которая в большинстве случаев будет O(1) хотя теоретически возможна деградация до O(n) в худшем случае, но это редко встречается на практике.
Существует следующая таблица соответствия ассоциативных контейнеров библиотеки Qt и STD:
|
Qt |
STL |
|
- |
std::set |
|
QSet |
std::unordered_set |
|
- |
std::multiset |
|
- |
std::unordered_multiset |
|
QMap |
std::map |
|
QMultiMap |
std::multimap |
|
QHash |
std::unordered_map |
|
QMultiHash |
std::unordered_multimap |
Здесь тоже следует обратить внимание, что контейнер QSet - это не то же самое, что обычный std::set.
