container::{const_,}iterator and const correct

[ne555]

Suppose that we want to provide an iterator class to traverse our container.

class iterator{
  iterator(Node *node):node(node){}
  Node *node;
};

iterator container::begin() const{
  return iterator( &header ); //invalid conversion from 'const Node*' to 'Node*'
}

So we need a class that works with constant nodes

const_iterator constainer::begin() const{
  return const_iterator( &header );
}
iterator constainer::begin(){
  return iterator( &header );
}

Note that the two methods are the same, except that one is for const objects. Is there a way to avoid the copy-paste?

Moreover all the methods provided in iterator will be in const_iterator. The implementation will be exactly the same, and with the typedef magic, even the prototype.

 //from /usr/local/include/c++/4.4.4/bits/stl_list.h
class iterator{
  typedef Node M_Node;
  typedef T* pointer;
  typedef T& reference;

  reference operator*() const{
    return *node;
  }
  
  M_node *node;
};

class const_iterator{
  typedef const Node M_Node;
  typedef const T* pointer;
  typedef const T& reference;

//from here all is the same
  reference operator*() const{
    return *node;
  }
  
  M_node *node;
};

Isn't there a simpler way to link the two types of iterators?

[bartoli]

If you are making your own iterator class, maybe make a base const_iterator class with only read only methods, and add only the non const methods to the derived iterator class?
That way you can also convert a non-const iterator to a const_iterator

[ne555]

class iterator : public const_iterator{
  //const Node *node; //this was inherit
  Node *another_node;
}

The problem is that all the methods work for node, not for another_node. Besides the return types are different, (the same characters are used, but they are not equal)
And I can't do another_node = node without const_cast (maybe not an issue).

Or do you suggest to get rid of operator* and operator-> and implement getters in const_iterator and setters in iterator? But then all the stl algorithms will not work.

[jsmith]

STL solved that problem by use of templates. I recommend looking at std::vector<>'s implementation, and look at the implementation of its iterator and const_iterator.

[moorecm]

Regarding jsmith's comment, the STL source can be difficult to navigate. Here are a few parts of interest from GNU's implementation.

http://chadmoore.us/source/gnu/libstdc++/libstdc++-2.90.8/stl/bits/stl_vector.h

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this  software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
private:
  typedef _Vector_base<_Tp, _Alloc> _Base;
  typedef vector<_Tp, _Alloc> vector_type;
public:
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef __normal_iterator<pointer, vector_type> iterator;
  typedef __normal_iterator<const_pointer, vector_type> const_iterator;

http://chadmoore.us/source/gnu/libstdc++/libstdc++-2.90.8/stl/bits/stl_iterator.h

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this  software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

// This iterator adapter is 'normal' in the sense that it does not
// change the semantics of any of the operators of its itererator
// parameter.  Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
template<typename _Iterator, typename _Container>
class __normal_iterator
  : public iterator<iterator_traits<_Iterator>::iterator_category,
                    iterator_traits<_Iterator>::value_type,
                    iterator_traits<_Iterator>::difference_type,
                    iterator_traits<_Iterator>::pointer,
                    iterator_traits<_Iterator>::reference>
{
public:

  typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;

  inline __normal_iterator() : _M_current() { }

  inline explicit __normal_iterator(const _Iterator& __i)
    : _M_current(__i) { }

  // Allow iterator to const_iterator conversion
  template<typename _Iter>
  inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
    : _M_current(__i.base()) { }

[ne555]

Like this?

template<class T>
class container{
    class node;
    template<class Node, class Type>
    class _iterator{
        typedef _iterator<Node, Type> self;
        typedef Type* pointer;
        typedef Type& reference;
    public:
        //operations
    private:
        Node *current;
    };  
    
public:
    typedef _iterator<node, T> iterator;
    typedef _iterator<const node, const T> const_iterator;
};