c++iteratorforward-list

Forward Iterator - Const version issue


I can't seem a way to fix this issue. I have implemented a templated forward iterator that I'd like to also use as const_iterator in my ForwardList class. What I tried so far is using an alias, and insert const as template argument, but it doesn't seem to work.

This is my forward iterator:

    template<typename T>
    class forward_iterator {
    private:
        Node<T>* m_iterator;

    public:
        using value_type = T;
        using reference = T&;
        using pointer = value_type*;
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;

        constexpr forward_iterator(Node<T>* forw_iter) : m_iterator{ forw_iter } {}

        constexpr Node<T>* getNodeAddress() const noexcept { return m_iterator; }
        constexpr Node<T>* getNodeNextAddress() const noexcept { return m_iterator->next; }
        constexpr reference operator*() const noexcept { return m_iterator->data; }
        constexpr pointer operator->() const noexcept { return m_iterator; }
        constexpr forward_iterator& operator++() noexcept {
            m_iterator = m_iterator->next;
            return *this;
        }
        constexpr forward_iterator operator++(int) noexcept {
            forward_iterator tmp(*this);
            m_iterator = m_iterator->next;
            return tmp;
        }
        constexpr friend bool operator== (const forward_iterator& first, const forward_iterator& second) noexcept { return (first.m_iterator == second.m_iterator); }
        constexpr friend bool operator!=(const forward_iterator& first, const forward_iterator& second) noexcept { return !(first.m_iterator == second.m_iterator); }
    };

And this is how I use the aliases in the ForwardList class:

template<typename Type>
    class ForwardList {
    private:
        Node<Type>* m_head;
        Node<Type>* m_tail;
        std::size_t m_size{};       

    public:
        using value_type = Type;
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using reference = value_type&;
        using const_reference = const value_type&;
        using pointer = Type*;
        using const_pointer = const pointer;
        using iterator = forward_iterator<value_type>;
        using const_iterator = forward_iterator<const Type>;

This is the node struct:

    template<typename T>
    struct Node {
        T data;
        Node* next;
        Node() = default;
        constexpr explicit Node(const T& data)
            : data{ data } {}
    };

I get an error when I use const_iterator though. For example:

constexpr const_iterator cbegin() const noexcept {
            return const_iterator(m_head);
        }

^ In the iterator functions, I get "Cannot convert from container::Node<Type> *const to container::forward_iterator<const Type>.

Another example:

constexpr iterator emplace_after(const_iterator position, Args...args)

^ In emplace_after, I can't pass in a normal "list.begin()" iterator, because the function cannot be found. I have to instead pass "list.cbegin()".

If anyone coud help be understand what's wrong that'd be fantastic.


Solution

  • The below makes your forward_iterator<const T> point at a Node<const T> while the forward_iterator<T> will point at a Node<T>. Both should point at a Node<T> whether T is const or not itself:

    template<typename T>
    class forward_iterator {
    private:
        Node<T>* m_iterator;
    

    I find it easier to create the iterator as a class template inside the container class template so that the original T is available. If you want to do it outside the class, you could add a template parameter to your iterator template:

    template<typename OrigT, typename T>
    class forward_iterator {
    private:
        Node<OrigT>* m_iterator;
    
    public:
        constexpr forward_iterator_impl(Node<OrigT>* forw_iter) : m_iterator{ forw_iter } {}
        ...
    

    And in the container class template:

    template<typename Type>
    class ForwardList {
    public:
        ...
        using iterator = forward_iterator<value_type, value_type>;
        using const_iterator = forward_iterator<value_type, const value_type>;
    

    By moving both the node and the iterator into the container class. It becomes easier to get it right. Demo