寻找.Net排序的集合，可以访问上一个和下一个元素

AZT 发表于 Dev

它

我正在实现Bentley-Ottman算法，该算法要求扫描线（SL）具有以下属性的数据结构：

维护的分类收集T，这里T是IComparable<T>，
元素的插入应为O(log count)，并且应返回元素是否已插入，
元件的缺失应O(log count)，
对于给定的元素e（无论是否已经在集合中），我需要e按排序顺序在集合旁边的上一个和下一个元素。

SortedList<TKey, TValue>O(count)在插入和删除处有一个at，因为它必须移动列表中的所有连续元素。但是，O(1)一旦知道的索引，便可以为其编制索引，并因此获得上一个和下一个元素e。

SortedDictionary<TKey, TValue>并SortedSet<T>具有O(log count)插入和删除的功能，但找不到任何可以提供下一个和上一个元素的迭代器。

有没有可以给我全部功能的实现方式？

如果没有，那么实现它的最快方法是什么？LinkedList<T>不允许二进制搜索。List<T>仍然有O(count)插入/删除。我真的必须实现自己的平衡树吗？

Xanatos

例如，TreeDictionary中的C5收集库和的NuGet和github上有一个

如果存在k的前置变量，则bool TryPredecessor（K k，out of KeyValuePair res）返回true，在这种情况下，将前任绑定到res；否则返回false并将KeyValuePair的默认值绑定到res。根据密钥比较器，k的前身是排序字典中的最大密钥严格小于k的条目。如果k没有前置项，则抛出NoSuchItemException；否则，抛出NoSuchItemException。即，任何密钥都不小于k。

和一个

如果存在k的后继，则bool TrySuccessor（K k，out of KeyValuePair res）返回true，在这种情况下，将后继绑定到res；否则返回false并将KeyValuePair的默认值绑定到res。k的后继项是排序字典中的条目，根据密钥比较器，其最小密钥严格大于k。如果k没有后继，则抛出NoSuchItemException；否则，抛出NoSuchItemException。也就是说，词典中的任何条目都不具有大于k的键。

并且应该拥有您所需的几乎所有东西。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。