Определяет ли приведение указателей к целым числам общий порядок указателей?
(относится к мой предыдущий вопрос)
В QT QMap документация говорит:
Тип ключа QMap должен обеспечивать
operator<()указав общий заказ.
Однако в qmap.hкажется, они используют что-то похожее на std::less сравнить указатели:
/*
QMap uses qMapLessThanKey() to compare keys. The default
implementation uses operator<(). For pointer types,
qMapLessThanKey() casts the pointers to integers before it
compares them, because operator<() is undefined on pointers
that come from different memory blocks. (In practice, this
is only a problem when running a program such as
BoundsChecker.)
*/
template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
{
return key1 < key2;
}
template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
{
Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
return quintptr(key1) < quintptr(key2);
}
Они просто приводят указатели на quintptrs (который является QT-версией uintptr_tнеподписанный int, способный хранение указателя) и сравните результаты.
Следующий тип обозначает целочисленный тип без знака со свойством, что любой действительный указатель на void может быть преобразован в этот тип, затем преобразован обратно в указатель на void, и результат будет сравниваться равным исходному указателю:
uintptr_t
Как вы думаете, это реализация qMapLessThanKey() на указатели в порядке?
Конечно, существует полный порядок на целочисленных типах. Но я думаю, что этого недостаточно, чтобы сделать вывод, что эта операция определяет общий порядок указателей.
Я думаю, что это правда, только если p1 == p2 подразумевает quintptr(p1) == quintptr(p2), который, AFAIK, не указан.
Как контрпример этого условия, представьте цель, использующую 40 битов для указателей; он может конвертировать указатели в quintptrустановка 40 младших бит в адрес указателя и оставление 24 старших бит без изменений (случайным образом). Этого достаточно для соблюдения конвертируемости quintptr и указатели, но это не определяет общий порядок для указателей.
Как вы думаете?
Решение
Я думаю, что вы не можете предположить, что на указатели есть общий порядок. Гарантии, данные стандартом для указателей на int-преобразования, довольно ограничены:
5.2.10 / 4: Указатель может быть явно преобразован в любой целочисленный тип, достаточно большой для его хранения. Функция отображения
реализации.5.2.10 / 5: Значение целочисленного типа или типа перечисления может быть явно преобразовано в указатель. Указатель преобразуется в целое число
достаточного размера (…) и обратно к тому же типу указателя будет иметь
его первоначальная стоимость; Отображения между указателями и целыми числами
в противном случае реализация определяется.
С практической точки зрения, большинство основных компиляторов преобразуют указатель в целое число поразрядным образом, и у вас будет общий порядок.
Но это не гарантировано. Это может не работать на прошлых платформах (x86 реальный и защищенный режим), на экзотической платформе (встроенные системы?), и — кто знает — на некоторых будущих платформах (?).
Возьмите пример сегментированная память из 8086: реальный адрес задается комбинацией сегмента (например, регистр DS для сегмента данных, SS для сегмента стека и т. д.) и offest:
Segment: XXXX YYYY YYYY YYYY 0000 16 bits shifted by 4 bits
Offset: 0000 ZZZZ ZZZZ ZZZZ ZZZZ 16 bits not sifted
------------------------
Address: AAAA AAAA AAAA AAAA AAAA 20 bits address
Теперь представьте, что компилятор преобразует указатель в int, просто выполняя математическую обработку адреса и помещая 20 бит в целое число: ваш сейф и полный порядок.
Но другой, в равной степени действительный подход, заключается в сохранении сегмента в 16 старших битах и смещения в 16 младших битах. Фактически, этот способ значительно облегчил бы / ускорил загрузку значений указателей в регистры процессора.
Этот подход соответствует стандартным требованиям c ++, но каждый отдельный адрес может быть представлен 16 различными указателями: ваш общий заказ потерян !!
** Есть ли альтернативы для заказа? **
Можно представить, используя указательную арифметику. Существуют строгие ограничения на арифметику указателей для элементов в одном массиве:
5.7 / 6: Когда вычитаются два указателя на элементы одного и того же объекта массива, результатом является разность индексов двух
элементы массива.
И подписки заказаны.
Массив может быть максимальным size_t элементы. Так что, наивно, если sizeof(pointer) <= sizof(size_t) Можно предположить, что взятие произвольного ссылочного указателя и выполнение некоторой арифметики указателей должны привести к полному порядку.
К сожалению, и здесь стандарт очень разумный:
5.7.7: Для сложения или вычитания, если выражения P или Q имеют тип «указатель на cv T», где T отличается от
cv-неквалифицированный тип элемента массива, поведение не определено.
Таким образом, арифметика указателей не справится с произвольными указателями. Опять же, возвращаясь к моделям сегментированной памяти, помогает понять: массивы могут иметь максимум 65535 байт, чтобы полностью поместиться в один сегмент. Но разные массивы могут использовать разные сегменты, так что арифметика указателей также не будет надежной для общего порядка.
В стандарте есть тонкое примечание о сопоставлении между указателем и целочисленным значением:
Это должно быть неудивительно для тех, кто знает адресацию
структура базовой машины.
Это означает, что должна быть возможность определить общий заказ. Но имейте в виду, что это будет непереносимо.
Другие решения
Стандарт гарантирует, что преобразование указателя на uintptr_t выдаст значение некоторого типа без знака, который, если привести его к исходному типу указателя, даст исходный указатель. Также требуется, чтобы любой указатель можно было разложить на последовательность unsigned char значения, и что с помощью такой последовательности unsigned char Значения для построения указателя приведут к оригиналу. Однако ни одна из этих гарантий не запрещает реализации включать биты заполнения в типы указателей, а также не гарантирует, что биты заполнения будут вести себя согласованно.
Если код избежал хранения указателей, и вместо этого приведите к uintptr_t каждый указатель возвращается из mallocзатем приведем эти значения обратно к указателям по мере необходимости, затем получим uintptr_t значения будут формировать рейтинг. Ранжирование может не иметь никакого отношения к порядку, в котором были созданы объекты, и к их расположению в памяти, но это будет ранжирование. Если какой-либо указатель конвертируется в uintptr_t однако более одного раза результирующие значения могут ранжироваться совершенно независимо.