QMap против класса QList в структуре Qt

Question

Я пытаюсь решить, использовать ли класс QList или QMap в некоторых моих будущих проектах Qt.Чтобы определить лучший выбор для меня, я хотел бы определить некоторые из их сходств и некоторые из их различий, чтобы понять, что лучше всего работает в определенных случаях.Верно ли мое понимание этих сходств и различий?

Сходства:

• Оба являются контейнерами

• Оба содержат неупорядоченные данные

Различия:

• QMap имеет пары ключей-значений, в то время как QList имеет только значения

• QMap использует хеш-функцию для размещения значений в соответствующем индексе, тогда как QList просто добавляет записи

Есть ли еще элементы сходства и различия?

Я мог бы взглянуть на общие определения информатики, но где-то читал, что в структуре Qt могут быть нюансы.

Answer 1

QList и QMap отличаются способом организации данных.Это приводит к разной производительности и немного другому потреблению памяти (для большинства случаев использования последнее обычно не имеет значения).Вы можете найти вычислительную сложность в документации Qt .Если вы храните много элементов, это может иметь большое значение.Подумайте о том, как часто вы хотите получать доступ к данным при выборе контейнера (поиск или вставка, а не удаление).

[Имейте в виду, однако, что алгоритмическая сложность является теоретическим свойством, которое полезно только для большихп.На практике линейный поиск по массиву с небольшим количеством элементов (<1000) часто превосходит списки / деревья из-за <a href="https://en.wikipedia.org/wiki/Locality_of_reference" rel="nofollow noreferrer"> местоположения ссылки .Если вам небезразлична производительность, не угадывайте, всегда измеряйте.]

Оба содержат неупорядоченные данные

На самом деле это не так для QMap.QMap реализован в виде самобалансирующегося бинарного дерева поиска , которое представляет собой отсортированную структуру данных.

Кстати: вы часто можете реализовать свой код универсальным способом, который облегчает переключениепозже к другому типу контейнера (например, если шаблон доступа изменяется или ваши предположения оказываются неверными).Использование auto может помочь сделать это безболезненным.

Answer 2

Я думаю, что вы сделали несколько ошибок в отношении QMap.

QMap сохраняет его содержимое всегда отсортированным по ключу. См. Документация здесь . Так что это не так, как вы упомянули.

Тогда QMap не использует хеш-функцию. Он хранит элементы, сравнивая их с operator<().

На самом деле, вы сбиваете с толку QMap и QHash. QHash действительно произвольно упорядочен, и его элементы должны обеспечивать operator==() для сравнения и qHash(key) функцию.

Думаю, это поможет вам лучше понять, что вам нужно использовать.