MyTetra Share
Делитесь знаниями!
Скорость выполнения операций для контейнеров QList, QLinkedList, QVector, QQueue, QStack
Время создания: 11.11.2019 12:16
Автор: xintrea
Текстовые метки: qt, контейнер, скорость, QList, QLinkedList, QVector, QQueue, QStack, QMap, QMultiMap, QHash, QSet
Раздел: Компьютер - Программирование - Язык C++ (Си++) - Библиотека Qt - Принципы написания кода
Запись: xintrea/mytetra_syncro/master/base/1573463812bmnem2qxze/text.html на raw.github.com

Последовательные контейнеры


В 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)



Существует следующая таблица соответствия ассоциативных контейнеров библиотеки 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.


Так же в этом разделе:
 
MyTetra Share v.0.59
Яндекс индекс цитирования