Pertanyaan Daftar tertaut dalam ruang yang dialokasikan?


Saya harap pertanyaan ini tidak akan terlalu membebani diskusi tetapi pada jawaban yang jelas.

Saya belajar C di universitas dan baru mulai menulis program pertama saya yang berguna (artinya tanpa spesifikasi). Saya baru saja menemukan masalah yang belum saya bahas sejauh ini, dan saya pikir mereka tidak menyebutkannya dalam ceramah:

Ketika saya mengalokasikan memori yang kemungkinan akan diubah ukurannya, saya seharusnya tidak menyimpan pointer ke alamat dari ruang yang dialokasikan ini. Karena ketika saya realokasi, ruang mungkin dipindahkan ke lokasi differend, yang membuat setiap pointer ke wilayah ini tidak berguna. Ini membawa saya pada kesimpulan bahwa saya tidak dapat menyimpan daftar tertaut di dalam ruang, dengan setiap elemen 'hidup' di suatu tempat di ruang ini, karena realokasi dapat membatalkan semua petunjuk 'berikutnya' dan 'sebelumnya'.

Ini adalah masalah yang tidak pernah saya temui, itulah mengapa saya ingin bertanya apakah ada solusi untuk ini. Secara khusus: Saya memiliki wilayah memori bersama dan ingin menyimpan semua data saya di dalamnya, sehingga proses yang berbeda dapat bekerja di dalamnya. Karena data (string) akan ditambahkan dan dihapus sering dan harus dalam urutan tertentu, saya pikir daftar yang ditautkan akan menjadi cara terbaik untuk pergi. Sekarang saya menyadari saya tidak bisa melakukannya dengan cara ini. Ataukah saya terlalu buta untuk melihat solusi yang jelas? Bagaimana Anda akan melakukan ini? (Saya tidak ingin menyimpan semuanya dalam file, itu harus tetap di memori (utama))

terima kasih dan salam, phil


4
2018-03-13 17:02


asal


Jawaban:


Saya t bisa dilakukan dengan mengorbankan kesederhanaan dan karena itu kinerja. Alih-alih menyimpan pointer di dalam memori bersama, Anda harus menyimpannya offset dari awal wilayah sebagai gantinya. Kemudian, ketika Anda ingin "dereference" salah satunya, Anda menambahkan offset ke pointer-to-the-shared-region.

Untuk menghindari kesalahan, saya akan membuat jenis khusus untuk ini, tergantung pada sebenarnya bahasa yang Anda gunakan

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;

4
2018-03-13 17:10



Metode lain yang sangat mirip dengan metode offset yang disarankan oleh Mooing Duck adalah array dan indeks array.

Jika setiap elemen daftar memiliki ukuran yang sama maka deklarasikan pointer ke array elemen daftar ini. Atur penunjuk itu ke awal wilayah memori. Simpan offset array sebagai ganti pointer untuk node yang ada dan yang berikutnya. Sekarang kompiler menangani penambahan offset untuk Anda.


1
2018-03-13 17:24