I think you’re right, this is by far the most difficult exercise on the C++ track.
Not only does it force you to use std::unique_ptr, it’s also not obvious at first glance and you have to read the error messages (which are notoriously hard to read) or the tests carefully.
And the tests use a range-based for loop with the comment “The tests below require an implementation of an iterator. You can get more details here: http://www.cplusplus.com/reference/iterator/” That page describes the iterator categories of the standard library and their syntactic and semantic requirements which is a lot to take in.
I’ve had a lot of discussions with students about these two aspects of the exercise, you’re not alone in your struggle.
I guess the intent of the original author was to enforce the use of std::unique_ptr for the left and right subtree of each node. I think that’s the right idea, the ownership of the subtrees should definitely be managed by a smart pointer. Without that explicit requirement in the tests I bet there would be a lot of solutions with owing raw pointers which is unidiomatic and dangerous.
But on the other hand having the member functions left() and right() return references to the std::unique_ptr members feels a little bit weird, most C++ programmers I know would just return (non-owning) raw pointers.
(And that invites a subtle issue where a value can be added to a subtree in a way that violates the invariant of the larger tree. That’s a tricky one.)
Maybe we could improve the exercise by either amending the instructions with a C++ specific part that explains what the solution should use std::unique_ptr and that left() and right() should return references to those members.
Or we could add the signatures of left() and right() to the initial .h file.
Or we could change the return type of left() and right() to raw pointers and add the std::unique_ptr to the initial .h file.
As for the range-based for loop and iterator: C++ is a large and complex programming language. I guess the author of this exercise saw and seized the opportunity to include these two concepts. I can understand that, they are important, they are not required in any other exercises on the C++ track, and AFAIK there’s no other exercise where they would fit naturally.
To solve this exercise you have to:
- define a
struct or class that acts as some sort of iterator (I’ll call it iterator from here on.)
- define an
operator* that returns the data of the current node.
- define an
operator++() that “increments” the iterator so that it refers to the next node
- define an
operator!= that compares two iterator and returns false iff they refer to the same node.
- define a function
begin() that returns an iterator which refers to the leftmost node in the tree
- define a function
end() that returns an iterator which represents the end of the tree
Maybe we could amend the instructions with a C++-specific explanation
(Almost?) all practice exercise here on Exercism start with a language-agnostic description of the task and some tests that specify the required output for a given input or sequence of operations.
I’m not a fan of breaking with that tradition and introducing C++-specific practice exercises that are tailored to a single concept in C++.
But maybe somebody else here has an idea.
