我正在寻找一个具有快速包含检查和添加/删除方法的集合(如 HashSet<T>
,如果 T
实现良好,则接近 O(1)),但它也有一个顺序。这并不意味着索引访问 - 它仅意味着如果我对其进行迭代,元素的顺序与我添加它们的顺序相同。
在 C# 中有类似的东西吗?是否HashSet<T>
甚至做这个把戏?(我在 MSDN 上找不到该信息,我检查了 HashSet<T>
和 HashSet<T>.GetEnumerator
。)
如果没有,我正在考虑用一个包含内部 HashSet<T>
的类来实现它和内部 LinkedList<T>
. HashSet<T>
将在 LinkedList<T>
时公开添加、删除和包含检查。会公开枚举器。
看来您正在寻找 OrderedDictionary
.
唯一的缺点是它不支持泛型,但您可以轻松地对其进行包装或将值转换为您需要的类型。
编辑:如@Blorgbeard在评论中提到,您可以在 another answer 中找到“OrderedSet”的实现。满足您的确切要求(并使用 LinkedList<T>
和 HashSet<T>
实现),这可能对您有用。
这是他们的实现(致谢原作者,不是我)
public class OrderedSet<T> : ICollection<T>
{
private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
private readonly LinkedList<T> m_LinkedList;
public OrderedSet()
: this(EqualityComparer<T>.Default)
{
}
public OrderedSet(IEqualityComparer<T> comparer)
{
m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
m_LinkedList = new LinkedList<T>();
}
public int Count
{
get { return m_Dictionary.Count; }
}
public virtual bool IsReadOnly
{
get { return m_Dictionary.IsReadOnly; }
}
void ICollection<T>.Add(T item)
{
Add(item);
}
public bool Add(T item)
{
if (m_Dictionary.ContainsKey(item)) return false;
LinkedListNode<T> node = m_LinkedList.AddLast(item);
m_Dictionary.Add(item, node);
return true;
}
public void Clear()
{
m_LinkedList.Clear();
m_Dictionary.Clear();
}
public bool Remove(T item)
{
LinkedListNode<T> node;
bool found = m_Dictionary.TryGetValue(item, out node);
if (!found) return false;
m_Dictionary.Remove(item);
m_LinkedList.Remove(node);
return true;
}
public IEnumerator<T> GetEnumerator()
{
return m_LinkedList.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public bool Contains(T item)
{
return m_Dictionary.ContainsKey(item);
}
public void CopyTo(T[] array, int arrayIndex)
{
m_LinkedList.CopyTo(array, arrayIndex);
}
}