So, when last we met, I had given you an overview of some of the high level decisions I had made. In the interim, snk_kid was kind enough to point out just how pointless this project really is: Dinkumware is working on STL/CLR, and it will be included with VS at some point in the near future. But that's OK. I'll bet I'll have SGL finished first, so when I'm done I'll forward them a copy for inspiration [wink]
Today, I would like to get down into the nitty gritty details of how everything actually works up to this point.
We will begin with iterators, because they were the hard part. The C++ iterator library defines five classes of iterators:
RandomAccess -> Bidirectional -> Forward -> Input -> OutputAll iterators support forward movement via operator++, so you can consider enumerations to be a form of InputIterator1. I have chosen to follow suit, and make use of the same heirarchy. I somewhat regret not making OutputIterator independant of the basic chain, but fixing that now would be non-trivial.
In C++, this heirarchy is largely imagined...you specify what type of iterator you are using the iterator_category tag, but otherwise a BidirectionalIterator is simply one that defines operator-- in addition to operator++. In C#, such behavior would not work...generic types and methods depend on inheritance to see what behavior is and is not allowed. For this reason, I define six types:
- interface InputIterator -- specifies a read-only property Value
- interface OutputIterator -- specifies a write-only property Value
- abstract class Iterator -- Implements operator++, Advance, and Distance in terms of the abstract method Increment(), and implements operator== in terms of Equals.
- abstract class ForwardIterator -- Derives from Iterator, InputIterator, and OutputIterator. Provides no additional functionality, and leaves the Value property abstract.
- abstract class BidirectionalIterator -- Adds an abstract method Decrement, and implements operator-- in terms of it. Also adds support for using operator- in place of Distance2, and overrides the default Advance to allow for negative values of n.
- abstract class RandomAccessIterator -- Adds an abstract indexer (essentially operator[]) that allows constant time movement of the iterator. Implements operator+ and operator- (when used with integral operands) and overrides the default Advance to make use of the indexer.
Now, lets say you are implementing an iterator for an iterator for a List class [err..LinkedList class...damn .Net calling arrays lists [flaming]]. In this case, you would want to inherit from BidirectionalIterator. In order to get all the functionality of a BidirectionalIterator you only have to provide five functions: self equality via Equals, the Value property, Increment, and Decrement. That's it...everything else you need is provided transparently by the underlying classes. If you were implementing Vector.Iterator, you would inherit from RandomAccessIterator, and provide the same functions, plus the indexer.
So what about using them? That's just as straight forward. Just decide what type of iterator you are working with, and go from there. As an example, here's a hypothetical implementation of for_each:
delegate void Function(T v);void for_each(Itr begin, Itr end, Function f) where Itr : Iterator, InputIterator{ for(; begin != end; ++begin) f(begin.Value);}//Later, within some function:List l;for_each(l.Begin(), l.End(), delegate(int v) {System.Console.Write("{0} ", v);});If you implementing Sort, which requires RandomAccessIterators, then you would simply replace the where line above with where Itr : RandomAccessIterator, and you'd be free to use begin[5] or end[-10].
Now, as I mentioned, there is a rather significant problem with the overview I just gave. Namely, overloaded operators don't work that way. In .Net, overloaded operators are static functions...this means you can't inherit them, and the return value is permanantly stuck with one type. You would not think this would be a problem, because even if dealing with a base class the virtual functions would still call the proper methods. And indeed, I am now entirely unable to recreate the bugs I encountered at the time.3 However, the combination of inheritance, generics, and overloaded operators resulted in some subtle bugs, especially with regards to equality. Sometimes, they could be gotten around with simple casts to the proper type, but not always.
The solution I found was the Curiously Recurring Generic. Observe:
class Iterator { public static Iterator operator++() {/*implement me*/}}class VectorIterator : Iterator {}Becomes
class Iterator where Itr : Iterator { public static Itr operator++() {/*implement me*/}}class VectorIterator : Iterator> {}Now, all the operators operate on the derived class instead of on the base class, even though the operator itself is defined in the base class. It is really quite slick, I think.
This recurence goes all the way up, with ForwardIterator, BidirectionalIterator and RandomAccessIterator all accepting the same second parameter. Only InputIterator and OutputIterator, which only define a property that doesn't care about the actual iterator in any way, are exempt.
This is not without its pitfalls, of course. In addition to making the definition of iterators slightly more complex, it seriously hinders the ability of the compiler to infer types automatically. You have to parameterize based on iterator, because you can not have a BidirectionIterator, for example, on its own. If it isn't obvious why, try it out:
void SomeFunc(BidirectionalIteratorvoid SomeFunc(Itr iterator) where Itr : BidirectionalIteratorC# does not look at the constraints list when infering parameters, so it has no way of knowing what type to assign to T. This means you have to specify it every time:
SomeFunc.Iterator>(l.Begin());As you might imagine, that gets annoying rather quickly. I have identified two ways to help it along. The first is for when I'm lazy:
void SomeFunc(Itr iterator, T placeholder)The placeholder is just there to put T into the argument list so that C# can figure things out on its own. Obviously, this is not an ideal solution. The alternative is much cleaner:
static class Algorithms { void SomeFunc(Itr iterator) where Itr : BidirectionalIterator {}}//later, to use it:Algorithms.SomeFunc(l.Begin());You still have to specify T, but that is typically fairly straight forward. It is the Itr parameter that you don't want to be bothered with. So while still not ideal, it is at least marginally easier to work with.4
I think that pretty much brings us up to speed on Iterators. Unfortunately, I got distracted a few times and now I have to work in an hour, so Containers will have to wait. They are pretty straight forward, however, and there are no real complications with their use.
The last thing I'd like to do is show how one can use iterators in practice. Namely, I'm going to show off the code that allows an iterator range to be used in a foreach structure. I stripped the comments, because they were in the XML format MS likes, and that made it a bit verbose for such a simple structure. I added a few where neccessary.
public class RangeEnumerator : IEnumerator, IEnumerable where U : Iterator, InputIterator { public RangeEnumerator(U begin_, U end_) { begin = begin_; end = end_; } IEnumerator IEnumerable.GetEnumerator() { return this; } public System.Collections.IEnumerator GetEnumerator() { return this; } public bool MoveNext() { //Enumerations start one before the begining of the range, so itr // itr being null signifies that position. if(itr == null) { itr = (U)begin.Clone(); return itr != end; } itr++; return itr != end; } public T Current { get { if(itr == null || itr == end) throw new InvalidOperationException(); return itr.Value; } } Object System.Collections.IEnumerator.Current { get { //Is it possible to somehow use the other form of Current for // this? I should probably yank both bodies into a separate // function. if(itr == null || itr == end) throw new InvalidOperationException(); return (Object)itr.Value; } } public void Reset() { itr = null; } // I don't know what this function is for, but I get yelled at if it // isn't here. public void Dispose() { } private U itr; private U begin; private U end; } //This is a helper class that allows the compiler to infer the two type // parameters. It occurs to me now that I could possibly move // RangeEnumerator into this class and simplify things a bit. public static class Range { public static RangeEnumerator Create(U begin, U end) where U : Iterator, InputIterator { return new RangeEnumerator(begin, end); } }This is how you actually use them:
class Program{ public static void Main(string[] args) { //I know we haven't covered vectors yet, but I'm use you can figure out what this does :) Vector<int> v = new Vector<int>(); for(int i = 0; i < 10; i++) v.PushBack(i); foreach(int i in new RangeEnumerator<int, Vector<int>.Iterator>(v.Begin(), v.End())) System.Console.WriteLine(i); //Or, more simply: foreach(int i in Range<int>.Create(v.Begin(), v.End())) System.Console.WriteLine(i); //Although it is not the point of the code, you can also do this: foreach(int i in v) System.Console.WriteLine(i); }}As an aside, when I finished typing out that demo program I pressed B.
And with that, I bid you fare well.
CM
1This is a bit of a simplification...you are only allowed to read from an input iterator once [this restriction is lifted by ForwardIterator], but you can reset an enumerator and pass through it multiple times if you like.
2I have to look through my notes to see if there's a reason why this functionality is provided by BidirectionalIterator and not by Iterator itself...the actual implementation is simply rhs.Distance(lhs), so there's no reason why it wouldn't work with ForwardIterators as well.
3The fact that I can't recreate the bugs, despite them being quite obvious at the time, bothers me. This calls into question all the decisions I have made since. I think over the next couple days I will try and work backwards and recreate the problems I had before. Hopefully, it wasn't just a misunderstanding that I have since rectified. I fully understood the source of the problems at the time, but I was learning a lot at the time so you never know.
4There is a third option I just now tried out:
void SomeFunc(BidirectionalIterator iterator) where Itr : BidirectionalIterator {}In that case, it infers both parameters just fine. However, equality doesn't work right. As I mentioned before, equality is the area that was most severely affected by the issues that lead to implementing the recusion in the first place. I know exactly how to fix it, and I'm willing to bet that doing so will lead me to remember what caused the bugs in the first place. So that is where I shall begin my search.
