C# リストのリストを一つのバッファで表現してみた

何がしたいか

可変長配列の可変長配列を、一つのバッファで表現したい。リストのリスト。

なんで？

可変長配列の可変長配列に関して、頻繁に全体を読み取り、たまに編集したい。そんな特殊なケースの場合に使えると思います。分散した部分リストのつなぎ合わせを回避できるというわけです。

ただ、自分のケースでもリストのリストで十分だと、これを書いているときに気付きました。編集するときだけリストのリストを作成し、普段はそれをつなぎ合わせたデータを使えば解決しました。

ですのでこれは供養です。

書いてみたコード

まだテストしてません。あとMyListはListのフィールドを直接いじれるようにして、Spanを多用できるようにしたやつです。Listに置き換えてもらって大丈夫です。

PartitionedListに要素とパートを追加していって、PartitionedList.GetPart(partIndex)で部分リストを取得。部分リストに対して普通のリストのような操作を行うことができます。部分リストへの操作で要素数が変わると、後続のパート全体に影響があるので要素数に変化がある操作は後ろからやるべきです。

using CommunityToolkit.Diagnostics;
using System;


namespace MyCollection
{
    public class PartitionedList<T>
    {
        public MyList<T> items;
        public MyList<int> offsets;
        public PartOfList GetPart(int index) => new PartOfList(this, index);
        public int GetPartElementCount(int partIndex)
        {
            return (partIndex == offsets.Count - 1)
                ? items.Count - offsets[partIndex]
                : offsets[partIndex + 1] - offsets[partIndex];
        }
        public int GetPartStart(int partIndex) => offsets[partIndex];
        public PartitionedList(int firstCapacity)
        {
            items = new(firstCapacity);
            offsets = new();
            offsets.Add(0);
        }
        public PartitionedList(Span<T> elements, Span<int> partOffset)
        {
            for(int i = 0; i < partOffset.Length-1; i++)
            {
                if (partOffset[i] > partOffset[i + 1]) ThrowHelper.ThrowInvalidDataException("partitionのオフセットは単調増加であるべきです");
            }
            if (partOffset[^1] > elements.Length) ThrowHelper.ThrowArgumentOutOfRangeException("partオフセットの開始地点が存在しない領域にあります");
            items = new(elements.Length);
            items._size = elements.Length;
            elements.CopyTo(items.BufferSpan());

            if (partOffset.Length == 0)
            {
                offsets = new(1);
                offsets.Add(0);
            }
            else
            {
                // パート開始オフセットの開始が0のとき、0を削除(共通処理で追加するため)
                if (partOffset[0] == 0) partOffset = partOffset.Slice(1);
                // 開始の0を追加
                offsets = new(partOffset.Length + 1);
                offsets._size = partOffset.Length + 1;
                offsets[0] = 0;
                //ループでパートを設定
                for (int i = 0; i < partOffset.Length; i++)
                {
                    offsets[i + 1] = partOffset[i];
                }
            }
        }

        public void AddPart()
        {
            offsets.Add(items.Count);
        }
        public void InsertPart(int index)
        {
            // 要素数0のパートを作成
            // (0,2,4) => (0,1)(2,3)(4...);
            // 1に追加するなら (0,2,2,4) => (0,1)()(2,3)(4...)
            offsets.Insert(index, offsets[index]);
        }
        private void OnChangePartCount(int changedPartIndex,int difference)
        {
            for (int i = changedPartIndex + 1; i < offsets.Count; i++)
            {
                offsets[i] += difference;
            }
        }
        public void RemovePartAndElements(int partIndex)
        {
            int partCount = GetPartElementCount(partIndex);
            int partStart = offsets[partIndex];
            items.RemoveRange(partStart, partCount);
            OnChangePartCount(partIndex, -partCount);
            offsets.RemoveAt(partIndex);
        }
        public ref struct PartOfList
        {
            private PartitionedList<T> src;
            private int partIndex;
            private int GetCount() => src.GetPartElementCount(partIndex);
            private int IndexOnSrc(int index) => src.GetPartStart(partIndex)+index;
            private void OnChangeCount(int difference) => src.OnChangePartCount(partIndex, difference);
            public PartOfList(PartitionedList<T> src,int partIndex)
            {
                this.src = src;
                this.partIndex = partIndex;
            }
            public T this[int index]
            {
                get => src.items[IndexOnSrc(index)];
                set => src.items[IndexOnSrc(index)] = value;
            }
            public void Add(in T item)
            {
                Insert(GetCount(), item);
            }
            public void AddRange(Span<T> items)
            {
                InsertRange(GetCount(), items);
            }
            public void Insert(int index,in T item)
            {
                if ((uint)index > (uint)GetCount()) ThrowHelper.ThrowArgumentOutOfRangeException();
                src.items.Insert(IndexOnSrc(index), item);
                OnChangeCount(+1);
            }
            public void InsertRange(int index,Span<T> items)
            {
                if ((uint)index > (uint)GetCount()) ThrowHelper.ThrowArgumentOutOfRangeException();
                src.items.InsertRange(IndexOnSrc(index), items);
                OnChangeCount(items.Length);
            }
            public void RemoveAt(int index)
            {
                if ((uint)index >= (uint)GetCount()) ThrowHelper.ThrowArgumentOutOfRangeException();
                src.items.RemoveAt(IndexOnSrc(index));
                OnChangeCount(-1);
            }
            public void RemoveRange(int index,int removeCount)
            {
                int count = GetCount();
                if ((uint)index >= (uint)count) ThrowHelper.ThrowArgumentOutOfRangeException();
                if (removeCount <= 0) ThrowHelper.ThrowArgumentException();
                // 領域外を削除しようとしたら例外(index + removeCount > count)
                // ※ 一番削除する数が多い場合、0 + count == count
                if (index + removeCount > count) ThrowHelper.ThrowArgumentOutOfRangeException();
                src.items.RemoveRange(IndexOnSrc(index), removeCount);
                OnChangeCount(-removeCount);
            }
        }
    }
}

チャッピーはお怒りです

チャッピーにレビューさせると、一生「コンストラクタ内で、Listの_sizeを直接変更するべきではありません。Add()を使ってください」って言われるんですよね。

「データの変更は少ない」という前提もあることだし、たしかにそっちのほうがいいかもしれませんね