集合与泛型.doc

第2章 集合与泛型
2.1 集合概述
所谓集合是特殊元素们的一种聚合。集合的元素被称为是成员。集合有两个最重要的属性，一个是集合成员都是无序的，另一个则是集合的成员不会出现超过一次。在计算机科学领域内集合扮演着非常重要的角色，但是不把集合包含作为C#语言的一种数据结构。
2.1.1 集合的定义
人们把集合定义成相关成员的无序聚集，而且集合中的成员不会出现超过一次。集合书写成用一对闭合大括号包裹成员列表的形式，例如{0，1，2，3，4，5，6，7，8，9}。只要全部成员只书写一次，就可以按照任意顺序书写集合，所以此前的集合实例还可以写成{9，8，7，6，5，4，3，2，1，0}或其他任意成员组合的形式。
为了使用集合需要知道一些有关集合的定义。
1. 不包含任何成员的集合称为空集合。全域是所有可能成员的集合。
2. 如果两个集合包含完全一样的成员，那么就认为这两个集合相等。
3. 如果第一个集合的全部成员都包含在第二个集合内，就认为第一个集合是第二个集合的子集。
2.1.2 集合的操作
下面描述了在集合上执行的基本操作。
1. 联合：由第一个集合中的所有成员和第二个集合中不包含在第一个集合的成员组成的新集合。
2. 交叉：由既属于第一个集合又属于第二个集合的成员组成的新集合。
3. 差异：由属于第一个集合但不属于第二个集合的成员组成的新集合。
2.2 集合类
ArrayList是与数组相当的集合类。还有其他类型的集合：队列、栈、有序表和哈希表，如下所示：
l ArrayList 动态数组
l Queue 队列
l Stack 栈
l BitArray 位数组
l Hashtable 散列表
l SortedList 有序表

集合类位于System.Collections命名空间，集合类可以组合为集合，存储Object类型的元素。
2.3 集合的一种实现
HashTable类是.NET框架类库中较为有效的数据结构之一，它的存取速度较其它类而言要快。下面就以散列表作为存储结构来实现一个集合类，具体代码如下：
using System;
using System.Collections;

//集合
public class Set
{
private Hashtable data;

public Set()
{
data = new Hashtable();
}

//添加成员。如果成员不在集合内，则添加到集合中
public void Add(Object item)
{
if (!data.ContainsValue(item))
{
data.Add(Hash(item), item);
}
}

//根据成员各字符的ASCII码值计算散列值（在散列表中数据项以键值对形式存在）
private string Hash(Object item)
{
char[] chars;
string s = item.ToString();
int hashValue = 0;
chars = s.ToCharArray();
for (int i = 0; i <= chars.GetUpperBound(0); i++)
{
hashValue += (int)chars[i];
}

return hashValue.ToString();
}

//删除成员
public void Remove(Object item)
{
data.Remove(Hash(item));
}

//成员数量
public int Size
{
get
{
return data.Count;
}
}

//求并集。由第一个集合中的所有成员和第二个集合中不包含在第一个集合的成员组成的新集合。
public Set Union(Set aSet)
{
Set tempSet = new Set();
foreach (Object hashObject in data.Keys)
{
tempSet.Add(this.data[hashObject]);
}
foreach (Object hashObject in aSet.data.Keys)
{
if (!(this.data.ContainsKey(hashObject)))
{
tempSet.Add(aSet.data[hashObject]);
}
}

return tempSet;
}

//求交集。由既属于第一个集合又属于第二个集合的成员组成的新集合。
public Set Intersection(Set aSet)
{
Set tempSet = new Set();
foreach (Object hashObject in data.Keys)
{
if (aSet.data.Contains(hashObject))
{
tempSet.Add(aSet.data[hashObject]);
}
}

return tempSet;
}

//判断子集。如果第二个集合大于第一个集合，并且第一个集合中所有成员都包含在第二个集合中，则第一个集合是第二个集合的子集。
public bool Subset(Set aSet)
{
if (this.Size > aSet.Size) return false;

foreach (Object key in this.data.Keys)
{
if (!(aSet.data.Contains(key))) return false;
}

return true;
}

//求差集。由属于第一个集合但不属于第二个集合的成员组成的新集合。
public Set Difference(Set aSet)
{
Set tempSet = new Set();
foreach (Object hashObject in data.Keys)
{
if (!(aSet.data.Contains(hashObject)))
{
tempSet.Add(data[hashObject]);
}
}

return tempSet;
}

public override string ToString()
{
string s = "";
foreach (Object key in data.Keys) s += data[key] + " ";

return s;
}
}

class Test
{
static void Main()
{
Set setA = new Set();
setA.Add("中国");
setA.Add("日本");
setA.Add("美国");
setA.Add("韩国");

Set setB = new Set();
setB.Add("日本");
setB.Add("韩国");
setB.Add("加拿大");
Set setC = new Set();

setC = setA.Union(setB);
Console.WriteLine("A: " + setA.ToString());
Console.WriteLine("B: " + setB.ToString());
Console.WriteLine("A union B: " + setC.ToString());

setC = setA.Intersection(setB);
Console.WriteLine("A intersect B: " + setC.ToString());

setC = setA.Difference(setB);
Console.WriteLine("A diff B: " + setC.ToString());

setC = setB.Difference(setA);
Console.WriteLine("B diff A: " + setC.ToString());

if (setB.Subset(setA))
{
Console.WriteLine("B is a subset of A");
}
else
{
Console.WriteLine("B is not a subset of A");
}

Console.Read();
}
}

运行结果如下：

2.1 泛型概述
泛型(Generic Type)是.NET Framework 2.0的一大特性。泛型的主要思想就是将算法与数据结构完全分离开来，使得一次定义的算法能够作用于多种数据结构，从而实现高度可重用的开发。通过泛型可以定义类型安全的数据结构，而没有必要使用实际的数据类型。这将显著提高性能并得到更高质量的代码，因为可以重用数据处理算法，而没有必要复制类型特定的代码。
泛型是一个很强大的特性，对于集合类而言尤其如此。.NET 1.1中的大多数集合类都基于Object类型。.NET 从2.0开始提供了实现为泛型的新集合类。
泛型不仅限于类，还可用于委托、接口和方法的泛型。
在.NET 2.0之前，不存在泛型，在开发通用容器时，需要通用容器能存储各种类型的实例。在.NET Framework 1.1下，必须使用基于object类型的系统集合类（例如ArrayList，Stack，Queen等），但由于集合类中的项都是Object类型的，因此每次使用时都必须进行装箱拆箱操作，不仅大大降低了程序的性能，而且存在类型安全问题（Object类在编译期间没有类型安全性）。
泛型(Generic Type)的出现较好的解决了上述问题，通过它，可以轻松创建指定类型的集合。泛型集合类不仅是类型安全的，而且使用时不需要进行烦琐的装箱拆箱操作。
泛型是C# 2.0中的新增元素(类似于C++中模板)。这种机制允许将类名作为参数传递给泛型类型，并生成相应的对象。主要利用System.Collections.Generic命名空间下面的List泛型类来创建集合。语法如下：
　　List<T> ListOfT = new List<T>( );
其中的"T"就是所要使用的类型，既可以是简单类型，如string、int，也可以是用户自定义类型。
下面看一个具体例子。
using System;
using System.Collections.Generic;

struct Student
{
public string sno; //学号
public string sname; //姓名
public int sage; //年龄

public Student(string sno, string sname, int sage)
{
this.sno = sno;
this.sname = sname;
this.sage = sage;
}
}

class SamplesGeneric
{
static void Main()
{
//创建Student对象
Student stu1 = new Student("001", "张三", 30);
Student stu2 = new Student("002", "李四", 20);
Student stu3 = new Student("003", "王五", 50);

//创建类型为Student的对象集合
List<Student> students = new List<Student>();

//将Student对象放入集合
students.Add(stu1);
students.Add(stu2);
students.Add(stu3);

//输出第1学生的姓名
Console.WriteLine(students[0].sname);
}
}

运行结果如下图：

下面介绍泛型的优点：
1. 性能
泛型的一个主要优点是性能。对值类型使用System.Collections命名空间的集合类，存储数据时需要把值类型转换为引用类型，获取数据时需要把引用类型转换为值类型，即需要进行装箱和拆箱操作。例如，下面例子在存取数据时就进行了装箱拆箱操作。
ArrayList list = new ArrayList();
list.Add(44);   // boxing - convert a value type to a reference type
int i1 = (int)list[0];   // unboxing - convert a reference type to a value type
foreach (int i2 in list)
{
Console.WriteLine(i2);   // unboxing
}
装箱和拆箱操作很容易使用，但性能损失比较大，迭代许多项时尤其如此。
System.Collections.Generic命名空间中的List<T>类不使用对象，而是在使用时定义类型。在下面的例子中，List<T>类的泛型类型定义为int，所以int类型在JIT编译器动态生成的类中使用，不再进行装箱和拆箱操作：
List<int> list = new List<int>();
list.Add(44);   // no boxing - value types are stored in the List<int>
int i1 = list[0];   // no unboxing, no cast needed
foreach (int i2 in list)
{
Console.WriteLine(i2);
}

2. 类型安全
泛型的另一个特性是类型安全。与ArrayList类一样，如果使用对象，可以在这个集合中添加任意类型。下面的例子在ArrayList类型的集合中添加一个整数、一个字符串和一个MyClass类型的对象：
ArrayList list = new ArrayList();
list.Add(44);
list.Add("mystring");
list.Add(new MyClass());

如果这个集合使用下面的foreach语句迭代，而该foreach语句使用整数元素来迭代，编译器就会编译这段代码。但并不是集合中的所有元素都可以转换为int，所以会出现一个运行异常：
foreach (int i in list)
{
Console.WriteLine(i);
}
错误应尽早发现。在泛型类List<T>中，泛型类型T定义了允许使用的类型。有了List<int>的定义，就只能把整数类型添加到集合中。编译器不会编译这段代码，因为Add()方法的参数无效：
List<int> list = new List<int>();
list.Add(44);
list.Add("mystring");   // compile time error
list.Add(new MyClass());   // compile time error

3. 代码重用
泛型允许更好地重用代码。泛型类可以定义一次，用许多不同的类型实例化。
例如，System.Collections.Generic命名空间中的List<T>类用一个int、一个字符串和一个MyClass类型实例化：
List<int> list = new List<int>();
list.Add(44);
List<string> stringList = new List<string>();
stringList.Add("mystring");
List<MyClass> myclassList = new List<MyClass>();
myClassList.Add(new MyClass());
泛型类型可以在一种语言中定义，在另一种.NET语言中使用。
2.2 创建泛型类
泛型最显著的一点就是它参数化了类型，把类型作为参数抽象出来，从而使我们在实际的运用当中能够更好的实现代码的重复利用，同时它提供了更强的类型安全，更高的效率，不过在约束方面，它只支持显式的约束，这样在灵活性方面就显得不是那么好了。泛型之所以能够提供更高的效率是因为泛型在实例化的时候采用了"on-demand"的模式,即按需实例化，发生在JIT(Just In Time)编译时。
下面来看如何定义一个泛型类，很简单，你只需要意识到一点——类型在这里被参数化了：
using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// 定义一个泛型类，该类有一个类型参数T
/// </summary>
/// <typeparam name="T">类型参数</typeparam>
class Item<T>
{
//泛型类的类型参数可用于类成员
public T Value;
public Item<T> Next;

public Item(T value)
{
this.Value = value;
this.Next = null;
}
}

class Collection<T> : IEnumerable<T>
{
public Item<T> First = null;
public Item<T> Last = null;

public void Add(T value)
{
Item<T> newItem = new Item<T>(value);
if (this.First == null)
{
this.First = newItem;
this.Last = newItem;
}
else
{
this.Last.Next = newItem;
this.Last = newItem;
}
}

public IEnumerator<T> GetEnumerator()
{
Item<T> current = this.First;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

class SamplesGeneric
{
static void Main()
{
//使用string来实例化Collection<T>类
Collection<string> names = new Collection<string>();

//调用泛型类中的方法
names.Add("张三");
names.Add("李四");
names.Add("王五");

foreach (string name in names)
{
Console.WriteLine(name);
}

//同样，也可以使用int来实例化Collection<T>类
Collection<int> ages = new Collection<int>();

//调用泛型类中的方法
ages.Add(25);
ages.Add(34);
ages.Add(47);

foreach (int age in ages)
{
Console.WriteLine(age);
}
Console.Read();
}
}

使用泛型类Collection<T>，相当于定义了一个类模板，在具体使用时，需要什么类型即可将它实例化为什么类型，从而实现了代码重用。由于可以用任何类型实例化它，且无需装箱操作，因此比基于Object的非泛型方式获取了更高的性能。如果将Collection<T>实例化为int类型，则使用Add ()方法传送非int值，就会出现一个编译错误，所以说它是类型安全的。使用泛型IEnumerable<T>，foreach语句也是类型安全的，如果foreach语句中的变量不是int，也会出现一个编译错误。
2.3 泛型类的特性
在创建泛型类时，需要一些其他C#关键字。例如，不能把null赋予泛型类型。此时，可以使用default关键字。如果泛型类型不需要Object类的功能，但需要调用泛型类上的某些特定方法，就可以定义约束。
1. 默认值
在创建泛型类时，如果需要给类型T指定null，但是，不能把null赋予泛型类型。原因是泛型类型也可以实例化为值类型，而null只能用于引用类型。为了解决这个问题，可以使用default关键字。通过default关键字，将null赋予引用类型，将0赋予值类型。
using System;
using System.Collections;
using System.Collections.Generic;

class SamplesGeneric<T>
{
public T Value;

public SamplesGeneric()
{
this.Value = default(T);//如果T是值类型则default（T）=0；如果T是引用类型则default（T）=null；

}
}

class Test
{
static void Main()
{
SamplesGeneric<int> obj1 = new SamplesGeneric<int>();
Console.WriteLine(obj1.Value);

SamplesGeneric<ArrayList> obj2 = new SamplesGeneric<ArrayList>();
Console.WriteLine(obj2.Value);

Console.Read();
}
}
注意：
default关键字根据上下文可以有多种含义。switch语句使用default定义默认情况。在泛型中，根据泛型类型是引用类型还是值类型，default关键字用于将泛型类型初始化为null或0。

2. 约束
C#中的泛型只支持显式的约束，因为这样才能保证C#所要求的类型安全，但显式的约束并非时必须的，如果不加约束，泛型类型参数将只能访问System.Object类型中的公有方法。“显式约束”由where子句表达，可以指定“基类约束”，“接口约束”，“构造器约束”，“值类型/引用类型约束”共四种约束。
1、基类约束：
class A { public void F1() {} }
class B { public void F2() {} }
class C<S,T>
where S: A // S继承自A
where T: B // T继承自B
{
　// 可以在类型为S的变量上调用F1，
　// 可以在类型为T的变量上调用F2
}

2、接口约束
interface IPrintable { void Print(); }
interface IComparable<T> { int CompareTo(T v);}
interface IKeyProvider<T> { T GetKey(); }
class Dictionary<K,V>
where K: IComparable<K>
where V: IPrintable, IKeyProvider<K>
{
　// 可以在类型为K的变量上调用CompareTo，
　// 可以在类型为V的变量上调用Print和GetKey
}

3、构造器约束
class A { public A() { } }
class B { public B(int i) { } }
class C<T>
where T : new()
{
　//可以在其中使用T t=new T();
}
C<A> c=new C<A>(); //可以，A有无参构造器
C<B> c=new C<B>(); //错误，B没有无参构造器

4、值/引用类型约束
public struct A { }
public class B { }
class C<T>
where T : struct
{
　// T在这里面是一个值类型
}
C<A> c=new C<A>(); //可以，A是一个值类型
C<B> c=new C<B>(); //错误，B是一个引用类型

提示：
在C#中，where子句的一个重要限制是，不能定义必须由泛型类型执行的运算符。运算符不能在接口中定义。在where子句中，只能定义基类、接口和默认构造函数。

3. 继承
如何实现泛型类的继承呢？这里需要满足下面两点中的任何一点即可：
1、泛型类继承中，父类的类型参数已被实例化，这种情况下子类不一定必须是泛型类；
2、父类的类型参数没有被实例化，但来源于子类，也就是说父类和子类都是泛型类，并且二者有相同的类型参数；
//如果这样写的话，显然会报找不到类型T的错误
class SubItem : Item<T> { }
//正确的写法应该是
class SubItem : Item <string>{ }
class SubItem <T> : Item<string> { }
class SubItem <T> : Item<T> { }

4. 静态成员
泛型类的静态成员只能在类的一个实例中共享。下面看一个例子。
using System;
using System.Collections.Generic;

class SamplesGeneric<T>
{
public static T Value;
}

class Test
{
static void Main()
{
SamplesGeneric<int>.Value = 5;
Console.WriteLine(SamplesGeneric<int>.Value);
SamplesGeneric<string>.Value = "hello";
Console.WriteLine(SamplesGeneric<string>.Value);

Console.Read();
}
}

2.4 泛型接口
泛型接口的创建以及继承规则和泛型类是一样的，看下面的代码：
using System;
using System.Collections.Generic;

interface IAdder<T>
{
T Add(T v1, T v2);
}

class Adder1 : IAdder<int>
{
public int Add(int v1, int v2)
{
return v1 + v2;
}
}

class Adder2 : IAdder<string>
{
public string Add(string v1, string v2)
{
return v1 + v2;
}
}

class SamplesGeneric
{
static void Main()
{
Adder1 adder1 = new Adder1();
int sum = adder1.Add(5, 7);
Console.WriteLine(sum);

Adder2 adder2 = new Adder2();
string str = adder2.Add("hello", "world");
Console.WriteLine(str);

Console.Read();
}
}

2.5 泛型方法
我们再来看泛型方法，C#的泛型机制只支持在方法声明上包含类型参数，也即是泛型方法。特别注意的是，泛型不支持在除了方法以外的其他类/接口成员上使用类型参数，但这些成员可以被包含在泛型类型中，并且可以使用泛型类型的类型参数。还有一点需要说的就是，泛型方法可以在泛型类型中，也可以存在于非泛型类型中。下面通过例子看一下泛型方法的声明与调用。
using System;
using System.Collections.Generic;

class Exchange
{
//声明一个泛型方法
public static void Swap<T>(ref T x, ref T y)
{
T temp;
temp = x;
x = y;
y = temp;
}
}

class SamplesGeneric
{
static void Main()
{
int i = 4;
int j = 5;
//在调用泛型方法时，对泛型方法的类型参数实例化
Exchange.Swap<int>(ref i, ref j);
Console.WriteLine("i = {0}, j = {1}", i, j);
//泛型方法可以像非泛型方法那样调用
Exchange.Swap(ref i, ref j);
Console.WriteLine("i = {0}, j = {1}", i, j);

Console.Read();
}
}

2.6 泛型委托
再来看一下泛型委托，泛型委托支持在返回值和参数上应用类型参数，下面例子中定义了一个类型参数为T的委托，然后在类中利用委托调用方法：
using System;
using System.Collections.Generic;

delegate string GetString<T>(T value);

class SamplesGeneric
{
public static string Method1(int i)
{
return i.ToString();
}

public static string Methed2(string s)
{
return s;
}

st