Bool operator() ( ChessCoordinate _c1, ChessCoordinate _c2 ) const

{

if( _c1.m_yPosition < _c2.m_yPosition )

return true;

else if( _c1.m_yPosition == _c2.m_yPosition )

return_c1.m_xPosition < _c2.m_xPosition;

Else

return true;

}

};

Создание объектов-отображений с пользовательскими компараторами выглядит так:

std::map< ChessCoordinate, Figure *, ChessCoordinateComparatorXY > chessDesk;

// ^ ^ ^

// тип ключа тип значения тип компаратора

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

template<
typenameKey, // тип ключа
typenameValue, // тип значения
typenameCompare = std::less< Key> // тип компаратора, < по умолчанию
>

classmap { /* … */ };

Контейнер std::map также содержит специальные формы конструкторов, принимающие объект-компаратор. Такая возможность может понадобиться для более сложных компараторов, имеющих вспомогательные переменные, требующие особой инициализации, передачи аргументов. В конструкторах std::map, не принимающих компаратор, создается собственный объект-компаратор с вызовом конструктора по умолчанию. Копию используемого отображением объекта-компаратор можно получить при помощи метода key_comp(), что может быть полезным для извлечения данных из компаратора, если он собирает какую-либо статистику по ходу работы.

Несколько сложнее использовать в качестве компаратора лямбда-выражения. Для инстанцирования std::map необходимо явно указывать тип компаратора. Тип лямбда-выражения не оговаривается стандартом и отдается на откуп конкретных компиляторов. Прямого средства для внедрения лямбда-выражений в качестве компараторов в стандартной библиотеке не предусотено.

Один из возможных обходных вариантов - использование в качестве типа компаратора универсальной вызываемой сущности std::function с идентичной сигнатурой:

typedefstd::map<
ChessCoordinate,
Figure *,
std::function< bool( ChessCoordinate, ChessCoordinate ) >

> ChessDesk;

Чтобы пристыковать конкретное лямбда-выражение, следует применить конструктор, принимающий объект-компаратор. В данном случае передаваемое единственным аргументом конструктора лямбда-выражение будет успешно преобразовано к типу std::function:

ChessDesk deskXY(
[] ( ChessCoordinate c1, ChessCoordinate c2 ) ->bool
{

// ... тело компаратора ...

}
);

Однако, следует четко осознавать, что средство std::function вносит дополнительный уровень косвенности, что снижает производительность отображения. В частности, через барьер std::function не может пройти встраивание функций (inline) и другие оптимизации для шаблонного кода.

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

template< typenameKey, typenameValue, typenameCompare >

std::map< Key, Value, Compare >
make_map ( constCompare & c )
{

returnstd::map< Key, Value, Compare >( c );

}

А теперь применим его для создания отображения с нужным компаратором-лямбдой:

autochessDesk = make_map< ChessCoordinate, Figure * >(

[] ( ChessCoordinate c1, ChessCoordinate c2 ) ->bool
{

// ... тело компаратора ...

}
);

Безусловно, шаблон make_map можно написать один раз и применять многократно.

Еще один возможный вариант стыковки основан на операторе decltype:

autocomparator = [] ( ChessCoordinate c1, ChessCoordinate c2 ) ->bool
{

// ... тело компаратора ...

}

std::map<
ChessCoordinate,
Figure *,
decltype( comparator )
> chessDesk( comparator );

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

Std::unordered_map

Контейнер std::unordered_map во многом похож на std::map, и большинство конструкторов, методов между ними совпадает. В частности, синтаксис поиска, итерирования, вставки, удаления, перегруженный оператор индексной выборки - полностью совпадет с std::map.

#include <unordered_map>

std::unordered_map< std::string, double > countriesSquare;

^ ^

тип тип

ключа значения

Основное отличие состоит в базовой структуре данных: std::unordered_map основан не на бинарных деревьях поиска, а на хэш-таблицах. Отсюда вытекают свойства данного контейнера:

● операции поиска, вставки и удаления обладают константной вычислительной сложностью (при условии минимальной частоты коллизий);

● итерирование содержимого хэш-таблицы происходит в непредсказуемом порядке.

Контейнер std::unordered_map следует выбирать всегда, когда для отображения не важен порядок итерирования, поскольку в общем случае отображение std::map уступает std::unordered_map по производительности (логарифмическая вычислительная сложность всегда хуже константной для достаточно больших контейнеров). Если же порядок перебора играет для программиста роль, контейнер std::unordered_map вообще не пригоден.

Так как элементы хэш-таблиц не упорядочены, в std::unordered_map отсутствуют специфические для контейнеров на основе бинарных деревьев поиска методы lower_bound, upper_bound и equal_range.

В противовес, имеется ряд дополнительных методов, специфических для работы хэш-таблиц и их внутренних ячеек, или корзин (buckets):

● методы begin/end и аналогичные дополнительно существуют в варианте, принимающем целое число, представляющее номер корзины;

● метод bucket_count() возвращает текущее число выделенных корзин;

● метод bucket_size(int) возвращает количество элементов, хранящихся в конкретной корзине;

● метод bucket(K) возвращает номер корзины, в которой хранится указанный ключ;

● метод load_factor() возвращает среднюю загруженность корзин в виде числа float;

● метод max_load_factor() возвращает максимально допустимую загруженность корзин в виде числа float, при превышении которой хэш-таблица должна автоматически вырасти в размере;

● метод max_load_factor( float ) устанавливает пользовательский лимит для максимально допустимой загруженности корзин;

● метод rehash(int) вручную назначает для хэш-таблицы указанное число корзин, при этом происходит повторное хэширование, и все итераторы становятся недействительными;

● метод reserve(int), требующий от таблицы создать столько корзин, чтобы в них без нарушения максимально допустимой загруженности поместилось указанное число элементов.

Итераторы std::unordered_map также относятся к категории двунаправленных. Итераторы могут стать недействительными не только при удалении элементов, но и в результате любой вставки либо вызова служебного метода, приводящего таблицу к росту и повторному хэшированию.

В отличие от std::map, контейнер std::unordered_map не требует от типа ключей наличия оператора < или аналогичного компаратора. Вместо них ожидается:

● унарный функтор для хэширования ключей, который должен возвращать хэш-код типа size_t;

● наличие возможности сравнения на равенство (==) напрямую либо через предикат.

Для всех встроенных типов, а также для std::string и ряда других библиотечных классов, средство для хэширования уже предусмотрено - эту роль играет функтор std::hash. Для сравнения на равенство также используется стандартный функтор std::equal_to:

template<
typenameKey, // тип ключа
typenameValue, // тип значения
typenameHash = std::hash< Key > // функтор для хэширования
typenameKeyEq = std::equal_to< Key > // предикат сравнения на равенство ==
>

classunordered_map { /* … */ };

Чтобы получить возможность использования собственных классов в качестве ключей контейнера std::unordered_map, необходимо доопределить соответствующие функторы. Ниже приведен пример функтора хэширования для координат шахматной доски:

structChessCoordinateHasher

{

size_t operator() ( ChessCoordinate c ) const

{

staticstd::hash< short> s_shortHasher;

returns_shortHasher( cc.m_x ) << 4 + s_shortHasher( cc.m_y );

}

};

В основе функтора хэширования лежит стандартный функтор std::hash< short >. Чтобы получить один результирующий хэш-код для двух координат, комбинируется результат поэлементного хэширования. Для комбинирования здесь используется сложение и сдвиг на 4 бита, поскольку типичная шахматная доска состоит из клеток с номерами 1..8, а для представления числа 8 необходимо 4 значащих бита. Можно определить любую другую логику хэширования и комбинирования, обеспечивающую свойства хэш-функций (повторяемость для одинаковых ключей, равномерное распределение значений).

Также понадобится определить предикат для сравнения ключей, либо перегрузить оператор сравнения на равенство координат:

bool operator== ( ChessCoordinate cc1, ChessCoordinate cc2 )

{

returncc1.m_x == cc2.m_x && cc1.m_y == cc2.m_y;

}

Теперь можно использовать хэш-таблицу для шахматных координат:

std::unordered_map< ChessCoordinate, Figure *, ChessCoordinateHasher > desk;

// ^ ^ ^

// тип ключа тип значения тип функтора хэширования

Стыковка лямбда-выражений и std::unordered_map ничем не отличается от способов, ранее приведенных для отображений std::map.