Waarom biedt de C++ STL geen “tree” containers?

Waarom biedt de C++ STL geen “boom”-containers en wat is het beste om in plaats daarvan te gebruiken?

Ik wil een hiërarchie van objecten opslaan als een boomstructuur, in plaats van een boomstructuur te gebruiken als prestatieverbetering…

Antwoord 1, autoriteit 100%

Er zijn twee redenen waarom u een boomstam zou willen gebruiken:

U wilt het probleem spiegelen met een boomstructuur:
Hiervoor hebben we boost grafiekbibliotheek

Of u wilt een container met boomachtige toegangskenmerken
Hiervoor hebben we

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

In principe zijn de kenmerken van deze twee containers zodanig dat ze praktisch moeten worden geïmplementeerd met behulp van bomen (hoewel dit eigenlijk geen vereiste is).

Zie ook deze vraag:
C tree-implementatie

Antwoord 2, autoriteit 52%

Waarschijnlijk om dezelfde reden dat er geen boomcontainer in boost zit. Er zijn veel manieren om zo’n container te implementeren, en er is geen goede manier om iedereen tevreden te stellen die het zou gebruiken.

Enkele zaken om te overwegen:

• Is het aantal kinderen voor een knooppunt vast of variabel?
• Hoeveel overhead per node? – bijv. heeft u ouderaanwijzingen, aanwijzingen voor broers en zussen, enz. nodig
• Welke algoritmen moeten we bieden? – verschillende iterators, zoekalgoritmen, enz.

Uiteindelijk is het probleem dat een boomcontainer die voor iedereen nuttig genoeg zou zijn, te zwaar zou zijn om de meeste mensen die hem gebruiken tevreden te stellen. Als u op zoek bent naar iets krachtigs, Boost Graph Libraryis in wezen een superset van waar een boombibliotheek voor zou kunnen worden gebruikt.

Hier zijn enkele andere algemene boomimplementaties:

• De boom van Kasper Peeters.hh
• Adobe’s bos
• core::tree

Antwoord 3, autoriteit 27%

De filosofie van de STL is dat je een container kiest op basis van garanties en niet op basis van hoe de container is geïmplementeerd. Uw keuze voor een container kan bijvoorbeeld gebaseerd zijn op de behoefte aan snelle opzoekingen. Wat u ook interesseert, de container kan worden geïmplementeerd als een unidirectionele lijst – zolang het zoeken erg snel is, zou u tevreden zijn. Dat komt omdat je de internals hoe dan ook niet aanraakt, je gebruikt iterators of lidfuncties voor de toegang. Uw code is niet gebonden aan hoe de container is geïmplementeerd, maar aan hoe snel deze is, of het een vaste en gedefinieerde volgorde heeft, of het efficiënt is in de ruimte, enzovoort.

Antwoord 4, autoriteit 27%

“Ik wil een hiërarchie van objecten opslaan als een boom”

C++11 is gekomen en gegaan en ze zagen nog steeds geen noodzaak om een std::treeaan te bieden, hoewel het idee wel opkwam (zie hier). Misschien is de reden dat ze dit niet hebben toegevoegd, dat het triviaal eenvoudig is om je eigen containers te bouwen bovenop de bestaande containers. Bijvoorbeeld…

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

Een eenvoudige verplaatsing zou recursie gebruiken…

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

Als u een hiërarchie wilt behouden enu wilt dat deze werkt met STL-algoritmen, dan kan het ingewikkeld worden. Je zou je eigen iterators kunnen bouwen en enige compatibiliteit bereiken, maar veel van de algoritmen hebben gewoon geen zin voor een hiërarchie (bijvoorbeeld iets dat de volgorde van een bereik verandert). Zelfs het definiërenvan een bereik binnen een hiërarchie kan een rommelige aangelegenheid zijn.

Antwoord 5, autoriteit 25%

Als u op zoek bent naar een RB-tree-implementatie, dan stl_tree.his misschien ook geschikt voor jou.

Antwoord 6, autoriteit 7%

de std::map is gebaseerd op een roodzwarte boom. Je kunt ook andere containersgebruiken om je eigen soorten bomen te implementeren.

Antwoord 7, autoriteit 5%

In zekere zin is std::map een boom (het moet dezelfde prestatiekenmerken hebben als een gebalanceerde binaire boom), maar het onthult geen andere boomfunctionaliteit. De waarschijnlijke redenering achter het niet opnemen van een echte boomgegevensstructuur was waarschijnlijk gewoon een kwestie van niet alles in de stl. De stl kan worden gezien als een raamwerk om te gebruiken bij het implementeren van uw eigen algoritmen en gegevensstructuren.

In het algemeen, als er een basisbibliotheekfunctionaliteit is die je wilt, die niet in de stl staat, is de oplossing om te kijken naar BOOST.

Anders is er een stelvan bibliothekenuitdaar, afhankelijk van de behoeften van uw stamboom.

Antwoord 8, autoriteit 3%

Alle STL-containers worden extern weergegeven als ‘reeksen’ met één iteratiemechanisme.
Bomen volgen dit idioom niet.

Antwoord 9, autoriteit 3%

Omdat de STL geen “alles”-bibliotheek is. Het bevat in wezen de minimale structuren die nodig zijn om dingen te bouwen.

Antwoord 10, autoriteit 3%

Dit ziet er veelbelovend uit en lijkt te zijn wat u zoekt:
http://tree.phi-sci.com/

Antwoord 11, autoriteit 3%

Ik denk dat er verschillende redenen zijn waarom er geen STL-bomen zijn. Bomen zijn in de eerste plaats een vorm van recursieve datastructuur die, net als een container (lijst, vector, set), een heel andere fijne structuur heeft die de juiste keuzes lastig maakt. Ze zijn ook heel gemakkelijk te construeren in basisvorm met behulp van de STL.

Een eindige geroote boom kan worden gezien als een container die een waarde of nuttige lading heeft, bijvoorbeeld een instantie van een klasse A en een mogelijk lege verzameling van geroote (sub) bomen; bomen met een lege verzameling subbomen worden gezien als bladeren.

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
{};

Je moet een beetje nadenken over iteratorontwerp enz. en welke product- en co-productbewerkingen je toelaat om te definiëren en efficiënt te zijn tussen bomen – en de originele STL moet goed geschreven zijn – zodat de lege set, vector of list container is in het standaardgeval echt leeg van elke payload.

Bomen spelen een essentiële rol in veel wiskundige structuren (zie de klassieke artikelen van Butcher, Grossman en Larsen; ook de papieren van Connes en Kriemer voor voorbeelden van hoe ze kunnen worden samengevoegd en hoe ze worden gebruikt om op te sommen). Het is niet juist om te denken dat hun rol eenvoudigweg is om bepaalde andere operaties te vergemakkelijken. In plaats daarvan vergemakkelijken ze die taken vanwege hun fundamentele rol als datastructuur.

Naast bomen zijn er echter ook “co-trees”; de bomen hebben vooral de eigenschap dat als je de root verwijdert, je alles verwijdert.

Beschouw iterators in de boom, waarschijnlijk zouden ze worden gerealiseerd als een eenvoudige stapel iterators, naar een knooppunt en naar zijn ouder, … tot aan de wortel.

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

U kunt er echter zoveel hebben als u wilt; gezamenlijk vormen ze een “boom”, maar waar alle pijlen in de richting van de wortel stromen, kan deze co-boom door iterators worden herhaald naar de triviale iterator en wortel; er kan echter niet overheen of omlaag worden genavigeerd (de andere iterators zijn hem niet bekend) noch kan het geheel van iterators worden verwijderd, behalve door alle instanties bij te houden.

Bomen zijn ongelooflijk nuttig, ze hebben veel structuur, dit maakt het een serieuze uitdaging om de definitief juiste aanpak te krijgen. Naar mijn mening is dit de reden waarom ze niet zijn geïmplementeerd in de STL. Bovendien heb ik in het verleden mensen religieus zien worden en het idee van een type container met instanties van zijn eigen type uitdagend vinden – maar ze moeten het onder ogen zien – dat is wat een boomtype vertegenwoordigt – het is een knooppunt met een eventueel lege verzameling (kleinere) bomen. De huidige taal staat het toe zonder uitdaging, mits de standaardconstructor voor container<B>geen ruimte op de heap (of ergens anders) toewijst voor een B, enz.

Ik zou het fijn vinden als dit, in een goede vorm, zijn weg naar de standaard zou vinden.

Antwoord 12, autoriteit 2%

IMO, een omissie. Maar ik denk dat er een goede reden is om geen boomstructuur in de STL op te nemen. Er zit veel logica in het onderhouden van een boomstructuur, die het best kan worden geschreven als lidfuncties in het basis TreeNode-object. Wanneer TreeNodeis ingepakt in een STL-header, wordt het alleen maar rommeliger.

Bijvoorbeeld:

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); } 
} ;

Antwoord 13

Als we de antwoorden hier lezen, zijn de veelvoorkomende genoemde redenen dat men niet door de boom kan gaan of dat de boom niet dezelfde interface aanneemt als andere STL-containers en dat men geen STL-algoritmen met een dergelijke boomstructuur zou kunnen gebruiken.

Met dat in gedachten heb ik geprobeerd mijn eigen boomgegevensstructuur te ontwerpen die een STL-achtige interface zal bieden en zoveel mogelijk bruikbaar zal zijn met bestaande STL-algoritmen.

Mijn idee was dat de tree gebaseerd moet zijn op de bestaande STL-containers en dat deze de container niet mag verbergen, zodat deze toegankelijk is voor gebruik met STL-algoritmen.

Het andere belangrijke kenmerk dat de boom moet bieden, zijn de doorlopende iterators.

Dit is wat ik heb kunnen bedenken: https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp

En hier zijn de tests: https: // github .com / CPPFW / UTKI / BLOB / MASTER / Tests / Tree / Tests.CPP

Antwoord 14

Alle STL-containers kunnen worden gebruikt met iterators. Je kunt geen iterator een boom hebben, omdat je niet ” één juiste ‘manier hebt, ga door de boom.