C# - 添加新元素时设置 returns 索引

Question

我正在寻找符合以下条件的collection：

collection 中的元素从不重复。也就是说，类似 ISet<T> 的东西。
除非从 collection 中删除元素，否则 collection 中元素的顺序不会改变。（在我的 use-case 中，我从不删除任何元素）。
我希望能够获取我刚刚添加的元素的索引。由于要求 1 这意味着：如果元素已经存在于 collection 中，则接收该元素的索引；如果该元素不存在，则接收类似 .Count 的内容。

我尝试使用 OrderedSet collection，然后使用 one-liner 扩展方法获取元素的索引。问题是每次我尝试在已经包含几千个的 collection 中添加新元素时，我的机器上大约需要 100 毫秒。将大量元素添加到巨大的 collection.

中时，这是一件大事

我怀疑获取索引可以在添加元素的同一个地方完成。因此，我正在为此目的寻找可能存在的 collection。

提前致谢。

Answer 1

怎么样：

public class SpecialList<T> : List<T>
{
    public new int Add(T Item)
    {
        if (Contains(Item))
        {
            return IndexOf(Item);
        }
        else
        {
            base.Add(Item);
            return Count - 1;
        }
    }
}

Answer 2

好的，所以考虑到这个问题我尝试了 4 种解决方案：

使用 AddWithIndex 扩展方法制作 OrderedSet<T>
使用 AddWithIndex 扩展方法制作 HashSet<T>。虽然它不能保证元素的顺序它在某些情况下仍然有用。
扩展 List<T> class
写我自己的IndexedSet<T>class

所有测试都是针对以下代码进行的：

static void Main(string[] args)
{
    var elements = Enumerable.Range(0, 1000000).Select(i => i.ToString()).ToList();

    //Initialize collection here
    //...

    var sw = new Stopwatch();
    sw.Start();
    foreach (var element in elements)
    {
        //Add element to collection here
        //...
    }
    sw.Stop();
    Console.WriteLine("Elapsed time: {0}", sw.Elapsed);

}

此测试仅涵盖所有元素都不同的情况，当您有很多重复元素时并不真正具有代表性。

测试 1. AddWithIndex HashSet<T>的扩展方法（OrderedSet<T>基本相同）：

 static class HashSetExtensions
 {
    public static int AddWithIndex<T>(this HashSet<T> set, T element)
    {
        if (set.Add(element))
        {
            return set.Count - 1;
        }
        return set.IndexOf(element);
    }

     public static int IndexOf<T>(this HashSet<T> set, T element)
     {
         int index = 0;
         foreach (var item in set)
         {
             if (element.Equals(item))
             {
                 return index;
             }
            index++;
        }
        return -1;
    }
}

这给了我 0.3842932 秒 HashSet<T> 和 1.1972123 秒 OrderedSet<T>。

测试 2。 从 List<T> 派生 JerryM 提出的方法在 7.6716346 秒 上得到了 20000 个元素的集合（比用于其他测试的集合少 50 倍的元素）和大致无限的时间在原来的 1000000 个元素上。

测试 3。 最后，我创建了以下 IndexedSet<T> 集合，它基本上是 List<T> 和 HashSet<T> 的包装器：

public class IndexedSet<T> : IReadOnlyList<T>, IList<T>
{
    private readonly List<T> _list = new List<T>();
    private readonly HashSet<T> _set = new HashSet<T>();

    public IEnumerator<T> GetEnumerator()
    {
        return _list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _list.GetEnumerator();
    }

    public int Add(T item)
    {
        if (_set.Add(item))
        {
            _list.Add(item);
            return _list.Count - 1;
        }

        return _list.IndexOf(item);
    }

    void ICollection<T>.Add(T item)
    {
        Add(item);
    }

    public void Clear()
    {
        _list.Clear();
        _set.Clear();
    }

    public bool Contains(T item)
    {
        return _set.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        _list.CopyTo(array, arrayIndex);
    }

    public bool Remove(T item)
    {
        bool remove = _set.Remove(item);
        if (remove)
            _list.Remove(item);
        return remove;
    }

    public int Count => _list.Count; 

    public bool IsReadOnly => false; 

    public int IndexOf(T item)
    {
        return _list.IndexOf(item);
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        T item = _list[index];
        _list.RemoveAt(index);
        _set.Remove(item);
    }

    public T this[int index]
    {
        get { return _list[index]; }
        set
        {
            T item = _list[index];
            _set.Remove(item);

            _list[index] = value;
            _set.Add(value);
        }
    }
}

这给了我 0.3558594 秒（这甚至比 HashSet<T> 的扩展快一点）并保证了元素的顺序（就像 OrderedSet<T>).

希望这对以后的人有用。

C# - 添加新元素时设置 returns 索引

C# - Set that returns index when adding new element

.net

c#

collections

performance

set