Как можно полностью упорядочить указатели?

Указатели в С++ в общем случае могут сравниваться только для равенства. Напротив, меньше, чем сравнение, допускается только для двух указателей, указывающих на подобъекты одного и того же полного объекта (например, элементов массива).

Таким образом, данный T * p, * q, вообще говоря, является незаконным для оценки p < q.

Стандартная библиотека содержит шаблоны классов-функторов std::less<T> и т.д., которые завершают встроенный оператор <. Однако в стандарте это говорит о типах указателей (20.8.5/8):

Для шаблонов greater, less, greater_equal и less_equal специализации для любого типа указателя дают общий порядок, даже если встроенные операторы <, >, <=, >= do not.

Как это можно реализовать? Возможно ли это реализовать?

Я взглянул на GCC 4.7.2 и Clang 3.2, которые вообще не содержат никакой специализации для типов указателей. Похоже, что они зависят от <, безоговорочно действующих на всех поддерживаемых платформах.

Ответ 1

Можно ли полностью указывать указатели? Не в портативном стандартном С++. Это почему стандарт требует реализации для решения проблемы, а не вы. Для любого заданного представления указателя должно быть возможно определить произвольное полное упорядочение, но как вы это сделаете, будет зависеть от представление указателя.

Для машин с плоским адресным пространством и байтовой адресацией обрабатывая указатель так, как если бы он был целым числом одинакового размера или без знака целого числа обычно достаточно; так будет обрабатываться большинство компиляторов сравнение в пределах объекта, так что на таких машинах нет необходимо, чтобы библиотека специализировалась на std::less et al. "Неуказанный" поведение просто происходит правильно.

Для текстовых машин (и, по крайней мере, один производство), может потребоваться преобразовать указатели в void* до того, как будет выполнено сопоставление на основе компилятора.

Для машин с сегментированными архитектурами может потребоваться больше работы. Для таких машин типично требовать, чтобы массив был полностью в одном сегмент и просто сравнить смещение в сегменте; это означает, что если a и b - два произвольных указателя, вы можете в итоге !(a < b) && !(b < a), но не a == b. В этом случае компилятор должен предоставить специализация std::less<> et al для указателей, которые (вероятно) извлеките сегмент и смещение от указателя и сделайте что-то вроде манипулирование ими.

EDIT:

О другой вещи, о которой стоит упомянуть, возможно: гарантии в С++ стандарт применяется только к стандарту С++, или в этом случае полученные указатели от стандартного С++. В большинстве современных систем довольно легко mmap один и тот же файл в два разных диапазона адресов и два указателя p и q, которые сравниваются неравномерно, но указывают на один и тот же объект.

Ответ 2

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

Да. Для любого конечного множества вы всегда можете определить произвольный полный порядок над ним.

Рассмотрим простой пример, в котором у вас есть только пять возможных различных значений указателя. Пусть назовем эти O (для nullptr), γ, ζ, χ, ψ ¹.

Скажем, что никакая пара двух разных указателей из четырех непустых указателей не может сравниваться с <. Мы можем просто произвольно сказать, что std::less дает нам этот порядок: O ζ γ ψ χ, даже если < не имеет.

Конечно, реализация этого произвольного упорядочения эффективным образом зависит от качества реализации.

¹ Я использую греческие буквы для удаления подсознательного понятия порядка, которое возникло бы из-за знакомства с латинским алфавитом; мои извинения читателям, которые знают порядок греческого алфавита

Ответ 3

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

В случае GCC и Clang они могут реализовать std::less как <, пока они обеспечивают более сильную гарантию для <. Поскольку они выполняют поведение для <, они могут полагаться на это поведение, но их пользователи не могут, поскольку это может измениться в будущем.

Ответ 4

Проблема - это сегментированные архитектуры, где адрес памяти состоит из двух частей: сегмента и смещения. Это "достаточно легко", чтобы превратить эти части в какую-то линейную форму, но это требует дополнительного кода, и решение было не налагать накладные расходы для operator<. Для сегментированных архитектур operator< может просто сравнивать смещения. Эта проблема присутствовала в более ранних версиях Windows.

Обратите внимание, что "достаточно легко" - это перспектива системного программиста. Различные селектора сегментов могут ссылаться на один и тот же блок памяти, поэтому для создания канонического упорядочения требуется прореживание деталей отображения сегментов, которое зависит от платформы и может быть медленным.