## Enumerables Without the Garbage: Part 2

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:

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!**