Determine type of template parameter in template

Question

I am trying to implement a generic linked list and linked list iterator in C++. I have a node struct as follows

template <typename T>
struct Node
{
    T m_data;
    Node<T>* m_next;
};

I also have a linked list iterator that is a template so it can generate both regular and const iterators.

template <typename NodeType>
class LinkedListIterator
{  
private:
    NodeType* m_node;
public:
    LinkedListIterator(NodeType* n);
    T& operator*() const;
};

My question is how do I properly declare the operator*() function? My expectation is that something like the following should work

LinkedListIterator<const Node<T>> my_iter(some_node_pointer);
*my_iter = new_value; // should not work

I understand that returning T in the operator*() does not make sense since this class does not have access to the typename in the Node class.

I found a work around by creating an alias to the type inside the Node class like so

template <typename T>
struct Node
{
    typedef T type_value;
    // rest of Node class...
};

and now I can do the following in my iterator class

template <typename NodeType>
class LinkedListIterator
{
public:
    typename NodeType::type_value& operator*() const;
};

This seems to work and will return the right value. So my question really should be, is this the best way to implement this? Do I need to have typedef to create an alias so that I can use that type? Or is there a way to determine the type inside the LinkedListIterator class?

The `typedef` (or better, `using` in C++11 and later) is one way to handle this, yes. Another way is to just use `auto`, eg: `auto& operator*() const { return m_node->m_data; }` — Remy Lebeau, Aug 14 '20 at 20:38
The "alias to the type inside" is what the C++ library itself does all the time. You'll be surprised to learn about the `value_type` member of every C++ container, and where that actually comes from. You guessed it. An alias. — Sam Varshavchik, Aug 14 '20 at 21:14
Though not related, I found `boost::typeindex::type_id_with_cvr().pretty_name();` is helpful to see what's the type of T and param. — BAKE ZQ, Aug 15 '20 at 09:55

Jan Schultke · Accepted Answer · 2020-08-14T22:25:14.033

Using a typedef like this is the canonical way to do it and frequently done in the standard library. In fact, all LegacyIterators should define value_type, difference_type, reference, pointer, and iterator_category. Only then can their traits be accessed universally using std::iterator_traits.

For example:

// a simple forward iterator
struct Iterator {
    using value_type = int;
    using reference = value_type &;
    using pointer = value_type *;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    // LegacyIterators also need two operators to be defined:

    // the result of operator* is unspecified, we can choose it freely
    value_type operator*();
    // operator++ needs to return a reference to self
    Iterator& operator++();
};

// we can now access the traits universally, as can various standard library functions
static_assert (std::is_same_v<std::iterator_traits<Iterator>::value_type, int> );

In summary, what you're doing is the right way to go about it, but you should stick to these exact names so that the standard library can access the traits of your iterator. Also I would recommend using using instead of typedef. Not only does it have = as a visual separator but it's universally applicable, e.g. it can be templated unlike typedef. See What is the difference between 'typedef' and 'using' in C++11?

Determine type of template parameter in template

1 Answers1