C ++: overloading list.end () and list.begin () methods for persistent iterators

Question

I'm still trying to implement my own version of the LinkedList class, and now I'm having problems with overload methods for persistent iterators. For example, when I try to print a list using this code:

cout << "citer:" << endl; for (UberList<int>::CIter it = ulist.begin(); it != ulist.end(); ++it) { cout << *it << " "; } cout << endl; 

I have these errors:

 Error E2034 UberList2.cpp 532: Cannot convert 'UberList<int>::Iter' to 'UberList<int>::CIter' in function main() Error E2094 UberList2.cpp 532: 'operator!=' not implemented in type 'UberList<int>::CIter' for arguments of type 'UberList<int>::Iter' in function main() 

as I understand it, this means that the usual methods are used end end and begin iterator. Here's how these methods are declared in my class:

 Iter begin(); Iter end(); CIter begin() const; CIter end() const; 

and

 template<class T> typename UberList<T>::Iter UberList<T>::begin() { Iter it; it.curr = head; return it; } template<class T> typename UberList<T>::Iter UberList<T>::end() { Iter it; it.curr = tail->next; return it; } template<class T> typename UberList<T>::CIter UberList<T>::begin() const { CIter it; it.ccurr = head; return it; } template<class T> typename UberList<T>::CIter UberList<T>::end() const { CIter it; it.ccurr = tail->next; return it; } 

Is there a way to get my program to use these const methods for constant iterators instead of the usual ones? I would be glad to hear any advice.

Oh, and here is the code of my class in one file just in case: http://pastebin.com/Jbvv5Hht

Answer 1

You must provide a conversion from Iter to CIter . Standard containers (table 65, in section 23.1 "Container Requirements", says that X::iterator converted to X::const_iterator )

The caller can guarantee that the const overload is invoked using the const reference, but you should not force them to do this because they will need to write something like:

 UberList<int>::CIter it = static_cast<const UberList<int> &>(ulist).begin() 

If you provide the “required” conversion, you don’t need to do anything special: your source code will work the same as for standard containers.

Answer 2

A few more comments on the OP code. Consider separating this giant uberl33tlist class and breaking it into smaller files. Seeing all these friends class ads makes me pretty uncomfortable. There are also some complex semantics when you use things like

 friend class UberList; friend class CIter; 

In some cases, these statements also end by declaring these classes, if they do not already exist. There's also something not quite right about your destination statement here:

 UberList<T> operator = (const UberList<T>& OL) { UberList<T> NL = new (OL); return NL; } 

Also have you

 it2++; ulist.insertAfter(b, it2); //... 

You are using postfix operator ++ for it2 but have not implemented this iterator class. Borland accepts it using the prefix instead, but gives a warning. Gcc actually designates this as an error and rejects the code. You might want to learn this.

Answer 3

Sigh: there is a level of hacking created to hide the fact that conceptually what you want to do cannot be done automatically in C ++ because it does not understand variance. Some other languages ​​(including Ocaml) do.

If you have a functor (a template class for C ++ programmers), the question arises as to how it and various functions behave with changing a parameter, for example, converting from T to T const. What you really want is:

 List<T> --> List<T const> 

In other words, you want the List functor to be covariant. But no, it’s not .. so in fact the List template is not a functor at all, because functors must preserve the structure and the transformation is not reflected as necessary. In turn, this means that either C ++ templates are violated OR the concept of const is violated, because a type system that does not support parametric polymorphism is violated by the specification :)

Providing a "const_iterator" does not solve this problem, it just breaks the gap. Where is the mutable and const_volatile version? What about double directions?

If you do not understand double links: consider a tree of vectors from T, which are two patterns:

 Tree<Vector<T>> 

The best solution here is to abandon const_iterator support. Just don’t worry. In any case, this is confused: what about the "const vector"? What is it? A vector that you cannot draw longer, but it still allows you to write elements?

The actual requirement is that the transforms commute, for example:

 vector<T> const == vector<T const> 

[or they are anticommuted if the transformation is inconsistent)

The fact that this does not happen shows that the vector is not functorial, in other words, the patterns cannot be effectively used for parametric polymorphism. If you really want your panties to be knotted, consider templates with function arguments and ask about the variance of the return type of the function and parameters and how this can affect the container. A good example is the creation of two functions, so they work in pairs. What if they are mutators, how does const work?

Answer 4

You need

 teamplate<class T> bool operator!=(UberList<T>::CIter,UberList<T>::CIter); 

Answer 5

It uses the usual begin method because the variable is not const. Thus, one way to fix it is to make another (reference) const variable:

 UberList<int> const & culist = ulist; for (UberList<int>::Citer it = culist.begin(); ...) 

Alternatively use const_cast.