Convert object of custom template based iterator class to const_iterator

Question

I'm studying OOP course (C++ is a base language) at university. My task is to implement own linked list template container class. I did it almost completely but faced with problem. It is known that STL provides iterator and const_iterator classes for iteration through list. They have almost the same implementation, the major difference is that iterator's methods return references while const_iterator's methods — constant references. I followed https://stackoverflow.com/a/3582733/2108548 and created separated template class ListIterator. Then I declared with typedef classes Iterator and ConstIterator inside the class List.

I got something like this:

template<typename T>
class ListNode
{
public:
    ListNode(T *node_value = nullptr, ListNode *node_prev = nullptr, ListNode *node_next = nullptr):
        value(node_value), prev(node_prev), next(node_next) { }

    T *value;
    ListNode *prev, *next;
};

template<typename T>
class ListIterator
{
    typedef ListNode<T> Node;

public:
    ListIterator();
    ListIterator(Node *node);
    ListIterator(ListIterator const &other);
    ListIterator &operator++();
// ...
    Node *i;
};

template<typename T>
class List: public Container
{
    typedef ListIterator<T> Iterator;
    typedef ListIterator<T const> ConstIterator;
// ...
    Iterator begin() const
    {
        return Iterator(m_first->next);
    }
    ConstIterator const_begin() const
    {
        return ConstIterator(begin());
    }
// ...
};

All worked great until I decided to make "copy-constructor" Iterator -> ConstIterator. So I need constructor method that gets ListIterator<T> (where T is the data class name) and creates new object type ListIterator<T const>. But in fact ConstIterator's constructor gets T const as a template parameter, so I need to remove const for constructor's parameter. I found header type_traits which does this. So I wrote "copy-constructor": typedef typename std::remove_cv::type NoConstT; ListIterator(ListIterator const &other);

But it doesn't work! I got this error after requesing const_begin():

List<int> list1;
list1 << 1 << 2 << 3;
int i = *list1.const_begin(); 

error: 'ListIterator<T>::ListIterator(const ListIterator<typename std::remove_cv<_Tp>::type>&) [with T = int; typename std::remove_cv<_Tp>::type = int]' cannot be overloaded with 'ListIterator<T>::ListIterator(const ListIterator<T>&) [with T = int; ListIterator<T> = ListIterator<int>]'

But that's not all. To accomplish my goal have to convert ListNode<T> to ListNode<T const> as well. But I have one more problem there: each list node contains pointers to previous and next nodes and if I try to initialize them in node's constructor I'll get recursion. Of course I can create function that handles converting all ListNode<T> nodes to ListNode<T const> by iteration through them. But I don't like this solution: it has huge overhead!

I asked this question my teacher. He couldn't understand it for several minutes, then when he got it he said: "It's elementary!" — "But I stuck with it for 3-4 hours!" — "If so, throw away const iterators and finalize list container without them. I need time to understand your code" (as you see my code is quite simple in my opinion). As I understood he didn't know answer to this question. But I really want to know how to make it! How can I solve this problem?

Sorry for tons of mistakes — I'm not a native English speaker.

Have you looked at how this is handled for STL types? For instance, my implementation `std::vector::iterator` is actually a specialization of `std::vector::const_iterator`. — Chad, Apr 04 '13 at 16:23
Ok I added one solution.. I will visit it again after I get back from work — Alon, Apr 04 '13 at 16:47

yuri kilochek · Accepted Answer · 2013-04-04T17:14:09.600

You can indeed use <type_traits>, just not in the way you describe. One approach would be to always declare a constructor from the same type and declare from non-const one conditionally with enable_if only when template argument is indeed not constant. And node should always be non-const, this you can do with remove_const.

#include <type_traits>

template<typename T>
class ListNode
{
   //...   
};

template<typename T>
class ListIterator
{
    typedef ListNode<typename std::remove_const<T>::type> Node;

public:
    ListIterator() {}
    ListIterator(Node*) {}
    ListIterator(ListIterator const&) {}
    template <typename U>
    ListIterator(ListIterator<U> const&, typename std::enable_if<!std::is_const<U>()>::type* = nullptr) {}
};

template<typename T>
class List
{
public:
    typedef ListIterator<T> Iterator;
    typedef ListIterator<T const> ConstIterator;
// ...
    Iterator begin()
    {
        return Iterator(/*...*/);
    }
    ConstIterator const_begin() const
    {
        return ConstIterator(/*...*/);
    }
// ...
};

int main() {
    List<int> list;
    List<int>::ConstIterator ci = list.const_begin(); 
    List<int>::Iterator i = list.begin(); 
    ci = i; // works fine as expected
    i = ci; // fails as expected
    i = i;  // works fine as expected
    ci = ci;  // works fine as expected
    return 0;
}

Thank you a lot! It works perfectly! With this solution there is no need method const_begin. It's good too. — rominf, Apr 04 '13 at 18:26
This is wonderful, I knew there must be a better way to express mutable and immutable iterator types than propagating template meta boiler plates all over the class/time continuum. — Coder Guy, Dec 04 '14 at 18:19

Convert object of custom template based iterator class to const_iterator

1 Answers1