IEnumerator<T> / IEnumerable<T> with position stored only temporarily?

Question

I'm developing a graph where I need to keep the memory usage per node as low as possible. Each node implements IEnumerator / IEnumerable.

IEnumerator / IEnumerable make use of "position" in the canonical examples, which is a persistent cursor value required for iteration (e.g. as used by foreach).

What I need to avoid is storing this "position" value internally to the node itself, as this adds overhead where every byte counts.

How can I construct the node class such that a temporary object stores this value -- preferably on the stack -- only while an iteration is taking place, and not as part of the node itself? Is this possible?

Answer 1

If "node" is the underlying data, then it is very incorrect to store the position in the node, as you are meant to be able to have separate enumerators. It is unclear how you are currently implementing this API, but if you use an " iterator block " with the position as a local variable it will be done correctly, but on the heap. You can also implement an iterator manually on the stack by creating a struct iterator. It is important that the public GetEnumerator() is returned as the struct type, so you will need to use explicit interface implementation for IEnumerable etc. Note that foreach over Node directly will use the stack, but IEnumerable etc will use the heap.

For example (using a basic linked-list):

using System;
using System.Collections;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        var list = new MyList<int>();
        list.Add(1);
        list.Add(2);
        list.Add(3);
        foreach (var i in list)
        { // this IS NOT using IEnumerable/IEnumerable<T>
            Console.WriteLine(i);
        }
    }
}
public class MyList<T> : IEnumerable<T>
{
    internal sealed class Node
    {
        private readonly T value;
        public Node Next { get; set; }
        public T Value { get { return value; } }
        public Node(T value) { this.value = value; }
    }
    Node root;
    public void Add(T value)
    {
        var newNode = new Node(value);
        var node = root;
        if (node == null) root = newNode;
        else
        {
            while (node.Next != null) node = node.Next;
            node.Next = newNode;
        }
    }
    public Enumerator GetEnumerator() { return new Enumerator(this); }
    IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
    IEnumerator<T> IEnumerable<T>.GetEnumerator() { return GetEnumerator(); }
    public struct Enumerator : IEnumerator, IEnumerator<T>
    {
        void IDisposable.Dispose() { node = null; list = null; }
        void IEnumerator.Reset() { node = null; }
        object IEnumerator.Current { get { return Current; } }
        private MyList<T> list;
        private Node node;
        public bool MoveNext()
        {
            if (node == null)
            {
                node = list.root;
                return node != null;
            }
            else
            {
                if (node.Next == null) return false;
                node = node.Next;
                return node != null;
            }
        }
        internal Enumerator(MyList<T> list) { this.list = list; node = null; }
        public T Current { get { return node == null ? default(T) : node.Value; } }
    }
}

Answer 2

Typically an IEnumerable<T> doesn't store a position - only an IEnumerator<T> does. (Iterator block implementations are odd in terms of implementing both, but they're definitely an anomaly.)

I suggest that you take the same approach that List<T> does: implement IEnumerable<T> with explicit interface implementation, but also have a public method returning a custom mutable struct (horrible I know, but it does solve your problem) which contains a reference to your node and the position within it. When you iterate using foreach, that struct value will only be stored on the stack (normally - assuming you're not doing this within an iterator block, for example).

The normal implementation would be to create a mutable reference type just for the IEnumerator<T>. Normally this is okay as even if you have a lot of IEnumerable<T> values live at the same time, you have few IEnumerator<T> values. Are you concerned about the concurrent number of live objects, or garbage collection?