Компараторы для ключей в std::map

 

Свойства отображений std::map вытекают из обеспечивающей базовой структуры данных - сбалансированных бинарных деревьев поиска (Balanced BST). Чаще всего реализация контейнера std::map основывается на алгоритме красно-черных деревьев (red-black trees), гарантирующем разницу высоты поддеревьев не более чем в 2 раза за счет своевременных вращений.

 

Отсюда вытекает обязательное требование к типу ключа: возможность сравнения ключа при помощи оператора < (меньше). Это требование аналогично требованиям алгоритмов сортировки. Для каждой пары ключей необходимо однозначное отношение порядка. Разумеется, такой оператор доступен для всех встроенных типов, перечислений, для строк std::string и даже для контейнеров-последовательностей из стандартной библиотеки.

 

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

 

struct ChessCoordinate

{

// Номера клеток по горизонтали и вертикали

const short m_xPosition, m_yPosition;

 

// Конструктор

ChessCoordinate (short _xPosition, short _yPosition)

: m_xPosition(_xPosition), m_yPosition(_yPosition)

{

// Инвариант: координата X должна находиться в интервале от 1 до 8

if (m_xPosition < 1 || m_xPosition > 8)

throw std::logic_error(“X coordinate out of range [1:8]”);

 

// Инвариант: координата Y должна находиться в интервале от 1 до 8

if (m_yPosition < 1 || m_yPosition > 8)

throw std::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)

return m_yPosition < c.m_yPosition;

 

Else

return true;

}

};

 

Поскольку в данном пользовательском типе перегружен оператор сравнения по <, его можно использовать в качестве ключа для отображения std::map:

 

class Figure;

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

// ^
// тип ключа имеет перегруженный оператор <

 

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

 

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

 

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

 

// Компаратор для шахматных координат: приоритет позиции X над позицией Y

struct ChessCoordinateComparatorXY

{

// Оператор функционального вызова

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

struct ChessCoordinateComparatorYX

{

// Оператор функционального вызова