Continuing the series this week we’ll delve into the iterator functions that modify the sequence. This includes handy tools like Copy, SwapRanges, and Transform. Of course this is all done without creating any garbage! Read on to see how and for the full source code.

Continuing through C++’s <algorithm> header, this week covers the first half of the “modifying sequence operations” functions. Specifically, these:

  • Copy: copy elements from one range to another
  • CopyN: copy the first N elements from one iterator to another
  • Copy: copy the elements that pass a test
  • CopyBackward: copy a range from end to start
  • SwapRanges: swap the elements in one range with another
  • Swap: swap the elements of two iterators
  • Transform: transform the elements of one or two ranges and output to another range
  • ReplaceIf: replace the elements of a range with a value if they pass a test
  • ReplaceCopyIf: replace a range with a given value or the elements of another range if they pass a test

One thing to notice about these functions is that they all work on ranges. Rather than an entire IEnumerable, you specify just the start and end iterators to operate on. Rather than outputting a whole new collection (e.g. a new array), you output to any iterator on an existing collection. This makes these functions much more flexible than the System.Linq extension methods, but also a little more verbose in their usage. For example, this is how you would double the elements of an array into a new array:

// System.Linq + IEnumerable extensions
int[] Double(int[] arr)
{
	return arr.Select(i => i * 2).ToArray();
}
 
// Iterators
int[] Double(int[] arr)
{
	var ret = new int[arr.Length];
	arr.Begin().Transform(arr.End(), ret.Begin(), DoubleInt);
	return ret;
}
private static Func<int, int> DoubleInt = i => i * 2;

However, say you wanted to double the first half of the array into the second half. This is trivial with iterators, but complex and hugely wasteful with System.Linq and IEnumerable:

// System.Linq + IEnumerable extensions
int[] DoubleFirstHalfIntoSecond(int[] arr)
{
	return arr.Take(arr.Length / 2)
		.Concat(arr.Skip(arr.Length / 2).Select(i => i * 2))
		.ToArray(); // Note: creates several enumerables and a new array
}
 
// Iterators
int[] DoubleFirstHalfIntoSecond(int[] arr)
{
	var halfIt = arr.IteratorAt(arr.Length/2);
	arr.Begin().Transform(halfIt, halfIt.GetNext(), DoubleInt);
	return arr; // Note: no allocations, uses same array
}
private static Func<int, int> DoubleInt = i => i * 2;

With this in mind, let’s look at a test app to show the usage, correctness, and (lack of) garbage creation by this week’s set of iterator functions. I’ve built on last week’s test app, so you might want to start reading at the Count function.

using System;
using System.Linq;
 
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private static readonly int[] defaultArr = { 1, 2, 2, 3 };
	private static readonly int[] arr = defaultArr.ToArray();
	private static readonly int[] arr2 = new int[arr.Length];
	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 Func<int, int> DoubleInt = i => i * 2;
	private static readonly Func<int, int, int> MultiplyInts = (a, b) => a * b;
	private static readonly Action<int> NoOp = i => { };
	private static int[] OneThreeThreeFour = { 1, 3, 3, 4 };
	private static int[] ThreeThreeOneTwo = { 3, 3, 1, 2 };
	private static int[] ThreeTwoOneTwo = { 3, 2, 1, 2 };
	private static int[] TwoThree = { 2, 3 };
 
	void Start()
	{
		GcTest();
		Debug.Log(Test());
	}
 
	string Test()
	{
		var log = "";
		Action<string> Log = msg => log += msg + "\n";
		Func<int[], string> ArrayToString = a => string.Join(
			", ",
			a.Select(i => i.ToString()).ToArray()
		);
		Action ResetArrays = () => {
			for (var i = 0; i < arr.Length; ++i)
			{
				arr[i] = defaultArr[i];
				arr2[i] = 0;
			}
		};
		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(), IsIntEven));
		Log("all positive?: " + arr.Begin().AllOf(arr.End(), IsIntGreaterThan0));
		Log("any > 10?: " + arr.Begin().AnyOf(arr.End(), IsIntGreaterThan10));
		Log("any == 2?: " + arr.Begin().AnyOf(arr.End(), IsIntEqualTo2));
		Log("none == 2?: " + arr.Begin().NoneOf(arr.End(), IsIntEqualTo2));
		Log("none > 10?: " + arr.Begin().NoneOf(arr.End(), IsIntGreaterThan10));
		log += "foreach: ";
		arr.Begin().ForEach(arr.End(), i => log += i + " ");
		log += "\n";
		Log("find 2 at index: " + arr.Begin().Find(arr.End(), 2, AreIntsEqual).Index);
		Log("first even at index: " + arr.Begin().FindIf(arr.End(), IsIntEven).Index);
		Log("first not even at index: " + arr.Begin().FindIfNot(arr.End(), IsIntEven).Index);
		Log(
			"end of [2,3] at index: "
			+ arr.Begin().FindEnd(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				AreIntsEqual
			).Index
		);
		Log(
			"first of [2,3] at index: "
			+ arr.Begin().FindFirstOf(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				AreIntsEqual
			).Index
		);
		Log(
			"adjacents at index: "
			+ arr.Begin().AdjacentFind(arr.End(), AreIntsEqual).Index
		);
		Log("count 2s: " + arr.Begin().Count(arr.End(), 2, AreIntsEqual));
		Log("count evens: " + arr.Begin().CountIf(arr.End(), IsIntEven));
		ArrayIterator<int> mm1;
		ArrayIterator<int> mm2;
		arr.Begin().Mismatch(
			arr.End(),
			new[] { 1, 3, 3, 4 }.Begin(),
			AreIntsEqual,
			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(), AreIntsEqual)
		);
		Log(
			"equal [1, 2, 2, 3]? "
			+ arr.Begin().Equal(arr.End(), new[] { 1, 2, 2, 3 }.Begin(), AreIntsEqual)
		);
		Log(
			"is permutation of [3, 3, 1, 2]? "
			+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 3, 1, 2 }.Begin(), AreIntsEqual)
		);
		Log(
			"is permutation of [3, 2, 1, 2]? "
			+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 2, 1, 2 }.Begin(), AreIntsEqual)
		);
		var sub = new[] { 2, 3 };
		Log(
			"search found [2, 3] at index: "
			+ arr.Begin().Search(arr.End(), sub.Begin(), sub.End(), AreIntsEqual).Index
		);
		Log(
			"search 2 2s found at index: "
			+ arr.Begin().SearchN(arr.End(), 2, 2, AreIntsEqual).Index
		);
		ResetArrays();
		Log(
			"copy first two returns iterator at index "
			+ arr.Begin().Copy(arr.IteratorAt(2), arr2.Begin()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copyN first three returns iterator at index "
			+ arr.Begin().CopyN(3, arr2.Begin()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copy evens returns iterator at index "
			+ arr.Begin().CopyIf(arr.End(), arr2.Begin(), IsIntEven).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copy backward middle two returns iterator at index "
			+ arr.IteratorAt(1).CopyBackward(arr.IteratorAt(3), arr2.End()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"swap middle two returns iterator at index "
			+ arr.IteratorAt(1).SwapRanges(arr.IteratorAt(3), arr2.IteratorAt(1)).Index
			+ ", arr now: "
			+ ArrayToString(arr)
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		var itA = arr.IteratorAt(0);
		var itB = arr.IteratorAt(1);
		itA.Swap(itB);
		Log("swap iterator at index 0 with iterator at index 1, arr now: " + ArrayToString(arr));
		ResetArrays();
		Log(
			"transform by doubling returns index "
			+ arr.Begin().Transform(arr.End(), arr.Begin(), DoubleInt).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		Log(
			"transform by multiplying with self returns index "
			+ arr.Begin().Transform(arr.End(), arr.Begin(), arr.Begin(), MultiplyInts).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		arr.Begin().ReplaceIf(arr.End(), IsIntEqualTo2, 20);
		Log("replace 2 with 20 " + ArrayToString(arr));
		ResetArrays();
		Log(
			"replace evens with 200 returns iterator at index "
			+ arr.Begin().ReplaceCopyIf(arr.End(), arr.Begin(), IsIntEven, 200).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		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().Find(arr.End(), 2, AreIntsEqual).Index;
		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().Count(arr.End(), 2, AreIntsEqual);
		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;
 
		val = arr.Begin().Copy(arr.IteratorAt(2), arr2.Begin()).Index;
		val = arr.Begin().CopyN(3, arr2.Begin()).Index;
		val = arr.Begin().CopyIf(arr.End(), arr2.Begin(), IsIntEven).Index;
		val = arr.IteratorAt(1).CopyBackward(arr.IteratorAt(3), arr2.End()).Index;
		val = arr.IteratorAt(1).SwapRanges(arr.IteratorAt(3), arr2.IteratorAt(1)).Index;
		var itA = arr.IteratorAt(0);
		var itB = arr.IteratorAt(1);
		itA.Swap(itB);
		val = arr.Begin().Transform(arr.End(), arr.Begin(), DoubleInt).Index;
		val = arr.Begin().Transform(arr.End(), arr.Begin(), arr.Begin(), MultiplyInts).Index;
		arr.Begin().ReplaceIf(arr.End(), IsIntEqualTo2, 20);
		val = arr.Begin().ReplaceCopyIf(arr.End(), arr.Begin(), IsIntEven, 200).Index;
		return val;
	}
}

This outputs:

advance 1 from begin: 200
distance from first to last: 4
all even?: True
all positive?: True
any > 10?: True
any == 2?: False
none == 2?: True
none > 10?: False
foreach: 200 200 200 200 
find 2 at index: 4
first even at index: 0
first not even at index: 4
end of [2,3] at index: 3
first of [2,3] at index: 0
adjacents at index: 0
count 2s: 0
count evens: 4
mismatch with [1, 3, 3, 4] at: 200, 1
equal [1, 3, 2, 3]? False
equal [1, 2, 2, 3]? False
is permutation of [3, 3, 1, 2]? False
is permutation of [3, 2, 1, 2]? False
search found [2, 3] at index: 4
search 2 2s found at index: 4
copy first two returns iterator at index 2, arr2 now: 1, 2, 0, 0
copyN first three returns iterator at index 3, arr2 now: 1, 2, 2, 0
copy evens returns iterator at index 2, arr2 now: 2, 2, 0, 0
copy backward middle two returns iterator at index 2, arr2 now: 0, 0, 2, 2
swap middle two returns iterator at index 3, arr now: 1, 0, 0, 3, arr2 now: 0, 2, 2, 0
swap iterator at index 0 with iterator at index 1, arr now: 2, 1, 2, 3
transform by doubling returns index 4, arr now: 2, 4, 4, 6
transform by multiplying with self returns index 4, arr now: 1, 4, 4, 9
replace 2 with 20 1, 20, 20, 3
replace evens with 200 returns iterator at index 4, arr now: 1, 200, 200, 3

And here’s a screenshot of Unity’s profiler in “deep” mode showing the lack of any garbage creation at all during the GcTest function:

Iterator GC Alloc, Part 3

To see the full iterator library, check out the updated GitHub project.

Let me know if you’ve got any questions about the iterator library, or any suggestions on how to make it better, in the comments!

Update: check out part four!