c# - 带有可替换物品的键控系列

Question

到目前为止，我一直在使用 KeyedCollection 创建一个大型对象集合（接近 100 万个），每个对象都有一个 uint ID 字段作为集合的键。这很好，但是现在我在扩展功能时遇到了一个问题：我有“覆盖”记录，需要用新项目替换具有相同键的任何现有项目。平均而言，可能会覆盖 20 条记录中的 1 条，甚至可能会覆盖同一条记录的多次。

如有必要，我不介意从 KeyedCollection 重构。我最好的选择是什么？字典<>? ids 不是连续的，所以直接索引就出来了。

Answer 1

这是一个老问题，我以前自己也使用过现有的答案。但是在再次使用 KeyedCollection<> 时，我意识到 Remove-and-then-Add 技术的效率低于我现在实施的技术。问题是 Remove() 方法线性搜索列表，然后将列表的其余部分向左移动一个条目。我在这里介绍的技术也线性搜索列表，但至少它避免了移动列表的其余部分。

注意。这仅适用于替换项目与要替换的项目具有相同密钥的情况。

   /// <summary>
   /// Derived (but still abstract) version of KeyedCollection{} to provide a couple of extra 
   /// services, in particular AddOrReplace() and Replace() methods.
   /// </summary>
   public abstract class KeyedList<TKey, TItem> : KeyedCollection<TKey, TItem>
   {
      /// <summary>
      /// Property to provide access to the "hidden" List{} in the base class.
      /// </summary>
      public List<TItem> BaseList
      {
         get { return base.Items as List<TItem>; }
      }


      /// <summary>
      /// Method to add a new object to the collection, or to replace an existing one if there is 
      /// already an object with the same key in the collection.
      /// </summary>
      public void AddOrReplace(TItem newObject)
      {
         int i = GetItemIndex(newObject);
         if (i != -1)
            base.SetItem(i, newObject);
         else
            base.Add(newObject);
      }


      /// <summary>
      /// Method to replace an existing object in the collection, i.e., an object with the same key. 
      /// An exception is thrown if there is no existing object with the same key.
      /// </summary>
      public void Replace(TItem newObject)
      {
         int i = GetItemIndex(newObject);
         if (i != -1)
            base.SetItem(i, newObject);
         else
            throw new Exception("Object to be replaced not found in collection.");
      }


      /// <summary>
      /// Method to get the index into the List{} in the base collection for an item that may or may 
      /// not be in the collection. Returns -1 if not found.
      /// </summary>
      private int GetItemIndex(TItem itemToFind)
      {
         TKey keyToFind = GetKeyForItem(itemToFind);
         return BaseList.FindIndex((TItem existingItem) => 
                                   GetKeyForItem(existingItem).Equals(keyToFind));
      }
   }

Answer 2

与Dictionary您应该从集合中删除该项目一样，更改/替换它并再次添加它。

Answer 3

我使用以下类作为可更新的键控集合。它仅适用于引用类型。

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using JetBrains.Annotations;


namespace Fiftytwo
{
    [PublicAPI]
    public abstract class UpdatableKeyedCollection<TKey, TValue> : KeyedCollection<TKey, TValue> where TValue : class
    {
        public List<TValue> ItemList => ( List<TValue> )Items;

        public bool AddOrUpdate ( [NotNull] TValue item )
        {
            int i, count = Count;
            if( count == 0 )
            {
                Add( item );
                return true;
            }

            List<TValue> list;

            TKey key = GetKeyForItem( item );
            var dict = Dictionary;
            IEqualityComparer<TKey> comparer;
            if( dict == null )
            {
                comparer = Comparer;
                list = ( List<TValue> )Items;
                for ( i = 0; i < count; ++i )
                {
                    if( comparer.Equals( GetKeyForItem( list[i] ), key ) )
                    {
                        list[i] = item;
                        return false;
                    }
                }
                Add( item );
                return true;
            }

            if( dict.TryGetValue( key, out TValue obj ) )
            {
                if( obj == item )
                    return false;

                comparer = Comparer;
                list = ( List<TValue> )Items;
                for ( i = 0; i < count; ++i )
                {
                    if( comparer.Equals( GetKeyForItem( list[i] ), key ) )
                    {
                        list[i] = item;
                        dict[key] = item;
                        return false;
                    }
                }

                throw new KeyNotFoundException(
                    $"Key {key} does not exist in the internal list but exists in the internal lookup dictionary." );
            }

            Add( item );
            return true;
        }

        [NotNull] public TValue GetOrAddNew ( [NotNull] TKey key, [NotNull] Func<TKey, TValue> createNew )
        {
            TValue value;

            int count = Count;
            if( count == 0 )
            {
                value = createNew( key );
                Add( value );
                return value;
            }

            var dict = Dictionary;
            if( dict == null )
            {
                var comparer = Comparer;
                var list = ( List<TValue> )Items;
                for ( int i = 0; i < count; ++i )
                {
                    if( comparer.Equals( GetKeyForItem( list[i] ), key ) )
                        return list[i];
                }
                value = createNew( key );
                Add( value );
                return value;
            }

            if( dict.TryGetValue( key, out value ) )
                return value;

            value = createNew( key );
            Add( value );
            return value;
        }
    }
}