Mengapa C ++ STL tidak menyediakan wadah "pohon"?

Mengapa C ++ STL tidak menyediakan wadah "tree", dan apa hal terbaik untuk digunakan?

Saya ingin menyimpan hierarki objek sebagai pohon, daripada menggunakan pohon sebagai peningkatan kinerja ...

Ada dua alasan Anda ingin menggunakan pohon:

Anda ingin mencerminkan masalah menggunakan struktur seperti pohon:
Untuk ini, kami telah meningkatkan perpustakaan grafik

Atau Anda ingin wadah yang memiliki karakteristik akses seperti pohon Untuk ini, kami memiliki

• std::map(dan std::multimap)
• std::set(dan std::multiset)

Pada dasarnya karakteristik kedua wadah ini sedemikian rupa sehingga praktis harus diimplementasikan menggunakan pohon (meskipun ini sebenarnya bukan persyaratan).

Lihat juga pertanyaan ini: Implementasi C tree

Mungkin karena alasan yang sama bahwa tidak ada wadah pohon dalam meningkatkan. Ada banyak cara untuk menerapkan wadah seperti itu, dan tidak ada cara yang baik untuk memuaskan semua orang yang akan menggunakannya.

Beberapa masalah untuk dipertimbangkan:

• Apakah jumlah anak untuk suatu simpul tetap atau variabel?
• Berapa overhead per node? - yaitu, apakah Anda memerlukan pointer orangtua, pointer saudara, dll.
• Algoritma apa yang harus disediakan? - berbagai iterator, algoritma pencarian, dll.

Pada akhirnya, masalahnya adalah wadah pohon yang cukup bermanfaat bagi semua orang, terlalu berat untuk memuaskan sebagian besar orang yang menggunakannya. Jika Anda mencari sesuatu yang kuat, Boost Graph Library pada dasarnya adalah superset dari apa perpustakaan pohon dapat digunakan untuk.

Berikut adalah beberapa implementasi pohon generik lainnya:

• Pohon Kasper Peeters
• Hutan Adobe
• inti :: pohon

Filosofi STL adalah bahwa Anda memilih wadah berdasarkan jaminan dan bukan berdasarkan bagaimana wadah diterapkan. Misalnya, pilihan wadah Anda mungkin didasarkan pada kebutuhan untuk pencarian cepat. Untuk semua yang Anda pedulikan, wadah dapat diimplementasikan sebagai daftar searah - selama pencarian sangat cepat Anda akan bahagia. Itu karena Anda tidak menyentuh internal, Anda menggunakan iterator atau fungsi anggota untuk akses. Kode Anda tidak terikat pada bagaimana wadah diterapkan tetapi seberapa cepat itu, atau apakah itu memiliki pemesanan tetap dan pasti, atau apakah itu efisien pada ruang, dan sebagainya.

"Aku ingin menyimpan hierarki objek sebagai pohon"

C ++ 11 telah datang dan pergi dan mereka masih tidak melihat kebutuhan untuk menyediakan std::tree, meskipun idenya muncul (lihat di sini ). Mungkin alasan mereka belum menambahkan ini adalah karena itu mudah untuk membuat sendiri di atas wadah yang ada. Sebagai contoh...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

Traversal sederhana akan menggunakan rekursi ...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

Jika Anda ingin mempertahankan hierarki dan Anda ingin itu bekerja dengan algoritma STL , maka segala sesuatunya mungkin menjadi rumit. Anda dapat membangun iterator Anda sendiri dan mencapai beberapa kompatibilitas, namun banyak algoritma yang tidak masuk akal untuk hierarki (apa pun yang mengubah urutan kisaran, misalnya). Bahkan mendefinisikan rentang dalam hierarki bisa menjadi bisnis yang berantakan.

Jika Anda mencari implementasi RB-tree, maka stl_tree.h mungkin cocok untuk Anda juga.

std :: map didasarkan pada pohon merah-hitam . Anda juga dapat menggunakan wadah lain untuk membantu Anda menerapkan jenis pohon Anda sendiri.

Di satu sisi, std :: map adalah pohon (harus memiliki karakteristik kinerja yang sama dengan pohon biner seimbang) tetapi tidak mengekspos fungsionalitas pohon lainnya. Kemungkinan alasan di balik tidak termasuk struktur data pohon nyata mungkin hanya masalah tidak termasuk semua yang ada di stl. Stl dapat dilihat sebagai kerangka kerja untuk digunakan dalam mengimplementasikan algoritma dan struktur data Anda sendiri.

Secara umum, jika ada fungsi pustaka dasar yang Anda inginkan, itu tidak ada di stl, perbaikannya adalah dengan melihat pada BOOST .

Jika tidak, ada sekelompok dari perpustakaan di luar sana , tergantung pada kebutuhan pohon Anda.

Semua wadah STL secara eksternal direpresentasikan sebagai "urutan" dengan satu mekanisme iterasi. Pohon tidak mengikuti idiom ini.

Karena STL bukan perpustakaan "segalanya". Ini berisi, pada dasarnya, struktur minimum yang diperlukan untuk membangun sesuatu.

Yang ini terlihat menjanjikan dan tampaknya adalah yang Anda cari: http://tree.phi-sci.com/

IMO, suatu kelalaian. Tapi saya pikir ada alasan bagus untuk tidak memasukkan struktur Tree dalam STL. Ada banyak logika dalam memelihara pohon, yang paling baik ditulis sebagai fungsi anggota ke TreeNodeobjek dasar . Ketika TreeNodedibungkus dalam header STL, itu hanya akan berantakan.

Sebagai contoh:

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  // insertion logic for if an insert is asked of me.
  // may append to children, or may pass off to one of the child nodes
  void insert( T* newData ) ;

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

Saya pikir ada beberapa alasan mengapa tidak ada pohon STL. Terutama Pohon adalah bentuk struktur data rekursif yang, seperti wadah (daftar, vektor, set), memiliki struktur halus yang sangat berbeda yang membuat pilihan yang benar rumit. Mereka juga sangat mudah dibangun dalam bentuk dasar menggunakan STL.

Pohon berakar terbatas dapat dianggap sebagai sebuah wadah yang memiliki nilai atau muatan, katakan sebuah instance dari kelas A dan, koleksi pohon (sub) yang mungkin kosong; pohon dengan koleksi sub pohon yang kosong dianggap sebagai daun.

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

Kita harus berpikir sedikit tentang desain iterator dll. Dan operasi produk dan produk samping mana yang memungkinkan untuk mendefinisikan dan menjadi efisien di antara pohon - dan STL asli harus ditulis dengan baik - sehingga set kosong, vektor atau daftar kontainer adalah benar-benar kosong dari muatan apa pun dalam kasus default.

Pohon memainkan peran penting dalam banyak struktur matematika (lihat makalah klasik dari Jagal, Grossman dan Larsen; juga makalah Connes dan Kriemer untuk contoh mereka dapat bergabung, dan bagaimana mereka digunakan untuk menghitung). Tidaklah benar untuk berpikir bahwa peran mereka hanya untuk memfasilitasi operasi-operasi tertentu lainnya. Sebaliknya mereka memfasilitasi tugas-tugas itu karena peran mendasar mereka sebagai struktur data.

Namun, selain pohon ada juga "co-tree"; pohon di atas semua memiliki properti yang jika Anda menghapus root Anda menghapus semuanya.

Pertimbangkan iterator di pohon, mungkin mereka akan direalisasikan sebagai setumpuk iterator sederhana, ke sebuah simpul, dan ke induknya, ... hingga ke akar.

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

Namun, Anda dapat memiliki sebanyak yang Anda suka; secara kolektif mereka membentuk "pohon" tetapi di mana semua panah mengalir ke arah root, co-tree ini dapat diiterasi melalui iterator menuju iterator dan root yang sepele; namun tidak dapat dinavigasi melintasi atau ke bawah (iterator lain tidak diketahui) atau ensemble iterator tidak dapat dihapus kecuali dengan melacak semua instance.

Pohon sangat berguna, mereka memiliki banyak struktur, ini membuatnya menjadi tantangan serius untuk mendapatkan pendekatan yang benar benar. Dalam pandangan saya ini adalah mengapa mereka tidak diterapkan di STL Selain itu, di masa lalu, saya telah melihat orang-orang menjadi religius dan menemukan ide tentang jenis wadah berisi contoh dari jenisnya sendiri menantang - tetapi mereka harus menghadapinya - itulah yang diwakili oleh jenis pohon - itu adalah simpul yang mengandung mungkin koleksi kosong pohon (lebih kecil). Bahasa saat ini memungkinkan tanpa tantangan menyediakan konstruktor default untuk container<B>tidak mengalokasikan ruang pada heap (atau tempat lain) untuk B, dll.

Untuk satu orang akan senang jika ini, dalam bentuk yang baik, menemukan jalan ke standar.

Membaca jawaban di sini alasan umum yang disebutkan adalah bahwa seseorang tidak dapat beralih melalui pohon atau bahwa pohon tidak menganggap antarmuka yang sama dengan wadah STL lainnya dan orang tidak dapat menggunakan algoritma STL dengan struktur pohon tersebut.

Setelah itu dalam pikiran saya mencoba merancang struktur data pohon saya sendiri yang akan memberikan antarmuka seperti STL dan akan dapat digunakan dengan ALGorthims STL yang ada sebanyak mungkin.

Gagasan saya adalah bahwa pohon harus didasarkan pada wadah STL yang ada dan tidak boleh menyembunyikan wadah, sehingga dapat diakses untuk digunakan dengan algoritma STL.

Fitur penting lain yang harus disediakan oleh pohon adalah iterator yang melintas.

Inilah yang saya dapat membuat: https://github.com/igagis/utki/blob/master/src/utki/tree.hpp

Dan inilah tesnya: https://github.com/igagis/utki/blob/master/tests/tree/tests.cpp

Semua wadah STL dapat digunakan dengan iterator. Anda tidak dapat memiliki iterator dan pohon, karena Anda tidak memiliki cara yang benar untuk melewati pohon tersebut.