Hacker News Reader

Comment by gumby | Hacker News Reader

First of all, Box is a terrible name because the term has been used for boxed pointers (putting tag bits into unused parts of the pointer) and, in some languages, immediates, for four decades at least. Also all C++ standard identifiers are thankfully lowercase snake case.

I don't understand why the author writes "raw value is straightforward and efficient... However, you can't allocate them dynamically and you can't build recursive data structure such as a linked list or a tree with them." 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.

And the deep copy behavior is rarely what I want in a mutable structure anyway (it's always safe, if usually wasteful, in a R/O structure).

View on HN

>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.

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.

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.

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.

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++.

Ah, thanks.

Reply on news.ycombinator.com