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

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

Имея это в виду, не упорядоченные ассоциативные контейнеры были добавлены в стандарт 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, эти классы включены из <Неупорядоченные_set> и <неупорядоченные_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.Unordered использует boost::hash, он также поддерживает некоторые другие типы, включая стандартные контейнеры. Чтобы использовать любые типы, не поддерживаемые этими методами, вы должны расширить скорость. Hash для поддержки типа или использования ваших собственных целевых принципов равенства и хэш-функций. Дополнительные подробности см. в разделе Показатели качества и функции хэша.

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