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?
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?