CODEWITHSUNDEEP
c#collectionsconcatenationimmutabilitydoubly-linked-list
astef
astef

Reputation: 9508

How to concatenate immutable collections efficiently?

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.

Upvotes: 0

Views: 1436

Answers (2)

Frank Schwieterman
Frank Schwieterman

Reputation: 24480

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);
        }

Upvotes: 2

Saul
Saul

Reputation: 18061

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
    }
}

Upvotes: 1

Related Questions