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.