Компараторы для ключей в std::map
Свойства отображений std::map вытекают из обеспечивающей базовой структуры данных - сбалансированных бинарных деревьев поиска (Balanced BST). Чаще всего реализация контейнера std::map основывается на алгоритме красно-черных деревьев (red-black trees), гарантирующем разницу высоты поддеревьев не более чем в 2 раза за счет своевременных вращений.
Отсюда вытекает обязательное требование к типу ключа: возможность сравнения ключа при помощи оператора < (меньше). Это требование аналогично требованиям алгоритмов сортировки. Для каждой пары ключей необходимо однозначное отношение порядка. Разумеется, такой оператор доступен для всех встроенных типов, перечислений, для строк std::string и даже для контейнеров-последовательностей из стандартной библиотеки.
Чтобы сделать ключом пользовательский класс, необходимо определить либо глобальный, либо внутриклассовый вариант оператора <, в зависимости от удобства. Пусть следующий класс представляет собой координаты клеток шахматной доски:
structChessCoordinate
{
// Номера клеток по горизонтали и вертикали
const shortm_xPosition, m_yPosition;
// Конструктор
ChessCoordinate ( short_xPosition, short_yPosition )
: m_xPosition( _xPosition ), m_yPosition( _yPosition )
{
// Инвариант: координата X должна находиться в интервале от 1 до 8
if( m_xPosition < 1 || m_xPosition > 8 )
throwstd::logic_error( “X coordinate out of range [1:8]” );
// Инвариант: координата Y должна находиться в интервале от 1 до 8
if( m_yPosition < 1 || m_yPosition > 8 )
throwstd::logic_error( “Y coordinate out of range [1:8]” );
}
// Перегруженный оператор “меньше” - необходим для std::map
Bool operator< ( ChessCoordinate c ) const
{
if( m_xPosition < c.m_xPosition )
return true;
else if( m_xPosition == c.m_xPosition )
returnm_yPosition < c.m_yPosition;
Else
return true;
}
};
Поскольку в данном пользовательском типе перегружен оператор сравнения по <, его можно использовать в качестве ключа для отображения std::map:
classFigure;
std::map< ChessCoordinate, Figure * > chessDesk;
// ^
// тип ключа имеет перегруженный оператор <
Очевидно, при итерировании такого отображения пары ключ-значение будут упорядочены в соответствии с семантикой перегруженного оператора <. В частности, главным критерием для порядка будет номер клетки на доске по горизонтали, а при равных горизонтальных номерах будут учитываться номера клеток по вертикали.
Оператор < имеет смысл перегружать только для тех типов, где имеется однозначное порядковое отношение. В нынешнем виде для координат на шахматной доске оператор < представляет лишь один из вариантов сравнения.. В одной ситуации может понадобиться порядок с X-координатой в качестве приоритетного признака, в другой ситуации - должна доминировать Y-координата, в третьих - может понадобиться обратить порядок вспять.
Чтобы учесть такие разные варианты, для std::map предусмотрен специальный третий аргумент шаблона, называемый компаратором (comparator). Компаратор - это бинарный предикат, который, получив два ключа, должен утвердительно ответитьв том случае, если первый ключ должен быть по порядку раньше второго. В качестве такого компаратора удобно использовать различные функциональные объекты:
// Компаратор для шахматных координат: приоритет позиции X над позицией Y
structChessCoordinateComparatorXY
{
// Оператор функционального вызова
Booloperator () ( ChessCoordinate _c1, ChessCoordinate _c2 ) const
{
if( _c1.m_xPosition < _c2.m_xPosition )
return true;
else if( _c1.m_xPosition == _c2.m_xPosition )
return_c1.m_yPosition < _c2.m_yPosition;
Else
return true;
}
};
// Компаратор для шахматных координат: приоритет позиции Y над позицией X
structChessCoordinateComparatorYX
{
// Оператор функционального вызова