Russian Qt Forum

Здравствуйте. Имеются разные QHash и QMap (ключи – числа, строки, есть даже пара строк, всего контейнеров чуть больше 10), в которых хранятся как «небольшие» структуры (3-5 полей), так и «большие» (15-20 полей). Количество элементов не очень большое – примерно от 500 до 2500. Сейчас доступ к контейнерам осуществляется через статические методы класса (сам контейнер является статической переменной-неуказателем в методе), возвращается указатель на контейнер.

Раньше я получал доступ к элементам по ключу через value(), но этот метод возвращает копию объекта, а не ссылку. Недавно поменял это всё на operator[] чтобы получать ссылки и не расходовать память на ненужные копии, но сейчас заметил, что в документации не рекомендуют использовать такой подход:
но это связано лишь со случаями когда ключа не существует, а у меня такие ситуации очень и очень маловероятны (все ключи известны заранее). Но является ли это хорошим подходом? Да и код имеет вид MyClass::myContainer()->operator[](key).someField (будет ли лучше/быстрее (*MyClass::myContainer())[key].someField? или лучше возвращать ссылки из методов вместо указателей?).

Заметил ещё методы find() и constFind(), возвращающие итераторы, из которых уже можно получить ссылку на значение, но будет ли это эффективнее, чем operator[]?

А может выгоднее хранить в контейнерах не сами элементы, а лишь указатели на них? Да, и данные в контейнерах не меняются и «живут» на протяжении всего жизненого цикла программы, если это имеет значение.

Я бы хранил в ассоциативных контейнерах лишь указатели, а сами элементы в списке, либо вообще просто в массиве. Если количество элементов известно заранее и не предполагается изменений, то массив лучше организовать в стеке. Будет ещё чуть быстрее. Я для себя проводил сравнение. Стековый вариант на 100000 lookup'ов выиграл на моей машине 10-20 мс.

хранить массив в стеке не получится, т.к. хоть количество элементов и известно, но оно не является константой, забитой в код.

а зачем вообще дополнительно хранить элементы в массиве? почему нельзя сделать чтобы они просто «висели в воздухе»?

C++ (Qt)
QHash<int, Item *> hash;
Item *item = new Item;
...
hash[0] = item;

из-за расположения элементов массива в памяти подряд?

Значит больше подходит под мою задачу: у меня фиксированное кол-во элементов. Я организовывал даже compile-time контейнер, но из-за того, что строковые ключи приходилось писать в виде "'m','y','k','e','y'", отказался от этой затеи - уж очень коряво выглядело. Впрочем, скорость lookup'а была очень высокой.

Это для стекового варианта. В принципе, то что ключи будут меняться - не проблема, главное знать заранее их максимально возможное количество. Ну и конечно согласиться с некоторым перерасходом памяти. В общем нужно выбрать что важнее: скорость или компактность.

Qt-шные контейнеры используют выравнивание в памяти для элементов.

меня больше интересует не скорость или расход памяти на хранение (с этим всё нормально), а именно вытаскивание элемента из контейнера. значит если хранить в контейнерах указатели (которые «висят в воздухе»), то можно спокойно использовать value() и ни о чём не беспокоиться?

Я как раз и говорил о lookup'е (поиске элемента) с выдачей результата.

Копирование указателя конечно дешевле, нежели копирование объекта какого-либо класса. И преимуществ от выравнивания памяти для выдачи элемента нет никаких: всё равно будет вызван конструктор копирования. Честно говоря, не могу понять, почему QHash не предоставляет возврат по ссылке. Хотя бы для версии value() с дефолтным значением могли бы сделать.

З.Ы. Придётся "вручную" удалять объекты из контейнера, если он содержит лишь указатели.

хорошо, спасибо

Это имеет значение. Ссылка возвращенная из QHash станет невалидной при добавлении новых элементов (rehash). Про QMap не знаю а вот std::map все хорошо - адрес не изменится при добавлении, и это бывает важно.

Если операции вставки-удаления крайне редки, то вообще имеет смысл хранить сортированный массив указателей и использовать binary_search, lower_bound. Это экономит память значительно, т.к. ассоциативный контейнер требует довольно жирных доп данных для каждого элемента. Поиск в сортированном массиве может и проигрывает хешу, но может и нет (напр хеш-ключ мудреный). Но во всяком случае он несколько быстрее чем в std::map/set

Если не хочется уходить от стандартных, то (для чтения) грамотно использовать итератор и потом возвращать указатель на данные или NULL

std::set использует бинарное дерево, так что поиск такой же как у упорядоченного массива.

после того, как перевел все контейнеры на хранение указателей, вспомнил наконец почему я отказался от этой идеи в начале: периодически я обращаюсь к несуществующим ключам в других структурах данных, получаяя default value, у которой поля-числа инициализированы заданным значением, что есть правильно. а вот в случае с указателями идет обращение к нулевому указателю, где программа и падает... хорошо, что существуют системы контроля версий :)