C#集合类(数据结构)

时间:2022-08-19 16:59:37

一、选择数据结构

1)线性容器
List<T>数组/Stack/Dequeue按需求模型选择即可,LinkedList<T>是双向链表增删修改快.
需要有序数组SortList<T>线性排序容器都可以;如果既需要查找快又需要频繁修改那么可以用List<T>记录索引,用LinkedList<T>存储。

2)二叉树类型容器
SortedDictionary<TKey,TValue>可以提供二叉树类型插入删除查找都比较折中的键值对容器。
SortedSet<T>一个集合值类型的容器,比SortedDictionary<TKey,TValue>需要更少的空间。

3)哈希表类型的容器
Dictionary<TKey,TValue>类似于C++/java中的HashMap实现,需要一个哈希函数和一个相等判断函数解决冲突,能够有很高的插入和查找效率。
HashSet<T>适合单个元素的集合操作类型。
ILookup<TKey,TValue>可以获得一个键对应多个值的存储类型,很有用的方面是从指定集合中筛选某种类型的数据集。

4)其它支持容器的接口类,委托,拓展方法和为了观察,封装位操作,封装多线程操作的衍生类型容器
其它功能类型的接口及其委托,拓展方法:
ICollection<T>、IEnumerable<T>、IEquatable<T>、IComparer<T>、IComparable<T>、IEqualityComparer<T>、IFormattable接口
为了观察,封装位操作,封装多线程操作的衍生类型容器:
ObservableCollection<T>,BitArray/BitVector32、IProducerConsumerCollection<T>接口

大多数集合类都在System.Collections.Generic命名空间中,非泛型的System.Collections中已经很少用了。
特定集合类位于System.Collections.Specialized中,线程安全的集合类在System.Collections.Concurrent中。

集合类主要有:

二.ICollection<T>、IEnumerable<T>、IEquatable<T>、IComparer<T>、IComparable<T>、IEqualityComparer<T>、IFormattable接口。


三.Array、List<T>、队列、栈、SortedList<TKey, TValue>、LinkedList<T>双向链表

1.List<T>

List<T>在C#中实现也是数组,动态数组长度不够会加倍。
不确定的数组需要可变数组用List<T>, 确定长度和数量多用Array, 不推荐用ArrayList因为添加的是object类型要装箱和拆箱性能慢。
1)初始化:
初始化时候可以直接赋值,或者指定Count和Capacity来初始化。
对List<T>填充完数据以后可以用TrimExcess()方法去除不需要的容量,只有空白容量超过10%才会去除成功。
List<T>可以用AddRange添加多个元素。
2)访问:
可以通过索引器访问的集合类有:Array,List<T>,ArrayList, StringCollection, List<T>。
List<T>实现了IEnumerable<T>接口,所以也可以用foreach来访问。

List<T>提供了ForEach方法,该方法用Action<T>作为参数。
public void ForEach(Action<T> action);
// 需要当前类中定义该委托的实例赋值给Action委托对象,也可以用Lambda表达式声明该实例。
public delegate void Action<T> (T obj);

3)删除
用RemoveAt效率较快,如果用Remove回先查找值然后删除回查找引用,如果有重写IEquatable<T>或者Object.Equals就会用这些方法判断,否则
是用默认的引用比较,如果是相同的引用地址那么就可以删除成功。
删除还可以用RemoveRange(index, count)来进行删除。
如果要删除指定特性的元素就可以用RemoveAll()方法,指定特性在Predicate<T>参数中指定。
要直接删除所有的元素用ICollection<T>接口中定义的Clear()方法。

4)搜索
IndexOf(),LastIndexOf(), FindIndex(), FindLastIndex(), Find(),FindLast().
判断存在用Exists();
FindIndex()方法需要一个Predicate类型的参数。
public int FindIndex(Predicate<T> match);
需要给委托对象传递一个声明的委托实例,例如:
public bool FindCountryPredicate(Racer racer)
{
   if( racer == null) return false;
   return racer.Country  == country;
}
将FindCountryPredicate传入函数参数,即可,RemoveAll()中也需要传递入该委托实例。
Find(), FindIndex(), FindAll()都需要这样的比较委托实例,委托实例的广泛使用,如果只写一次可以用Lambd表达式来写,多次将其封装为函数。

5)排序
排序Sort方法也需要传递比较大小的委托实例。
有大概三种比较大小的委托函数:
默认的是IComparable<T>一个other参数的比较委托。
IComparer<T>两个参数的比较委托。
重载Sort方法,该方法需要一个Comparison<T>的委托实例。Comparison<T>的委托定义是public delegate int Comparison<T>(T x, T y);

可以调用Reverse()方法逆转整个集合的排序。

6)类型转换
使用List<T>类的ConvertAll<TOutput>()方法,可以把所有的集合类型转换为另一种类型。
该TOutput委托的定义如下:
public sealed delegate TOutput Convert<TInput, TOutput>(TInput from);
需要定义一个委托实例,传入该函数参数即可。

7)只读集合
一般集合都是要支持读写的,但是有些比较特殊的应用需要给客户提供一个只读集合,那么可以使用List<T>集合的AsReadOnly()方法就可以返回

一个ReadOnlyCollection<T>类型的对象。ReadOnlyCollection<T>和List<T>的差别只是不能写排序删除等,其它实现都一样。

List简单例子:

 static void Main()
{
var graham = new Racer(7, "Graham", "Hill", "UK", 14);
var emerson = new Racer(13, "Emerson", "Fittipaldi", "Brazil", 14);
var mario = new Racer(16, "Mario", "Andretti", "USA", 12);

var racers = new List<Racer>(20) { graham, emerson, mario };

racers.Add(new Racer(24, "Michael", "Schumacher", "Germany", 91));
racers.Add(new Racer(27, "Mika", "Hakkinen", "Finland", 20));

racers.AddRange(new Racer[] {
new Racer(14, "Niki", "Lauda", "Austria", 25),
new Racer(21, "Alain", "Prost", "France", 51)});

var racers2 = new List<Racer>(new Racer[] {
new Racer(12, "Jochen", "Rindt", "Austria", 6),
new Racer(22, "Ayrton", "Senna", "Brazil", 41) });

Console.WriteLine("-------racers------------");
for( int i = 0; i < racers.Count; i++ )
{
Console.WriteLine(racers[i].ToString());
}
Console.WriteLine("-------racers2------------");
for (int i = 0; i < racers2.Count; i++)
{
Console.WriteLine(racers2[i].ToString());
}
}

2.Queue<T>

先进先出,实现了ICollection和IEnumerable<T>接口,但没有实现ICollection<T>接口,因此这个接口定义的Add()和Remove()方法不能用于队列。
没有实现List<T>接口,所以也不支持索引器访问。

队列中的常用方法,Count返回个数,Dequeue()进队列,Enqueue出队列并删除队列头元素,Peek从队列头部读取队列但不删除元素。
TrimExcess()可以清除Capacity中的大于10%时候的元素。

队列Queue<T>的构造默认会4,8,16,32递增的增加容量,.net 1.0版本的Queue却是一开始就给了个32项的空数组。
队列例子:

public class DocumentManager
{
// readonly只是说这个队列对象不写(比如另一个对象拷贝给它),但是内部的元素是可以写的
private readonly Queue<Document> documentQueue = new Queue<Document>();

public void AddDocument(Document doc)
{
lock (this)
{
documentQueue.Enqueue(doc);
}
}

public Document GetDocument()
{
Document doc = null;
lock (this)
{
doc = documentQueue.Dequeue();
}
return doc;
}

public bool IsDocumentAvailable
{
get
{
return documentQueue.Count > 0;
}
}
}


using System;
using System.Threading;
namespace Wrox.ProCSharp.Collections
{
public class ProcessDocuments
{
private DocumentManager documentManager;
protected ProcessDocuments(DocumentManager dm)
{
documentManager = dm;
}

public static void Start(DocumentManager dm)
{
// ParameterizedThreadStart;
// public delegate void ParameterizedThreadStart(object obj);
// 直接这样启动一个线程了。
new Thread( new ProcessDocuments(dm).Run ).Start();
}

protected void Run(object obj) // 这里用不用object obj参数都可以,IL会做转换为友object的。
{
while (true)
{
if (documentManager.IsDocumentAvailable)
{
Document doc = documentManager.GetDocument();
Console.WriteLine("Processing document {0}", doc.Title);
}
Thread.Sleep(new Random().Next(20));
}
}
}
}

using System;
using System.Threading;

namespace Wrox.ProCSharp.Collections
{
class Program
{
static void Main()
{
var dm = new DocumentManager();
ProcessDocuments.Start(dm);
// Create documents and add them to the DocumentManager
for (int i = 0; i < 1000; i++)
{
Document doc = new Document("Doc " + i.ToString(), "content");
dm.AddDocument(doc);
Console.WriteLine("Added document {0}", doc.Title);
Thread.Sleep(new Random().Next(20));
}
}
}
}

3.Stack<T>

后进先出,Count属性,Push(),Pop()方法会删除最顶元素,Peek()不会删除,Contains()确定某个元素是否在栈中是则返回true.

using System;
using System.Collections.Generic;
namespace Wrox.ProCSharp.Collections
{
class Program
{
static void Main()
{
var alphabet = new Stack<char>();
alphabet.Push('A');
alphabet.Push('B');
alphabet.Push('C');

Console.Write("First iteration: ");
// 迭代遍历用了迭代模式,不会删除
foreach (char item in alphabet)
{
Console.Write(item);
}

Console.Write("Second iteration: ");
while (alphabet.Count > 0)
{
// Pop会删除
Console.Write(alphabet.Pop());
}
Console.WriteLine();
}
}
}

4.SortedList<TKey, TValue>

实现是基于数组的列表,定义了单一任意类型的键和单一任意类型的值的数据结构,可以直接创建一个空的排序列表;或者重载构造函数可以定义列表容量和传递一个IComparer<TKey>接口的对象,该接口用于给列表中的元素排序。

为容器添加元素可以用Add()方法,也可以用索引下标赋值,相同键添加时候Add方法会抛出异常不能覆盖旧键,索引下标相同键时候会覆盖旧键不抛异常。

访问时候可以用集合迭代器元素的Key,Value属性访问键和值;也可以用集合的Values和Keys属性来返回所有的键值属性,类似C++中的STL map一样。
通过索引器键值访问元素时候,如果键不存在,那么会抛出异常,为了避免异常发生,可以用ContiansKey方法来判断是否存在集合中,再用索引器访问。
还可以直接用TryGetValue方法,尝试获得该键的值,如果不存在也不会抛出异常。

实例:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Wrox.ProCSharp.Collections
{
class Program
{
static void Main(string[] args)
{
var books = new SortedList<string, string>();
books.Add("C# 2008 Wrox Box", "978–0–470–047205–7");
books.Add("Professional ASP.NET MVC 1.0", "978–0–470–38461–9");

books["Beginning Visual C# 2008"] = "978–0–470-19135-4";
books["Professional C# 2008"] = "978–0–470–19137–6";

foreach (KeyValuePair<string, string> book in books)
{
Console.WriteLine("{0}, {1}", book.Key, book.Value);
}

foreach (string isbn in books.Values)
{
Console.WriteLine(isbn);
}

foreach (string title in books.Keys)
{
Console.WriteLine(title);
}

{
string isbn;
string title = "Professional C# 7.0";
// 出现异常
try
{
isbn = books[title];
}
catch ( KeyNotFoundException err)
{
Console.WriteLine("Exception " + err.ToString());
}

if (!books.TryGetValue(title, out isbn))
{
Console.WriteLine("{0} not found", title);
}
}
}
}
}

5.LinkList<T>

LinkList<T>才是链表而且是双向链表,前面的都是基于数组的。链表典型的特征就是插入删除非常方便,但是查找比较慢需要O(n)的查找效率。
LinkedList<T>包含LinkedListNode<T>类型的元素,该节点定义了List、Next、Previous、Value,List属性返回和节点相关的LinkedList<T>对象。LinkedList<T>可以访问成员的第一个和最后一个元素(First和Last);可以在指定位置AddAfter()/AddBefore()/AddFirst()/AddLast()方法;删除指定位置的元素Remove()/RemoveFirst()/RemoveLast()方法;查找Find()和FindLast()。
LinkList<T>实例:
Document.cs:

namespace Wrox.ProCSharp.Collections
{
public class Document
{
public string Title { get; private set; }
public string Content { get; private set; }
public byte Priority { get; private set; }

public Document(string title, string content, byte priority = 0)
{
this.Title = title;
this.Content = content;
this.Priority = priority;
}
}

}

PriorityDocumentManager.cs:

using System;
using System.Collections.Generic;

namespace Wrox.ProCSharp.Collections
{
public class PriorityDocumentManager
{
// 真正存放排序好的document的结构体
private readonly LinkedList<Document> documentList;

// priorities 0.9, 方便索引documentList本优先级的最后一个元素;
// 用一个List<T>数组索引器,提高效率,找到数组和链表之间平衡点的提高性能的好方法。
private readonly List<LinkedListNode<Document>> priorityNodes;

public PriorityDocumentManager()
{
documentList = new LinkedList<Document>();

priorityNodes = new List<LinkedListNode<Document>>(10);
for (int i = 0; i < 10; i++)
{
priorityNodes.Add(new LinkedListNode<Document>(null));
}
}

// 对外接口
public void AddDocument(Document d)
{
if (d == null) throw new ArgumentNullException("d");

AddDocumentToPriorityNode(d, d.Priority);
}

private void AddDocumentToPriorityNode(Document doc, int priority)
{
// 外部调用要保证priority就是doc.priority, 否则后面会导致问题
if (priority > 9 || priority < 0)
throw new ArgumentException("Priority must be between 0 and 9");

// 1.开始空或者中间空,递归会导致这里不进来!=null(因为小优先级的有元素时候)
if (priorityNodes[priority].Value == null)
{
--priority;
if (priority >= 0)
{
// check for the next lower priority
// 2)递归是为了检测小于优先级的有没有存在元素的,这时priority会小于doc.priority
AddDocumentToPriorityNode(doc, priority);
}
else // now no priority node exists with the same priority or lower
// add the new document to the end
{
// 1)第一次会进来或者当前priority以下的优先级都没有的情况也会进来
// 更小优先级的都没有,那么它就是最小优先级的
documentList.AddLast(doc);
// priorityNodes存放的时链表最后的那个元素,doc.Priority和documentList.Last上的优先级一样的
priorityNodes[doc.Priority] = documentList.Last;
}
return;
}
// 直接进来,或者递归进来,说明当前优先级或者递归减到的优先级有元素。
else // a priority node exists
{
// 从priorityNodes获取的是当前优先级,最后一个节点的元素
LinkedListNode<Document> prioNode = priorityNodes[priority];
// 1)直接进来时候,如果优先级相等,如果是递归进来的不会到这里因为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
// 当前优先级存的是优先级最后的节点,doc.Priority和prioNode.Next;上的优先级一样的
priorityNodes[doc.Priority] = prioNode.Next;
}
// 2)递归时候进来的,因为priority 小于了doc.Priority,且priority有值,所以要放到priority前面
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
// 当前优先级存的是优先级最后的节点,doc.Priority和prioNode.Next;上的优先级一样的
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)
// 优先级高的出链表,并且删除该document
public Document GetDocument()
{
Document doc = documentList.First.Value;
documentList.RemoveFirst();
return doc;
}

}

}
Program.cs:

namespace Wrox.ProCSharp.Collections
{
class Program
{
static void Main()
{
PriorityDocumentManager pdm = new PriorityDocumentManager();
// 传入时候就排序好了,LinkList<T>结构方便优先级类型的插入操作(利于插入和删除)
pdm.AddDocument(new Document("one", "Sample", 8));
pdm.AddDocument(new Document("two", "Sample", 3));
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", 1));
pdm.AddDocument(new Document("eight", "Sample", 1));

// 展示排序好的
pdm.DisplayAllNodes();

}
}
}

四.Dictionary<TKey,TValue>、多键值ILookup<TKey,TValue>、SortedDictionary<TKey,TValue>、HashSet<T>和SortedSet<T>

1.Dictionary<TKey,TValue>

.net提供了几个字典类,其中最主要的类是Dictionary<TKey,TValue>。
字典基于hash_map存储结构,提供了快速的查找方法,查找效率是O(1),但是也不是绝对的因为要解决hash映射函数计算和解决冲突。
也可以*的添加和删除元素,有点像List<T>但是没有内存元素挪动性能开销。
Dictionary数据结构很类似C++中的hash_map/unordered_map工作方式,或者就是这样的实现:
hash_map其插入过程是:
    得到key
    通过hash函数得到hash值
    得到桶号(一般都为hash值对桶数求模)
    存放key和value在桶内。

其取值过程是:
    得到key
    通过hash函数得到hash值
    得到桶号(一般都为hash值对桶数求模)
    比较桶的内部元素是否与key相等,若都不相等,则没有找到。
    取出相等的记录的value。
因此C#中要用Dictionary类,键类型需要重写:
1)哈希函数:Object类的GetHashCode()方法,GetHashCode()返回int值用于计算键对应位置放置的hashCode用作元素索引。
GetHashCode()实现要求:
相同的键总是返回相同的int值,不同的键可以返回相同的int值。
它应该执行得比较快,计算开销不大,hashCode应该尽量平均分布在int可以存储的整个数字范围上。
不能抛出异常。
至少使用一个键对象的字段,hashCode最好在键对象的生存期中不发生变化。

2)解决冲突:键类型必须实现IEquatable<T>.Equals()方法,或者重写Object类的Equals()方法,因为不同的键值需要返回不同的hashCode,相同的键返回相同hashCode。
默认没有重写,那么Equals方法比较的是引用无论是值类型还是引用类型,GetHashCode()是根据对象的地址计算hashCode,所以默认是基于引用的比较。
相同的int类型传入,只要不是相同的int引用,就会导致无法返回结果。
所以基础类型都重写了上述两个方法,基础类型中string比较通过字符串值有较好的散列平均分布,int也是通过值比较但是很难平均分布。

如果重写了一个Equals方法(一般是值比较),但是没有重写GetHashCode()方法(一般也是基于值的获取hashCode)那么获取hashCode的方法将是获取引用,使用字典类就会导致诡异的行为,将对象放入了字典中,但是取不出来了(因为键引用不同),或者取出来的是一个错误的结果,所以编译器会给一个编译警告!
如果键类型没有重写GetHashCode()和Equals()方法;也可以实现IEqualityComparer<T>接口的比较器它定义了GetHashCode()和Equals()方法,并将传递的对象作为参数,将比较器传入Dictionary<TKey,TValue>一个重载版本的构造函数即可。
Employee.cs:

using System;
namespace Wrox.ProCSharp.Collections
{
// 将类的一个实例序列化为一个文件
[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);
}
}
}

EmployeeId.cs:

using System;

namespace Wrox.ProCSharp.Collections
{
[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)
{
if (id == null) throw new ArgumentNullException("id");

prefix = (id.ToUpper())[0];
int numLength = id.Length - 1;
try
{
// 截取前面6位,有可能提供的number一样,这样多个键会产生一个相同的GetHashCode()。
// 但是后面会通过Equals方法进行解决冲突。
number = int.Parse(id.Substring(1, numLength > 6 ? 6 : numLength));
}
catch (FormatException)
{
throw new EmployeeIdException("Invalid EmployeeId format");
}
}

public override string ToString()
{
return prefix.ToString() + string.Format("{0,6:000000}", number);
}
// 获取确定的,int类型上均匀分配的,高性能的产生hashCode方法
public override int GetHashCode()
{
return (number ^ number << 16) * 0x15051505;
}

public bool Equals(EmployeeId other)
{
if (other == null) return false;
// number相同情况下,如果prefix也相同,那么就会导致完全相同了
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);
}
}
}

Program.cs:

using System;
using System.Collections.Generic;

namespace Wrox.ProCSharp.Collections
{
class Program
{
static void Main()
{
// capacity是素数
var employees = new Dictionary<EmployeeId, Employee>(31);

var idKyle = new EmployeeId("T3755");
var kyle = new Employee(idKyle, "Kyle Bush", 5443890.00m);
employees.Add(idKyle, kyle);
Console.WriteLine(kyle);

var idCarl = new EmployeeId("F3547");
var carl = new Employee(idCarl, "Carl Edwards", 5597120.00m);
employees.Add(idCarl, carl);
Console.WriteLine(carl);

var idJimmie = new EmployeeId("C3386");
var jimmie = new Employee(idJimmie, "Jimmie Johnson", 5024710.00m);
var jimmie2 = new Employee(idJimmie, "Jimmie Cen", 5024710.00m);
employees.Add(idJimmie, jimmie);
//employees.Add(idJimmie, jimmie2); // 相同key,用Add不会覆盖,但是会抛出异常
Console.WriteLine(jimmie);

var idDale = new EmployeeId("C3323");
var dale = new Employee(idDale, "Dale Earnhardt Jr.", 3522740.00m);
employees[idDale] = dale;
Console.WriteLine(dale);

var idJeff = new EmployeeId("C3234");
var jeff = new Employee(idJeff, "Jeff Burton", 3879540.00m);
var jeff2 = new Employee(idJeff, "Jeff Cen", 3879540.00m);
// 下标索引方式添加元素
employees[idJeff] = jeff;
employees[idJeff] = jeff2; // 相同key,用下标索引会覆盖
Console.WriteLine(jeff);

while (true)
{
Console.Write("Enter employee id (X to exit)> ");
var userInput = Console.ReadLine();
userInput = userInput.ToUpper();
if (userInput == "X") break;

EmployeeId id;
try
{
// 第一位字符会去掉,用后面的数字作为真正的key
id = new EmployeeId(userInput);

Employee employee;
// 如果用下标访问的话,不存在会抛出异常NotFoundException
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);
}
}
}
}
}

2.ILookup<TKey,TValue>

非常类似于Dictionary<TKey,TValue>,会把键映射到一个值集上,但是ILookup<TKey,TValue>是在System.Core命名空间中,用System.Linq命名空间定义。
ILookup<TKey,TValue>是一个拓展结构,不能像其它容器那样直接创建,需要从实现了IEnumerable<T>接口的容器中用ToLookup函数获取。
ToLookup函数需要传递一个Func<TSource, TKey>类型的键委托,可以用Lambda表达式来实现,例如:

static void Main()
{
var racers = new List<Racer>();
racers.Add(new Racer(26, "Jacques", "Villeneuve", "Canada", 11));
racers.Add(new Racer(18, "Alan", "Jones", "Australia", 12));
racers.Add(new Racer(11, "Jackie", "Stewart", "United Kingdom", 27));
racers.Add(new Racer(15, "James", "Hunt", "United Kingdom", 10));
racers.Add(new Racer(5, "Jack", "Brabham", "Australia", 14));
//public static ILookup<TKey, TSource> ToLookup<TSource, TKey>
//(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
//创建一个1:n 的映射。 它可以方便的将数据分类成组,并生成一个字典供查询使用。
//System.Linq.Enumerable::ToLookup
//public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
// this IEnumerable<TSource> source?,是.net的拓展方法机制,用实例调用静态方法,但是编译器是将实例作为静态方法的第一个参数来调用静态方法的。
var lookupRacers = racers.ToLookup(x => x.Country);
foreach (Racer r in lookupRacers["Australia"])
{
Console.WriteLine(r);
}
}

3.SortedDictionary<TKey,TValue>

是一个二叉树,其中元素根据键来排序,该键类型必须实现IComparable<TKey>接口,或者需要传递一个IComparer<TKey>接口的比较器用作有序字典的构造函数的一个参数。其实类似于C++中

的map类型了,类似java中的TreeMap类型。
SortedDictionary<TKey,TValue>和SortedList<TKey,TValue>,但SortedDictionary<TKey,TValue>类插入和删除元素比较快,查找速度比较慢,内存开销比SortedList<TKey,TValue>大。

SortedList<TKey,TValue>适用很少修改的情形,因为有更快的查找速度,用更小的内存。

4.HashSet<T>和SortedSet<T>

HashSet<T>是无序的和SortedSet<T>是有序的都实现了接口ISet<T>,ISet<T>提供了集合的交集,并集,判断集合关系等操作。
直接创建集合对象就可以了,为集合添加元素可以用Add()方法如果重复那么会返回false不会抛出异常。
IsSubsetOf和IsSupersetOf方法比较集合实现了IEnumerable<T>接口的集合,并返回一个布尔结果,Overlaps()是判断有交集。
UnionWith()方法将多个集合求并,ExceptWith()求差集。
SortedSet<T>如果是自定义类型,那么需要提供排序的委托实例。

ObservableCollection<T>类,是为WPF定义的,这样UI可以得到集合的变化,在命名空间:System.Collections.ObjectModel中定义。
ObservableCollection<T>派生自Collection<T>基类,所以集合类的很多操作该容器都满足,并在内部使用了List<T>类。
ObservableCollection<T>对象的CollectionChanged事件可以添加消息处理函数也就是委托实例,当集合发生变化时候可以回调到处理函数中。

五.BitArray/BitVector32、IProducerConsumerCollection<T>接口

1.BitArray/BitVector32用集合进行位操作

1).BitArray位于System.Collections命名空间中,用于不确定位大小的操作,可以包含非常多的位,应该是存储在堆中。
BitArray是一个引用类型,包含一个int数组,其中每32位使用一个新整数。
BitArray可以用索引器对数组中的位进行操作,索引器是bool类型,还可以用Get(),Set方法访问数组中的位。
BitArray的位操作,Not非,And()与,Or()或,Xor()异或操作。

2).BitVector32是值类型
BitVector32位于System.Collections.Specialized中,32位的操纵,存储在栈中,速度很快。
BitVector32属性方法,Data返回二进制数据的整型大小.
BitVector32的访问可以使用索引器,索引器是重载的,可以使用掩码或BitVector32.Section类型的片段来获取和设置值。
CreateMask()为结构中的特定位创建掩码。
CreateSection()用于创建32位中的几个片段。
位操作例子:

using System;
using System.Collections;
using System.Collections.Specialized;
using System.Text;
namespace BitArraySample
{
class Program
{
static void Main()
{
BitArrayDemo();
BitVectorDemo();
}

static void BitArrayDemo()
{
var bits1 = new BitArray(8);
// 全部设置为1
bits1.SetAll(true);
// 索引1设置为false
bits1.Set(1, false);
// 设置用下标索引器设置值
bits1[5] = false;
bits1[7] = false;
Console.Write("initialized: ");
DisplayBits(bits1);
Console.WriteLine();

// 位的一些运算
DisplayBits(bits1);
bits1.Not();
Console.Write(" not ");
DisplayBits(bits1);
Console.WriteLine();

var bits2 = new BitArray(bits1);
bits2[0] = true;
bits2[1] = false;
bits2[4] = true;
DisplayBits(bits1);

Console.Write(" or ");
DisplayBits(bits2);
Console.Write(" : ");
bits1.Or(bits2);
DisplayBits(bits1);
Console.WriteLine();

DisplayBits(bits2);
Console.Write(" and ");
DisplayBits(bits1);
Console.Write(" : ");
bits2.And(bits1);
DisplayBits(bits2);
Console.WriteLine();

DisplayBits(bits1);
Console.Write(" xor ");
DisplayBits(bits2);
bits1.Xor(bits2);
Console.Write(" : ");
DisplayBits(bits1);
Console.WriteLine();
}

static void BitVectorDemo()
{

var bits1 = new BitVector32();
// 书面写法,不考虑大小端,最后一个位的掩码(考虑是小端也就是地址读到的第一个)
int bit1 = BitVector32.CreateMask();
// 基于bit1位的上一个位的掩码,其实bit1是1
int bit2 = BitVector32.CreateMask(bit1);
// 基于bit2位的上一个位的掩码,其实bit2是2
int bit3 = BitVector32.CreateMask(bit2);
int bit4 = BitVector32.CreateMask(bit3);
int bit5 = BitVector32.CreateMask(bit4);

// 用索引器将末尾取值为1,其实bit1是1
bits1[bit1] = true;
// 用索引器将倒数第二位取值为0,其实bit2是2
bits1[bit2] = false;
bits1[bit3] = true;
bits1[bit4] = true;
Console.WriteLine(bits1);
// 可以一次性的把有1下标的赋值为true
bits1[0xabcdef] = true;
Console.WriteLine(bits1);

int received = 0x79abcdef;
// 一次性的把有1下标的赋值为true,为0的赋值位0
var bits2 = new BitVector32(received);
Console.WriteLine(bits2);
// sections: FF EEE DDD CCCC BBBBBBBB AAAAAAAAAAAA
// 从底地址开始截取0xfff片段的索引值
BitVector32.Section sectionA = BitVector32.CreateSection(0xfff);
// 基于sectionA偏移,取0xff位数上的索引值
BitVector32.Section sectionB = BitVector32.CreateSection(0xff, sectionA);
BitVector32.Section sectionC = BitVector32.CreateSection(0xf, sectionB);
BitVector32.Section sectionD = BitVector32.CreateSection(0x7, sectionC);
BitVector32.Section sectionE = BitVector32.CreateSection(0x7, sectionD);
BitVector32.Section sectionF = BitVector32.CreateSection(0x3, sectionE);

// 用索引片段,访问bits2在该片段上的元素
Console.WriteLine("Section A: " + IntToBinaryString(bits2[sectionA], true));
Console.WriteLine("Section B: " + IntToBinaryString(bits2[sectionB], true));
Console.WriteLine("Section C: " + IntToBinaryString(bits2[sectionC], true));
Console.WriteLine("Section D: " + IntToBinaryString(bits2[sectionD], true));
Console.WriteLine("Section E: " + IntToBinaryString(bits2[sectionE], true));
Console.WriteLine("Section F: " + IntToBinaryString(bits2[sectionF], true));
}

static string IntToBinaryString(int bits, bool removeTrailingZero)
{
var sb = new StringBuilder(32);
for (int i = 0; i < 32; i++)
{
// 从左边读起,读完后丢弃左边位数,所以与上0x80000000
if ((bits & 0x80000000) != 0)
{
sb.Append("1");
}
else
{
sb.Append("0");
}
bits = bits << 1;
}
string s = sb.ToString();
if (removeTrailingZero)
return s.TrimStart('0');
else
return s;
}

static void DisplayBits(BitArray bits)
{
// 可以直接迭代输出
foreach (bool bit in bits)
{
Console.Write(bit ? 1 : 0);
}
}
}
}

2.IProducerConsumerCollection<T>接口

.net4.0中包含了新的命名空间System.Collections.Concurrent,定义了一些线程安全的集合,这些集合实现了IProducerConsumerCollection<T>接口(生产消费者模式)。
这样多线程访问这些集合就不需要Lock{}操作了。只需要用相应集合的TryAdd和TryTake方法,这两个方法分为阻塞的和非阻塞的,如果失败会返回false否则返回true。
这些集合有:
ConcurrentQueue<T>集合,Enqueue(),TryDequeue()和TryPeek方法。
ConcurrentStack<T>类。
ConcurrentBag<T>类。
ConcurrentDictionary<TKey, TValue>这个是线程安全的键值集合,TryAdd,TryGetValue, TryRemove,TryUpdate方法以非阻塞方式访问成员。因为基于键和值ConcurrentDictionary<TKey,

TValue>没有实现IProducerConsumerCollection<T>接口,但是也是支持线程安全的。
ConcurrentXXX类型的集合是线程安全的。

BlockingCollection<T>定义了集合操作阻塞的接口,使用令牌机制,可以指定等待的最长时间。BlockingCollection<T>是针对实现了IProducerConsumerCollection<T>接口的任意类型修饰器,默认是使用了ConcurrentQueue<T>类。
实现例子:
static void Main()
{
BlockingDemoSimple();
}

static void BlockingDemoSimple()
{
// 阻塞的容器
var sharedCollection = new BlockingCollection<int>();

// 定义两个事件对象和等待事件完成的重置消息句柄
var events = new ManualResetEventSlim[2];
var waits = new WaitHandle[2];
for (int i = 0; i < 2; i++)
{
events[i] = new ManualResetEventSlim(false);
waits[i] = events[i].WaitHandle;
}

var producer = new Thread(obj =>
{
// 解析传入的集合容器和事件对象
var state = (Tuple<BlockingCollection<int>, ManualResetEventSlim>)obj;
var coll = state.Item1;
var ev = state.Item2;
var r = new Random();

for (int i = 0; i < 300; i++)
{
// 阻塞函数,var coll前面强转确定类型,可以添加元素
coll.Add(r.Next(3000));
}
// 事件完成,释放信号
ev.Set();
});
producer.Start(Tuple.Create<BlockingCollection<int>, ManualResetEventSlim>(sharedCollection, events[0]));

var consumer = new Thread(obj =>
{
// 解析传入的集合容器和事件对象
var state = (Tuple<BlockingCollection<int>, ManualResetEventSlim>)obj;
var coll = state.Item1;
var ev = state.Item2;

for (int i = 0; i < 300; i++)
{
// 阻塞函数,前面强转确定类型,提取元素
int result = coll.Take();
}
// 事件完成,释放信号
ev.Set();
});
consumer.Start(Tuple.Create<BlockingCollection<int>, ManualResetEventSlim>(sharedCollection, events[1]));

// 主线程会阻塞一直等待信号到来
if (!WaitHandle.WaitAll(waits))
Console.WriteLine("wait failed");
else
Console.WriteLine("reading/writing finished");

}