Компараторы для ключей в 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;