ID #4481

构建可反转排序的泛型字典类(5)--实现IEnumerable接

5. 实现IEnumerable<KeyValuePair<TKey, TValue>>接口

我们先来看看ReversibleSortedList类的定义:

public class ReversibleSortedList<TKey, TValue> :
IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable

它一共实现了6个接口。但从本质上来说,实现IDictionary<TKey, TValue>接口和IDictionary接口就等同于实现了以上6个接口。因为 IDictionary<TKey, TValue>继承自 ICollection<KeyValuePair<TKey, TValue>>和 IEnumerable<KeyValuePair<TKey, TValue>>接口,而IDictionary 接口继承自ICollection和IEnumerable接口。下面我们来看一下这些接口的关系 图:

图2 ReversibleSortedList类接口关系图

其实 ReversibleSortedList类的大部份代码都用于实现左边这两个接口,看到这张图 你应该理解了为什么会需要1300行的代码。为了一步一步地实现这个类,我们需 要首先实现底层接口,由于ICollection接口本身就继承自IEnumerable接口,所 以首先应该实现的是IEnumerable接口。从前面一节可以知道IEnumerable接口的 实现需要一个嵌套类,它返回一个枚举器。我们可以为IDictionary<TKey, TValue>接口和IDictionary接口实现同一个枚举器,只要这个枚举器实现了 IEnumerator<KeyValuePair<K, V>>接口和IDictionaryEnumerator 接口就可以了。前者是IDictionary<TKey, TValue>接口所需要的枚举器 ,后者是IDictionary接口所需要的枚举器(见前一节)。下面是我们的这个枚 举器所需实现的接口的关系图:

图3 Enumerator<K, V>类接口关系图

实现这个类需要注 意一个问题,在ReversibleSortedList类中添加了一个新的成员变量:version 。在插入元素时(insert方法)会更改这个version值,表示类中的元素已经进 行了改动。为什么要使用它呢?在此我做些推测。从MSDN中或许可以找到线索。 我们在MSDN找到关于Dictionary<TKey, TValue>类的介绍,这个类跟 ReversibleSortedList类非常相似。在关于它的线程安全中有这么一段话:

此类型的公共静态成员是线程安全的。但不能保证任何实例成员是线程 安全的。

只要不修改该集合,Dictionary<(Of <(TKey, TValue>)>) 就可以同时支持多个阅读器。 即便如此,从头到尾对一个集 合进行枚举本质上并不是一个线程安全的过程。当出现枚举与写访问互相争用这 种极少发生的情况时,必须在整个枚举过程中锁定集合。若要允许多个线程访问 集合以进行读写操作,则必须实现自己的同步。

可以推测,version用于 在枚举过程中判断是否有其他线程更改了ReversibleSortedList实例中存储的元 素,以便弹出异常。这一点可以在稍后的代码中看见。

这时可能有人会 问了,前面一节中关没有这种判断啊?好,让我们看看上一节关于IDictionary 接口的代码。在它的实现枚举器的嵌套类SimpleDictionaryEnumerator中,看看 它的构造方法:

public SimpleDictionaryEnumerator (SimpleDictionary sd)
    {
      items = new DictionaryEntry[sd.Count];
      Array.Copy(sd.items, 0, items, 0, sd.Count);
    }

从代码中可以看出,它 把外部类中的所有元素拷贝到另一块内存中进行枚举,这样在多线程访问集合时 自然不会出错,但如果集合中的元素很多就会带来性能上的损失。而我们实现的 ReversibleSortedList类将直接使用集合中的元素进行枚举,所以需要使用 version来保证在出错时可以弹出异常。

下面我们在 “ReversibleSortedList 0.3版本”的基础上继续构建。关于 version的代码这里不再讲解,请大家查看稍后完整的0.4版本的代码。首先添加 一个实现枚举器的嵌套类:

private struct Enumerator<K, V> : IEnumerator<KeyValuePair<K, V>>, IDisposable,
    IDictionaryEnumerator, IEnumerator
  {
     private ReversibleSortedList<K, V> _ReversibleSortedList;
    private K key;
    private V value;
     private int index;
    private int version;
     internal Enumerator(ReversibleSortedList<K, V> ReversibleSortedList)
    {  //获取外部类中的元素引用,以对 它进行枚举
      this._ReversibleSortedList = ReversibleSortedList;
      this.index = 0;
       this.version = this._ReversibleSortedList.version;//记录外部类版本号
      //设置键和值为其默认类型,请参考:
       //http://cgbluesky.blog.163.com/blog/static/2412355820081695340822/
      this.key = default(K);
      this.value = default(V);
    }
    public void Dispose()
     {
      this.index = 0;
      this.key = default(K);
      this.value = default(V);
    }
    object IDictionaryEnumerator.Key
    {
       get
      {
        if ((this.index == 0) ||
          (this.index == (this._ReversibleSortedList.Count + 1)))
        {
          throw new InvalidOperationException(
               "不能进行枚举操作.");
         }
        return this.key;
      }
     }
    public bool MoveNext()
    {
       if (this.version != this._ReversibleSortedList.version)
       {  //版本检查
        throw new InvalidOperationException("枚举版本检查失败!");
       }
      if (this.index < this._ReversibleSortedList.Count)
      {
         this.key = this._ReversibleSortedList.keys[this.index];
         this.value = this._ReversibleSortedList.values [this.index];
        this.index++;
         return true;
      }
      this.index = this._ReversibleSortedList.Count + 1;
      this.key = default(K);
      this.value = default(V);
       return false;
    }
    DictionaryEntry IDictionaryEnumerator.Entry
    {
      get
      {
        if ((this.index == 0) ||
           (this.index == (this._ReversibleSortedList.Count + 1)))
        {
          throw new InvalidOperationException("不能进行枚举操作.");
         }
        return new DictionaryEntry(this.key, this.value);
      }
    }
    public KeyValuePair<K, V> Current
    {
       get
      {
        return new KeyValuePair<K, V>(this.key, this.value);
      }
    }
    object IEnumerator.Current
    {
      get
      {
        if ((this.index == 0) ||
          (this.index == (this._ReversibleSortedList.Count + 1)))
        {
          throw new InvalidOperationException("不能进行 枚举操作");
        }
        return new DictionaryEntry(this.key, this.value);
      }
     }
    object IDictionaryEnumerator.Value
     {
      get
      {
        if ((this.index == 0) ||
          (this.index == (this._ReversibleSortedList.Count + 1)))
        {
          throw new InvalidOperationException("不能进行 枚举操作");
        }
        return this.value;
      }
    }
    void IEnumerator.Reset()
    {
      if (this.version != this._ReversibleSortedList.version)
      {
         throw new InvalidOperationException("枚举版本检查失败! ");
      }
      this.index = 0;
       this.key = default(K);
      this.value = default (V);
    }
  }

这个嵌套类的代码对照图3很 容易看懂,每个方法的功能在MSDN中也有详细的介绍,这里不再对它进行讲解。 接下来要给外部类实现IEnumerable<KeyValuePair<TKey, TValue>>和 IEnumerable接口。更改类声明代码如下:

public class ReversibleSortedList<TKey, TValue> :

IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable

当然,这两个接口分别只有一个成员:GetEnumerator()方 法,刚才所创建的嵌套类就是为这个方法所创建的。接下来在 ReversibleSortedList类中使用显式接口成员实现来实现这两个接口:

IEnumerator<KeyValuePair<TKey, TValue>>
     IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
  {
    return new Enumerator<TKey, TValue>(this);
  }
  IEnumerator IEnumerable.GetEnumerator()
  {
    return new Enumerator<TKey, TValue>(this);
  }

好,现在 更改Main()方法中的代码看看是否可以使用foreach循环来访问 ReversibleSortedList中的元素,当然,前面所写的Print()成员方法可以退休 了。

static void Main()
  {
     ReversibleSortedList<int, string> rs=new ReversibleSortedList<int, string>();
    rs.Add (3,"a");
    rs.Add(1,"b");
     rs.Add(2,"c");
    rs.Add(6,"d");
     rs.Add(5,"e");
    rs.Add (4,"f");
    foreach (KeyValuePair<int, string> d in rs)
    {
      Console.WriteLine (d.Key + "  " + d.Value);
    }
  }

由于代码已经达到300行,贴到博客上会导致运行缓慢,后面所 有的可运行代码将以文件的形式给出,大家可以直接下载运行。

ReversibleSortedList 0.4版本:实现迭代

运行结果:

1  b
2  c
3  a
4  f
5  e
6  d

真棒,现在已经取得了阶段性的成果。但还有一些遗憾 ,虽然在Enumerator类中实现了IDictionaryEnumerator接口,但还不能在 foreach中使用DictionaryEntry访问元素。这是因为IDictionary接口重载了 GetEnumerator()接口,而它返回的是一个IDictionaryEnumerator接口,也就是 说,只有实现了IDictionary接口才能使用DictionaryEntry访问其中元素。实现 IDictionary接口之前我们需要建立一些辅助的内部类,这将在下一节进行讲解 。

本文配套源码


2011-07-01 18:00
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

C#中实现DataGrid双向排序

C#几种常用的排序算法

C#快速排序类

C# GridView 排序及分页

C#四种排序算法