binary-search-tree: left() and right() return modifiable subtree
- 主要言語
- C++
- スター
- 290
- フォーク
- 244
- PR マージ指標
- 30日以内にマージされた PR はありません
説明
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.
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
評価
この issue はまだ評価されていません。