IndexedSet

UGUI 中定义了一种特殊的容器，被称为 IndexedSet。该容器结合了 List 与 Dictionary

使得它具有以下的优点：

保证容器中元素的唯一性（类似于 Set）
快速的随机元素删除（使用了 swap 的技巧）
连续访问（由 List 保证的缓存友好特性）

但同时，这种容器也有一些缺点：

使用更多的内存（同时维护了一个 List 与一个 Dictionary）
顺序并不能一直保持（Swap 技巧的弊端）
序列化不友好（同时维护两种数据结构）

下面就来看一下该类的实现。

首先，该类被标记为 internal。这说明该容器仅有 UGUI 程序集内部能够使用；其次，该类是一个泛型类并继承了 IList<T>。

此外可以看出，类中同时维护了一个 List 与一个 Dictionary。

internal class IndexedSet<T> : IList<T>
{
    //This is a container that gives:
    //  - Unique items
    //  - Fast random removal
    //  - Fast unique inclusion to the end
    //  - Sequential access
    //Downsides:
    //  - Uses more memory
    //  - Ordering is not persistent
    //  - Not Serialization Friendly.

    //We use a Dictionary to speed up list lookup, this makes it cheaper to guarantee no duplicates (set)
    //When removing we move the last item to the removed item position, this way we only need to update the index cache of a single item. (fast removal)
    //Order of the elements is not guaranteed. A removal will change the order of the items.

    readonly List<T> m_List = new List<T>();
    Dictionary<T, int> m_Dictionary = new Dictionary<T, int>();

    // ...
}

IList 是 .NET 中的一个接口，继承自 ICollection 和 IEnumerable。它定义了一些用于操作集合的标准方法和属性。

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
    T this[int index] { get; set; }

    int IndexOf(T item);

    void Insert(int index, T item);

    void RemoveAt(int index);
}

回到 IndexedSet 类中，其中的 Add 及 AddUnique 方法分别用于向容器中添加元素。Add 方法直接添加元素，而 AddUnique 方法则会先检查元素是否已经存在于容器中，若存在则返回 false，否则添加元素并返回 true。

可以看出，Dictionary 中的键为插入到 List 中的元素，而值为该元素在 List 中的索引。因而可以通过 Dictionary 快速查找元素在 List 中的索引。

在 Add 与 AddUnique 方法中，会同时向 List 与 Dictionary 中添加元素。List 用于保证元素的顺序，而 Dictionary 用于保证元素的唯一性。

public void Add(T item)
{
    m_List.Add(item);
    m_Dictionary.Add(item, m_List.Count - 1);
}

public bool AddUnique(T item)
{
    if (m_Dictionary.ContainsKey(item))
        return false;

    m_List.Add(item);
    m_Dictionary.Add(item, m_List.Count - 1);

    return true;
}

接下来是 Remove 相关方法的实现，这里使用了 swap 的技巧。当需要删除一个元素时，将该元素与最后一个元素交换，然后删除最后一个元素。这样做的好处是只需要更新一个元素的索引，而不用移动所有元素。但同时，这也会打乱元素的顺序。

public bool Remove(T item)
{
    int index = -1;
    if (!m_Dictionary.TryGetValue(item, out index))
        return false;

    RemoveAt(index);
    return true;
}

public void RemoveAt(int index)
{
    T item = m_List[index];
    m_Dictionary.Remove(item);
    if (index == m_List.Count - 1)
        m_List.RemoveAt(index);
    else
    {
        int replaceItemIndex = m_List.Count - 1;
        T replaceItem = m_List[replaceItemIndex];
        m_List[index] = replaceItem;
        m_Dictionary[replaceItem] = index;
        m_List.RemoveAt(replaceItemIndex);
    }
}

public void RemoveAll(Predicate<T> match)
{
    //I guess this could be optmized by instead of removing the items from the list immediatly,
    //We move them to the end, and then remove all in one go.
    //But I don't think this is going to be the bottleneck, so leaving as is for now.
    int i = 0;
    while (i < m_List.Count)
    {
        T item = m_List[i];
        if (match(item))
            Remove(item);
        else
            i++;
    }
}

为了恢复元素的顺序，IndexedSet 类中还提供了 Sort 方法。该方法会对 List 中的元素进行排序，并重新构建 Dictionary 中的索引。

//Sorts the internal list, this makes the exposed index accessor sorted as well.
//But note that any insertion or deletion, can unorder the collection again.
public void Sort(Comparison<T> sortLayoutFunction)
{
    //There might be better ways to sort and keep the dictionary index up to date.
    m_List.Sort(sortLayoutFunction);
    //Rebuild the dictionary index.
    for (int i = 0; i < m_List.Count; ++i)
    {
        T item = m_List[i];
        m_Dictionary[item] = i;
    }
}

此外，IndexedSet 类还提供了一些其他方法，如 Clear、Contains、CopyTo、IndexOf 等，这里就不一一分析了。

但有两个地方比较有意思：

public IEnumerator<T> GetEnumerator()
{
    throw new System.NotImplementedException();
}

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

这两个方法分别实现了 IEnumerable<T> 与 IEnumerable 接口。但是它们都抛出了一个 NotImplementedException 异常。这是因为 IndexedSet 类并不希望外部直接通过 foreach 来遍历元素，而是通过 List 的索引来访问元素。

public void Insert(int index, T item)
{
    //We could support this, but the semantics would be weird. Order is not guaranteed..
    throw new NotSupportedException("Random Insertion is semantically invalid, since this structure does not guarantee ordering.");
}

Insert 方法也抛出了一个异常。虽然 List 与 Dictionary 本身都支持插入操作，但是 IndexedSet 类并不希望外部直接插入元素。因为这样会打破元素的顺序。

总结

IndexedSet 类是 UGUI 中的一个特殨容器，它结合了 List 与 Dictionary 的优点，同时也有一些缺点。这种容器适用于需要保证元素唯一性、快速删除元素、连续访问元素的场景。

IndexedSet 内部维护了一个 List 与一个 Dictionary，List 用于保证元素的顺序，而 Dictionary 用于保证元素的唯一性。当需要删除元素时，IndexedSet 会使用 swap 的技巧，将需要删除的元素与最后一个元素交换，然后删除最后一个元素。