оптимальный доступ к элементам ассоциативных контейнеров

[kambala]

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

Раньше я получал доступ к элементам по ключу через value(), но этот метод возвращает копию объекта, а не ссылку. Недавно поменял это всё на operator[] чтобы получать ссылки и не расходовать память на ненужные копии, но сейчас заметил, что в документации не рекомендуют использовать такой подход:

In general, we recommend that you use contains() and value() rather than operator[]() for looking up a key in a hash. The reason is that operator[]() silently inserts an item into the hash if no item exists with the same key (unless the hash is const)

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

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

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

[alexis031182]

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

[kambala]

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

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

Код

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

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

[alexis031182]

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

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

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

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

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

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

[kambala]

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

[alexis031182]

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

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

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

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

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

[kambala]

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

[Igors]

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

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

А может выгоднее хранить в контейнерах не сами элементы, а лишь указатели на них?

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

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

[DmitryM]

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

[kambala]

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