Is There A Way To Remove Duplicate Code While Providing lvalue and rvalue Overloads?

Question

While learning C++ I decided to write a simple templated binary search tree (bst) and encountered the following problem: I want to be able to construct a bst by both passing it an lvalue like const T &val and an rvalue like T &&val. Similarly I want to be able to insert lvalues and rvalues. So I ended up with a lot of duplicate code which I don't like:

/// copy constructor
explicit inline constexpr binary_search_tree(const T &val)
    : _root{std::make_unique<binary_search_tree_node>(val)} {}

/// move constructor
explicit inline constexpr binary_search_tree(T &&val)
    : _root{std::make_unique<binary_search_tree_node>(std::move(val))} {}

for the constructors, where binary_search_tree_node is a private member ofbinary_search_tree which then had to provide copy and move constructor as well:

struct binary_search_tree_node {
  T value;
  std::unique_ptr<binary_search_tree_node> left;
  std::unique_ptr<binary_search_tree_node> right;

  // prohibit creation of tree_node without value
  inline constexpr binary_search_tree_node() = delete;

  /// copy constructor
  explicit inline constexpr binary_search_tree_node(const T &val)
      : value{val}, left{nullptr}, right{nullptr} {}

  /// move constructor
  explicit inline constexpr binary_search_tree_node(T &&val)
      : value{std::move(val)}, left{nullptr}, right{nullptr} {}
};

Also:

inline constexpr void insert(const T &v) {
  if (!_root) {
    _root = std::make_unique<binary_search_tree_node>(v);
    ++_size;
  } else {
    insert(_root, v);
  }
}

inline constexpr void insert(T &&v) {
  if (!_root) {
    _root = std::make_unique<binary_search_tree_node>(std::move(v));
    ++_size;
  } else {
    insert(_root, std::move(v));
  }
}

for the insert functions.

The list goes on when I want to search a value: Should I provide overloads for find(const T &val) and find(T &&val)..?

So my question is whether there is a way of combining these overloads or any other way to remove this duplicate code?

I read about reference collapsing rules but I am not sure whether I could make use of this concept here.

Any other thoughts or suggestions are also appreciated.

Answer 1

Yes, you can use reference collapsing to reduce the amount of function written.

For example, your function insert can use a rvalue reference + immediate context to leverage reference collapsing, resulting in a forwarding reference:

template<typename U>
inline constexpr void insert(U &&v) { // v is a forwarding reference
    if (!_root) {
        // we use std::forward to keep rvalue-ness
        // of the named object when v is an rvalue, but not when it's a lvalue
        _root = std::make_unique<binary_search_tree_node>(std::forward<U>(v));
        ++_size;
    } else {
        insert(_root, std::forward<U>(v));
    }
}

Even though the parameter is using an rvalue reference, lvalue will work here because of the reference collapsing. If U deduces to int&, then the parameter is kind of int& &&, which collapse to int&. On the contrary, if an rvalue is sent, it will deduce int as U so the parameter is int &&.

This pattern is called a forwarding reference.

As you can see, such code only has that property if template argument deduction is there for the forwarding parameter.

Be aware that making it a template will make it accept more types than anticipated if not constrained correctly.

You can also use a copy then move to avoid code duplication:

inline constexpr void insert(const T &v) {
    T copy = v;
    insert(std::move(copy)); // calls the rvalue overload
}