IndexedCollection.cs

using System;
using System.Collections;
using System.Collections.ObjectModel;
using System.Collections.Specialized;

namespace ConsoleApp1
{
    public class Item
    {
        internal int Index { get; set; } = -1;
        public object Content { get; set; }
    }

    public class ItemCollection : ObservableCollection<Item>
    {
        public new int IndexOf(Item item)
        {
            return item.Index;
        }

        protected override void OnCollectionChanged(NotifyCollectionChangedEventArgs e)
        {
            base.OnCollectionChanged(e);

            switch (e.Action)
            {
                case NotifyCollectionChangedAction.Add:
                {
                    SetManagedItems(e.NewStartingIndex, e.NewItems);
                    break;
                }
                case NotifyCollectionChangedAction.Remove:
                {
                    RemoveManagedItems(e.OldStartingIndex, e.OldItems);
                    break;
                }
                case NotifyCollectionChangedAction.Reset:
                case NotifyCollectionChangedAction.Move:
                case NotifyCollectionChangedAction.Replace:
                {
                    SetManagedItems(0, this);
                    break;
                }
            }
        }

        private void SetManagedItems(int index, IList items)
        {
            foreach (Item item in items)
                item.Index = index++;
            for (var i = index; i < Count; i++)
                this[i].Index = i;
        }

        private void RemoveManagedItems(int index, IList items)
        {
            var removedCount = items.Count;
            for (var i = index; i < Count; i++)
                this[i].Index -= removedCount;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Initializing 20M items...");
            var items = new Item[20000000];
            for (var i = 0; i < 20000000; i++)
                items[i] = new Item { Content = i.ToString() };

            Console.WriteLine("Setting up classic collection...");
            var classicCollection = new ObservableCollection<Item>();
            for (var i = 0; i < 20000000; i++)
                classicCollection.Add(items[i]);
            classicCollection.RemoveAt(1000);

            Console.WriteLine("Setting up custom collection...");
            var collection = new ItemCollection();
            for (var i = 0; i < 20000000; i++)
                collection.Add(items[i]);
            collection.RemoveAt(1000);

            Console.WriteLine("Computing some indexes with classic collection:");
            Console.WriteLine(classicCollection.IndexOf(items[0]));
            for (int i = 19000000; i < 20000000; i += 100000)
                Console.WriteLine(classicCollection.IndexOf(items[i]));
            Console.WriteLine();

            Console.WriteLine("Getting the same indexes with custom collection:");
            Console.WriteLine(collection.IndexOf(items[0]));
            for (int i = 19000000; i < 20000000; i += 100000)
                Console.WriteLine(collection.IndexOf(items[i]));
            Console.WriteLine();
        }
    }
}