порядок размещение ключей в QHash<int, int>

[Karl-Philipp]

с праздниками всех!

Допустим, что есть хеш QHash<int, int>. В процессе работы с этим хешем заметил, что он размещает свои элементы не в произвольном порядке, как написано в Ассистанте, а в порядке возростания ключей.

Подскажите, пожалуйста, это недокументированное стандартное поведение для приведенного хеша или чистая случайность и в процессе работы есть возможность иного размещения ключей в хеше?

[Dendy]

Чистая случайность. Ключи располагаются не в собстенном порядке (ибо оператора < может даже не быть), а в порядке возрастания qHash( ключ ) % QHash::capacity().

[Rcus]

не совсем случайность для типов данных размером <= sizeof(uint) функция qHash возвращает значение аргумента

[Dendy]

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

[Karl-Philipp]

Друзья!
Мне надо следующее: вытягивать из хеша ключи в порядке возрастания. Для этого я хочу создать дополнительный контейнер QList (вытянуть туда все ключи и отсортировать), а потом, пробегаясь по элементам этого контейнера, доставать их из хеша.
Может есть менее затратный вариант, чем создавать дополнительный контейнер?
Ключей в хеше много (в пределах милиона).

[ритт]

QMap. хранит элементы в порядке возрастания значения ключа.
или я что не так понял?

[Karl-Philipp]

элементов очень много (около миллиона). На определенном этапе работы программы хеш часто используется для поиска ключей, вставки новых, а в документации написано:
>> QHash provides faster lookups than QMap.
Вот и был выбран QHash.

[Dendy]

А результирующая задача то какая? Что с этим сортированым списком потом делать?

[Karl-Philipp]

А результирующая задача то какая? Что с этим сортированым списком потом делать?

Чуть подробнее:
1) есть хеш:
QHash((1, 5)(2, 3)(4, 2)(4, 1)(7, 2)(5, 1))
2) мне надо вытягивать ключи в порядке возрастания и делать некоторые преобразования с другими контейнерами на основе вытянутого ключа и значения.
(на данном этапе это и есть результирующая задача)

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

[Dendy]

Офигенно развёрнутое обьяснение задачи. То что вытягивать ключи в опрядке возрастания нужно для того чтобы потом что-то с ними делать и так ясно. Иначе вы бы этим не занимались. Под "задачей" понимается нечто большее. Попробуйте обьяснить копнув на один уровень вглубь. Что именно это за индексы, что физически из себя представляет сортированый список, насколько часто это нужно делать.

[Karl-Philipp]

разворачиваю постановку задачи :-)

есть следующая основная структура данных:
QHash<int, QHash<int, class T1> > someHash;
надо извлекать значения (value - хеши второго уровня) из каждого ключа первого уровня.

Порядок извлечения value должен основываться на количестве значений (хешей второго уровня). Хеши должны извлекаться в порядке возрастания их количеств для данного ключа :-)

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

Создаю дополнительный контейнер QList (вытягиваю туда все ключи (количества хешей второго уровня в основной структуре) и сортирую). Затем, пробегаясь по элементам этого контейнера, достаю значения, представляющие собой ключи из вспомагательного хеша и обращаюсь в основную структуру данных для осуществления нужных мне преобразований.

извините :-)

[Dendy]

У меня подозрение что вам здесь нужен не QHash, а специализированный контейнер для таких операций. Или база данных.

[Karl-Philipp]

если быть более точным, то основная структура выглядит так:
QHash<int, QHash<int, QHash<int, int> > > myHash;

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

Значения первых уровней структуры данных периодически удаляются и добавляются, не знаю (не имею опыта работы с базами), будет ли обращение к базе и преобразования в ней настолько быстрыми, как к структуре данных, основанной на хеше?

Dendy, уточните, пожалуйста про специализированный контейнер, как примерно может выглядеть этот класс?

по идее, предложенный мною механизм должен работать достаточно быстро. Правда памяти он будет откусывать достаточно много :-)

[Dendy]

Не буду вводить в заблуждение, сам работал достаточно посредственно с чёрно-красными деревьями, погуглите, возможно их алгоритмы именно то что вам нужно. Хотя если у вас миллионы элементов, то это уже задача для базы данных. QHash спроектирован не для этого. Он работает медленно путём прямого перебора или есть память, выделяемую под букеты. Для нескольких элементов (возможно, тысяч) это терпимо. Собственно он предназначен для избавления программиста от геммороя в простых случаях.

[Karl-Philipp]

про красно-черные деревья почитал в Wikipedia - Red-black tree интересная идея, но, просветите меня, пожалуйста по такому поводу:

на этой же странице (про красно-черные деревья) нашёл:
>> In the C++ Standard Template Library, the containers std::set<Value> and std::map<Key,Value> are often based on red-black trees
вывод - поиск происходит достаточно быстро (используется же метод красно-черных деревьев!)

В Ассистанте про QMap написано, что поиск ключа медленнее, чем в QHash (для QMap - Average O(log n), к слову, для QHash время поиска - Average O(1) )

выходит, что std::map и QMap имеют разную реализацию, если в случае map (STL) мы получаем быстрый поиск, а в случае QMap - медленный?

---------------------------

...Хотя если у вас миллионы элементов, то это уже задача для базы данных...

про базы подумаю, почитаю еще.

Общее (суммарное) количество элементов в моём случае в пределах одного миллиона. Это означает, что количество всех хешей в основной структуре около миллиона, а я писал только про верхний уровень - извините ошибся. В каждом хеше-значении на первом уровне основной структуры данных (QHash<int, QHash<int, QHash<int, int> > >) как раз будет в пределах 100000 элементов.

QHash спроектирован не для этого. Он работает медленно путём прямого перебора или есть память, выделяемую под букеты. Для нескольких элементов (возможно, тысяч) это терпимо.

Про память особо не заморачиваюсь, пусть ест :-)
почитал в Интернете, народ пишет, что STL-ий контейнер еще хорошо справляется с сотней тысяч объектов, но не больше. Что скажете, будет ли QHash справляться с сотней тысяч объектов так же как и STL контейнер?

Я все это веду к тому, что может, все-таки можно использовать предложенную мною структуру хешей? :-)