exercism / exercism/cpp

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

Đang mở
#264 6 bình luận 1 reaction 0 người được giao Xem trên GitHub
Ngôn ngữ chính
C++
Star
290
Fork
244
Chỉ số merge pull request
Không có pull request nào được merge trong 30 ngày

Mô tả

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.

Hướng dẫn đóng góp

Chưa lập chỉ mục được hướng dẫn đóng góp cho kho mã nguồn này

Hướng nghiên cứu

Bắt đầu với bài tập binary-search-tree và kiểm tra example.h, tập trung vào binary_tree::left(), binary_tree::right() và insert(). So sánh ownership và constness của chúng với các test hiện tại được hiển thị trong issue. Được xem là hoàn tất khi example và các test thống nhất về một subtree API const-safe không thể làm mất invariant của cây.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Đánh giá

Công nghệ
cpp
Lĩnh vực
backend
Loại issue
Lỗi
Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức độ hoạt động
Đình trệ
Độ rõ ràng
Cần làm rõ
Mức phù hợp với người mới
25/100

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.