Thoughts about the Entry API

The entry API has many tricky constraints that are non-obvious, which makes the key being a reference or not a big issue. I discussed this a while back here: Head-Desking on Entry API 4.0

The reason insertion methods don’t return an Entry is because this is, in general, non-trivial to do. Inserting can completely restructure the data structure, and reconstituting the entry could be very expensive if this wasn’t desired.

Consider, for instance, a tree without parent pointers. An Entry for such a type is a stack of the searched nodes. Inserting could trigger a total rebalance, requiring a brand-new search stack to be computed.

1 Like