Как указатели могут быть полностью упорядочены?
В целом, указатели в C ++ могут сравниваться только на равенство. Напротив, сравнение меньше, чем допустимо, только для двух указателей, которые указывают на подобъекты одного и того же законченного объекта (например, элементов массива).
Так дано T * p, * q, это вообще незаконно оценивать p < q,
Стандартная библиотека содержит шаблоны классов функторов std::less<T> и т.д., которые обертывают встроенный оператор <, Однако в стандарте есть, что сказать о типах указателей (20.8.5 / 8):
Для шаблонов
greater,less,greater_equal, а такжеless_equal, специализации для любого типа указателя дают общий порядок, даже если встроенные операторы<,>,<=,>=не делайте.
Как это можно реализовать? Возможно ли вообще это реализовать?
Я взглянул на GCC 4.7.2 и Clang 3.2, которые не содержат любой специализация для типов указателей вообще. Кажется, они зависят от < быть действительным на всех поддерживаемых платформах.
Решение
Могут ли указатели быть полностью упорядочены? Не в портативном, стандартном C ++. Это
почему стандарт требует реализации для решения проблемы, а не
вы. Для любого данного представления указателя это должно быть возможно
определить произвольный общий порядок, но как вы это сделаете, будет зависеть от
представление указателя.
Для машин с плоским адресным пространством и байтовой адресацией, просто
обращение с указателем, как если бы оно было целочисленным или неподписанным
обычно достаточно целого числа; это то, как будет обрабатывать большинство компиляторов
сравнение внутри объекта, так что на таких машинах нет
нужно для библиотеки специализироваться std::less и другие. «Неуточненное» поведение просто делает правильные вещи.
Для машин с адресом слова (и по крайней мере один еще в
производство), может потребоваться преобразовать указатели в void*
до компилятора родное сравнение будет работать.
Для машин с сегментированной архитектурой может потребоваться дополнительная работа.
На таких машинах обычно требуется, чтобы массив был полностью в одном
сегмент, и просто сравните смещение в сегменте; это означает, что если
a а также b два произвольных указателя, вы можете в конечном итоге с !(a < b) && но нет
!(b < a)a == b, В этом случае компилятор должен предоставить
специализации std::less<> и др. для указателей, которые (вероятно)
извлечь сегмент и смещение из указателя, и сделать что-то вроде
манипулирование ими.
РЕДАКТИРОВАТЬ:
Возможно, стоит упомянуть еще одну вещь: гарантии в C ++
Стандарт применяется только к стандарту C ++, или в этом случае полученные указатели
из стандарта C ++. На большинстве современных систем это довольно легко mmap
один и тот же файл с двумя разными диапазонами адресов и имеет два указателя p
а также q которые сравнивают неравные, но которые указывают на один и тот же объект.
Другие решения
Можно ли реализовать стандартную библиотеку для целей, где указатели не формируют общий, общий порядок?
Да. Для любого конечного множества вы всегда можете определить произвольный общий порядок над ним.
Рассмотрим простой пример, где у вас есть только пять возможных различных значений указателя. Назовем их O (для nullptr), γ, ζ, χ, ψ1.
Допустим, что ни одна пара двух разных указателей из четырех ненулевых указателей не может быть сравнена с <, Мы можем просто произвольно сказать, что std::less дает нам этот порядок: O ζ γ ψ χ, даже если < не делает.
Конечно, эффективное выполнение этого произвольного порядка является вопросом качества реализации.
1 Я использую греческие буквы, чтобы удалить подсознательное представление о порядке, которое возникнет из-за знакомства с латинским алфавитом; мои извинения читателям, которые знают порядок греческого алфавита
На большинстве платформ с плоским адресным пространством они могут просто выполнять числовое сравнение между указателями. На платформах, где это невозможно, разработчик должен придумать какой-то другой метод установления общего порядка для использования в std::less, но они могут потенциально использовать более эффективный метод для <, поскольку у него есть более слабая гарантия.
В случае GCC и Clang они могут реализовать std::less как < до тех пор, пока они обеспечивают более надежную гарантию <, Так как именно они реализуют поведение для <, они могут полагаться на это поведение, но их пользователи не могут, так как это может измениться в будущем.
Проблема заключается в сегментированных архитектурах, где адрес памяти состоит из двух частей: сегмента и смещения. «Достаточно просто» превратить эти части в какую-то линейную форму, но это требует дополнительного кода, и было решено не накладывать эти накладные расходы на operator<, Для сегментированных архитектур operator< можно просто сравнить смещения. Эта проблема присутствовала в более ранних версиях Windows.
Обратите внимание, что «достаточно просто» — это точка зрения системного программиста. Различные селекторы сегментов могут ссылаться на один и тот же блок памяти, поэтому для создания канонического упорядочения необходимо изучить детали отображения сегментов, которое зависит от платформы и может быть медленным.