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

Question

(связанный с my previous question)

В QT, то QMap documentation говорит:

Ключ типа 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); 
} 

Они просто бросают указатели на quintptr с (что является QT-версия uintptr_t, то есть , unsigned int, который способен storing a pointer) и сравнить результаты.

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Возьмем пример segmented memory из 8086: Реальный адрес задается комбинацией сегмента (например, DS регистр для сегмента данных, АС для сегмента стека, ...) и 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 имеют тип «указатель на сорте Т», где Т отличная от типа элемента с категорией неквалифицированного массива , поведение не определено.

Так что арифметика указателей не будет делать трюк для произвольных указателей. Опять же, вернемся к сегментированным моделям памяти, помогает понять: массивы могут иметь максимум 65535 байт, чтобы полностью соответствовать одному сегменту. Но разные массивы могут использовать разные сегменты, чтобы арифметика указателей была бы ненадежной и для общего порядка.

Заключение

Там тонкое замечание в стандарте на отображение между указателем и INTERAL значение:

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

Это означает, что должно быть возможно определить общий порядок. Но имейте в виду, что он не переносится.

Answer 2

Стандарт гарантирует, что преобразование указателя в uintptr_t приведет к значению какого-либо неподписанного типа, который, если его применить к исходному типу указателя, даст исходный указатель. Он также предусматривает, что любой указатель может быть разложен в последовательность значений unsigned char и что использование такой последовательности значений unsigned char для построения указателя даст исходный код. Тем не менее, ни одна из гарантий не запретила бы реализацию из включения битов заполнения в типы указателей, а также не гарантировала бы, что биты заполнения будут вести себя согласованно.

Если код избегать хранения указателей, и вместо того, чтобы бросить в uintptr_t каждом указателе, возвращаемом из malloc, позже отливок этих значений обратно в указатели по мере необходимости, а затем полученные значения uintptr_t бы сформировать рейтинг. Ранжирование может не иметь никакого отношения к порядку, в котором были созданы объекты, или к их расположению в памяти, но это будет ранжирование. Однако, если какой-либо указатель преобразуется в uintptr_t более одного раза, результирующие значения могут оцениваться полностью независимо.