Last week’s article introduced the concept of iterators as an alternative to the GC-heavy IEnumerable. Today’s article expands the iterator library to include a bunch of more functions to make it useful. Think of these like the extension functions in System.Linq: Any, IndexOf, etc. These have all been tailored to iterators and none of them will create any garbage whatsoever.

Since this iterator library is inspired by the iterators found in the C++ Standard Library, it’s only natural to start building by implementing functions found in the <iterator> and <algorithm> headers. Specifically, I’ve ported over the “non-modifying sequence operations” section for today:

  • Advance: get an iterator forward N steps
  • Distance: get the number of steps between iterators
  • AllOf: check if every step passes some test
  • AnyOf: check if any step passes some test
  • NoneOf: check if none of the steps pass some test
  • ForEach: call a function with the value at each step
  • Find: find a value
  • FindIf: find a value the passes a test
  • FindIfNot: find a value that doesn’t pass a test
  • FindEnd: find a value starting at the end
  • FindFirstOf: find any value from one sequence in another sequence
  • AdjacentFind: find adjacent values
  • Count: count how many times a value is found
  • CountIf: count how many times a test passes
  • Mismatch: find iterators for when two sequences differ
  • Equal: check if two sequences are the same
  • IsPermutation: check if one sequence is a permutation of the other
  • Search: find a subsequence
  • SearchN: find multiple adjacent values

I’ve renamed them to PascalCase to fit the C# convention, but they are otherwise just like their C++ counterparts. Feel free to read the C++ documentation for more information and examples about any of them.

One difference between the C# and C++ versions is that I’ve omitted overloaded versions of some of these. In particular, some have versions that rely on default comparison. Since there’s no such thing with C# generics, IEquatable<T> would need to be used. Unfortunately, using this interface forces garbage creation as basic types like int need to be “boxed” into objects that implement the Equals function.

Instead of providing these default comparison versions, I’ve provided the “predicate” version of each. That means you need to pass a Func<T, T, bool> that returns whether two values are the same. You can use a lambda, anonymous delegate, class function, or instance function to do the job. Just keep in mind that when you call the function a Delegate will be created as garbage. To avoid this, I recommend caching the delegate creation and never releasing it. This will avoid ever needing to collect the garbage, which is the painful part of garbage creation. Here’s how:

class MyClass
{
	// Create the delegate only once
	private static readonly Func<int, int, bool> AreIntsEqual = (a, b) => a == b;
 
	int CountTwos(int[] array)
	{
		// Use the cached delegate
		return array.Begin().Count(array.End(), 2, AreIntsEqual);
	}
}

Next, there’s one really key difference between a lot of the System.Linq extension methods and the iterator functions here today. When you use array.Any(i => i % 2 == 0) to check if any of the values is even, for example, it will check the entire enumerable. With these iterator functions, you get to specify the start and end iterators of the range to check. That means you can check if any of the values at index 2, 3, and 4 are even, not the whole array by doing this:

array.IteratorAt(2).AnyOf(array.IteratorAt(4), i => i % 2 == 0)

This can be a massive performance boost and easier to use in addition to creating zero garbage. For example, you’d need to do this with IEnumerable to achieve the same effect, but it’s less obvious what range you’re working on:

array.Skip(2).Take(3).Any(i => i % 2 == 0)</code>

Finally, let’s look at a little test script to do some validation. This script will do some simple correctness testing as well as a check to make sure there’s no garbage being allocated. Have a look to see some examples of how to use these iterator functions:

using System;
using System.Collections.Generic;
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private static readonly int[] arr = new[] { 1, 2, 2, 3 };
	private static readonly Func<int, int, bool> AreIntsEqual = (a, b) => a == b;
	private static readonly Func<int, bool> IsIntEven = i => i % 2 == 0;
	private static readonly Func<int, bool> IsIntEqualTo2 = i => i == 2;
	private static readonly Func<int, bool> IsIntGreaterThan0 = i => i > 0;
	private static readonly Func<int, bool> IsIntGreaterThan10 = i => i > 10;
	private static readonly Action<int> NoOp = i => {};
	private static int[] OneThreeThreeFour = new[]{ 1, 3, 3, 4 };
	private static int[] ThreeThreeOneTwo = new[] { 3, 3, 1, 2 };
	private static int[] ThreeTwoOneTwo = new[] { 3, 2, 1, 2 };
	private static int[] TwoThree = new[] { 2, 3 };
 
	void Start()
	{
		GcTest();
		Debug.Log(Test());
	}
 
	string Test()
	{
		var log = "";
		Action<string> Log = msg => log += msg + "\n";
		Log("advance 1 from begin: " + arr.Begin().GetAdvanced(1).GetCurrent());
		Log("distance from first to last: " + arr.Begin().Distance(arr.End()));
		Log("all even?: " + arr.Begin().AllOf(arr.End(), i => i % 2 == 0));
		Log("all positive?: " + arr.Begin().AllOf(arr.End(), i => i > 0));
		Log("any > 10?: " + arr.Begin().AnyOf(arr.End(), i => i > 10));
		Log("any == 2?: " + arr.Begin().AnyOf(arr.End(), i => i == 2));
		Log("none == 2?: " + arr.Begin().NoneOf(arr.End(), i => i == 2));
		Log("none > 10?: " + arr.Begin().NoneOf(arr.End(), i => i > 10));
		log += "foreach: ";
		arr.Begin().ForEach(arr.End(), i => log += i + " ");
		log += "\n";
		Log("first even at index: " + arr.Begin().FindIf(arr.End(), i => i % 2 == 0).Index);
		Log("first not even at index: " + arr.Begin().FindIfNot(arr.End(), i => i % 2 == 0).Index);
		Log(
			"end of [2,3] at index: "
			+ arr.Begin().FindEnd(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				(a, b) => a == b
			).Index
		);
		Log(
			"first of [2,3] at index: "
			+ arr.Begin().FindFirstOf(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				(a, b) => a == b
			).Index
		);
		Log(
			"adjacents at index: "
			+ arr.Begin().AdjacentFind(arr.End(), (a, b) => a == b).Index
		);
		Log("count evens: " + arr.Begin().CountIf(arr.End(), i => i % 2 == 0));
		ArrayIterator<int> mm1;
		ArrayIterator<int> mm2;
		arr.Begin().Mismatch(
			arr.End(),
			new[]{ 1, 3, 3, 4 }.Begin(),
			(a, b) => a == b,
			out mm1,
			out mm2
		);
		Log(
			"mismatch with [1, 3, 3, 4] at: "
			+ mm1.GetCurrent() + ", " + mm2.GetCurrent()
		);
		Log(
			"equal [1, 3, 2, 3]? "
			+ arr.Begin().Equal(arr.End(), new[] { 1, 3, 2, 3 }.Begin(), (a, b) => a == b)
		);
		Log(
			"equal [1, 2, 2, 3]? "
			+ arr.Begin().Equal(arr.End(), new[] { 1, 2, 2, 3 }.Begin(), (a, b) => a == b)
		);
		Log(
			"is permutation of [3, 3, 1, 2]? "
			+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 3, 1, 2 }.Begin(), (a, b) => a == b)
		);
		Log(
			"is permutation of [3, 2, 1, 2]? "
			+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 2, 1, 2 }.Begin(), (a, b) => a == b)
		);
		var sub = new[] { 2, 3 };
		Log(
			"search found [2, 3] at index: "
			+ arr.Begin().Search(arr.End(), sub.Begin(), sub.End(), (a, b) => a == b).Index
		);
		Log(
			"search 2 2s found at index: "
			+ arr.Begin().SearchN(arr.End(), 2, 2, (a, b) => a == b).Index
		);
		return log;
	}
 
	int GcTest()
	{
		int val;
		arr.Begin().GetAdvanced(1).GetCurrent();
		arr.Begin().Distance(arr.End());
		arr.Begin().AllOf(arr.End(), IsIntEven);
		arr.Begin().AllOf(arr.End(), IsIntGreaterThan0);
		arr.Begin().AnyOf(arr.End(), IsIntGreaterThan10);
		arr.Begin().AnyOf(arr.End(), IsIntEqualTo2);
		arr.Begin().NoneOf(arr.End(), IsIntEqualTo2);
		arr.Begin().NoneOf(arr.End(), IsIntGreaterThan10);
		arr.Begin().ForEach(arr.End(), NoOp);
		val = arr.Begin().FindIf(arr.End(), IsIntEven).Index;
		val = arr.Begin().FindIfNot(arr.End(), IsIntEven).Index;
		val = arr.Begin().FindEnd(
			arr.End(),
			arr.IteratorAt(1),
			arr.IteratorAt(2),
			AreIntsEqual
		).Index;
		val = arr.Begin().FindFirstOf(
			arr.End(),
			arr.IteratorAt(1),
			arr.IteratorAt(2),
			AreIntsEqual
		).Index;
		val = arr.Begin().AdjacentFind(arr.End(), AreIntsEqual).Index;
		arr.Begin().CountIf(arr.End(), IsIntEven);
		ArrayIterator<int> mm1;
		ArrayIterator<int> mm2;
		arr.Begin().Mismatch(
			arr.End(),
			OneThreeThreeFour.Begin(),
			AreIntsEqual,
			out mm1,
			out mm2
		);
		arr.Begin().IsPermutation(arr.End(), ThreeThreeOneTwo.Begin(), AreIntsEqual);
		arr.Begin().IsPermutation(arr.End(), ThreeTwoOneTwo.Begin(), AreIntsEqual);
		val = arr.Begin().Search(arr.End(), TwoThree.Begin(), TwoThree.End(), AreIntsEqual).Index;
		val = arr.Begin().SearchN(arr.End(), 2, 2, AreIntsEqual).Index;
		return val;
	}
}

Here’s the output of running this:

advance 1 from begin: 2
distance from first to last: 4
all even?: False
all positive?: True
any > 10?: False
any == 2?: True
none == 2?: False
none > 10?: True
foreach: 1 2 2 3 
first even at index: 1
first not even at index: 0
end of [2,3] at index: 2
first of [2,3] at index: 1
adjacents at index: 1
count evens: 2
mismatch with [1, 3, 3, 4] at: 2, 3
equal [1, 3, 2, 3]? False
equal [1, 2, 2, 3]? True
is permutation of [3, 3, 1, 2]? False
is permutation of [3, 2, 1, 2]? True
search found [2, 3] at index: 2
search 2 2s found at index: 1

And here’s a screenshot from Unity 5.3.4f1’s profiler in “deep” mode showing that absolutely no garbage is created by any of these functions:

Iterator Library GC Alloc

I’ve posted the Iterator.cs file with all of these functions on a new GitHub project. In future articles I’ll be porting more functions over from C++ to expand on the library’s capabilities. If you’ve got any favorites you’d like included, even if they’re not from C++, let me know in the comments!

Update: check out part three!