Russian Qt Forum

Привет, друзья!
Пытаюсь более углублённо познать cpp но никак не могу разобраться с некоторыми моментами. Попытавшись заглянуть под капот STL просто увидел кучу буковок... В связи с этим прошу вас помочь.
Как я понял, принцип работы map и hash_map примерно одинаковый, только в первом случае идет дополнительная проверка ключей с помощью operator<(), что даёт нам упорядоченность по алфавиту. В hash_map же используется operator==().
Первое, что здесь не понятно - это объявления (переписываю из книжки Страуструпа)

C++ (Qt)
template<class Key, class T, class Cmp=less<Key>, class A=allocator<pair<const Key,T> > >
class std::map
{
    // ...
};
template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<pair<const Key, T> > >
class hash_map
{
    // ...
};

кто такие less, Hash и equal_to? Я это расценил как имена неких функций, объявление которых я не нашёл.

Также мне никак не разобраться в принципе хранения. Для hash_map написано следующее:

C++ (Qt)
class hash_map
{
    // ...
vector<Entry> v;          // истинные входы
vector<Entry*>b;         // хэш-таблица: указатели внутрь v
    // ...
};

И приведён рисунок
(http://i9.pixs.ru/storage/1/3/9/Untitledpn_8879375_15670139.png)
Мне не совсем понятно назначение b. Почему бы просто не иметь массив структур Entry?

Нашёл в STL std::less. Это структура наследованная от std::binary_function. У less определена функция

C++ (Qt)
bool operator()(x,y)

. Насчёт массива указателей понял, что вызывается хэш-функция, которая предоставляет некий uchar, остаток от деления которого на размер массива будет необходимый индекс указателя. По указателю мы получаем список Entry и ищем нужный нам ключ.

Устройство map и hash_map совершенно/принципиально различно. Как Вы знаете, hash хранит данные "по корзинам" (bins), основная идея - спрыгнуть на нужную корзину по остатку от деления. Но надо как-то хранить данные и в каждой корзине. Поэтому сами данные хранятся в первом контейнере "беспорядочно", но имеют указатели на предыдущий и следующий в той же корзине. А головы этих списков хранятся в контейнере указателей

Точнее нужный эл-т оператором ==. (хеш-ключ не уникален)

Да, с этим я разобрался. А что же в случае с map?

Там гораздо более сложная организация данных известная как "красно-черное дерево"

Слышал о таком. Спасибо.

Для Qt контейнеров есть простая вводная статья:
http://doc.qt.digia.com/qq/qq19-containers.html

Спасибо, Old. Я понял исходя из картинки, что QMap производит поиск как по методу половинного деления.
На некоторых картинках фигурируют QBasicAtomic. Из описания не понял назначения. Как вектор можно использовать в мультипоточности?

Атомарный там счетчик, для организации потоко-безопасного implicit share.
Это позволяет безопасно передавать коллекции между потоками, без реального копирования данных.