Определяет ли приведение указателей к целым числам общий порядок указателей?

(связано с моим предыдущим вопросом)

В 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то есть беззнаковое целое, способное хранить указатель) и сравнить результаты.

Следующий тип обозначает целочисленный тип без знака со свойством, что любой действительный указатель на void может быть преобразован в этот тип, затем преобразован обратно в указатель на void, и результат будет сравниваться равным исходному указателю: uintptr_t

Как вы думаете, это реализация qMapLessThanKey() на указатели в порядке?

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

Я думаю, что это правда, только если p1 == p2 подразумевает quintptr(p1) == quintptr(p2), который, AFAIK, не указан.

Как контрпример этого условия, представьте цель, использующую 40 битов для указателей; он может конвертировать указатели в quintptrустановка 40 младших бит в адрес указателя и оставление 24 старших бит без изменений (случайным образом). Этого достаточно для соблюдения конвертируемости quintptr и указатели, но это не определяет общий порядок для указателей.

Как вы думаете?

Источник

2 ответа

Решение

Я думаю, что вы не можете предположить, что на указатели есть общий порядок. Гарантии, данные стандартом для указателей на int-преобразования, довольно ограничены:

5.2.10 / 4: указатель может быть явно преобразован в любой целочисленный тип, достаточно большой для его хранения. Функция отображения определяется реализацией.

5.2.10 / 5: значение целочисленного типа или типа перечисления может быть явно преобразовано в указатель. Указатель, преобразованный в целое число достаточного размера (...) и обратно в тот же тип указателя, будет иметь свое первоначальное значение; Отображения между указателями и целыми числами определяются реализацией.

С практической точки зрения, большинство основных компиляторов преобразуют указатель в целое число поразрядным образом, и у вас будет полный порядок.

Теоретическая проблема:

Но это не гарантировано. Он может не работать на прошлых платформах ( реальный x86 и защищенный режим), на экзотических платформах (встроенные системы?) И -who знает- на некоторых будущих платформах (?).

Возьмите пример сегментированной памяти 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 однако несколько раз результирующие значения могут ранжироваться совершенно независимо.

Источник
Другие вопросы по тегам