How can I use decltype as the template parameter for a return type of a templated class?

Question

See the following code

    template <typename T> 
    struct Node
    {
      T data;
      Node<T>* left;
      Node<T>* right;

      Node (T d, Node<T>* l = nullptr, Node<T>* r = nullptr) : data(d), left(l), right(r) {}
    };

    template <typename ItType>
    auto buildBinaryTree (ItType start, ItType end) -> Node<decltype(*start)>* // doesn't like this line
    {
      // implementation removed for simplicity of post as the signature is the issue
    }

    template <typename T> 
    Node<T>* buildBinaryTree (std::vector<T>& v)
    {
      if  ( v.empty() )
       return nullptr; 

      std::sort(v.begin(), v.end());
      return buildBinaryTree (v.begin(), v.end()); 
    }

int main()
{
  std::vector<int> v { 1,2,3,4,5,6,7,8,9,10 };
  Node<int>* root = buildBinaryTree ( v );

Basically what is the best way to implement the following signature as I am getting a compile error

main.cpp:81:10: error: cannot initialize return object of type 'Node<int> *'
      with an rvalue of type 'Node<decltype(* start)> *'
  return buildBinaryTree (v.begin(), v.end());

Answer 1

Perhaps the nicest solution, if you are using the containers of the standard library, is the following:

template <typename ItType>
auto buildBinaryTree (ItType start, ItType end) -> Node<typename ItType::value_type>* 

UPDATE: We need an extra level of indirection with value_type as follows: std::iterator_traits<ItType>::value_type (kindly pointed out by Praetorian).

---

Another solution is to change

auto buildBinaryTree (ItType start, ItType end) -> Node<decltype(*start)>* 

to this (You may need to #include <type_traits>):

auto buildBinaryTree (ItType start, ItType end) -> Node<typename std::remove_reference<decltype(*start)>::type>* 

The gcc error message was clear:

error: cannot convert Node<int&>* to Node<int>* in return

apparently, you are using clang, which, unfortunately, doesn't give such a clear error message... :(

Answer 2

Try this:

Node<typename std::decay<decltype(*start)>::type> *

You need to #include <type_traits>.

A cleaner solution might be to use std::iterator_traits<ItType>::value_type, though.