澳门新葡新京之不可变数据类型,高级编程9

阅读目录:

集合

 


 

1.集合接口和类型

接口

说明

IEnumerable<T>

如果foreach语句用于集合,就需要IEnumerable接口.这个借口定义了方法GetEnumerator(),他返回一个实现了IEnumerator接口的枚举

ICollection<T>

ICollection<T>接口有泛型集合类实现.使用这个借口可以获得集合中的元素个数(Count属性),把集合复制到数组中(CopyTo()方法),还可以从集合中添加和删除元素(Add(),Remove(),Clear())

List<T>

IList<T>接口用于可通过位置访问其中的元素列表,这个接口定义了一个 索引器,可以在集合的指定位置插入或删除 mount些项(Insert()和Remove()方法).IList<T>接口派生自ICollection<T>接口

ISet<T>

ISet<T>接口是.NET4中新增的.实现这个接口的集允许合并不同的集.获得两个集的交集,检查两个集合是否重叠.ISet<T>接口派生自ICollection<T>接口

IDictionary<TKey,TValue>

IDictionary<TKey,TValue>接口由包含键和值的泛型集合类 实现.使用这个接口可以访问所有的键和值,使用键类型的索引器可以访问某些项,还可以添加或删除某些项

ILookup<TKey,TValue>

ILookup<TKey,TValue>接口类似于IDictionary<TKey,TValue>接口,实现该接口的集合有键和值,且可以通过一个键包含多个值

IComparer<T>

接口ICommparer<T>由比较器实现,通过Comparer()方法给集合中的元素排序

IEqualityComparer<T>

接口IEqualityComparer<T>由一个比较器实现,该比较器可用于字典中的键.使用这个接口,可以对对象进行相等性比较.在.NET中,这个接口也由数组和元组实现

IProducerConsumerColllection<T>

IProducerConsumerCollection<T>接口是.NET4中新增的,它支持新的线程安全的集合类

IReadOnlyList<T>、

IReadOnlyDictionary<T>、

IReadOnlyCollection<T>

初始化后不能修改的集合,只能检索对象,不能添加和删除.

 

2.列表

先看看一个实例:

澳门新葡新京 1澳门新葡新京 2

[Serializable]
  public class Racer : IComparable<Racer>, IFormattable
  {
    public int Id { get; private set; }
    public string FirstName { get; set; }
    public string LastName { get; set; }
    public string Country { get; set; }
    public int Wins { get; set; }

    public Racer(int id, string firstName, string lastName, string country)
      : this(id, firstName, lastName, country, wins: 0)
    {
    }
    public Racer(int id, string firstName, string lastName, string country, int wins)
    {
      this.Id = id;
      this.FirstName = firstName;
      this.LastName = lastName;
      this.Country = country;
      this.Wins = wins;
    }

    public override string ToString()
    {
      return String.Format("{0} {1}", FirstName, LastName);
    }

    public string ToString(string format, IFormatProvider formatProvider)
    {
      if (format == null) format = "N";
      switch (format.ToUpper())
      {
        case null:
        case "N": // name
          return ToString();
        case "F": // first name
          return FirstName;
        case "L": // last name
          return LastName;
        case "W": // Wins
          return String.Format("{0}, Wins: {1}", ToString(), Wins);
        case "C": // Country
          return String.Format("{0}, Country: {1}", ToString(), Country);
        case "A": // All
          return String.Format("{0}, {1} Wins: {2}", ToString(), Country, Wins);
        default:
          throw new FormatException(String.Format(formatProvider,
                "Format {0} is not supported", format));
      }
    }

    public string ToString(string format)
    {
      return ToString(format, null);
    }

    public int CompareTo(Racer other)
    {
      if (other == null) return -1;
      int compare = string.Compare(this.LastName, other.LastName);
      if (compare == 0)
        return string.Compare(this.FirstName, other.FirstName);
      return compare;
    }
  }

View Code

  1. 不可变对象
  2. 自定义不可变集合
  3. Net提供的不可变集合
  4. 不可变优点
  5. 不可变对象缺点
创建列表

使用默认的构造函数创建一个空列表,元素添加到列表后,列表容量会扩大到可接纳4个元素。
如果添加了第5个元素,列表大小会重新设置为8个元素。每次都会将列表的容量重新设置为原来的2倍.

var intList=new List<int>();

 

如果列表的容量变了,整个集合就要重新分配到新的内存块中,我们可以在初始化时设置它的容量:

List<int> intList=new List<int>(10);

如果列表的个数超过10个,可以设置容量Capacity:

intList.Capacity = 20;

如果列表的元素已经添加完了,列表会存在多余的容量空间。可以使用TrimExcess方法去除不要的容量:

intList.TrimExcess();

a.集合初始值设定项

使用初始化构造器初始化设定项

int[] arr = { 1, 2, 3 };
var intList = new List<int>(arr) ;

括号中初始化

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

 

b.添加元素

intList.Add(5);

添加数组

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

c.插入元素

intList.Insert(3, 4);

d.访问元素

使用索引获取:

var value = intList[3];

循环遍历:

foreach (var item in intList)
{
     var res = item;
}

forEach方法:

class List<T> : IList<T>
{
    private T[] items;
    public void forEach(Action<T> action)
    {
        if (action == null) throw new ArgumentNullException("action");
        foreach (var item in items)
        {
            action(item);
        }
    }
}

然后我们可以这样调用:

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

e.删除元素

按索引删除,比较快

intList.RemoveAt(3);

按元素值删除

intList.Remove(4);

f.搜索

在集合中搜索元素。可以查找索引和元素。

FindIndex通过匹配元素值,获得索引:

intList.FindIndex(m => m==4);

FindIndex方法参数Predicate<T>传入匹配的表达式,返回匹配的元素索引值,Predicate<T>委托表示定义一组条件并确定指定对象是否符合这些条件的方法

intList.Find(m => m == 4);
intList.FindAll(m => m > 2);

Find返回了匹配条件的元素值,FindAll返回了匹配条件的所有元素

g.排序

列表使用Sort方法进行元素排序

intList.Sort();

intList.Sort((m, n) => m);

Sort(Comparison<T>
comparison)方法参数中的委托Comparison含有2个参数,方法将这2个元素进行比较,然后返回绝对值,如果返回-1的,元素需要排前面,返回1的元素需要排后面.

Sort(IComparer<T>
comparer)方法参数中是一个比较接口,接口实现Comparer方法

澳门新葡新京 3澳门新葡新京 4

public enum CompareType
  {
    FirstName,
    LastName,
    Country,
    Wins
  }

  public class RacerComparer : IComparer<Racer>
  {
    private CompareType compareType;
    public RacerComparer(CompareType compareType)
    {
      this.compareType = compareType;
    }

    public int Compare(Racer x, Racer y)
    {
      if (x == null && y == null) return 0;
      if (x == null) return -1;
      if (y == null) return 1;

      int result;
      switch (compareType)
      {
        case CompareType.FirstName:
          return string.Compare(x.FirstName, y.FirstName);
        case CompareType.LastName:
          return string.Compare(x.LastName, y.LastName);
        case CompareType.Country:
          result = string.Compare(x.Country, y.Country);
          if (result == 0)
            return string.Compare(x.LastName, y.LastName);
          else
            return result;
        case CompareType.Wins:
          return x.Wins.CompareTo(y.Wins);
        default:
          throw new ArgumentException("Invalid Compare Type");
      }
    }
  }

View Code

 

h.类型转换

 Converter委托

public delegate TOutput Converter<in TInput, out TOutput>(TInput input);

ConvertAll可以将一种类型的集合转换为另一种类型的集合。

intList.ConvertAll(m => m.ToString());

不可变对象

不可变(immutable):
即对象一旦被创建初始化后,它们的值就不能被改变,之后的每次改变都会产生一个新对象。

var str="mushroomsir";
str.Substring(0, 6)

c#中的string是不可变的,Substring(0,
6)返回的是一个新字符串值,而原字符串在共享域中是不变的。另外一个StringBuilder是可变的,这也是推荐使用StringBuilder的原因。

var age=18; 

当存储值18的内存分配给age变量时,它的内存值也是不可以被修改的。

age=2;

此时会在栈中开辟新值2赋值给age变量,而不能改变18这个内存里的值,int在c#中也是不可变的。

class Contact
{ 
    public string Name { get;  set; }
    public string Address { get;  set; }
    public Contact(string contactName, string contactAddress)
    {
        Name = contactName;
        Address = contactAddress;               
    }
}
   var mutable = new Contact("二毛", "清华");
   mutable.Name = "大毛";
   mutable.Address = "北大";

我们实例化MutableContact赋值给mutable,随后我们可以修改MutableContact对象内部字段值,它已经不是初始后的值,可称为可变(mutable)对象。

可变对象在多线程并发中共享,是存在一些问题的。多线程下A线程赋值到 Name =
“大毛” 这一步,其他的线程有可能读取到的数据就是:

  mutable.Name == "大毛";
  mutable.Address == "清华";

很明显这样数据完整性就不能保障,也有称数据撕裂。我们把可变对象更改为不可变对象如下:

public class Contact2
{
    public string Name { get; private set; }
    public string Address { get; private set; }
    private Contact2(string contactName, string contactAddress)
    {
        Name = contactName;
        Address = contactAddress;               
    }
    public static Contact2 CreateContact(string name, string address)
    {
        return new Contact2(name, address);
    }
}

使用时只能通过Contact2的构造函数来初始化Name和Address字段。Contact2此时即为不可变对象,因为对象本身是个不可变整体。通过使用不可变对象可以不用担心数据完整性,也能保证数据安全性,不会被其他线程修改。

只读集合

创建集合后,它们是只读的。

3.队列

代表了一个先进先出的对象集合。当您需要对各项进行先进先出的访问时,则使用队列。当您在列表中添加一项,称为入队,当您从列表中移除一项时,称为出队

添加队列元素时加上lock,因为多线程可以同时访问,所以对队列进行锁定访问。

澳门新葡新京 5

 

澳门新葡新京 6澳门新葡新京 7

using System;
using System.Collections;

namespace CollectionsApplication
{
   class Program
   {
      static void Main(string[] args)
      {
         Queue q = new Queue();

         q.Enqueue('A');
         q.Enqueue('M');
         q.Enqueue('G');
         q.Enqueue('W');

         Console.WriteLine("Current queue: ");
         foreach (char c in q)
            Console.Write(c + " ");
         Console.WriteLine();
         q.Enqueue('V');
         q.Enqueue('H');
         Console.WriteLine("Current queue: ");         
         foreach (char c in q)
            Console.Write(c + " ");
         Console.WriteLine();
         Console.WriteLine("Removing some values ");
         char ch = (char)q.Dequeue();
         Console.WriteLine("The removed value: {0}", ch);
         ch = (char)q.Dequeue();
         Console.WriteLine("The removed value: {0}", ch);
         Console.ReadKey();
      }
   }
}

View Code

当上面的代码被编译和执行时,它会产生下列结果:

Current queue: 
A M G W 
Current queue: 
A M G W V H 
Removing values
The removed value: A
The removed value: M

澳门新葡新京 8澳门新葡新京 9

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));
            }

        }
    }

Program

澳门新葡新京 10澳门新葡新京 11

public class ProcessDocuments
  {
    public static void Start(DocumentManager dm)
    {
      Task.Factory.StartNew(new ProcessDocuments(dm).Run);
    }

    protected ProcessDocuments(DocumentManager dm)
    {
      if (dm == null)
        throw new ArgumentNullException("dm");
      documentManager = dm;
    }

    private DocumentManager documentManager;

    protected void Run()
    {
      while (true)
      {
        if (documentManager.IsDocumentAvailable)
        {
          Document doc = documentManager.GetDocument();
          Console.WriteLine("Processing document {0}", doc.Title);
        }
        Thread.Sleep(new Random().Next(20));
      }
    }
  }

ProcessDocuments

澳门新葡新京 12澳门新葡新京 13

public class DocumentManager
  {
    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;
      }
    }
  }

DocumentManager

澳门新葡新京 14澳门新葡新京 15

public class Document
  {
    public string Title { get; private set; }
    public string Content { get; private set; }

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

Document

4.栈

代表了一个后进先出的对象集合。当您需要对各项进行后进先出的访问时,则使用堆栈。当您在列表中添加一项,称为推入元素,当您从列表中移除一项时,称为弹出元素。

澳门新葡新京 16

澳门新葡新京 17澳门新葡新京 18

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.WriteLine();

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


        }
    }

Program

First iteration: CBA
Second iteration: CBA

5.链表

LinkedList<T>是一个双向链表,其元素指向它前面和后面的元素,这样通过移动下一个元素就可以正向遍历整个链表。通过移动到前一个元素可以反向遍历这个链表

链表的优点是,如果将元素插入列表的中间位置,使用链表会很快,在插入一个元素时,只需要修改上一个元素的Next引用和下一个元素的Previous引用,使他们引用所插入的元素。

澳门新葡新京 19澳门新葡新京 20

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)
    {
      this.Title = title;
      this.Content = content;
      this.Priority = priority;
    }
  }

Document

澳门新葡新京 21澳门新葡新京 22

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>>(10);
      for (int i = 0; i < 10; 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 >= 0)
        {
          // 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

澳门新葡新京 23澳门新葡新京 24

 class Program
  {
    static void Main()
    {
        PriorityDocumentManager pdm = new PriorityDocumentManager();
        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();

    }
  }

Program

 

6.有序列表

SortedList基于键对集合进行排序.

class Program
  {
    static void Main()
    {
      var books = new SortedList<string, string>();
      books.Add("sty", "");
      books.Add("abc", "");
      books.Add("123", "");
      foreach (var item in books.Keys)
      {
          Console.WriteLine(item);
      }

    }
  }

123
abc
sty

 

7.字典

字典:用于在名称/值对中存储信息,字典的名称即键不能重复.

澳门新葡新京 25

HashTable和Dictionary

1.HashTable大数据量插入数据时需要花费比Dictionary大的多的时间。

2.for方式遍历HashTable和Dictionary速度最快。

3.在foreach方式遍历时Dictionary遍历速度更快。

4.HashTable在取值时需要进行类型转换,Dictionary不用做类型转换。

在单线程的时候使用Dictionary更好一些,多线程的时候使用HashTable更好。

 

有序字典SortedList和SortedDictionary

SortedDictionary 泛型类是检索运算复杂度为 O(log n) 的二叉搜索树,其中 n 是字典中的元素数。就这一点而言,它与 SortedList 泛型类相似。这两个类具有相似的对象模型,并且都具有
O(log n)
的检索运算复杂度。这两个类的区别在于内存的使用以及插入和移除元素的速度:

  • SortedList 使用的内存比 SortedDictionary 少。

  • SortedDictionary 可对未排序的数据执行更快的插入和移除操作:它的时间复杂度为
    O(log n),而SortedList 为 O(n)。

  • 如果使用排序数据一次性填充列表,则 SortedList 比 SortedDictionary 快。

8.集

包含不重复元素的集合,叫“集”。.NET包含2个集。HashSet<T>和SortedSet<T>,它们继承ISet;SortedSet是一个有序集.

ISet提供了Add方法,如果HashSet中存在这个元素,再次使用Add方法不会抛出异常,返回bool值是否添加

var companyTeams = new HashSet<string>() { "Ferrari", "McLaren", "Mercedes" };
var traditionalTeams = new HashSet<string>() { "Ferrari", "McLaren" };
var privateTeams = new HashSet<string>() { "Red Bull", "Lotus", "Toro Rosso", "Force India", "Sauber" };

if (privateTeams.Add("Williams"))
    Console.WriteLine("Williams added");
if (!companyTeams.Add("McLaren"))
    Console.WriteLine("McLaren was already in this set");

IsSubsetOf方法判断了traditionalTeams集合是否companyTeams的子集
IsSupersetOf方法判断了companyTeams集合是否traditionalTeams的超集(包含它拥有的所有元素,并且多余它的元素)

var companyTeams = new HashSet<string>() { "Ferrari", "McLaren", "Mercedes" };
var traditionalTeams = new HashSet<string>() { "Ferrari", "McLaren" };
var privateTeams = new HashSet<string>() { "Red Bull", "Lotus", "Toro Rosso", "Force India", "Sauber" };

if (traditionalTeams.IsSubsetOf(companyTeams))
{
  Console.WriteLine("traditionalTeams is subset of companyTeams");
}

if (companyTeams.IsSupersetOf(traditionalTeams))
{
   Console.WriteLine("companyTeams is a superset of traditionalTeams");
}

SortedSet的UnionWith方法可以修改这个集合,并且包含传入的集合

var allTeams = new SortedSet<string>(companyTeams);
allTeams.UnionWith(privateTeams);
allTeams.UnionWith(traditionalTeams);

 

9.可视察的集合

如果需要记录集合何时添加和删除元素的信息,可以使用ObservableCollection<T>,这个本身是为WPF定制的。

ObservableCollection<T>类用于创建自定义集合,在内部使用List<T>类,重写虚方法RemoveItem和SetItem()方法触发CollectionChanged事件。

澳门新葡新京 26澳门新葡新京 27

class Program
  {
    static void Main()
    {
      var data = new ObservableCollection<string>();
      data.CollectionChanged += Data_CollectionChanged;
      data.Add("One");
      data.Add("Two");
      data.Insert(1, "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);
        }
      }


      Console.WriteLine();

    }
  }

View Code

Data_CollectionChanged方法接收了NotifyCollectionChangedEventArgs,包含了集合的变化信息,Action属性给出了是否添加或删除一项的信息,对于删除的项,会设置OldItems属性,列出删除的项

对于添加的项,会设置NewItems属性,列出添加的项。

action: Add
starting index for new item(s): 0
new item(s):
One

action: Add
starting index for new item(s): 1
new item(s):
Two

action: Add
starting index for new item(s): 1
new item(s):
Three

action: Remove
starting index for old item(s): 0
old item(s):
One

 

10.位数组

自定义不可变集合

我们去枚举可变集合时,出于线程安全的考虑我们往往需要进行加锁处理,防止该集合在其他线程被修改,而使用不可变集合则能避免这个问题。我们平常使用的数据结构都是采用可变模式来实现的,那怎么实现一个不可变数据结构呢!以栈来示例,具体代码如下:

澳门新葡新京 28澳门新葡新京 29

public interface IStack<T> : IEnumerable<T>
{
    IStack<T> Push(T value);
    IStack<T> Pop();
    T Peek();
    bool IsEmpty { get; }
}
public sealed class Stack<T> : IStack<T>
{
    private sealed class EmptyStack : IStack<T>
    {
        public bool IsEmpty { get { return true; } }
        public T Peek() { throw new Exception("Empty stack"); }
        public IStack<T> Push(T value) { return new Stack<T>(value, this); }
        public IStack<T> Pop() { throw new Exception("Empty stack"); }
        public IEnumerator<T> GetEnumerator() { yield break; }
        IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
    }
    private static readonly EmptyStack empty = new EmptyStack();
    public static IStack<T> Empty { get { return empty; } }
    private readonly T head;
    private readonly IStack<T> tail;
    private Stack(T head, IStack<T> tail)
    {
        this.head = head;
        this.tail = tail;
    }
    public bool IsEmpty { get { return false; } }
    public T Peek() { return head; }
    public IStack<T> Pop() { return tail; }
    public IStack<T> Push(T value) { return new Stack<T>(value, this); }
    public IEnumerator<T> GetEnumerator()
    {
        for (IStack<T> stack = this; !stack.IsEmpty; stack = stack.Pop())
            yield return stack.Peek();
    }
    IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}

View Code

  • 入栈时会实例化一个新栈对象
  • 将新值通过构造函数传入,并存放在新对象Head位置,旧栈对象放在在Tail位置引用
  • 出栈时返回当前栈对象的Tail引用的栈对象

使用方法如下:

IStack<int> s1 = Stack<int>.Empty;
IStack<int> s2 = s1.Push(10);
IStack<int> s3 = s2.Push(20);
IStack<int> s4 = s3.Push(30);
IStack<int> v3 = s4.Pop();
foreach (var item in s4)
{
//dosomething
}

每次Push都是一个新对象,旧对象不可修改,这样在枚举集合就不需要担心其他线程修改了。

BitArray类的方法和属性

下表列出了一些BitArray类的常用属性:

属性 描述
Count 获取包含在BitArray元素的数量
IsReadOnly 获取一个值,指示BitArray是否是只读
Item 获取或设置在所述BitArray的特定位置的比特的值
Length 获取或设置在BitArray元素的数量

下表列出了一些BitArray类的常用方法:

 

S.N 方法名称及用途
1 public BitArray And( BitArray value ); 
执行对指定BitArray的相应元素在当前BitArray元素的按位与运算
2 public bool Get( int index ); 
获取在所述BitArray的特定位置的比特的值
3 public BitArray Not();
反转当前BitArray所有的位值,使设置为true的元素被更改为false,并设置为false元素更改为true
4 public BitArray Or( BitArray value ); 
在执行对指定BitArray的相应元素在当前BitArray的元素的按位或操作
5 public void Set( int index, bool value ); 
设置在所述BitArray为指定值的特定位置的比特值
6 public void SetAll( bool value ); 
设置在BitArray所有位设置为指定值
7 public BitArray Xor( BitArray value ); 
执行关于对在指定BitArray的相应元素中的当前BitArray的元素按位异或运算

当需要存储位,但不知道事先比特数就使用它。您可以通过使用一个整数索引,它从零开始访问BitArray集合中的项。

澳门新葡新京 30澳门新葡新京 31

using System;
using System.Collections;

namespace CollectionsApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            //creating two  bit arrays of size 8
            BitArray ba1 = new BitArray(8);
            BitArray ba2 = new BitArray(8);
            byte[] a = { 60 };
            byte[] b = { 13 };

            //storing the values 60, and 13 into the bit arrays
            ba1 = new BitArray(a);
            ba2 = new BitArray(b);

            //content of ba1
            Console.WriteLine("Bit array ba1: 60");
            for (int i = 0; i < ba1.Count; i++)
            {
                Console.Write("{0, -6} ", ba1[i]);
            }
            Console.WriteLine();

            //content of ba2
            Console.WriteLine("Bit array ba2: 13");
            for (int i = 0; i < ba2.Count; i++)
            {
                Console.Write("{0, -6} ", ba2[i]);
            }
            Console.WriteLine();


            BitArray ba3 = new BitArray(8);
            ba3 = ba1.And(ba2);

            //content of ba3
            Console.WriteLine("Bit array ba3 after AND operation: 12");
            for (int i = 0; i < ba3.Count; i++)
            {
                Console.Write("{0, -6} ", ba3[i]);
            }
            Console.WriteLine();

            ba3 = ba1.Or(ba2);
            //content of ba3
            Console.WriteLine("Bit array ba3 after OR operation: 61");
            for (int i = 0; i < ba3.Count; i++)
            {
                Console.Write("{0, -6} ", ba3[i]);
            }
            Console.WriteLine();

            Console.ReadKey();
        }
    }
}

View Code

让我们编译和运行上面的程序,这将产生以下结果:

Bit array ba1: 60 
False False True True True True False False 
Bit array ba2: 13
True False True True False False False False 
Bit array ba3 after AND operation: 12
False False True True False False False False 
Bit array ba3 after OR operation: 61
True False True True False False False False 

Net提供的不可变集合

不可变队列,不可变列表等数据结构如果都自己实现工作量确实有点大。幸好的是Net在4.5版本已经提供了不可变集合的基础类库。
使用Nuget安装:

Install-Package Microsoft.Bcl.Immutable

使用如下,和上面我们自定义的几乎一样:

        ImmutableStack<int> a1 = ImmutableStack<int>.Empty;
        ImmutableStack<int> a2 = a1.Push(10);
        ImmutableStack<int> a3 = a2.Push(20);
        ImmutableStack<int> a4 = a3.Push(30);
        ImmutableStack<int> iv3 = a4.Pop(); 

使用Net不可变列表集合有一点要注意的是,当我们Push值时要重新赋值给原变量才正确,因为push后会生成一个新对象,原a1只是旧值:

   ImmutableStack<int> a1 = ImmutableStack<int>.Empty;
   a1.Push(10); //不正确,a1仍是空值值,push会生成新的栈。
   a1 = a1.Push(10); //需要将新栈重新赋值给a1

NET提供的常用数据结构

  • ImmutableStack
  • ImmutableQueue
  • ImmutableList
  • ImmutableHashSet
  • ImmutableSortedSet
  • ImmutableDictionary<K, V>
  • ImmutableSortedDictionary<K, V>

不可变集合和可变集合在算法复杂度上的不同:

澳门新葡新京 32

BitVector32

提供了一个简单结构,该结构以32位内存存储布尔和小数值

对于内部使用的布尔值和小整数,BitVector32 比 BitArray 更有效。 BitArray 可以按需要无限地扩大,但它有内存和性能方面的系统开销,这是类实例所要求的。 相比之下,BitVector32 只使用 32
位。

BitVector32 结构可以设置成包含小整数的若干节或包含布尔值的若干位标志,但不能同时包含两者。BitVector32.Section 是 BitVector32 中的窗口,且由最小数量的连续位构成,连续位可以包含 CreateSection 中指定的最大值。 例如,带有最大值 1 的节只由一个位构成,而带有最大值 5
的节由三个位构成。 可以创建带有最大值 1 的 BitVector32.Section 作为布尔值,从而使您能够在同一 BitVector32 中存储整数和布尔值。

BitVector32 既可以设置为节,也可以设置为位标志,分别有成员可以应用于这两种情形。 例如,BitVector32.Item 属性是作为节设置的 BitVector32 的索引器,而 BitVector32.Item 属性是作为位标志设置的BitVector32 的索引器。 CreateMask 创建一系列屏蔽,这些屏蔽可用于访问作为位标志设置的 BitVector32 中的单个位。

在作为节设置的 BitVector32 上使用屏蔽可能会导致意外的结果。

澳门新葡新京 33澳门新葡新京 34

using System;
using System.Collections.Specialized;


public class SamplesBitVector32  {

   public static void Main()  {

      // Creates and initializes a BitVector32 with all bit flags set to FALSE.
      BitVector32 myBV = new BitVector32( 0 );

      // Creates masks to isolate each of the first five bit flags.
      int myBit1 = BitVector32.CreateMask();
      int myBit2 = BitVector32.CreateMask( myBit1 );
      int myBit3 = BitVector32.CreateMask( myBit2 );
      int myBit4 = BitVector32.CreateMask( myBit3 );
      int myBit5 = BitVector32.CreateMask( myBit4 );

      // Sets the alternating bits to TRUE.
      Console.WriteLine( "Setting alternating bits to TRUE:" );
      Console.WriteLine( "   Initial:         {0}", myBV.ToString() );
      myBV[myBit1] = true;
      Console.WriteLine( "   myBit1 = TRUE:   {0}", myBV.ToString() );
      myBV[myBit3] = true;
      Console.WriteLine( "   myBit3 = TRUE:   {0}", myBV.ToString() );
      myBV[myBit5] = true;
      Console.WriteLine( "   myBit5 = TRUE:   {0}", myBV.ToString() );

   }

}

/*
This code produces the following output.

Setting alternating bits to TRUE:
   Initial:         BitVector32{00000000000000000000000000000000}
   myBit1 = TRUE:   BitVector32{00000000000000000000000000000001}
   myBit3 = TRUE:   BitVector32{00000000000000000000000000000101}
   myBit5 = TRUE:   BitVector32{00000000000000000000000000010101}


*/
BitVector用作节集合

using System;
using System.Collections.Specialized;


public class SamplesBitVector32  {

   public static void Main()  {

      // Creates and initializes a BitVector32.
      BitVector32 myBV = new BitVector32( 0 );

      // Creates four sections in the BitVector32 with maximum values 6, 3, 1, and 15.
      // mySect3, which uses exactly one bit, can also be used as a bit flag.
      BitVector32.Section mySect1 = BitVector32.CreateSection( 6 );
      BitVector32.Section mySect2 = BitVector32.CreateSection( 3, mySect1 );
      BitVector32.Section mySect3 = BitVector32.CreateSection( 1, mySect2 );
      BitVector32.Section mySect4 = BitVector32.CreateSection( 15, mySect3 );

      // Displays the values of the sections.
      Console.WriteLine( "Initial values:" );
      Console.WriteLine( "\tmySect1: {0}", myBV[mySect1] );
      Console.WriteLine( "\tmySect2: {0}", myBV[mySect2] );
      Console.WriteLine( "\tmySect3: {0}", myBV[mySect3] );
      Console.WriteLine( "\tmySect4: {0}", myBV[mySect4] );

      // Sets each section to a new value and displays the value of the BitVector32 at each step.
      Console.WriteLine( "Changing the values of each section:" );
      Console.WriteLine( "\tInitial:    \t{0}", myBV.ToString() );
      myBV[mySect1] = 5;
      Console.WriteLine( "\tmySect1 = 5:\t{0}", myBV.ToString() );
      myBV[mySect2] = 3;
      Console.WriteLine( "\tmySect2 = 3:\t{0}", myBV.ToString() );
      myBV[mySect3] = 1;
      Console.WriteLine( "\tmySect3 = 1:\t{0}", myBV.ToString() );
      myBV[mySect4] = 9;
      Console.WriteLine( "\tmySect4 = 9:\t{0}", myBV.ToString() );

      // Displays the values of the sections.
      Console.WriteLine( "New values:" );
      Console.WriteLine( "\tmySect1: {0}", myBV[mySect1] );
      Console.WriteLine( "\tmySect2: {0}", myBV[mySect2] );
      Console.WriteLine( "\tmySect3: {0}", myBV[mySect3] );
      Console.WriteLine( "\tmySect4: {0}", myBV[mySect4] );

   }

}

View Code

澳门新葡新京 35澳门新葡新京 36

/*
This code produces the following output.

Initial values:
        mySect1: 0
        mySect2: 0
        mySect3: 0
        mySect4: 0
Changing the values of each section:
        Initial:        BitVector32{00000000000000000000000000000000}
        mySect1 = 5:    BitVector32{00000000000000000000000000000101}
        mySect2 = 3:    BitVector32{00000000000000000000000000011101}
        mySect3 = 1:    BitVector32{00000000000000000000000000111101}
        mySect4 = 9:    BitVector32{00000000000000000000001001111101}
New values:
        mySect1: 5
        mySect2: 3
        mySect3: 1
        mySect4: 9

*/

View Code

 

11.不变的集合

Net提供的不可变集合

ImmutableStack<int> a1 = ImmutableStack<int>.Empty;
ImmutableStack<int> a2 = a1.Push(10);
ImmutableStack<int> a3 = a2.Push(20);
ImmutableStack<int> a4 = a3.Push(30);
ImmutableStack<int> iv3 = a4.Pop(); 

使用Net不可变列表集合有一点要注意的是,当我们Push值时要重新赋值给原变量才正确,因为push后会生成一个新对象,原a1只是旧值:

ImmutableStack<int> a1 = ImmutableStack<int>.Empty;
a1.Push(10); //不正确,a1仍是空值值,push会生成新的栈。
a1 = a1.Push(10); //需要将新栈重新赋值给a1

NET提供的常用数据结构

1.ImmutableStack
2.ImmutableQueue
3.ImmutableList
4.ImmutableHashSet
5.ImmutableSortedSet
6.ImmutableDictionary<K, V>
7.ImmutableSortedDictionary<K, V>

不可变优点

1.集合共享安全,从不被改变
2.访问集合时,不需要锁集合(线程安全)
3.修改集合不担心旧集合被改变
4.书写更简洁,函数式风格。 var list =
ImmutableList.Empty.Add(10).Add(20).Add(30);
5.保证数据完整性,安全性

不可变对象缺点

不可变本身的优点即是缺点,当每次对象/集合操作都会返回个新值。而旧值依旧会保留一段时间,这会使内存有极大开销,也会给GC造成回收负担,性能也比可变集合差的多。

澳门新葡新京 37

 

12.并发集合

线程安全的集合可防止多个线程以相互冲突的方式访问集合

.NET 的System.Collections.Concurrent提供了几个安全的类和功能:

说明
BlockingCollection<T>
ConcurrentBag<T>
ConcurrentDictionary<TKey, TValue>
ConcurrentQueue<T>
ConcurrentStack<T>
OrderablePartitioner<TSource>
Partitioner
Partitioner<TSource>

1)创建管道

将这些并发集合类用于管道,一个任务向一个集合类写入一些内容,同时另一个任务从该集合中读取内容

示例中多个任务形成一个管道.
第一个管道,
第1阶段的任务读取文件名,添加到队列,这个任务运行同时,
第2阶段的任务已经开始从队列中读取文件名并加载它们的程序,结果被写入另一个队列。
第3阶段同时启动,读取并处理第2个队列的内容,结果被写入一个字典。

第3阶段完成,并且内容已被最终处理,字典得到完整结果时,下一阶段才开始。
第4阶段从字典中读取内容,转换数据,然后写入队列中
第5阶段在项中添加颜色信息,然后把它们添加到另一个队列中,最后一个阶段显示信息。
第4到第6阶段也可以并发运行.

澳门新葡新京 38澳门新葡新京 39

class Program
  {
    static void Main(string[] args)
    {
      StartPipeline();
      Console.ReadLine();
    }

    private static async void StartPipeline()
    {
      var fileNames = new BlockingCollection<string>();
      var lines = new BlockingCollection<string>();
      var words = new ConcurrentDictionary<string, int>();
      var items = new BlockingCollection<Info>();
      var coloredItems = new BlockingCollection<Info>();

      Task t1 = PipelineStages.ReadFilenamesAsync(@"../../..", fileNames);
      ConsoleHelper.WriteLine("started stage 1");
      Task t2 = PipelineStages.LoadContentAsync(fileNames, lines);
      ConsoleHelper.WriteLine("started stage 2");
      Task t3 = PipelineStages.ProcessContentAsync(lines, words);
      await Task.WhenAll(t1, t2, t3);
      ConsoleHelper.WriteLine("stages 1, 2, 3 completed");

      Task t4 = PipelineStages.TransferContentAsync(words, items);
      Task t5 = PipelineStages.AddColorAsync(items, coloredItems);
      Task t6 = PipelineStages.ShowContentAsync(coloredItems);
      ConsoleHelper.WriteLine("stages 4, 5, 6 started");

      await Task.WhenAll(t4, t5, t6);

      ConsoleHelper.WriteLine("all stages finished");
    }
  }

Program

澳门新葡新京 40澳门新葡新京 41

public class ConsoleHelper
  {
    private static object syncOutput = new object();

    public static void WriteLine(string message)
    {
      lock (syncOutput)
      {
        Console.WriteLine(message);
      }
    }

    public static void WriteLine(string message, string color)
    {
      lock (syncOutput)
      {
        Console.ForegroundColor = (ConsoleColor)Enum.Parse(typeof(ConsoleColor), color);
        Console.WriteLine(message);
        Console.ResetColor();
      }
    }
  }

ConsoleHelper

澳门新葡新京 42澳门新葡新京 43

public static class PipelineStages
  {
    public static Task ReadFilenamesAsync(string path, BlockingCollection<string> output)
    {
      return Task.Run(() =>
        {
          foreach (string filename in Directory.EnumerateFiles(path, "*.cs", SearchOption.AllDirectories))
          {
            output.Add(filename);
            ConsoleHelper.WriteLine(string.Format("stage 1: added {0}", filename));
          }
          output.CompleteAdding();
        });
    }

    public static async Task LoadContentAsync(BlockingCollection<string> input, BlockingCollection<string> output)
    {
      foreach (var filename in input.GetConsumingEnumerable())
      {
        using (FileStream stream = File.OpenRead(filename))
        {
          var reader = new StreamReader(stream);
          string line = null;
          while ((line = await reader.ReadLineAsync()) != null)
          {
            output.Add(line);
            ConsoleHelper.WriteLine(string.Format("stage 2: added {0}", line));
          }
        }
      }
      output.CompleteAdding();
    }

    public static Task ProcessContentAsync(BlockingCollection<string> input, ConcurrentDictionary<string, int> output)
    {
      return Task.Run(() =>
        {
          foreach (var line in input.GetConsumingEnumerable())
          {
            string[] words = line.Split(' ', ';', '\t', '{', '}', '(', ')', ':', ',', '"');
            foreach (var word in words.Where(w => !string.IsNullOrEmpty(w)))
            {
              output.AddOrIncrementValue(word);
              ConsoleHelper.WriteLine(string.Format("stage 3: added {0}", word));
            }
          }
        });
    }

    public static Task TransferContentAsync(ConcurrentDictionary<string, int> input, BlockingCollection<Info> output)
    {
      return Task.Run(() =>
        {
          foreach (var word in input.Keys)
          {
            int value;
            if (input.TryGetValue(word, out value))
            {
              var info = new Info { Word = word, Count = value };
              output.Add(info);
              ConsoleHelper.WriteLine(string.Format("stage 4: added {0}", info));
            }
          }
          output.CompleteAdding();
        });
    }

    public static Task AddColorAsync(BlockingCollection<Info> input, BlockingCollection<Info> output)
    {
      return Task.Run(() =>
        {
          foreach (var item in input.GetConsumingEnumerable())
          {
            if (item.Count > 40)
            {
              item.Color = "Red";
            }
            else if (item.Count > 20)
            {
              item.Color = "Yellow";
            }
            else
            {
              item.Color = "Green";
            }
            output.Add(item);
            ConsoleHelper.WriteLine(string.Format("stage 5: added color {1} to {0}", item, item.Color));
          }
          output.CompleteAdding();
        });
    }

    public static Task ShowContentAsync(BlockingCollection<Info> input)
    {
      return Task.Run(() =>
        {
          foreach (var item in input.GetConsumingEnumerable())
          {
            ConsoleHelper.WriteLine(string.Format("stage 6: {0}", item), item.Color);
          }
        });
    }
  }

PipelineStages

 

2)使用BlockingCollection

第1阶段的ReadFilenamesAsync方法,实现了迭代目录文件名。在完成文件名添加后调用output.CompleteAdding();用以通知所有读取器不再等待集合中任何额外的项.如果没有调用的话,循环中读取器会添加等待更多的项.

澳门新葡新京 44澳门新葡新京 45

public static Task ReadFilenamesAsync(string path, BlockingCollection<string> output)
    {
      return Task.Run(() =>
        {
          foreach (string filename in Directory.EnumerateFiles(path, "*.cs", SearchOption.AllDirectories))
          {
            output.Add(filename);
            ConsoleHelper.WriteLine(string.Format("stage 1: added {0}", filename));
          }
          output.CompleteAdding();
        });
    }

ReadFilenamesAsync

下一阶段读取文件并将器内容添加到另一个集合中,由LoadContentAsync方法完成,该方法使用了输入集合传递的文件名,打开文件,把文件中的所有行添加到输出的集合中。在循环中用输入阻塞集合调用GetConsumingEnumerable()方法,以迭代各项,不使用也是可以的,但是值会迭代当前状态的集合。不会迭代以后添加的项。

如果在填充集合的同时,使用读取器读取集合,则需要使用GetConsumingEnumerable()方法获取阻塞集合的枚举器,而不是直接迭代集合

澳门新葡新京 46澳门新葡新京 47

public static async Task LoadContentAsync(BlockingCollection<string> input, BlockingCollection<string> output)
    {
      foreach (var filename in input.GetConsumingEnumerable())
      {
        using (FileStream stream = File.OpenRead(filename))
        {
          var reader = new StreamReader(stream);
          string line = null;
          while ((line = await reader.ReadLineAsync()) != null)
          {
            output.Add(line);
            ConsoleHelper.WriteLine(string.Format("stage 2: added {0}", line));
          }
        }
      }
      output.CompleteAdding();
    }

LoadContentAsync

 

3)使用ConcurrentDictionary

澳门新葡新京 48

澳门新葡新京 49澳门新葡新京 50

public static Task ProcessContentAsync(BlockingCollection<string> input, ConcurrentDictionary<string, int> output)
    {
      return Task.Run(() =>
        {
          foreach (var line in input.GetConsumingEnumerable())
          {
            string[] words = line.Split(' ', ';', '\t', '{', '}', '(', ')', ':', ',', '"');
            foreach (var word in words.Where(w => !string.IsNullOrEmpty(w)))
            {
              output.AddOrIncrementValue(word);
              ConsoleHelper.WriteLine(string.Format("stage 3: added {0}", word));
            }
          }
        });
    }

ProcessContentAsync

澳门新葡新京 51

澳门新葡新京 52澳门新葡新京 53

public static class ConcurrentDictionaryExtension
  {
    public static void AddOrIncrementValue(this ConcurrentDictionary<string, int> dict, string key)
    {
      bool success = false;
      while (!success)
      {
        int value;
        if (dict.TryGetValue(key, out value))
        {
          if (dict.TryUpdate(key, value + 1, value))
          {
            success = true;
          }
        }
        else
        {
          if (dict.TryAdd(key, 1))
          {
            success = true;
          }
        }
      }
    }
  }

ConcurrentDictionaryExtension

澳门新葡新京 54

在完成第3个阶段后,第4到6阶段也可以并行运行,TransferContentAsync从字典中获取数据,进行类型转换,输出到BlockingCollection<string>中

澳门新葡新京 55澳门新葡新京 56

 public static Task ProcessContentAsync(BlockingCollection<string> input, ConcurrentDictionary<string, int> output)
    {
      return Task.Run(() =>
        {
          foreach (var line in input.GetConsumingEnumerable())
          {
            string[] words = line.Split(' ', ';', '\t', '{', '}', '(', ')', ':', ',', '"');
            foreach (var word in words.Where(w => !string.IsNullOrEmpty(w)))
            {
              output.AddOrIncrementValue(word);
              ConsoleHelper.WriteLine(string.Format("stage 3: added {0}", word));
            }
          }
        });
    }

    public static Task TransferContentAsync(ConcurrentDictionary<string, int> input, BlockingCollection<Info> output)
    {
      return Task.Run(() =>
        {
          foreach (var word in input.Keys)
          {
            int value;
            if (input.TryGetValue(word, out value))
            {
              var info = new Info { Word = word, Count = value };
              output.Add(info);
              ConsoleHelper.WriteLine(string.Format("stage 4: added {0}", info));
            }
          }
          output.CompleteAdding();
        });
    }

    public static Task AddColorAsync(BlockingCollection<Info> input, BlockingCollection<Info> output)
    {
      return Task.Run(() =>
        {
          foreach (var item in input.GetConsumingEnumerable())
          {
            if (item.Count > 40)
            {
              item.Color = "Red";
            }
            else if (item.Count > 20)
            {
              item.Color = "Yellow";
            }
            else
            {
              item.Color = "Green";
            }
            output.Add(item);
            ConsoleHelper.WriteLine(string.Format("stage 5: added color {1} to {0}", item, item.Color));
          }
          output.CompleteAdding();
        });
    }

    public static Task ShowContentAsync(BlockingCollection<Info> input)
    {
      return Task.Run(() =>
        {
          foreach (var item in input.GetConsumingEnumerable())
          {
            ConsoleHelper.WriteLine(string.Format("stage 6: {0}", item), item.Color);
          }
        });
    }

View Code

 

 

13.性能

集合的方法常常有性能提示,给出大写O记录操作时间。

澳门新葡新京 57

O(1)表示无论集合中有多少数据项,这个操作需要的时间都不变。
O(n)表示对于集合执行一个操作需要的事件在最坏情况时是N.
O(log n)表示操作需要的时间随集合中元素的增加而增加

澳门新葡新京 58

不可变优点

  • 集合共享安全,从不被改变
  • 访问集合时,不需要锁集合(线程安全)
  • 修改集合不担心旧集合被改变
  • 书写更简洁,函数式风格。 var list =
    ImmutableList.Empty.Add(10).Add(20).Add(30);
  • 保证数据完整性,安全性
非泛型类集合

泛型集合类是在.NET2.0的时候出来的,也就是说在1.0的时候是没有这么方便的东西的。现在基本上我们已经不使用这些集合类了,除非在做一些和老代码保持兼容的工作的时候。来看看1.0时代的.NET程序员们都有哪些集合类可以用。

ArraryList后来被List<T>替代。

HashTable 后来被Dictionary<TKey,TValue>替代。 
Queue 后来被Queue<T>替代。 
SortedList 后来被SortedList<T>替代。 
Stack 后来被Stack<T>替代。

不可变对象缺点

不可变本身的优点即是缺点,当每次对象/集合操作都会返回个新值。而旧值依旧会保留一段时间,这会使内存有极大开销,也会给GC造成回收负担,性能也比可变集合差的多。

跟string和StringBuild一样,Net提供的不可变集合也增加了批量操作的API,用来避免大量创建对象:

     ImmutableList<string> immutable = ImmutableList<string>.Empty;
        //转换成可批量操作的集合
        var immutable2 = immutable.ToBuilder();
        immutable2.Add("xx");
        immutable2.Add("xxx");
        //还原成不可变集合
        immutable = immutable2.ToImmutable();

我们来对比下可变集合、不可变Builder集合、不可变集合的性能,添加新对象1000W次:

澳门新葡新京 59

比较代码如下:

澳门新葡新京 60澳门新葡新京 61

   private static void List()
        {
            var list = new List<object>();
            var sp = Stopwatch.StartNew();

            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                list.Add(obj);
            }
            Console.WriteLine("可变列表集合:"+sp.Elapsed);
        }

        private static void BuilderImmutableList()
        {
            var list = ImmutableList<object>.Empty;
            var sp = Stopwatch.StartNew();
            var blist= list.ToBuilder();
            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                blist.Add(obj);
            }
            list=blist.ToImmutable();

            Console.WriteLine("不可变Builder列表集合:"+sp.Elapsed);
        }
        private static void ImmutableList()
        {
            var list = ImmutableList<object>.Empty;
            var sp = Stopwatch.StartNew();

            for (int i = 0; i < 1000 * 10000; i++)
            {
                var obj = new object();
                list = list.Add(obj);
            }

            Console.WriteLine("不可变列表集合:" + sp.Elapsed);
        }

View Code

另外一个缺点比较有趣,也有不少人忽略。
由于string的不可变特性,所以当我们使用string在保存敏感信息时,就需要特别注意。
比如密码 var
pwd=”mushroomsir”,此时密码会以明文存储在内存中,也许你稍后会加密置空等,但这都是会生成新值的。而明文会长时间存储在共享域内存中,任何能拿到dump文件的人都可以看到明文,增加了密码被窃取的风险。当然这不是一个新问题,net2.0提供的有SecureString来进行安全存储,使用时进行恢复及清理。

IntPtr addr = Marshal.SecureStringToBSTR(secureString);
string temp = Marshal.PtrToStringBSTR(addr);
Marshal.ZeroFreeBSTR(addr);
WriteProcessMemory(...)

 

线程安全的集合类

ConcurrentQueue 线程安全版本的Queue 
ConcurrentStack线程安全版本的Stack 
ConcurrentBag线程安全的对象集合 
ConcurrentDictionary线程安全的Dictionary 
BlockingCollection

 

相关文章