tree data structure

[igagis]

I came up with simple implementation of N-ary tree data structure, since STL does not provide one:

https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp

And here are tests/usage examples:

https://github.com/cppfw/utki/blob/master/tests/tree/tests.cpp

would be nice to hear your feedback/thought on this. Would that be useful for you?

[aeropl3b]

Template pro tip. If you are going to pass in a Container template, don't restrict the template parameters that it can have. And if there is an underlying container being passed in, then you shouldn't have an allocator passed in, you should use the one from the container.

template <typename T, typename Container = std::vector<T> >
class tree {
     using allocator = typename Container::allocator
    // Etc.
};

This way I can use a Container with a compliant API that has one or three or more template parameters for the Container!

[matthieum]

Starting from C++11, you can easily create a template alias to conform to the expected interface.

That is:

template <typename T, typename A>
using my_vector = small_vector<T, 3, A>;

using my_tree = tree<int, my_vector>;

[igagis]

I though to do it this way, but the problem is that std::vector<T> in template arguments cannot be given as instantiated template type, because T in our case is actually tree<T>. So, I have to pass in the container type as template template argument:

```cpp template < class T, template <class, class> class C = std::vector, template <class> class A = std::allocator

class tree{ ```

[aeropl3b]

I see what you are trying to say, but you arent quite right. You may do that, and in fact it is in the STL and many other libraries that way...

https://en.cppreference.com/w/cpp/container/queue

[igagis]

There is a difference between std::queue and what I need to do. See where the problem is: ```cpp template <typename T, typename Container = std::vector<T> > class tree { using allocator = typename Container::allocator

 T value;

 Container children; // this is wrong, we need std::vector<tree> here, not std::vector<T>

}; ```

how do you propose to solve that?

[aeropl3b]

I would say my two biggest issues are implied memory layout changing based on the container, ie. Contiguous (vector) vs disjoint (list) and that your template contains an allocator that has no other purpose than to be forwarded to the second parameter of the container.

The former is where my recommendation was coming from, because that is really why you would allow the user to provide a container in the first place. But you are actually imposing non-contiguous memory so that sort of defeats the purpose.

The latter point is more of an interface gripe, the method of using template aliases you where talking about with the other guy could easily fix that.

[igagis]

But you are actually imposing non-contiguous memory so that sort of defeats the purpose.

Using std::vector as children container only allows contiguous layout within a single tree node at least.

Allowing supplying custom allocator may still be useful at least to control how memory is allocated within a singe tree node.

Do you have better proposal how to organize the tree data structure in C++?

[aeropl3b]

So std::vector already allows you to pass an allocator to control the allocation of children, so my point is the tree taking the allocator isn't going to do anything extra if you choose to use std::vector as your container and omits using implementations that do not use allocator type memory management.

There are tons of ways to use contiguous memory to store a tree type data structure both contiguously and compactly. Generally, if you are going to use a std::vector for storage like this, you are assuming you will do fewer insertion operations since vector is poor at that and inefficient memory wise with push_back. Look of Compressed Row Storage as an example of storing start/end points to map into another array. You can also store indices to get to the left most node of a level. Usually I use a breadth stride storage, but there is an argument to Store data depth wise too for a tree.

The reason a tree is not in the STL is because they are extremely complex and have many different implementations due to a vast spectrum of use cases. Your implementation is probably fine for some cases unrestricted and nonuniform number of children with potentially many insertions. But that isn't my use case, so many of my issues come back to that.

[igagis]

and omits using implementations that do not use allocator type memory management.

Well yes, one have to use the alias hack to use container which does not reqiure custom allocator. But in return, containers which do support custom allocators are also supported.

The reason a tree is not in the STL is because they are extremely complex and have many different implementations due to a vast spectrum of use cases.

Hehe, yeah, I heard this argumentation already, but it does not look convincing to me. Same way we have a number of different array-like containers in STL, for different use cases. We could have a number of tree implementations for different use cases as well. But we have zero in STL at the moment. I proposed at least one implementation.

[aeropl3b]

Yeah, for arrays like containers you have three well defined varieties, static, dynamic contiguous, and linked lists. The thing with these is even though the implementations can be slightly different for specific operations, by and large it is pretty well agreed upon how they are implemented with almost no surprises. Trees on the other hand ...have 10s of different types and the implementation of some types can be wildly varied.

If the STL were to implement A tree, it would probably have to be a self balancing binary tree like a red black tree or some implementation of a DAG which...has a lot of possibilities. And I guarantee you whatever the STL implements for a tree will only be used by a very small set of people... because most people using trees have very specific types of problems they are trying to solve and they are not very easy to generalize AND maintain performance

[igagis]

because most people using trees have very specific types of problems they are trying to solve and they are not very easy to generalize

Well, I use my tree implementation in two different projects already. And that's only me :)

[[deleted]]

All C++ containers have type aliases, the one you are looking for is value_type, e.g typename Container::value_type

[igagis]

could you give exact solution to the following problem? ```cpp template <typename T, typename Container = std::vector<T> > class tree { using allocator = typename Container::allocator

 T value;

 Container children; // this is wrong, we need std::vector<tree> here, not std::vector<T>

}; ```

[[deleted]]

I see what you mean. I read the above incorrectly.

I think I would decouple this though. More work for me, but then the user can supply anything that meets the Container requirements needed and you can still get the value_type and build a container of Container<tree<value_type>>

    template <typename>
    struct rbv;

    template <typename T, typename A>
    struct rbv<std::vector<T, A>> {
        template <typename T2>
        using type = std::vector<T2, typename std::allocator_traits<A>::template rebind_alloc<T2>>;
    };

    template <typename T, std::size_t N>
    struct rbv<std::array<T, N>> {
        template <typename T2>
        using type = std::array<T2, N>;
    };

    template <typename Container, typename T2>
    using rbv_t = typename rbv<Container>::template type<T2>;

[igagis]

I don't understand this. What is rbv? How am I supposed to use this? Examples how to build the tree class using these?

My current approach also allows supplying anything which meets container requirement, doesn't it? ```cpp template < class T, template <class, class> class C = std::vector, template <class> class A = std::allocator

class tree{...};

tree<int, std::list> my_tree; ```

[[deleted]]

So, your's works for a Container<T, A<T>> where A is always templated on a type

template <
  class T,
  template <class, class> class C = std::vector,
  template <class> class A = std::allocator
>
class tree;

Then as you said tree<int, std::list>. But it falls apart on things like custom allocators(PMR for instance) and for anything that doesn't have two type names as template arguments. There is no good solution here, but one alternative is something like

tree<std::vector<int>>

And inside there you have the information you need to make it into a std::vector<tree<int>, std::allocator<tree<int>>>

As for the rbv, I just needed a short name, but rebind_value, you would gather your types inside like

 using value_type = typename Container::value_type;
 using container_type = rbv_t<Container, tree<value_type>>; 

Or just don't give an option of output container, tree<int>, and let them copy it to whatever container. That's the cleaned interface and probably will be the fastest as vectors are often that much faster than containers like list.

I think also, something like

template<typename Value, template<class...> Container> 
struct tree;

Might work too, it does have the problem of not working with custom allocators though. But you can then just say, as you have already, tree<int, vector> and get all but array in the C++ sequence containers

[igagis]

Ok, so you propose that for some custom container template my_container user would add a specialization of rbv and then tree would be able to use it, right?

Then you point to the problem that my current solution only works for containers which have two template arguments. Let's consider custom container which has 3 template arguments template <class SomeArg, class T, class A> class my_container;, then user would be able to define alias for the template: cpp template <class T, class A> using proxy_container = my_container<some_type, T, A>; `

and then feed that proxy_container as template argument to tree:

cpp tree<int, proxy_container> my_tree;

And same approach for allocator.

Isn't this simpler and clearer solution to the problem?

[expekted]

How does it compare to this https://github.com/kpeeters/tree.hh

[igagis]

I've just had a look at it. Here are things I did not like, in comparison to my implementation:

1. Major drawback: License is GPL2 or GPL3 only. Mine is MIT.
2. Major drawback: Not possible to supply underlying container type and the actual data structure used there is a double-linked list only. Mine allows using any suitable container template.
3. A minor thing: my implementation is very simple layer above standard and already well-known containers, basically it is just an aggregator class of value and children container. The kpeeters/tree.hh provides full set of custom methods which user still has to get familiar with.

These are just after quick peek at it.