Для доступа к данным на основе поиска ключей стандартная библиотека C++ предлагает<std::set>,<std::map>,<std::multiset>и<std::multimap>. Они обычно реализуются с использованием сбалансированных двоичных деревьев, так что время поиска имеет логарифмическую сложность. Как правило, это нормально, но во многих случаях хеш-таблицаможет работать лучше, поскольку доступ к данным в среднем имеет постоянную сложность. В худшем случае сложность линейна, но этого редко и с некоторой осторожностью можно избежать.

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

С учетом этого в стандарт C++ были добавлены неупорядоченные ассоциативные контейнеры. Это реализация контейнеров, описанных в C++11, с некоторымиотклонениями от стандартадля работы с компиляторами и библиотеками, не относящимися к C++11.

<unordered_set>и<unordered_multiset>определены в заголовке<<boost/unordered_set.hpp>>

namespace boost {
    template <
        class Key,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
    class unordered_set;
    template<
        class Key,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
    class unordered_multiset;
}

<unordered_map>и<unordered_multimap>определены в заголовке<<boost/unordered_map.hpp>>

namespace boost {
    template <
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
    class unordered_map;
    template<
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
    class unordered_multimap;
}

При использовании Boost. TR1, эти классы включены из<<unordered_set>>и<<unordered_map>>, с классами, добавленными к пространству имен<std::tr1>.

Контейнеры используются аналогично обычным ассоциативным контейнерам:

typedef boost::unordered_map<std::string, int> map;
map x;
x["one"] = 1;
x["two"] = 2;
x["three"] = 3;
assert(x.at("one") == 1);
assert(x.find("missing") == x.end());

Но поскольку элементы не упорядочены, выход:

BOOST_FOREACH(map::value_type i, x) {
    std::cout<<i.first<<","<<i.second<<"\n";
}

может быть в любом порядке. Например, это может быть:

two,2
one,1
three,3

Для хранения объекта в неупорядоченном ассоциативном контейнере требуется как ключевая функция равенства, так и хеш-функция. Объекты функции по умолчанию в стандартных контейнерах поддерживают несколько основных типов, включая целые типы, типы с плавающей запятой, типы указателей и стандартные строки. С самого начала. Неупорядоченное использование<boost::hash>также поддерживает некоторые другие типы, включая стандартные контейнеры. Чтобы использовать любые типы, не поддерживаемые этими методами, вы должнырасширить Boost. Хэш для поддержки типаили использования собственных предикатов равенства и хеш-функций. См. разделПредикаты равенства и функции хешированиядля более подробной информации.

Есть и другие отличия, которые перечислены в разделеСравнение с ассоциативными контейнерами.