Неупорядоченные контейнеры

Неупорядоченные контейнеры являются разновидностью хеш-таблиц. В С++11 представлены следующие типы:

• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset

Эти классы должны называться hash_map и т.п., но поскольку этими именами очень часто злоупотребляют, то при выборе новых имен комитет решил остановиться на unordered_map и т.д. как на наименьшем зле. “unordered” в названии классов говорит об отличиях между map и unordered_map: перебор элементов объекта типа map происходит в порядке, зависящем от оператора сравнения (по умолчанию используется <), в то время как значения в unordered_map не должны содержать оператор сравнения и хеш-таблица по своей природе не упорядочена. И наоборот, элементам, хранящимся в map не требуется хеш-функция.

Основная идея сводится к тому, чтобы использовать unordered_map в качестве более оптимизированной версии map, когда такая оптимизация возможна и обоснована. Например:

map< string, int> m {

{" Dijkstra", 1972}, {" Scott", 1976},

{" Wilkes", 1967}, {" Hamming", 1968}

};

m[" Ritchie" ] = 1983;

for(auto x: m) cout < < '{' < < x.first < < ', ' < < x.second < < '}';

unordered_map< string, int> um {

{" Dijkstra", 1972}, {" Scott", 1976},

{" Wilkes", 1967}, {" Hamming", 1968}

};

um[" Ritchie" ] = 1983;

for(auto x: um) cout < < '{' < < x.first < < ', ' < < x.second < < '}';

Итератор объекта m будет перебирать элементы в алфавитном порядке, а итератор объекта um – нет (если только не по чистой случайности). Процессы поиска элементов в m и um абсолютно различны. Поиск в m осуществляется за log2(m.size()) сравнений, в то время как поиск в um приводит к одному вызову хеш-функции и одной или более проверке равенства. Для нескольких элементов (скажем, для нескольких десятков), сложно сказать, какой из этих вариантов будет работать быстрее. Для большого количества элементов (например, если речь идет о тысячах) - поиск в unordered_map может быть значительно быстрее чем в map.

Продолжение следует.

См. также:

• Standard: 23.5 Unordered associative containers.

std:: tuple

Определен в < tuple>. Представляет собой упорядоченную последовательность из N значений, где N является константой от 0 до большого значения, зависящего от реализации. Вы можете рассматривать кортеж (tuple) как неименованную структуру, члены которой соответствуют типам элементов кортежа. Следует отметить, что элементы в tuple хранятся компактным образом; кортеж не является связным списком.

Типы элементов кортежа могут задаваться явно, а могут выводиться (при вызове make_tuple()), доступ к элементам осуществляется с помощью индекса (начинается с 0) путем вызова метода get():

tuple< string, int> t2(" Kylling", 123);

// t будет типа tuple< string, int, double>

auto t = make_tuple(string(" Herring"), 10, 1.23);

string s = get< 0> (t);

int x = get< 1> (t);

double d = get< 2> (t);

Кортежи используются (явно или неявно) для хранения гетерогенного списка элементов, известного во время компиляции, и когда нет желания определять для этого именованный класс. Например, tuple используетсядля хранения элементоввнутри std:: function и std:: bind.

Наиболее часто используется кортеж из двух элементов, т.е. пара (pair). Однако пара напрямую поддерживается классом std:: pair из стандартной библиотеки(20.3.3 Pairs). pair может использоваться для инициализации кортежа, но обратное преобразование невозможно.

Операторы сравнения (==,! =, <, < =, > и > =) определены для кортежей совместимых типов.

См. также:

• Standard: 20.5.2 Class template tuple
• Variadic template paper
• Boost:: tuple