1

我正在寻找的数据结构应该是标准关联的，允许在给定唯一键的情况下快速（至少优于 O(n)）检索/替换/添加/删除项目，就像任何树或哈希图一样。

bool ContainsKey(TKey key);
bool TryGetValue(TKey key, out TValue value);
void Remove(TKey key);
Add(TKey key, TValue value);
Update(TKey key, TValue value);
int Count { get; }

棘手的部分是还要公开以下内容（也比 O(n) 好）：

int IndexOf(TKey key);
TKey GetKey(int index);

index 是插入顺序（在添加时），如果发生删除，则更新。

这是我想要的一个例子：

InsertionOrderedMap<string, T> map = new InsertionOrderedMap<string, T>();

map.Add("id1", t1);
map.Add("id2", t2);
map.Add("id0", t0);

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(1, map.IndexOf("id2"));
Assert.AreEquals(2, map.IndexOf("id0"));

map.Remove("id2");

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(-1, map.IndexOf("id2"));
Assert.AreEquals(1, map.IndexOf("id0"));

map.Update("id0", t3);

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(1, map.IndexOf("id0"));

Assert.AreEquals("id1", map.GetKey(0));
Assert.AreEquals("id0", map.GetKey(1));

我想我知道如何自己实现一个，但我想知道这样的容器是否已经存在。

4

0 回答 0