双 link 列表

Question

我正在尝试制作一个内存高效的双向链表。该列表存储下一个地址和上一个地址的异或，但我在函数 XOR 中遇到错误。错误是：

[Error] cast from 'node*' to 'unsigned int' loses precision [-fpermissive]

我的代码是：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *next;
}*start,*temp;
node* XOR(node *a,node *b)
{
    return (node *)((unsigned int)(a)^(unsigned int)(b));   
}
void push(int data)
{
    node *a=new node;
    a->data=data;
    a->next=XOR(start,NULL);
    if(start!=NULL)
    start->next=XOR(start->next,a);
    start=a;
}
void disp()
{
    temp=start;
    node *prev,*cur;
    while(temp)
    {
        cout<<temp->data<<" ";
        if(temp==start)
        {
            prev=temp;
            temp=temp->next;
        }
        else
        {
            cur=temp;
            temp=XOR(temp->next,prev);
            prev=cur;
        }
    }
}
main()
{
    start=NULL;
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    push(7);
    push(8);
}

Answer 1

不能保证unsigned int 与指针一样大，在许多情况下指针是64 位而unsigned int 是32 位。因此在这种情况下，高 32 位被丢弃，使指针无效。您需要 uintptr_t 而不是 unsigned int。

更正后的代码必须先：

#include <cstdint>

在顶部的某处，以便为 uintptr_t 添加声明以及各种其他有用的类型，然后更改行：

return (node *)((unsigned int)(a)^(unsigned int)(b));

收件人：

return (node *)((uintptr_t)(a)^(uintptr_t)(b));

请查看此处以更好地解释 uintptr_t 和其他类似类型的工作原理 http://www.cplusplus.com/reference/cstdint/

最后我要提到的是，在大多数现代机器中，xored 链表实际上会比普通的双向链表慢，而不是快，因为该技术使 CPU 和编译器更难预测什么你做得很好，优化得很好，这种效果比小 space 节省的速度提升更大。

Answer 2

您应该使用 #include <cstdint> 中定义的 uintptr_t。

uintptr_t 的真正目的是能够保存 void* 指针并在不损失精度的情况下转换回来。

使用

uintptr_t XOR(node *a,node *b)
{
    return reinterpret_cast<uintptr_t>(a)^reinterpret_cast<uintptr_t>(b);   
}

然后我不会将其转换回 node*，直到您最终 return 转换为有效指针的 uintptr_t。

我不相信当你转换一个 uintptr_t 不是直接从一个指针转换到另一个指针时会发生什么。

双 link 列表

Doubly link list

c++

xor

doubly-linked-list