Может ли связанный список XOR быть реализован на C ++, не вызывая неопределенного поведения?

 **[связанный список XOR](https://en.wikipedia.org/wiki/XOR_linked_list)**  - это модифицированная версия нормального двусвязного список, в котором каждый узел хранит только один «указатель» вместо двух. Этот «указатель» состоит из XOR следующего и предыдущего указателей. Для перемещения по списку требуется два указателя - один для текущего узла и один для следующего или предыдущего узла. Чтобы перемещаться вперед, адрес предыдущего узла XORed с «указателем», хранящимся в текущем узле, отображая истинный «следующий» указатель.

Стандарт C ++ вызывает кучу операций над указателями и целыми числами, что приводит к неопределенному поведению - например, вы не можете гарантировать, что установка определенного бита в число не приведет к тому, что аппаратное обеспечение вызовет прерывание, поэтому в некоторых случаях результаты бит twiddling может быть неопределенным.

Мой вопрос следующий: существует ли реализация C ++ связанного с XOR списка, которая не приводит к неопределенному поведению?

>  Мой вопрос следующий: существует ли реализация C ++ связанного списка XOR, которая не приводит к неопределенному поведению? 
> 
> 

Если по «есть ли реализация» вы имеете в виду «уже написано», то я не знаю. Если вы имеете в виду «возможно ли написать одно», тогда да, но могут быть некоторые предостережения о переносимости.

Вы можете погладить свое содержание, если вы конвертируете оба указателя в  `uintptr_t` , прежде чем начать, и сохраните этот тип в узле вместо указателя. Побитовые операции с неподписанными типами никогда не приводят к неопределенному поведению.

Однако  `uintptr_t`  является необязательным типом, и поэтому он не является полностью переносимым. Нет требования, чтобы реализация C ++ фактически имела целочисленный тип, способный представлять адрес. Если в реализации нет  `uintptr_t` , тогда код разрешается компилировать с помощью диагностики, и в этом случае его поведение выходит за рамки стандарта. Не уверен, считаете ли вы, что нарушение «без UB» или нет. Я имею в виду, серьезно, компилятор, который позволяет использовать код, который использует неопределенные типы? ;-)

Чтобы избежать  `uintptr_t`  I  *подумайте* , что вы можете сделать свое свертывание бит в массиве символов  `sizeof (node *)`  unsigned. Указатели являются типами POD и поэтому могут быть скопированы, повернуты и искалечены при условии, что представление объекта будет восстановлено до исходного состояния, прежде чем оно будет использоваться в качестве указателя.

Также обратите внимание, что если ваша реализация на C ++ имеет сборщик мусора, то преобразование в целое число/xor/xor-back-again/convert-to-pointer не обязательно останавливает собираемый объект (потому что это приводит к «несанкционированному производному указатель"). Поэтому для переносимости вы должны  *также*  убедиться, что результирующие указатели действительны. Два способа сделать это:

1. вызывают  `declare_reachable` .
2. Используйте реализацию с  *безопасным указателем безопасности*  (это определяется реализацией, если это так, и вы можете проверить его с помощью  `get_pointer_safety()`  с учетом того, что непринужденной реализации разрешено ложно утверждать, что это строго).

Вы можете подумать, что есть третий способ (хотя и тот, который побеждает цель связанного списка XOR, если у вас его вообще не будет):

* сохранить отдельный контейнер всех значений указателя

*This is not guaranteed to work*. An unsafely derived pointer is invalid even if it happens to be equal to a safely-derived pointer (3.7.4.3/4). I was surprised too.