C#集合基础与运用

1. 集合接口与集合类型............................................... 1

(1) 集合的命名空间................................................. 2

(2) 集合接口介绍..................................................... 2

1、 IEnumerable与IEnumerator接口............. 2

2、集合和列表实现的接口表............................ 2

2. 集合的基本操作....................................................... 2

(1) 创建集合............................................................. 2

(2) 添加元素............................................................. 3

(3) 插入元素............................................................. 3

(4) 访问元素............................................................. 3

(5) 删除元素............................................................. 4

(6) 搜索元素............................................................. 4

(7) 元素排序............................................................. 4

(8) 类型转换............................................................. 4

(9) 只读集合............................................................. 5

(10) 集合常用的扩展方法(常用)........................... 5

3. 常见集合的特性....................................................... 5

(1) 非泛型集合对应的泛型集合............................. 5

(2) 队列(Queue<T>)................................................. 5

(3) 栈(Stack<T>)..................................................... 6

(4) 链表(LinkedList<T>)....................................... 7

(5) 有序列表(SortedList<K,V>)........................... 7

(6) 字典..................................................................... 8

1、 Dictionary<K,V>.......................................... 8

2、 Lookup<K,V>.................................................. 8

3、 SortedDictionary<K,V>.............................. 8

(7) 集(ISet<T>接口)............................................... 8

4. 可观察的集合(深入)............................................... 8

(1) ObservableCollection<T>类简介................... 8

(2) 使用示例............................................................. 8

5. 位数组(深入)........................................................... 9

(1) BitArray、BitVector32介绍.......................... 9

(2) BitArray............................................................. 9

(3) BitVector32..................................................... 10

6. 并发集合(.NET 4新增)........................................ 10

(1) ConcurrentQueue<T>....................................... 10

(2) ConcurrentStack<T>....................................... 10

(3) ConcurrentBag<T>........................................... 10

(4) ConcurrentDictionary<K, V>....................... 10

(5) BlockingCollection<T>................................. 10

7. 不同集合类的性能................................................. 10

1.集合接口与集合类型

(1)集合的命名空间

大多数集合类都可以在System.Collections和System.Collections.Generic名称空间中找到。泛型集合位于System.Collections.Generic名称空间中；专用于特定类型的集合类位于System.Collections.Specialized名称空间中；线程安全的集合位于System.Collections.Concurrent名称空间中。

(2)集合接口介绍

1、IEnumerable与IEnumerator接口

其实IEnumerable接口是非常的简单，只包含一个抽象的方法GetEnumerator()，它返回一个可用于循环访问集合的IEnumerator对象。

public interface IEnumerable

{

IEnumerator GetEnumerator();

}

IEnumerator对象有什么呢？它是一个真正的集合访问器，没有它，就不能使用foreach语句遍历集合或数组，因为只有IEnumerator对象才能访问集合中的项。IEnumerator接口定义了：一个Current属性用来获取当前集合中的项；MoveNext方法将游标的内部位置向前移动；Reset方法将枚举数设置为其初始位置，该位置位于集合中第一个元素之前。

public interface IEnumerator

{

object Current { get; }

bool MoveNext();

void Reset();

}

一个collection要支持foreach进行遍历，就必须实现IEnumerable,并以某种方式返回迭代器对象:IEnumerator。

2、集合和列表实现的接口表

接口	说明
IEnumerable<T>	如果foreach语句用于集合，就需要此接口。
ICollection<T>	此集合定义了Count属性、CopyTo、Add、Remove、Clear方法
IList<T>	可以通过位置访问几何元素
ISet<T>	此集合不允许有重复的元素
IDictionary<K,V>	含有键值对的集合
ILookup<K,V>	含有键值对的集合，但可以通过一个键包含多个值
IComparer<T>	集合元素比较器，用于集合元素的排序
IEqualityComparer<T>	用于字典集合的比较器
IProducerConsumerCollection<T>	线程安全的集合

2.集合的基本操作

(1)创建集合

使用默认的构造函数创建一个空集合，元素添加到集合之后，集合的容量就会扩大为4。当集合的容量被使用完，且还在向集合中添加元素时，集合的容量就会扩大成原来的2倍！可使用Capacity属性设置或访问集合的容量，使用Count属性访问集合的元素个数。也可使用TrimExcess方法调整集合容量，节省内存！

class Program

{

static void Main(string[] args)

{

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

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

{

if (list.Count == (list.Capacity))

{

Console.WriteLine("容量使用量："+list.Count + "/" + list.Capacity);

}

list.Add(i);

}

Console.WriteLine("容量使用量：" + list.Count + "/" + list.Capacity);

list.TrimExcess();//调整容量

Console.WriteLine("容量使用量：" + list.Count + "/" + list.Capacity);

Console.Read();

}

}

创建集合时可以为集合设置初始值，如下：

List<int> list = new List<int>() { 1,2,3,4,5,6,7,8,9,0};

List<string> list = new List<int>() { "aa", "bb", "cc" };

(2)添加元素

为集合添加元素可使用Add方法，还可以使用AddRange方法一次添加多个元素，因为AddRange方法的参数是IEnumerable<T>类型的对象，所以可以添加数组到集合里。

class Program

{

static void Main(string[] args)

{

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

list.AddRange(new string[]{"aa","bb","cc"});//添加数组

list.AddRange(list);//添加集合

foreach (string s in list)

{

Console.WriteLine(s);

}

Console.Read();

}

}

(3)插入元素

插入元素可以使用Insert方法，同样使用InsertRange方法插入多个元素，与AddRange方法类似。

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "aa", "bb", "ff" };

list.Insert(2, "cc");//插入元素

list.InsertRange(3, new string[] { "dd", "ee" });//插入集合

foreach (string s in list)

{

Console.WriteLine(s);

}

Console.Read();

}

}

(4)访问元素

可以使用索引器访问集合中某个位置的元素，例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "aa", "bb", "cc" };

Console.WriteLine(list[1]);//访问第1个位置上的元素，下标从0开始

Console.Read();

}

}

集合的遍历，除了使用foreach外，还可以使用集合的Foreach方法，该方法的参数是一个Action<T>委托类型，可以使用Lambda表达式。例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "aa", "bb", "cc" };

list.ForEach(temp => Console.WriteLine("元素：" + temp));

//也可使用： list.ForEach(Console.WriteLine);

Console.Read();

}

}

(5)删除元素

使用RemoveAt删除指定位置的元素，使用Remove删除指定的元素，使用RemoveRange删除指定位置范围的元素，使用Clear删除所有元素，使用RemoveAll选择删除的元素。

注意：RemoveAll方法的参数是一个Predicate<T>委托类型，使用方式如下：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "12", "123", "1234", "12345" };

//删除长度小于4的元素

list.RemoveAll(x => { bool flag = x.Length < 4; return flag; });

list.ForEach(Console.WriteLine);

Console.Read();

}

}

(6)搜索元素

用于搜索的方法有：IndexOf、LastIndexOf、FindIndex、FindLastIndex、FindLast、Find、FindAll、Exists等方法。

IndexOf、LastIndexOf、FindIndex、FindLastIndex方法用于搜索元素的位置。

FindLast、Find、FindAll方法用于搜索满足条件的元素。

Exists用于判断集合是否存在某些元素。

参数可以使用Predicate<T>委托类型(Lambda表达式)的方法有：FindIndex、FindLastIndex、Find、FindLast、FindAll、Exists。例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "12", "123", "1234", "12345" };

//搜索长度小于4的元素

list=list.FindAll(x => { bool flag = x.Length < 4; return flag; });

list.ForEach(Console.WriteLine);

Console.Read();

}

}

(7)元素排序

可以使用Sort方法对元素排序，也可以调用Reverse方法逆转集合顺序，Sort方法使用快速排序算法。Sort使用了几个重载的方法，可以传递的参数有泛型委托Comparison<T>和泛型接口IComparer<T>，例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "12", "123", "1234", "12345" };

//按字符串长度排序

list.Sort((x, y) => { return y.Length - x.Length; });

list.ForEach(Console.WriteLine);

Console.Read();

}

}

(8)类型转换

使用ConvertAll<TOutput>方法可以把集合里的所有元素转换成另一种类型，ConvertAll<TOutput>使用了Converter委托，其定义如下：

public sealeddelegate TOutput Converter<TInput, TOutput>(TInput from)

TInput是委托方法的参数类型，TOutput是委托方法的返回值类型。例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "12", "123", "1234", "12345" };

//把字符串转换成数字(String->int)

List<int> array = list.ConvertAll<int>(temp => Int32.Parse(temp));

array.ForEach(temp => Console.WriteLine((temp + 1)));

Console.Read();

}

}

(9)只读集合

集合的AsReadOnly方法可以返回一个ReadOnlyCollection<T>类型的集合；ReadOnlyCollection<T>是一个只读集合类型，除了不能使用修改集合的方法与属性，其它与集合一样。

(10)集合常用的扩展方法(常用)

集合的扩展方法很多，这里只举两个例子：Select与Where。例如：

Select：将序列中的每个元素投影到新表中。

class Program

{

static void Main(string[] args)

{

List<int> list = new List<int>() {1,3,5,7,9};

IEnumerable<string> array = list.Select<int, string>(x => (x * x).ToString());

foreach(string s in array)

{

Console.WriteLine(s);

}

Console.Read();

}

}

Where：基于谓词筛选值序列。

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string> { "1", "12", "123", "1234" };

//查询长度小于3的元素

IEnumerable<string> query = list.Where(temp => temp.Length < 3);

foreach (string s in query)

{

Console.WriteLine(s);

}

Console.Read();

}

}

3.常见集合的特性

(1)非泛型集合对应的泛型集合

非泛型集合类	对应的泛型集合类
ArrayList	List<T>
HashTable	DIctionary<T>
Queue	Queue<T>
Stack	Stack<T>
SortedList	SortedList<T>

(2)队列(Queue<T>)

队列是其元素以先进先出的方式来处理的集合。该集合没有Add与Remove方法，其重要的方法如下：

Enqueue	在队列的尾端添加元素
Dequeue	在队列的头部读取并删除元素
Peek	只读取队列头部的元素

程序示例如：

class Program

{

static void Main(string[] args)

{

Queue<string> queue = new Queue<string>();

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

{

queue.Enqueue(i.ToString());//在尾部添加元素

}

PrintQueue(queue);//输出元素

string s = queue.Dequeue();//读取并删除头部元素

Console.WriteLine("读取并删除头部元素:" + s);

queue.Enqueue("5");//在尾部添加元素

s = queue.Peek();//读取头部元素

Console.WriteLine("读取头部元素:" + s);

PrintQueue(queue);//输出元素

Console.Read();

}

//输出元素

private static void PrintQueue(Queue<string> q)

{

IEnumerable<string> list = q.Where(t => true);

foreach (string t in list)

{

Console.WriteLine(t);

}

}

}

(3)栈(Stack<T>)

栈是一个后进先出的容器，其重要的方法如下：

Push	在栈顶压入一个元素入栈
Pop	从站顶读取并删除一个元素
Peek	只从站顶读取一个元素

程序示例如：

class Program

{

static void Main(string[] args)

{

Stack<string> stack = new Stack<string>();

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

{

stack.Push(i.ToString());//入栈

}

PrintStack(stack);//输出元素

string s = stack.Pop();//读取并删除栈顶元素

Console.WriteLine("读取并删除栈顶元素:" + s);

s = stack.Peek();//只读取栈顶元素

Console.WriteLine("只读取栈顶元素:" + s);

PrintStack(stack);//输出元素

Console.Read();

}

//输出元素

private static void PrintStack(Stack<string> s)

{

IEnumerable<string> list = s.Where(t => true);

foreach (string t in list)

{

Console.WriteLine(t);

}

}

}

(4)链表(LinkedList<T>)

LinkedList<T>是一个双向链表。链表的优点是，如果将元素插入列表的中间位置，使用链表就会非常快，只需要修改下一个元素的Next引用与上一个元素的Previous引用。链表不能在集合中只存储元素，必须要把元素存到LinkedListNode<T>类型的对象中，LinkedListNode<T>定义了属性：List、Next、Value、Previous。List属性返回与该节点相关的LinkedList<T>对象，Next、Previous用于遍历链表。

LinkedList<T>对象可以访问第一个和最后一个元素(Frist与Last)、在指定位置插入元素(AddAfter()、AddBefore()、AddFirst()、AddLast()方法)，删除指定位置的元素(ReMove()、ReMoveFirst()、RemoveLast()方法)，从链表的开头(Find())或结尾(FindLast())开始搜索元素。

程序示例如：

class Program

{

static void Main(string[] args)

{

LinkedList<int> link = new LinkedList<int>();

LinkedListNode<int> node;

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

{

node = new LinkedListNode<int>(i);

if (i % 2 == 0)

{

link.AddFirst(node);//从头部添加节点

}

else

{

link.AddLast(node);//从尾部添加节点

}

}

PrintLink(link);//输出元素

Console.Read();

}

//输出元素

private static void PrintLink(LinkedList<int> l)

{

IEnumerable<int> list = l.Where(t => true);

foreach (int t in list)

{

Console.WriteLine(t);

}

}

}

(5)有序列表(SortedList<K,V>)

SortedList<K,V>是基于键对集合进行排序的集合类，它只允许每个键只有一个对应值，如果需要每个键对应多个值可以使用Lookup<K,V>。可以使用foreach遍历该集合，枚举器返回的是KeyValuePair<K,V>类型的元素。除了使用Add方法添加元素，还可以使用索引器添加。例如：

class Program

{

static void Main(string[] args)

{

SortedList<string, string> sort = new SortedList<string, string>();

sort.Add("K1", "V1");//Add方法添加元素

sort["K2"] = "V2";//索引器添加元素

PrintSorted(sort);//输出元素

Console.WriteLine("是否存在[K3]：" + sort.ContainsKey("K3"));

string value = null;

Console.WriteLine("是否存在[K2]：" + sort.TryGetValue("K2", out value));

Console.WriteLine("[K2]的值：" + value);

Console.Read();

}

//输出元素

private static void PrintSorted(SortedList<string, string> s)

{

IEnumerable<KeyValuePair<string, string>> list = s.Where(t => true);

foreach (KeyValuePair<string, string> t in list)

{

Console.WriteLine(t.Key + " ---> " + t.Value);

}

}

}

(6)字典

字典中键的类型必须重写Object类的GetHashCode()方法。只要字典类需要确定元素的位置，他就会调用GetHashCode()方法。除了实现GetHashCode()方法外，键类型还必须实现IEquatable<T>.Equals()方法，或重写Object类的Equals()方法。

因为不同的对象可能返回相同的散列码(GetHashCode方法返回值)，但是如果A.Equals(B)返回true，则A和B的散列码就必须相同。这似乎有点奇怪，但这非常重要，因为字典的性能取决于GetHashCode()方法实现的代码。

1、Dictionary<K,V>

Dictionary<K,V>类支持每个键关联一个值，与SortedList<K,V>很类似。

2、Lookup<K,V>

Lookup<K,V>类把键映射到一个值集上。创建Lookup<K,V>类对象必须调用ToLookup()扩展方法，该方法返回一个Lookup<K,V>对象。ToLookup()方法需要一个Func<T,K>类型的委托参数，Func<T,K>类型定义了键的选择器。

ToLookup()是一个奇妙的函数，用于对一个集合进行操作，创建一个1：n 的映射。 它可以方便的将数据分类成组，并生成一个字典供查询使用。例如：

class Program

{

static void Main(string[] args)

{

List<string> list = new List<string>() { "1","12","123","1234","a","ab","abc"};

var lookup=list.ToLookup(x => x.Length);//根据元素的长度分组

foreach (var t in lookup)

{

List<string> temp=t.ToList<string>();//把一组数据转换成集合

temp.ForEach(x=>Console.Write(x+"、"));//输出集合

Console.WriteLine();

}

Console.Read();

}

}

3、SortedDictionary<K,V>

SortedDictionary<K,V>类是一个二叉搜索树，其中的元素根据键来排序，该键类型必须实现IComparable<T>接口。

SortedDictionary<K,V>与SortedList<K,V>的区别：

SortedList<K,V>类使用的内存比SortedDictionary<K,V>少。

SortedDictionary<K,V>类的元素的插入与删除比较快。

在用于已排好序的集合，若不需要修改容量SortedList<K,V>会比较快。

区别的根本原因：SortedList<K,V>实现的是一个基于数组的集合，SortedDictionary<K,V>实现的是一个基于字典的集合。

(7)集(ISet<T>接口)

不包含重复元素的集合称为集，.NET Framework包含两个集(HashSet<T>和SortedSet<T>),它们都实现ISet<T>接口。HashSet<T>是不包含重复元素的无序列表，SortedSet<T>是不包含重复元素的有序列表。

4.可观察的集合(深入)

(1)ObservableCollection<T>类简介

ObservableCollection<T>类是为WPF定义的，这样UI就可以得知集合的变化，因为只要修改了ObservableCollection<T>类对象集合中的元素，它就会产生CollectionChanged事件。

(2)使用示例

class Program

{

static void Main(string[] args)

{

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

list.CollectionChanged += ListCollectionChanged;//添加事件方法

list.Add(10);//产生事件

list.Add(20);//产生事件

list.Remove(10);//产生事件

Console.Read();

}

//事件方法

private static void ListCollectionChanged(object sender,

NotifyCollectionChangedEventArgs e)

{

Console.WriteLine("本次修改的方式：" + e.Action.ToString());

if (e.OldItems != null)

{

Console.WriteLine("本次修改的位置：" + e.OldStartingIndex);

Console.WriteLine("本次修改的元素个数：" + e.OldItems.Count);

}

if (e.NewItems != null)

{

Console.WriteLine("本次修改的位置：" + e.NewStartingIndex);

Console.WriteLine("本次修改的元素个数：" + e.NewItems.Count);

}

Console.WriteLine();

}

}

5.位数组(深入)

(1)BitArray、BitVector32介绍

如果需要处理的数字有许多位，就可以使用BitArray类与BitVector32结构。它们的区别是：BitArray类可以重新设置大小，它可以包含很多位；BitVector32结构是基于栈的，因此比较快，但它只能包含32为，它们存在一个整数中。

(2)BitArray

BitArray类是一个引用类型，它包含一个int数组，其中32位使用一个新整数，其成员如下：

Count、Length	Count、Length可得到数组的位数，Length可设置其数组的大小
Get、Set	使用Get、Set可访问数组中的位
SetAll	SetAll()方法设置所有的位值
Not	Not()方法对数组中所有的位求反
And、Or、Xor	And()是与操作，Or()是或操作，Xor()是异或操作

程序示例：

class Program

{

static void Main(string[] args)

{

BitArray barray = new BitArray(20);

barray.SetAll(true);//对所有位赋值

PrintBitArray(barray);//输出

barray.Set(1, false);

barray[2] = false;

PrintBitArray(barray);//输出

Console.Read();

}

//输出函数

private static void PrintBitArray(BitArray b)

{

foreach (bool bit in b)

{

Console.Write(bit ? 1 : 0);

}

Console.WriteLine();

}

}

(3)BitVector32

BitVector32结构的效率更高，因为它是值类型！它常用成员如下：

Data	Data属性把BitVector32结构返回成一个整数
索引器	访问BitVector32结构的值可以使用索引器
CreateMask	这是一个静态方法，为访问BitVector32结构中特定的类创建掩码
CreateSection	这是一个静态方法，用于创建32位中的几个片段

程序示例：

class Program

{

static void Main(string[] args)

{

BitVector32 b32 = new BitVector32();

PrintBitVector32(b32);//输出位

int bit = BitVector32.CreateMask();

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

{

b32[bit] = true;

Console.WriteLine(bit);

PrintBitVector32(b32);//输出位

b32[bit] = false;

bit = BitVector32.CreateMask(bit);

}

Console.WriteLine(b32.Data);//输出数

Console.Read();

}

//输出函数

private static void PrintBitVector32(BitVector32 b32)

{

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

{

Console.Write(b32[i] ? 1 : 0);

}

Console.WriteLine();

}

}

6.并发集合(.NET 4新增)

(1)ConcurrentQueue<T>

这个集合类用一种免锁定的算法实现，访问队列元素的方法有：TryDequeue、TryPeek和Enqueue。

(2)ConcurrentStack<T>

这个集合类定义了：Push()、PushRange、TryPeek、TryPop、TryPopRange方法。

(3)ConcurrentBag<T>

ConcurrentBag<T>表示对象的线程安全的无序集合。对于同一个线程值的添加和删除是非常快的，因为ConcurrentBag内部将数据按线程的标识而独立存储，所以一个线程从自己的数据中移除一个数据是非常快的，当然如果这个线程中没有数据，那么只能从其他线程中移除数据，此时会发生一些性能损耗从而确保线程安全！

(4)ConcurrentDictionary<K, V>

这是一个线程安全的键值集合，TyrAdd、TryGetValue、TryRemove、TryUpdate方法以非阻塞的方式访问元素。

(5)BlockingCollection<T>

这个集合在可以添加或提取元素元素之前，会阻塞线程并一直等待。可以使用Add、Take方法用来添加和删除元素，这些方法会阻塞当前线程，一直等到任务可以执行为止。

7.不同集合类的性能

集合	Add	Insert	Remove	Item	Sort	Find
List	O(1)或O(n)	O(n)	O(n)	O(1)	O(n log n)-O(n^2)
Stack	O(1)或O(n)	n/a	O(1)	n/a	n/a	n/a
Queue	O(1)或O(n)	n/a	O(1)	n/a	n/a	n/a
HashSet	O(1)或O(n)	O(1)或O(n)	O(1)	n/a	n/a	n/a
SortedSet	O(1)或O(n)	O(1)或O(n)	O(1)	n/a	n/a	n/a
LinkedList	O(1)	O(1)	O(1)	n/a	n/a	O(n)
Dictionary	O(1)或O(n)	n/a	O(1)	O(1)	n/a	n/a
SortedDictionary	O(log n)	n/a	O(log n)	O(log n)	n/a	n/a
SortedList	O(n)或O(log n)	n/a	O(n)	O(n)或O(log n)	n/a	n/a