c++ - 分配空间中的链表？

Question

我希望这个问题不要过于强调讨论，而是要有一个明确的答案。

我在大学学习了 C，然后才开始编写我的第一个有用的程序(意思是没有规范)。我只是偶然发现了一个到目前为止我还没有处理过的问题，我想他们在讲座中没有提到它:

当我分配可能调整大小的内存时，我不应该存储指向该分配空间地址的指针。因为当我重新分配时，空间可能会移动到不同的位置，这使得指向该区域的每个指针都变得毫无值(value)。这使我得出结论，我不能在空间内存储链表，每个元素都“存在”在这个空间的某个地方，因为重新分配可能会使所有“下一个”和“上一个”指针无效。

这是我从来没有遇到过的问题，所以我想问问你是否有解决办法。具体来说:我有一个共享内存区域，想将所有数据存储在其中，以便不同的进程可以在其中工作。由于数据(字符串)将被频繁添加和删除并且必须按特定顺序排列，因此我认为链表是最好的方法。现在我意识到我不能这样做。还是我太盲目而看不到明显的解决方案？你会怎么做？ (我不想将整个东西存储在一个文件中，它应该留在(主)内存中)

谢谢和最好的问候， 菲尔

Answer 1

它可以以牺牲简单性和性能为代价来完成。不是将指针存储在共享内存中，而是必须从区域的开头存储偏移量。然后，当您想要“取消引用”其中之一时，将偏移量添加到指向共享区域的指针。

为避免错误，我会为此创建一个特殊类型，具体取决于您使用的实际语言

C

 //seriously, this is one situation where I would find a global justified
 region_ptr region;

 //store these instead of pointers inside the memory region
 struct node_offset {ptrdiff_t offset};

 //used to get a temporary pointer from an offset in a region
 //the pointer is invalidated when the memory is reallocated
 //the pointer cannot be stored in the region
 node* get_node_ptr(node_offset offset) 
 {return (node*)((char*)region+offset.offset);}

 //used to get an offset from a pointer in a region
 //store offsets in the region, not pointers
 node_offset set_node_ptr(region* r, node* offset) 
 {node_offset o = {(char*)offset.offset-(char*)region}; return o;}

C++

 //seriously, this is one situation where I would find a global justified
 region_ptr region;

 //store these in the memory region
 //but you can pretend they're actual pointers
 template<class T>
 struct offset_ptr { 
     offset_ptr() : offset(0) {}

     T* get() const {return (T*)((char*)region + offset);}
     void set(T* ptr) {offset = (char*)ptr - (char*)region;}

     offset_ptr(T* ptr) {set(ptr);}
     offset_ptr& operator=(T* ptr) {set(ptr); return *this;}
     operator T*() const {return get();}
     T* operator->() const {return get();}
     T& operator*() const {return *get();}

 private:
     ptrdiff_t offset;
 };

 template<class T>
 struct offset_delete {
     typedef offset_ptr<T> pointer;
     void operator()(offset_ptr<T> ptr) const {ptr->~T();}
 };
 //std::unique_ptr<node, offset_delete<node>> node_ptr;