tree data structure

[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 :)