C# pointers, iterators and generics

Question

I am greatly stumped

How can I use an iterator in C# like a C++ iterator? I cannot find a Begin() or End() accessor, I cannot even find out how to declare an iterator. I have read about the Ienumerator. My goal is to implement the Merge Function. Here is part of my Merge function written in C++. Mostly, I am looking for the C# equivalent of what is shown, except I will be using a Reference type rather than integers.

void merge(vector<int>::iterator left, vector<int>::iterator right, vector<int>::iterator      leftEnd, vector<int>::iterator rightEnd, vector<int>::iterator full)
{

    while(left != leftEnd && right!= rightEnd) //compare left and right until the end of the vector is reached
    {
        if(*right < *left)      //right < left so insert right to the output vector and advance the iterators
        {
            *full++ = *right++;
        }
        else                   //left < right so insert left to the output vector and advance the iterators
        {
            *full++ = *left++;
        }
    }

    while(left != leftEnd)    //copy any remaining elements into the output from left 
    {
        *full++ = *left++;
    }
}

Also, what collection(s) should I use? (currently I have been trying List<T> and LinkedList<T>).

Answer 1

It sounds like you want something like:

bool leftValid = left.MoveNext();
bool rightValid = right.MoveNext();

while (leftValid && rightValid)
{
    if (right.Current < left.Current)
    {
        full.Add(right.Current);
        rightValid = right.MoveNext();
    }
    else
    {
        full.Add(left.Current);
        leftValid = left.MoveNext();
    }
}

while (leftValid)
{
    full.Add(left.Current);
    leftValid = left.MoveNext();    
}

while (rightValid)
{
    full.Add(right.Current);
    rightValid = right.MoveNext();    
}

Here full would need to be some sort of IList<T> - .NET iterators don't let you make changes to the underlying collection.

You shouldn't try to write "bridging" code to let you use .NET iterators like C++ ones; it's much better to try to start thinking in terms of the .NET iterators when you're using .NET.

Note that it's quite rare to pass iterators around in .NET. It would be more natural to make your method to IEnumerable<T> parameters, and do something like:

using (IEnumerable<T> leftIterator = leftSequence.GetEnumerator())
{
    using (IEnumerable<T> rightIterator = rightSequence.GetEnumerator())
    {
        // Code as above, just using leftIterator and rightIterator
        // instead of left and right
    }
}

Answer 2

.net containers don't support C++ style iterators. The only thing they have is a

• simple forward iterator called IEnumerator<T>
• which can't modify the collection
• isn't random access
• can't be copied (some collections have value type iterators which can be copied, but that's tricky business and rarely used)
• and on most collections also gets invalidated whenever you modify the collection

Pretty much the only thing they can do is being iterated over in a foreach statement.

---

You might want to look into the IList<T> interface which allows random access, but is only supported on collections which support fast indexing. On such a collection you could implement in-place merge sort by using indices.

void Merge<T>(IList<T> container,int left, int right, int leftEnd, int rightEnd, int full)

and then use container[left] instead of *left.

---

Unfortunate consequence of this is, that you can't implement an efficient in-place container agnostic sorting function like C++ has.