Apa artinya struktur data menjadi "mengganggu"?

Saya telah melihat istilah intrusif yang digunakan untuk menggambarkan struktur data seperti daftar dan tumpukan, tetapi apa artinya?

Dapatkah Anda memberikan contoh kode dari struktur data yang mengganggu, dan apa perbedaannya dari yang non-intrusif?

Juga, mengapa membuatnya mengganggu (atau, tidak mengganggu)? Apa manfaatnya? Apa kerugiannya?

Struktur data intrusif adalah salah satu yang membutuhkan bantuan dari elemen yang ingin disimpan untuk menyimpannya.

Biarkan saya mengubah itu. Ketika Anda memasukkan sesuatu ke dalam struktur data itu, "sesuatu" itu menjadi sadar akan fakta bahwa itu ada dalam struktur data itu, dalam beberapa cara. Menambahkan elemen ke struktur data mengubah elemen tersebut.

Misalnya, Anda dapat membuat pohon biner non-intrusif, di mana setiap node memiliki referensi ke sub-pohon kiri dan kanan, dan referensi ke nilai elemen node tersebut.

Atau, Anda dapat membuat yang mengganggu di mana referensi ke sub-pohon tersebut disematkan ke dalam nilai itu sendiri.

Contoh struktur data yang mengganggu adalah daftar elemen yang dapat berubah. Jika elemen berubah, daftar perlu diatur ulang, sehingga objek daftar harus mengganggu privasi elemen untuk mendapatkan kerja sama mereka. yaitu. elemen harus mengetahui tentang daftarnya, dan menginformasikan perubahan.

Sistem ORM biasanya berputar di sekitar struktur data yang mengganggu, untuk meminimalkan iterasi pada daftar objek yang besar. Misalnya, jika Anda mengambil daftar semua karyawan di database, lalu mengubah nama salah satu dari mereka, dan ingin menyimpannya kembali ke database, daftar karyawan yang mengganggu akan diberi tahu saat objek karyawan berubah karena itu objek tahu di daftar mana.

Daftar non-intrusif tidak akan diberitahukan, dan harus mencari tahu apa yang berubah dan bagaimana daftar itu berubah dengan sendirinya.

Dalam wadah yang mengganggu, data itu sendiri bertanggung jawab untuk menyimpan informasi yang diperlukan untuk wadah tersebut. Artinya di satu sisi tipe data perlu dikhususkan bergantung pada bagaimana ia akan disimpan, di sisi lain itu berarti bahwa data "tahu" bagaimana ia disimpan dan dengan demikian dapat dioptimalkan sedikit lebih baik.

Tidak mengganggu:

template<typename T>
class LinkedList
{
  struct ListItem
  {
    T Value;
    ListItem* Prev;
    ListItem* Next;
  };

  ListItem* FirstItem;
  ListItem* LastItem;

  [...]
  ListItem* append(T&& val)
  {
    LastItem = LastItem.Next = new ListItem{val, LastItem, nullptr};
  };
};

LinkedList<int> IntList;

Mengganggu:

template<typename T>
class LinkedList
{
  T* FirstItem;
  T* LastItem;

  [...]
  T* append(T&& val)
  {
    T* newValue = new T(val);
    newValue.Next = nullptr;
    newValue.Prev = LastItem;
    LastItem.Next = newValue;
    LastItem = newValue;
  };
};

struct IntListItem
{
  int Value;
  IntListItem* Prev;
  IntListItem* Next;
};

LinkedList<IntListItem> IntList;

Secara pribadi saya lebih suka desain yang mengganggu karena transparansi itu.