4 ms·

>There is clearly something I don't understand here. Consider an int -- you can dynamically allocate one, you can put it in a tree putting a box into a tree wil

>There is clearly something I don't understand here. Consider an int -- you can dynamically allocate one, you can put it in a tree putting a box into a tree will still require other data applicable to the tree itself, same as an int), and so on. So I don't understand the point being made here. To make a tree, you need something allowing an object (a tree node) to own an object of the same type as itself (another tree node). There are various options for this: raw pointer, unique_ptr, shared_ptr, auto_ptr, box. Without using one of those options, the tree isn't possible. That's the author's point. std::box can be used in place of one of the other pointer types.

nurettin 3y ago
Can't you use edge lists/arrays to represent your tree? And maybe even topologically sort your node list according to whatever kind of traversal you want to make? At least that's what I used to do in the qbasic days.
- Thorrez 3y ago
  Yeah, good point. You could use std::vector or std::list. Under the hood those both use pointers, but kind of similar to how under the hood std::unique_ptr or std::box would use raw pointers. In the specific case of a binary tree, where you only need left and right, std::vector/std::list would be overkill and slow down your program. But in a b-tree, std::vector would be good. You can't use std::array or plain C arrays for the same reason you can't use raw values.
gumby 3y ago
I understand that fine. My problem is the author calls out the “raw value” as distinct from “raw pointer”, implying a non pointer value which would be the content of a tree node. This makes the entire paragraph hard to make sense of.
- maattdd 3y ago
  We don't care about the content of the node. The interesting part is how do you define the Node itself. struct Node<T> { Node<T> left; Node<T> right; }; would obviously be the best choice (what I call in the article "raw value"). But it's not valid C++.
  - gumby 3y ago
    Ah, thanks.

nurettin 3y ago

Can't you use edge lists/arrays to represent your tree? And maybe even topologically sort your node list according to whatever kind of traversal you want to make? At least that's what I used to do in the qbasic days.

Thorrez 3y ago
Yeah, good point. You could use std::vector or std::list. Under the hood those both use pointers, but kind of similar to how under the hood std::unique_ptr or std::box would use raw pointers. In the specific case of a binary tree, where you only need left and right, std::vector/std::list would be overkill and slow down your program. But in a b-tree, std::vector would be good. You can't use std::array or plain C arrays for the same reason you can't use raw values.

gumby 3y ago

I understand that fine. My problem is the author calls out the “raw value” as distinct from “raw pointer”, implying a non pointer value which would be the content of a tree node. This makes the entire paragraph hard to make sense of.

maattdd 3y ago
We don't care about the content of the node. The interesting part is how do you define the Node itself. struct Node<T> { Node<T> left; Node<T> right; }; would obviously be the best choice (what I call in the article "raw value"). But it's not valid C++.
- gumby 3y ago
  Ah, thanks.