C# 集合(9) 持续更新

数组的大小是固定的。如果元素个数动态，就使用集合类。

List<T>是与数组相当的集合类。其他的集合：队列、栈、链表、字典和集。

.NET Framework 1.0 包括非泛型集合类，如 ArrayList 和 HashTable 。

创建List

List<int> list = new List<int>();

使用默认构造函数创建一个空列表。如果列表添加元素后，容量会扩大为 4 个元素。如果添加第 5 个元素，容量为 8 。

如果列表的容量改变了，整个集合就要重新分配到一个新的内存块中。为了节省时间，可以直接创建一个容量为10的集合。

List<int> list = new List<int>();

Console.WriteLine(list.Capacity);

list.Capacity = ;

TrimExcess 方法

如果已经将元素添加到列表中，且不希望添加更多的元素，就可以调用 TrimExcess 方法，去除不需要的容量。但是因为重新定位需要时间，所以如果元素个数超过了容量的 90%， TrimExcess（）方法就什么也不做。

list.TrimExcess();

集合初始化值

List<int> intList = new List<int>(){,,,,};

List<string> stringList = new List<string>(){"one", "two"};

编译器会把集合初始化值设定项变成，在列表中的每一项调用 Add 方法。

添加元素 Add

List<int> intList = new List<int>(){,,,,};

intList.Add();

intList.Add();

AddRange 一次给集合添加多个元素

intList.AddRange(new int[]{,,});

也可以向构造函数传递

List<int> intList = new List<int>(new int[] { , ,  });

插入元素 Insert

 List<int> intList = new List<int>(new int[] { , ,  });

 intList.Insert(,);

 intList.InsertRange(, new int[] {  });

访问元素

int value = intList[];

可以通过索引访问的集合类有 ArrayList、StringCollection 和 List<T> 。

foreach 遍历集合中的元素时。

编译器解析 foreach 语句时，利用了 IEnumerator 和 IEnumerable 接口。

 List<int> intList = new List<int>(new int[] { , ,  });

 foreach (int value in intList)

 {

     Console.WriteLine(value);

 }

 Console.WriteLine("**************");

 intList.ForEach(Console.WriteLine);

 Console.WriteLine("**************");

 intList.ForEach(ActionFun);

 Console.WriteLine("**************");

 intList.ForEach(i => Console.WriteLine(i));

删除元素

List<int> intList = new List<int>(new int[] { , ,  });

//intList.RemoveAt(intList.IndexOf(1));

//intList.Remove(1);

intList.RemoveRange(,);

intList.ForEach(Console.WriteLine);

搜索元素

FindIndex

需要一个 Predicate<T> 参数

使用Predicate<T>委托变量引用一个“判断条件函数”，换句话说，就是需要一个返回类型是 Bool

private static void Main(string[] args)

{

    List<int> intList = new List<int>(new int[] { , , ,,,, });

    compare = ;

    Console.WriteLine(intList.FindIndex(ActionFun));

    Console.WriteLine(intList.IndexOf());

    Console.WriteLine("输出大的值");

    List<int> bitIntList = intList.FindAll(v => v >= );

    bitIntList.ForEach(Console.WriteLine);

}

private static int compare;

private static bool ActionFun(int i)

{

    return compare == i;

}

排序元素

Sort函数

public void Sort();

public void Sort(Comparison<T> comparison);

public void Sort(IComparer<T> comparer);

public void Sort(int index, int count, IComparer<T> comparer);

List<int> bitIntList = intList.FindAll(v => v >= );

bitIntList.Sort();

bitIntList.ForEach(Console.WriteLine);

翻转元素

bitIntList.Reverse();

类型转化

 List<int> intList = new List<int>(new int[] { , , ,,,, });

 List<uint> uintList = intList.ConvertAll(r => (uint) r);

 foreach (uint v in uintList)

 {

     Console.WriteLine(v);

 }

只读集合

List<int> intList = new List<int>(new int[] { , , ,,,, });

ReadOnlyCollection<int> readOnlyList = intList.AsReadOnly();

foreach (int i in readOnlyList)

{

    Console.WriteLine(i);

}

队列

队列是其元素以先进先出（FIFO）的方式处理集合。先放入队列中的元素会先读取。

Enqueue方法在队列的一端添加元素，DeQueue方法在队列一端读取和删除元素。

Peek 从队列中读取第一个元素，但不删除它。

TrimExcess 重新设置队列容量

 Queue<int> intQueue = new Queue<int>();

 for (int i = ; i < ; i++)

 {

     intQueue.Enqueue(i);

 }

 while (intQueue.Count > )

 {

     Console.WriteLine(intQueue.Dequeue());

 }

栈

栈是后进先出（LIFO）的容器。

Push 向末尾添加有元素。

Pop 返回末尾元素，并删除该元素。

Stack<int> intList = new Stack<int>();

for (int i = ; i < ; i++)

{

    intList.Push(i);

}

for (int i = ; i < ; i++)

{

    Console.WriteLine(intList.Pop());

}

链表

LinkedList<T> 是双向链表。

通过移动下一个元素，可以正向遍历整个链表。

通过移动前一个元素，反向遍历整个链表。

链表优点

如果将元素插入列表的中间位置，使用链表就会非常快。插入一个元素时，只需要修改上一个元素的Next引用和下一个元素的Previous引用，使它们引用所插入的元素。 而在List<T>类中，插入一个元素时，需要移动该元素后面的所有元素。

链表缺点

链表的元素只能一个接一个地访问，所以这需要较长的时间来查找位于链表中间或尾部的元素。

使用LinkedListNode<T>类，可以获得列表中的下一个元素和上一个元素。LinkedListNode<T>定义了 List、Next、Previous 和 Value 。

List 属性返回与节点相关的 LinkedList<T>对象， Next 和 Previous，下一个元素和上一个元素。 Value 返回与节点相关的元素，其类型是 T 。

LinkedList<T>类定义的方法

第一个元素（First）、第二个元素（Last）

指定位置插入元素（ AddAfter()、AddBefore()、AddFirst()、AddLast() ）

删除指定位置元素（ Remove()、RemoveFirst()、RemoveLast() ）

搜索元素（从开头搜索 Find() 从结尾搜索 FindLast() ）

public class PriorityDocumentManager

{

  private readonly LinkedList<Document> documentList;

  // priorities 0.9

  private readonly List<LinkedListNode<Document>> priorityNodes;

  public PriorityDocumentManager()

  {

    documentList = new LinkedList<Document>();

    priorityNodes = new List<LinkedListNode<Document>>();

    for (int i = ; i < ; i++)

    {

      priorityNodes.Add(new LinkedListNode<Document>(null));

    }

  }

  public void AddDocument(Document d)

  {

    // Contract.Requires<ArgumentNullException>(d != null, "argument d must not be null");

    //  if (d == null) throw new ArgumentNullException("d");

    AddDocumentToPriorityNode(d, d.Priority);

  }

  private void AddDocumentToPriorityNode(Document doc, int priority)

  {

    // Contract.Requires<ArgumentException>(priority >= 0 && priority < 10, "priority value must be between 0 and 9");

    //if (priority > 9 || priority < 0)

    //    throw new ArgumentException("Priority must be between 0 and 9");

    if (priorityNodes[priority].Value == null)

    {

      --priority;

      if (priority >= )

      {

        // check for the next lower priority

        AddDocumentToPriorityNode(doc, priority);

      }

      else // now no priority node exists with the same priority or lower

      // add the new document to the end

      {

        documentList.AddLast(doc);

        priorityNodes[doc.Priority] = documentList.Last;

      }

      return;

    }

    else // a priority node exists

    {

      LinkedListNode<Document> prioNode = priorityNodes[priority];

      if (priority == doc.Priority)

      // priority node with the same priority exists

      {

        documentList.AddAfter(prioNode, doc);

        // set the priority node to the last document with the same priority

        priorityNodes[doc.Priority] = prioNode.Next;

      }

      else // only priority node with a lower priority exists

      {

        // get the first node of the lower priority

        LinkedListNode<Document> firstPrioNode = prioNode;

        while (firstPrioNode.Previous != null &&

           firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)

        {

          firstPrioNode = prioNode.Previous;

          prioNode = firstPrioNode;

        }

        documentList.AddBefore(firstPrioNode, doc);

        // set the priority node to the new value

        priorityNodes[doc.Priority] = firstPrioNode.Previous;

      }

    }

  }

  public void DisplayAllNodes()

  {

    foreach (Document doc in documentList)

    {

      Console.WriteLine("priority: {0}, title {1}", doc.Priority, doc.Title);

    }

  }

  // returns the document with the highest priority

  // (that's first in the linked list)

  public Document GetDocument()

  {

    Document doc = documentList.First.Value;

    documentList.RemoveFirst();

    return doc;

  }

}

PriorityDocumentManager pdm = new PriorityDocumentManager();

//pdm.AddDocument(new Document("one", "Sample", 8));

pdm.AddDocument(new Document("two", "Sample", ));

//pdm.AddDocument(new Document("three", "Sample", 4));

//pdm.AddDocument(new Document("four", "Sample", 8));

//pdm.AddDocument(new Document("five", "Sample", 1));

//pdm.AddDocument(new Document("six", "Sample", 9));

pdm.AddDocument(new Document("seven", "Sample", ));

pdm.AddDocument(new Document("eight", "Sample", ));

pdm.DisplayAllNodes();

有序列表

SortedList mySL1 = new SortedList();

mySL1.Add(1.3, "fox");

mySL1.Add(1.4, "jumped");

mySL1.Add(1.5, "over");

mySL1.Add(1.2, "brown");

mySL1.Add(1.1, "quick");

mySL1.Add(1.0, "The");

mySL1.Add(1.6, "the");

mySL1.Add(1.8, "dog");

mySL1.Add(1.7, "lazy");

//获得指定索引处的键和值

int myIndex = ;

Console.WriteLine("The key   at index {0} is {1}.", myIndex, mySL1.GetKey(myIndex));

Console.WriteLine("The value at index {0} is {1}.", myIndex, mySL1.GetByIndex(myIndex));

看看存储的顺序

为了避免访问不存在的键。

可以使用 ContainsKey 判断是否存在该键，用 TryGetValue 尝试获得该键的值。

注意使用 TryGetValue 要保证存在该键，否则会出现抛出键不存在的异常。

SortedList<int,string> mySL1 = new SortedList<int, string>();

mySL1.Add(, "fox");

Console.WriteLine(mySL1.ContainsKey());

string value;

if(mySL1.TryGetValue(,out value))

    Console.WriteLine("key 11 value " + value);

SortedList 键对一个值。如果需要对多个值，可以用 Lookup。

Lookup https://msdn.microsoft.com/en-us/library/bb460184(v=vs.110).aspx

遍历

foreach (KeyValuePair<int,string> sl in mySL1)

{

    Console.WriteLine(sl.Key + "  " + sl.Value);

}

字典

字典允许按照键访问按照键访问元素。字典也称为映射或散列列表。字典主要特性能根据键快速查找值。可以自由添加和删除元素。有点像List<T>类，但没有在内存中移动后续元素的性能开销。

字典中的键会转换为一个散列。利用散列创建一个数字，将索引和值关联起来。然后索引包含一个到值的链接。

键的类型

键是通过重写Object类的GetHasCode方法，GetHasCode必须满足一下要求

相同的对象总是返回相同的值。
不同的对象可以返回相同的值。
执行比较快，计算开销较小。
不能抛出异常。
至少使用一个实例字段
散列代码值平均分布在int可以存在整个数字范围上。
散列代码最好在对象的生存期中不发生变化。

字典的主要性能取决于 GetHashCode 方法的实现。

除了实现GetHashCode方法外还要实现Equals方法。因为不同的键对象可能返回相同的散列代码。字典使用Equals比较键，字典检查两个键是否相等。如果相等 GetHashCode 方法须返回相同的散列代码。

public override int GetHashCode()

{

    int hashCode = (number ^ number << ) * 0x15051505;

    return hashCode;

}

先将数字向左移动16位，再与原来的数字进行异或，再结果乘以十六进制数 15051505。散列代码在整数取值区域上的分布相当均匀。

Serializable 表示该对象可以序列化。

http://www.cnblogs.com/zwl12549/archive/2007/08/14/854718.html

示例

EmployeeId .cs

[Serializable]

public class EmployeeIdException : Exception

{

  public EmployeeIdException(string message) : base(message) { }

}

[Serializable]

public struct EmployeeId : IEquatable<EmployeeId>

{

  private readonly char prefix;

  private readonly int number;

  public EmployeeId(string id)

  {

    // Contract.Requires<ArgumentNullException>(id != null);

    prefix = (id.ToUpper())[];

    int numLength = id.Length - ;

    try

    {

      number = int.Parse(id.Substring(, numLength >  ?  : numLength));

    }

    catch (FormatException)

    {

      throw new EmployeeIdException("Invalid EmployeeId format");

    }

  }

  public override string ToString()

  {

    return prefix.ToString() + string.Format("{0,6:000000}", number);

  }

  public override int GetHashCode()

  {

      int hashCode = (number ^ number << ) * 0x15051505;

    return hashCode;

  }

  public bool Equals(EmployeeId other)

  {

    if (other == null) return false;

    return (prefix == other.prefix && number == other.number);

  }

  public override bool Equals(object obj)

  {

    return Equals((EmployeeId)obj);

  }

  public static bool operator ==(EmployeeId left, EmployeeId right)

  {

    return left.Equals(right);

  }

  public static bool operator !=(EmployeeId left, EmployeeId right)

  {

    return !(left == right);

  }

}

Employee.cs

[Serializable]

public class Employee

{

  private string name;

  private decimal salary;

  private readonly EmployeeId id;

  public Employee(EmployeeId id, string name, decimal salary)

  {

    this.id = id;

    this.name = name;

    this.salary = salary;

  }

  public override string ToString()

  {

    return String.Format("{0}: {1, -20} {2:C}",

          id.ToString(), name, salary);

  }

}

Main

static void Main()

{

  var employees = new Dictionary<EmployeeId, Employee>();

  var idTony = new EmployeeId("C3755");

  var tony = new Employee(idTony, "Tony Stewart", 379025.00m);

  employees.Add(idTony, tony);

  Console.WriteLine(tony);

  var idCarl = new EmployeeId("F3547");

  var carl = new Employee(idCarl, "Carl Edwards", 403466.00m);

  employees.Add(idCarl, carl);

  Console.WriteLine(carl);

  var idKevin = new EmployeeId("C3386");

  var kevin = new Employee(idKevin, "Kevin Harwick", 415261.00m);

  employees.Add(idKevin, kevin);

  Console.WriteLine(kevin);

  var idMatt = new EmployeeId("F3323");

  var matt = new Employee(idMatt, "Matt Kenseth", 1589390.00m);

  employees[idMatt] = matt;

  Console.WriteLine(matt);

  var idBrad = new EmployeeId("D3234");

  var brad = new Employee(idBrad, "Brad Keselowski", 322295.00m);

  employees[idBrad] = brad;

  Console.WriteLine(brad);

  while (true)

  {

    Console.Write("Enter employee id (X to exit)> ");

    var userInput = Console.ReadLine();

    userInput = userInput.ToUpper();

    if (userInput == "X") break;

    EmployeeId id;

    try

    {

      id = new EmployeeId(userInput);

      Employee employee;

      if (!employees.TryGetValue(id, out employee))

      {

        Console.WriteLine("Employee with id {0} does not exist", id);

      }

      else

      {

        Console.WriteLine(employee);

      }

    }

    catch (EmployeeIdException ex)

    {

      Console.WriteLine(ex.Message);

    }

  }

}

Lookup 键对多个值

Lookup 须调用 ToLookup 方法，该方法返回一个 Lookup<TKey,Telement>对象。ToLookup方法是一个扩展方法，用于实现IEnumerable<T>接口的所有类。

有序的字典

SortedDictionary<TKey, TValue>类是一个二叉搜索树，其中的元素根据键来排序。该键类型必须实现IComparer<TKey>接口。如果键类型不能排序，则还可以创建 IComparer<TKey> 接口的比较容器。将比较器用作有序字典的构造函数的参数。

SortedDictionary跟SortedList 类似。SortedList 类使用的内存比 SortedDictionary 类少。 SortedDictionary 在插入和删除排序的数据时比较快。

集

包含不重复元素的集合称为“集（set）”。包括两种集合

HashSet<T> 包含不重复元素的无序列表。

SortedSet<T> 包含不重复元素的有序列表。

它们都实现ISet<T>接口。

HashSet<string> stringHashSet = new HashSet<string>() { "Zhao","Li" };

Console.WriteLine(stringHashSet.Add("Zhao"));

Console.WriteLine(stringHashSet.Add("Bao"));

Add方法返回布尔值，如果该元素已经存在集，就不添加，并返回false。

IsSubsetOf() 和 IsSupersetOf() 比较集实现了IEnumerable<T>接口的集合结果。

IsSubsetOf 验证 stringHashSet2 每个元素是否都存在 stringHashSet1。

HashSet<string> stringHashSet1 = new HashSet<string>() { "Zhao","Li" };

HashSet<string> stringHashSet2 = new HashSet<string>() { "Zhao", "Li", "wang" };

if (stringHashSet2.IsSubsetOf(stringHashSet1))

{

    Console.WriteLine("stringHashSet2 中每个元素都存在 stringHashSet1 集合方法中 ");

}

else

{

    Console.WriteLine("不存在");

}

IsSupersetOf 判断有没有额外的元素。

if (stringHashSet2.IsSupersetOf(stringHashSet1))

{

    Console.WriteLine("stringHashSet2 是否有没有 stringHashSet1 额外的元素 ");

}

Overlaps 判断集合是否有重叠。

if (stringHashSet2.Overlaps(stringHashSet1))

{

    Console.WriteLine("有重叠");

}

UnionWith 合并两个集合

SortedSet<string> allTeams = new SortedSet<string>(stringHashSet1);

allTeams.UnionWith(stringHashSet2);

foreach (var team in allTeams)

{

    Console.WriteLine(team);

}

ExceptWith 排除有重叠的集合

SortedSet<string> allTeams = new SortedSet<string>(stringHashSet2);

allTeams.ExceptWith(stringHashSet1);

foreach (var team in allTeams)

{

    Console.WriteLine(team);

}

可观查的集合

ObservableCollection<T> 这个类在WPF中定义的，所以需要引用程序集 WindowBase 。引用名称空间 using System.Collections.ObjectModel 。

static void Main()

{

    var data = new ObservableCollection<string>();

    data.CollectionChanged += Data_CollectionChanged;

    data.Add("One");

    data.Add("Two");

    data.Insert(, "Three");

    data.Remove("One");

}

static void Data_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)

{

    Console.WriteLine("action: {0}", e.Action.ToString());

    if (e.OldItems != null)

    {

        Console.WriteLine("starting index for old item(s): {0}", e.OldStartingIndex);

        Console.WriteLine("old item(s):");

        foreach (var item in e.OldItems)

        {

            Console.WriteLine(item);

        }

    }

    if (e.NewItems != null)

    {

        Console.WriteLine("starting index for new item(s): {0}", e.NewStartingIndex);

        Console.WriteLine("new item(s): ");

        foreach (var item in e.NewItems)

        {

            Console.WriteLine(item);

        }

    }

}

位数组

BitArray 和 BitVector32

他们最重要的区别是 BitArray 可以重新设置大小，包含非常多的位。

BitVector32 是基于栈的，因此非常快，它仅包含32位，存储一个整数中。

BitArray类

BitArray类是一个引用类型，它包含一个int数组，其中每32位使用一个新整数。

方法

Count Length                     Count 和 Length 都返回数组的长度，Length 赋值，可以重新设置长度

Item Get Set                     Item 使用索引器读写数组中的位。 Get和Set 一样

SetAll                           设置所有位的值

Not                              所有值取反

And Or Xor                       And 执行二元And，只要两个数组位都为1时，结果位才是1。 Or 只要一个数组位为1时，结果就是 。 Xor 异或操作 只有两个位不一样时，才会 1 如  10001 xor 10000 = 00001

BitArray bitArray = new BitArray();

bitArray.SetAll(true);

bitArray.Set(,false);

foreach (bool b in bitArray)

{

    Console.Write(b ?  : );

}

Console.WriteLine();

BitVector32

如果事先知道需要的位数，可以用BitVector32 代替 BitArray 类。BitVector32效率较高，因为是值类型，栈上存储位。

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

并发集合

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

性能

集合类提供很多相同的功能。如 SortedList 类与 SortedDictionary 类的功能几乎完全相同。一个集合使用的内存少。另外一个集合元素检索速度快。

巴特西