Qhash?

[Soulq]

в ассистенте все есть 

Код:

// Here's an example QSet with QString values:

 QSet<QString> set;
// To insert a value into the set, use insert():

 set.insert("one");
 set.insert("three");
 set.insert("seven");
// Another way to insert items into the set is to use operator<<():
 set << "twelve" << "fifteen" << "nineteen";
// To test whether an item belongs to the set or not, use contains():

 if (!set.contains("ninety-nine"))

Да-да я уже разобрался, еще раз спасибо.
 

[Soulq]

А какая скорость поиска элемента у qset?

[twp]

http://doc.qt.nokia.com/latest/containers.html#algorithmic-complexity

[Igors]

А какая скорость поиска элемента у qset?

http://doc.qt.nokia.com/latest/containers.html#algorithmic-complexity

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

[twp]

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

[Igors]

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

Реально первая очередь будет и последней, а до размышлений дело не дойдет. Просто получена новая порция поверхностных знаний - вот и все. Понимаю что не нужно (да и невозможно) вникать во все до мелочей, многое надо просто использовать - это нормально. Но все же иногда интересно "а как же работает напр тот же QHash". Я открывал исходники но понял далеко не все.  Если можете объяснить принципиальный алгоритм на котором построен QHash - буду благодарен.

[Fat-Zer]

Реально первая очередь будет и последней, а до размышлений дело не дойдет. Просто получена новая порция поверхностных знаний - вот и все. Понимаю что не нужно (да и невозможно) вникать во все до мелочей, многое надо просто использовать - это нормально. Но все же иногда интересно "а как же работает напр тот же QHash". Я открывал исходники но понял далеко не все.  Если можете объяснить принципиальный алгоритм на котором построен QHash - буду благодарен.

всегда считал, что и там, и в QSet обычная хеш-таблица... или я не прав?

[Igors]

всегда считал, что и там, и в QSet обычная хеш-таблица... или я не прав?

Понятно что QSet сводится к тому же QHash. Понятно для чего нужен хеш и как его использовать. Я спрашиваю как он устроен. Ну напр. std::set - красно-черное дерево, поиск - спуск, вставка - балансировка. А здесь как?

[Fat-Zer]

Понятно что QSet сводится к тому же QHash. Понятно для чего нужен хеш и как его использовать. Я спрашиваю как он устроен. Ну напр. std::set - красно-черное дерево, поиск - спуск, вставка - балансировка. А здесь как?

большой массив, qHash вычисляет индекс в этом массиве, в котором должен хранится элемент. остаётся два вопроса:
1) что делать, если для нескольких элементов одинаковый индекс ака коллизии
2) когда расширять табицу
в общем тыц

[Igors]

большой массив, qHash вычисляет индекс в этом массиве, в котором должен хранится элемент. остаётся два вопроса:
1) что делать, если для нескольких элементов одинаковый индекс ака коллизии
2) когда расширять табицу
в общем тыц

А что собственно "тыц"?  Это из той же оперы что и предыдущая ссылка - хороша чтобы иметь общее понятие, но не более того. Кто такой "большой массив"? Что. если я вставил 2 ключа напр 1 и 10000, так уже 10К элементов полетели? Вряд ли, слишком тупо. Также популярный/практический вопрос - а почему итератор хеша не выдает элементы в отсортированном порядке (в отличие от QMap)?

[Soulq]

Вроде почитал сет ищет за логарифм

[Fat-Zer]

Кто такой "большой массив"?

обычный массив, алоцированный в хипе или список не очень больших массивов... это детали реализации... там хоть std::vector хоть QList может быть бекэндом... на самом деле используется обычный массив в хипе...

Что. если я вставил 2 ключа напр 1 и 10000, так уже 10К элементов полетели?

нет, хеш функция потом берётся по модулю количества значений в массиве.

Вряд ли, слишком тупо. Также популярный/практический вопрос - а почему итератор хеша не выдает элементы в отсортированном порядке (в отличие от QMap)?

очевидно - значения в хеш таблице хранятся по другому порядку (значения хеш функции % размер массива)

Вроде почитал сет ищет за логарифм

кто-то вас обманывает... QSet - ищет за о(1) в лучшем случае, и за о(n) в худшем... а вот std::set за лагорифм, ибо иснован на деревьях...

[twp]

Кому интересно вот описание реализации основных контейнеров Qt.