Why does the C STL not provide any tree containers

Question

Why does the C   STL not provide any  tree  containers  and what s the best thing to use instead   I want to store a hierarchy of objects as a tree  rather than use a tree as a performance enhancement

User · Answer

the std  map is based on a red black tree  You can also use other containers to help you implement your own types of trees

User · Answer

The STL s philosophy is that you choose a container based on guarantees and not based on how the container is implemented   For example  your choice of container may be based on a need for fast lookups   For all you care  the container may be implemented as a unidirectional list -- as long as searching is very fast you d be happy   That s because you re not touching the internals anyhow  you re using iterators or member functions for the access   Your code is not bound to how the container is implemented but to how fast it is  or whether it has a fixed and defined ordering  or whether it is efficient on space  and so on

User · Answer

Probably for the same reason that there is no tree container in boost  There are many ways to implement such a container  and there is no good way to satisfy everyone who would use it   Some issues to consider    Are the number of children for a node fixed or variable    How much overhead per node  - ie  do you need parent pointers  sibling pointers  etc    What algorithms to provide  - different iterators  search algorithms  etc    In the end  the problem ends up being that a tree container that would be useful enough to everyone  would be too heavyweight to satisfy most of the people using it  If you are looking for something powerful  Boost Graph Library is essentially a superset of what a tree library could be used for   Here are some other generic tree implementations    Kasper Peeters  tree hh   Adobe s forest   core  tree

User · Answer

Probably for the same reason that there is no tree container in boost  There are many ways to implement such a container  and there is no good way to satisfy everyone who would use it   Some issues to consider    Are the number of children for a node fixed or variable    How much overhead per node  - ie  do you need parent pointers  sibling pointers  etc    What algorithms to provide  - different iterators  search algorithms  etc    In the end  the problem ends up being that a tree container that would be useful enough to everyone  would be too heavyweight to satisfy most of the people using it  If you are looking for something powerful  Boost Graph Library is essentially a superset of what a tree library could be used for   Here are some other generic tree implementations    Kasper Peeters  tree hh   Adobe s forest   core  tree

User · Answer

All STL containers can be used with iterators  You can t have an iterator an a tree  because you don t have   one right   way do go through the tree

User · Answer

the std  map is based on a red black tree  You can also use other containers to help you implement your own types of trees

User · Answer

The STL s philosophy is that you choose a container based on guarantees and not based on how the container is implemented   For example  your choice of container may be based on a need for fast lookups   For all you care  the container may be implemented as a unidirectional list -- as long as searching is very fast you d be happy   That s because you re not touching the internals anyhow  you re using iterators or member functions for the access   Your code is not bound to how the container is implemented but to how fast it is  or whether it has a fixed and defined ordering  or whether it is efficient on space  and so on

User · Answer

All STL container are externally represented as  sequences  with one iteration mechanism  Trees don t follow this idiom

User · Answer

Because the STL is not an  everything  library  It contains  essentially  the minimum structures needed to build things

User · Answer

Reading through the answers here the common named reasons are that one cannot iterate through the tree or that the tree does not assume the similar interface to other STL containers and one could not use STL algorithms with such tree structure  Having that in mind I tried to design my own tree data structure which will provide STL-like interface and will be usable with existing STL algorthims as much as possible  My idea was that the tree must be based on the existing STL containers and that it must not hide the container  so that it will be accessible to use with STL algorithms  The other important feature the tree must provide is the traversing iterators  Here is what I was able to come up with  https   github com cppfw utki blob master src utki tree hpp And here are the tests  https   github com cppfw utki blob master tests tree tests cpp

User · Answer

IMO  an omission   But I think there is good reason not to include a Tree structure in the STL   There is a lot of logic in maintaining a tree  which is best written as member functions into the base TreeNode object   When TreeNode is wrapped up in an STL header  it just gets messier   For example   template  lt typename T gt  struct TreeNode     T  DATA      data of type T to be stored at this TreeNode    vector lt  TreeNode lt T gt    gt  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  lt typename T gt  struct Tree     TreeNode lt T gt   root        TREE LEVEL functions   void clear     delete root   root 0       void insert  T  data     if root root- gt insert data

User · Answer

Because the STL is not an  everything  library  It contains  essentially  the minimum structures needed to build things

User · Answer

Probably for the same reason that there is no tree container in boost  There are many ways to implement such a container  and there is no good way to satisfy everyone who would use it   Some issues to consider    Are the number of children for a node fixed or variable    How much overhead per node  - ie  do you need parent pointers  sibling pointers  etc    What algorithms to provide  - different iterators  search algorithms  etc    In the end  the problem ends up being that a tree container that would be useful enough to everyone  would be too heavyweight to satisfy most of the people using it  If you are looking for something powerful  Boost Graph Library is essentially a superset of what a tree library could be used for   Here are some other generic tree implementations    Kasper Peeters  tree hh   Adobe s forest   core  tree

User · Answer

Probably for the same reason that there is no tree container in boost  There are many ways to implement such a container  and there is no good way to satisfy everyone who would use it   Some issues to consider    Are the number of children for a node fixed or variable    How much overhead per node  - ie  do you need parent pointers  sibling pointers  etc    What algorithms to provide  - different iterators  search algorithms  etc    In the end  the problem ends up being that a tree container that would be useful enough to everyone  would be too heavyweight to satisfy most of the people using it  If you are looking for something powerful  Boost Graph Library is essentially a superset of what a tree library could be used for   Here are some other generic tree implementations    Kasper Peeters  tree hh   Adobe s forest   core  tree

User · Answer

In a way  std  map is a tree  it is required to have the same performance characteristics as a balanced binary tree  but it doesn t expose other tree functionality   The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl   The stl can be looked as a framework to use in implementing your own algorithms and data structures   In general  if there s a basic library functionality that you want  that s not in the stl  the fix is to look at BOOST   Otherwise  there s a bunch of libraries out there  depending on the needs of your tree

User · Answer

If you are looking for a RB-tree implementation  then stl tree h might be appropriate for you too

User · Answer

The STL s philosophy is that you choose a container based on guarantees and not based on how the container is implemented   For example  your choice of container may be based on a need for fast lookups   For all you care  the container may be implemented as a unidirectional list -- as long as searching is very fast you d be happy   That s because you re not touching the internals anyhow  you re using iterators or member functions for the access   Your code is not bound to how the container is implemented but to how fast it is  or whether it has a fixed and defined ordering  or whether it is efficient on space  and so on

User · Answer

There are two reasons you could want to use a tree   You want to mirror the problem using a tree-like structure  For this we have boost graph library  Or you want a container that has tree like access characteristics For this we have   std  map  and std  multimap  std  set  and std  multiset    Basically the characteristics of these two containers is such that they practically have to be implemented using trees  though this is not actually a requirement    See also this question  C tree Implementation

User · Answer

I want to store a hierarchy of objects as a tree    C  11 has come and gone and they still didn t see a need to provide a std  tree  although the idea did come up  see here    Maybe the reason they haven t added this is that it is trivially easy to build your own on top of the existing containers   For example     template lt  typename T  gt  struct tree node         T t     std  vector lt tree node gt  children          A simple traversal would use recursion     template lt  typename T  gt  void tree node lt T gt   walk depth first   const         cout lt  lt t     for   auto  amp  n  children   n walk depth first           If you want to maintain a hierarchy and you want it to work with STL algorithms  then things may get complicated   You could build your own iterators and achieve some compatibility  however many of the algorithms simply don t make any sense for a hierarchy  anything that changes the order of a range  for example    Even defining a range within a hierarchy could be a messy business

User · Answer

There are two reasons you could want to use a tree   You want to mirror the problem using a tree-like structure  For this we have boost graph library  Or you want a container that has tree like access characteristics For this we have   std  map  and std  multimap  std  set  and std  multiset    Basically the characteristics of these two containers is such that they practically have to be implemented using trees  though this is not actually a requirement    See also this question  C tree Implementation

User · Answer

Because the STL is not an  everything  library  It contains  essentially  the minimum structures needed to build things

User · Answer

All STL containers can be used with iterators  You can t have an iterator an a tree  because you don t have   one right   way do go through the tree

User · Answer

I think there are several reasons why there are no STL trees  Primarily Trees are a form of recursive data structure which  like a container  list  vector  set   has very different fine structure which makes the correct choices tricky  They are also very easy to construct in basic form using the STL   A finite rooted tree can be thought of as a container which has a value or payload  say an instance of a class A and  a possibly empty collection of rooted  sub  trees  trees with empty collection of subtrees are thought of as leaves    template lt class A gt  struct unordered tree   std  set lt unordered tree gt   A      template lt class A gt  struct b tree   std  vector lt b tree gt   A      template lt class A gt  struct planar tree   std  list lt planar tree gt   A       One has to think a little about iterator design etc  and which product and co-product operations one allows to define and be efficient between trees - and the original STL has to be well written - so that the empty set  vector or list container is really empty of any payload in the default case     Trees play an essential role in many mathematical structures  see the classical papers of Butcher  Grossman and Larsen  also the papers of Connes and Kriemer for examples of they can be joined  and how they are used to enumerate   It is not correct to think their role is simply to facilitate certain other operations  Rather they facilitate those tasks because of their fundamental role as a data structure    However  in addition to trees there are also  co-trees   the trees above all have the property that if you delete the root you delete everything   Consider iterators on the tree  probably they would be realised as a simple stack of iterators  to a node  and to its parent      up to the root    template lt class TREE gt  struct node iterator   std  stack lt TREE  iterator gt   operator     return  back             However  you can have as many as you like  collectively they form a  tree  but  where all the arrows flow in the direction toward the root  this co-tree can be iterated through iterators towards the trivial iterator and root  however it cannot be navigated across or down  the other iterators are not known to it  nor can the ensemble of iterators be deleted except by keeping track of all the instances    Trees are incredibly useful  they have a lot of structure  this makes it a serious challenge to get the definitively correct approach  In my view this is why they are not implemented in the STL  Moreover  in the past  I have seen people get religious and find the idea of a type of container containing instances of its own type challenging - but they have to face it - that is what a tree type represents - it is a node containing a possibly empty collection of  smaller  trees  The current language permits it without challenge providing the default constructor for container lt B gt  does not allocate space on the heap  or anywhere else  for an B  etc    I for one would be pleased if this did  in a good form  find its way into the standard

User · Answer

If you are looking for a RB-tree implementation  then stl tree h might be appropriate for you too

User · Answer

All STL container are externally represented as  sequences  with one iteration mechanism  Trees don t follow this idiom

User · Answer

I think there are several reasons why there are no STL trees  Primarily Trees are a form of recursive data structure which  like a container  list  vector  set   has very different fine structure which makes the correct choices tricky  They are also very easy to construct in basic form using the STL   A finite rooted tree can be thought of as a container which has a value or payload  say an instance of a class A and  a possibly empty collection of rooted  sub  trees  trees with empty collection of subtrees are thought of as leaves    template lt class A gt  struct unordered tree   std  set lt unordered tree gt   A      template lt class A gt  struct b tree   std  vector lt b tree gt   A      template lt class A gt  struct planar tree   std  list lt planar tree gt   A       One has to think a little about iterator design etc  and which product and co-product operations one allows to define and be efficient between trees - and the original STL has to be well written - so that the empty set  vector or list container is really empty of any payload in the default case     Trees play an essential role in many mathematical structures  see the classical papers of Butcher  Grossman and Larsen  also the papers of Connes and Kriemer for examples of they can be joined  and how they are used to enumerate   It is not correct to think their role is simply to facilitate certain other operations  Rather they facilitate those tasks because of their fundamental role as a data structure    However  in addition to trees there are also  co-trees   the trees above all have the property that if you delete the root you delete everything   Consider iterators on the tree  probably they would be realised as a simple stack of iterators  to a node  and to its parent      up to the root    template lt class TREE gt  struct node iterator   std  stack lt TREE  iterator gt   operator     return  back             However  you can have as many as you like  collectively they form a  tree  but  where all the arrows flow in the direction toward the root  this co-tree can be iterated through iterators towards the trivial iterator and root  however it cannot be navigated across or down  the other iterators are not known to it  nor can the ensemble of iterators be deleted except by keeping track of all the instances    Trees are incredibly useful  they have a lot of structure  this makes it a serious challenge to get the definitively correct approach  In my view this is why they are not implemented in the STL  Moreover  in the past  I have seen people get religious and find the idea of a type of container containing instances of its own type challenging - but they have to face it - that is what a tree type represents - it is a node containing a possibly empty collection of  smaller  trees  The current language permits it without challenge providing the default constructor for container lt B gt  does not allocate space on the heap  or anywhere else  for an B  etc    I for one would be pleased if this did  in a good form  find its way into the standard

User · Answer

Because the STL is not an  everything  library  It contains  essentially  the minimum structures needed to build things

User · Answer

IMO  an omission   But I think there is good reason not to include a Tree structure in the STL   There is a lot of logic in maintaining a tree  which is best written as member functions into the base TreeNode object   When TreeNode is wrapped up in an STL header  it just gets messier   For example   template  lt typename T gt  struct TreeNode     T  DATA      data of type T to be stored at this TreeNode    vector lt  TreeNode lt T gt    gt  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  lt typename T gt  struct Tree     TreeNode lt T gt   root        TREE LEVEL functions   void clear     delete root   root 0       void insert  T  data     if root root- gt insert data

User · Answer

Reading through the answers here the common named reasons are that one cannot iterate through the tree or that the tree does not assume the similar interface to other STL containers and one could not use STL algorithms with such tree structure  Having that in mind I tried to design my own tree data structure which will provide STL-like interface and will be usable with existing STL algorthims as much as possible  My idea was that the tree must be based on the existing STL containers and that it must not hide the container  so that it will be accessible to use with STL algorithms  The other important feature the tree must provide is the traversing iterators  Here is what I was able to come up with  https   github com cppfw utki blob master src utki tree hpp And here are the tests  https   github com cppfw utki blob master tests tree tests cpp

User · Answer

In a way  std  map is a tree  it is required to have the same performance characteristics as a balanced binary tree  but it doesn t expose other tree functionality   The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl   The stl can be looked as a framework to use in implementing your own algorithms and data structures   In general  if there s a basic library functionality that you want  that s not in the stl  the fix is to look at BOOST   Otherwise  there s a bunch of libraries out there  depending on the needs of your tree

User · Answer

This one looks promising and seems to be what you re looking for  http   tree phi-sci com

User · Answer

the std  map is based on a red black tree  You can also use other containers to help you implement your own types of trees

User · Answer

There are two reasons you could want to use a tree   You want to mirror the problem using a tree-like structure  For this we have boost graph library  Or you want a container that has tree like access characteristics For this we have   std  map  and std  multimap  std  set  and std  multiset    Basically the characteristics of these two containers is such that they practically have to be implemented using trees  though this is not actually a requirement    See also this question  C tree Implementation

User · Answer

There are two reasons you could want to use a tree   You want to mirror the problem using a tree-like structure  For this we have boost graph library  Or you want a container that has tree like access characteristics For this we have   std  map  and std  multimap  std  set  and std  multiset    Basically the characteristics of these two containers is such that they practically have to be implemented using trees  though this is not actually a requirement    See also this question  C tree Implementation

User · Answer

In a way  std  map is a tree  it is required to have the same performance characteristics as a balanced binary tree  but it doesn t expose other tree functionality   The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl   The stl can be looked as a framework to use in implementing your own algorithms and data structures   In general  if there s a basic library functionality that you want  that s not in the stl  the fix is to look at BOOST   Otherwise  there s a bunch of libraries out there  depending on the needs of your tree

User · Answer

In a way  std  map is a tree  it is required to have the same performance characteristics as a balanced binary tree  but it doesn t expose other tree functionality   The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl   The stl can be looked as a framework to use in implementing your own algorithms and data structures   In general  if there s a basic library functionality that you want  that s not in the stl  the fix is to look at BOOST   Otherwise  there s a bunch of libraries out there  depending on the needs of your tree

User · Answer

This one looks promising and seems to be what you re looking for  http   tree phi-sci com

User · Answer

I want to store a hierarchy of objects as a tree    C  11 has come and gone and they still didn t see a need to provide a std  tree  although the idea did come up  see here    Maybe the reason they haven t added this is that it is trivially easy to build your own on top of the existing containers   For example     template lt  typename T  gt  struct tree node         T t     std  vector lt tree node gt  children          A simple traversal would use recursion     template lt  typename T  gt  void tree node lt T gt   walk depth first   const         cout lt  lt t     for   auto  amp  n  children   n walk depth first           If you want to maintain a hierarchy and you want it to work with STL algorithms  then things may get complicated   You could build your own iterators and achieve some compatibility  however many of the algorithms simply don t make any sense for a hierarchy  anything that changes the order of a range  for example    Even defining a range within a hierarchy could be a messy business

User · Answer

the std  map is based on a red black tree  You can also use other containers to help you implement your own types of trees

User · Answer

The STL s philosophy is that you choose a container based on guarantees and not based on how the container is implemented   For example  your choice of container may be based on a need for fast lookups   For all you care  the container may be implemented as a unidirectional list -- as long as searching is very fast you d be happy   That s because you re not touching the internals anyhow  you re using iterators or member functions for the access   Your code is not bound to how the container is implemented but to how fast it is  or whether it has a fixed and defined ordering  or whether it is efficient on space  and so on

[c++] Why does the C++ STL not provide any "tree" containers?

Examples related to c++

Examples related to data-structures

Examples related to tree

Examples related to stl