container::{const_,}iterator and const correct

ne555 (4385)
Suppose that we want to provide an iterator class to traverse our container.
1
2
3
4
5
6
7
8
 
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
1
2
3
4
5
6
 
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 //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 (262)
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 (4385) 
1
2
3
4
 
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 (5804)
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 (1826)
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
/*
 *
 * 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.
 */

1
2
3
4
5
6
7
8
9
10
11
12
 
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
/*
 *
 * 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.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// 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()) { }
Last edited on
ne555 (4385)
Like this?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
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;
};
Last edited on
Topic archived. No new replies allowed.

C++

Forum