How to concatenate immutable collections efficiently?

Question

I'm using System.Collections.Immutable and I want to find a way to concatenate several immutable collections without copying all the items (better than O(n)). All I need from resulting collection is IReadOnlyCollection<T> implementation.

My first idea was to use immutable double-linked list, but it seems that only prototypes of it exists over the Internet, and there's no reliable implementation. See, for example: Efficient implementation of immutable (double) LinkedList

Another idea is to create an immutable list of immutable lists and implement IReadOnlyCollection<T> on top of it. But again, it's a self-made solution for quite a popular problem, and I'm afraid I'm overlooking something.

I'm not quite sure what you try to accomplish but I don't think copying is that much of an issue [link](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.iimmutablelist-1?view=netcore-2.2):"When you add or remove items from an IImmutableList, a copy of the original list is created, with the changes applied. Incremental changes to a list share as much memory as possible with earlier versions of a list and enable garbage collection to clean up any unique list data that is no longer being referenced." — vdL, Aug 22 '19 at 17:45

Frank Schwieterman · Answer 1 · 2019-10-28T16:58:22.643

IEnumerable's Concat() will return an enumerable implementation that simply enumerates the passed in enumerables without making a copy of them.

Be aware that a similar method IEnumerable Append allows adding single element to an enumerable.

Here is a passing test that verifies the original enumerable isn't ran when Concat and Append is called, execution is delayed until the concat or append result is enumerated (I wasn't sure given the wording of Append()'s documentation):

        [Fact]
        public void Test()
        {
            var selectClauseExecutionCount = 0;
            var original = Enumerable.Range(1, 100);

            var enumerated = original.Select(a =>
            {
                selectClauseExecutionCount++; ;
                return a;
            });

            var concated = enumerated.Concat(new[] { 1, 2, 3 });

            Assert.Equal(0, selectClauseExecutionCount);

            var appended = concated.Append(5);

            Assert.Equal(0, selectClauseExecutionCount);

            Assert.Equal(5, appended.Last());

            Assert.Equal(100, selectClauseExecutionCount);
        }

score 1 · Answer 2 · answered Aug 22 '19 at 20:15

If a double-linked immutable list or a list of lists is suitable for you then I'm guessing that you're just looking for a good way to merge and iterate any number of immutable lists as one, without creating unnecessary new copies of their elements.

From the docs you can see that IReadOnlyCollection<T> derives directly from IEnumerable<T> so if you can relax the constraint and have the resulting collection as IEnumerable<T> then your problem can be solved with LINQ and the ref keyword (as the parent interface is essentially readonly as well).

public IEnumerable<T> Concat<T>(params IReadOnlyCollection<T>[] things)
{
    return things.SelectMany(x => x.Select(y => SelectByReference(ref y)));
}

private static ref T SelectByReference<T>(ref T t)
{
    return ref t;
}

private void Example()
{
    var c1 = new ReadOnlyCollection<string>(new[] { "1", "2" });
    var c2 = new ReadOnlyCollection<string>(new[] { "3", "4" });
    var c3 = new ReadOnlyCollection<string>(new[] { "5", "6" });

    var resulting = Concat(c1, c2, c3);

    foreach (var item in resulting)
    {
        // read the item etc without any copies being created
    }
}

This `SelectByReference` is helpful for value types and makes no sense with reference types, am I right? — astef, Aug 23 '19 at 10:40
Enumeration is not a problem, of course. I intentionally specified `IReadOnlyCollection` as a requirement, because if I can compute count, then possibly I can do a more complex things in the same way. I really think that this concat operation should exist in the `ImmutableList` — astef, Aug 23 '19 at 10:48
@astef Yes you're right `SelectByReference` is to make sure no copies are made even with value types. As to having framework support for creating a readonly "view" of several other collections I agree that it would be useful. Maybe be even something as simple as another constructor for `ReadOnlyCollection`. — Saul, Aug 23 '19 at 12:49

How to concatenate immutable collections efficiently?

2 Answers2