exercism / exercism/cpp

binary-search-tree: left() and right() return modifiable subtree

Ouverte
#264 6 commentaires 1 réaction 0 personnes assignées Voir sur GitHub
Langage dominant
C++
Étoiles
290
Forks
244
Métriques de merge des PR
Aucune PR mergée en 30 j

Description

In the exercise "`binary-search-tree`" the methods `left()` and `right()` are hard to implement correctly. The example implementation itself is IMHO incorrect.

The tests look like this:
```cpp
template
using tree_ptr = typename std::unique_ptr>;

template
static void test_leaf(const tree_ptr &tree, const T& data, bool has_left, bool has_right)

//...

test_leaf(tested->left(), 2, false, false);
```

That forces implementations of `binary_tree::left()` (and `binary_tree::right()`) to return a `tree_ptr` reference or rvaue which points to a non-`const` subtree.
Remember: `const std::unique_ptr` means that the `unique_ptr` itself is `const`, not the object it points to.

Somebody could take the example implementation (`example.h`) and write
```cpp
auto tree = binary_tree::binary_tree(100);
tree.insert(50);
tree.left()->insert(150);
```
and thus invalidate the invariant of `tree`.

I consider any implementation of a binary search tree that can be corrupted that way as faulty. I came up with three alternatives that avoid this issue and pass the current tests:

- `binary_tree` could have a member variable `allow_insert` that is `true` for the root and `false` for all subtrees
- `binary_tree` could have a parent pointer and `insert()` could check for each of its parents if the new value violates that parent's invariant
- `left()` and `right()` could copy the subtree and return a `unique_ptr` to that copy.

But IMHO none of those alternatives feels right.

The easiest solution would be if `left()` and `right()` could return `const` raw pointers. But one could argue that raw pointers result in unclear ownership.

Guide de contribution

Aucun guide de contribution indexé pour ce dépôt

Piste de recherche

Commencez par l’exercice de binary-search-tree et examinez example.h, en vous concentrant sur binary_tree::left(), binary_tree::right() et insert(). Comparez leur ownership et leur constness avec les tests actuels présentés dans l’issue. C’est terminé lorsque l’exemple et les tests s’accordent sur une API de sous-arbre const-safe qui ne peut pas invalider l’invariant de l’arbre.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Évaluation

Stack technique
cpp
Domaine
backend
Type d'issue
Bug
Difficulté
5/5
Temps estimé
Plus d'une semaine
Activité
À l'abandon
Clarté
À clarifier
Accessibilité débutants
25/100

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.