是否有SortedList< T> .NET中的类？ [英] Is there a SortedList<T> class in .NET?
问题描述
我需要根据它们的内容（实际上根据它们的一个属性来排序一些对象，这不是关键，并且可以在不同对象之间重复）。
.NET提供了两个类（ SortedDictionary < a>和 SortedList ），以及两者都使用二叉树来实现。它们之间的唯一区别是
- SortedList使用的内存比SortedDictionary少。
- SortedDictionary对于未排序数据O（log n）具有更快的插入和删除操作，而对于SortedList具有更快的插入和删除操作。
- 如果列表是从排序数据一次填充，SortedList比SortedDictionary更快。
我可以使用列表实现所需的功能，，然后使用其排序）方法，其自定义实施 IComparer ，但是它不会是时间有效的，因为我每次我想插入一个新的对象排序整个列表，而一个好的SortedList只是插入项目在正确的位置。
我需要一个具有RefreshPosition（int index）的SortedList类，只移动改变（或插入）的对象，而不是每当对象内部改变时调用整个列表。
我缺少一些明显的东西？
也许我很慢，不是是最容易实现的吗？
class SortedList< T& ：List< T>
{
public new void Add（T item）
{
Insert（〜BinarySearch（item），item）;
}
}
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
$ b不幸的是，添加是不可重写的，所以我不得不新它不是那么好当你有列表< T> list = new SortedList< T> ;; 我实际上需要做....所以我去重建整个东西... class SortedList< T> ：IList< T>
{
private List< T> list = new List< T>（）;
public int IndexOf（T item）
{
var index = list.BinarySearch（item）;
return index< 0？ -1：index;
}
public void Insert（int index，T item）
{
throw new NotImplementedException（不能在索引处插入;必须保留顺序。
}
public void RemoveAt（int index）
{
list.RemoveAt（index）;
}
public T this [int index]
{
get
{
return list [index]
}
set
{
list.RemoveAt（index）;
this.Add（value）;
}
}
public void Add（T item）
{
list.Insert（〜list.BinarySearch（item），item）;
}
public void clear（）
{
list.Clear（）;
}
public bool包含（T item）
{
return list.BinarySearch（item）> = 0;
}
public void CopyTo（T [] array，int arrayIndex）
{
list.CopyTo（array，arrayIndex）;
}
public int Count
{
get {return list.Count; }
}
public bool IsReadOnly
{
get {return false; }
}
public bool Remove（T item）
{
var index = list.BinarySearch（item）;
if（index< 0）return false;
list.RemoveAt（index）;
return true;
}
public IEnumerator< T> GetEnumerator（）
{
return list.GetEnumerator（）;
}
IEnumerator IEnumerable.GetEnumerator（）
{
return list.GetEnumerator（）;
}
}
或者这样的东西是更合适的删除函数...
public bool Remove（T item）
{
var index = list.BinarySearch（item）;
if（index< 0）return false;
while（（IComparable）item）.CompareTo（（IComparable）list [index]）== 0）
{
if（item == list [index]）
{
list.RemoveAt（index）;
return true;
}
index ++;
}
return false;
}
假设项目可以比较等于但不等于...
I need to sort some objects according to their contents (in fact according to one of their properties, which is NOT the key and may be duplicated between different objects).
.NET provides two classes (SortedDictionary and SortedList), and both are implemented using a binary tree. The only differences between them are
- SortedList uses less memory than SortedDictionary.
- SortedDictionary has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList.
- If the list is populated all at once from sorted data, SortedList is faster than SortedDictionary.
I could achieve what I want using a List, and then using its Sort() method with a custom implementation of IComparer, but it would not be time-efficient as I would sort the whole List each time I want to insert a new object, whereas a good SortedList would just insert the item at the right position.
What I need is a SortedList class with a RefreshPosition(int index) to move only the changed (or inserted) object rather than resorting the whole list each time an object inside changes.
Am I missing something obvious ?
Maybe I'm slow, but isn't this the easiest implementation ever?
class SortedList<T> : List<T>
{
public new void Add(T item)
{
Insert(~BinarySearch(item), item);
}
}
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
Unfortunately, Add wasn't overrideable so I had to new it which isn't so nice when you have List<T> list = new SortedList<T>; which I actually needed to do.... so I went ahead and rebuilt the whole thing...
class SortedList<T> : IList<T>
{
private List<T> list = new List<T>();
public int IndexOf(T item)
{
var index = list.BinarySearch(item);
return index < 0 ? -1 : index;
}
public void Insert(int index, T item)
{
throw new NotImplementedException("Cannot insert at index; must preserve order.");
}
public void RemoveAt(int index)
{
list.RemoveAt(index);
}
public T this[int index]
{
get
{
return list[index];
}
set
{
list.RemoveAt(index);
this.Add(value);
}
}
public void Add(T item)
{
list.Insert(~list.BinarySearch(item), item);
}
public void Clear()
{
list.Clear();
}
public bool Contains(T item)
{
return list.BinarySearch(item) >= 0;
}
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
public int Count
{
get { return list.Count; }
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
var index = list.BinarySearch(item);
if (index < 0) return false;
list.RemoveAt(index);
return true;
}
public IEnumerator<T> GetEnumerator()
{
return list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return list.GetEnumerator();
}
}
Or perhaps something like this is a more appropriate Remove function...
public bool Remove(T item)
{
var index = list.BinarySearch(item);
if (index < 0) return false;
while (((IComparable)item).CompareTo((IComparable)list[index]) == 0)
{
if (item == list[index])
{
list.RemoveAt(index);
return true;
}
index++;
}
return false;
}
Assuming items can compare equal but not be equal...
这篇关于是否有SortedList< T> .NET中的类？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
