c++stliteratorconst-iteratorforward-list

Implementation my own List and iterator STL C++


Hi everyone,

I'm having problems implementing my own List with iterator for the project at Univeristy. What should I do for correct iterating over loop? Could somebody help me? Sory for my English if is incorrect.

#ifndef __List__
#define __List__

template <class type>
class List
{
public:
    struct Node
    {
        type value;
        Node* next;
    };
    Node* root;
    class iterator
    {
    public:
        typedef iterator self_type;
        typedef Node& reference;
        typedef Node* pointer;
        typedef std::forward_iterator_tag iterator_category;
        typedef int difference_type;
        iterator(pointer ptr) : ptr_(ptr) { }
        self_type operator++() { self_type i = *this->ptr_->next; return i; }
        self_type operator++(int junk) { ptr_++; return *this; }
        reference operator*() { return ptr_; }
        type operator->() { return ptr->value; }
        bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
        bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
    private:
        pointer ptr_;
    };

    class const_iterator
    {
    public:
        typedef const_iterator self_type;
        typedef type value_type;
        typedef Node& reference;
        typedef Node* pointer;
        typedef int difference_type;
        typedef std::forward_iterator_tag iterator_category;
        const_iterator(pointer ptr) : ptr_(ptr) { }
        self_type operator++() { self_type i = *this->ptr_->next; return i; }
        self_type operator++(int junk) { ptr_++; return *this; }
        const reference operator*() { return *ptr_; }
        const type operator->() { return ptr->value; }
        bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
        bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
    private:
        pointer ptr_;
    };

    List();
    List(std::initializer_list<type> vals);
    ~List();
    iterator begin()
    {
        return iterator(root);
    }
    iterator end()
    {
        return iterator(nullptr);
    }
    const_iterator begin() const
    {
        return const_iterator(root);
    }
    const_iterator end() const
    {
        return const_iterator(nullptr);
    }
    Node* last();
    void push_back(type obj);
};

template <class type>
List<type>::List()
{
    root = nullptr;
}

template <class type>
List<type>::List(std::initializer_list<type> vals)
{
    root = nullptr;
    for (auto& elem : vals)
        push_back(elem);
}

template <class type>
List<type>::~List()
{
}

template <class type>
typename List<type>::Node* List<type>::last()
{
    Node* tmp = root;
    while (tmp->next != nullptr)
        tmp = tmp->next;
    return tmp;
}

template <class type>
void List<type>::push_back(type obj)
{
    Node* tmp = new Node;
    tmp->value = obj;
    tmp->next = nullptr;
    if (root == nullptr)
        root = tmp;
    else
    {
        Node* l = last();
        l->next = tmp;
    }
}

#endif

I would like to iterate over my List like the first loop or even the second.

int main()
{
    List<Product*> ProductBase{ new Product("Lubella Spaghetti 500 g", 10.0, 3.1, 0.23, 1), new Product("Nescafé Gold Blend 200 g", 20.0, 1.2, 0.23, 1) };
    for (auto i = ProductBase.begin(); i != ProductBase.end(); ++i)
        i->display_product();
    for (auto elem : ProductBase)
        elem->display_product();
    system("PAUSE");
}

Solution

  • In the operator++ of the iterator and const_iterator you need to add

    _ptr = ptr_->next
    

    and I would rather not implement

    self_type operator++(int junk)
    

    in the iterator class. List iterators typically can only advance one step forward.

    Also, in the const_iterator, make sure you only return const pointers, so that the compiler will issue an error if the caller tries to use the const_iterator to mutate the list.