使用Iterator简化代码2-TwoLevelIterator
上一篇文章中，我们讲到使用Iterator可以降低Merge类的代码量，使得接口更为清晰，代码更易维护。
总的来说使用Iterator模式有下面两个好处
- 提供简单的接口
- 统一的访问方式
下面我们再来看一个例子，我们为一个书店写程序，书店里有许多书Book，每个书架（BookShelf)上有多本书。
类结构如下所示
class Book { private: string book_name_; }; class Shelf { private: vector<Book> books_; };
如何遍历书架上所有的书呢？
一种实现方法是：
vector<Book>& GetBooks() const { return books_; } 然后调用者会遍历所有的书
这样的实现暴漏了内部太多的细节，调用者根本就不需要知道Shelf存储Book的方式，仅仅需要遍历所有的数据即可。
而且这样当我们换用另外一种数据结构存储Book时，客户端的代码就需要进行修改。
如果使用Iterator模式则没有这个问题
// iterator.h class Iterator { public: virtual bool Valid() const = 0; virtual void SeekToFirst() const = 0; virtual void Seek(const Book& book) = 0; virtual void Next() = 0; virtual const Book& GetValue() = 0; }; // shelf.h class Shelf { public: Iterator* NewIterator() const; private: vector<Book> books_; }; // shelf.cc BookIterator : public Iterator { }; Iterator* Shelf::NewIterator() const { return new BookIterator(this); }
这种实现方式更加简单也更加的灵活.
再来看一下我们的书店(BookStore)类，一个书店中有许多个书架，我们仍然需要遍历书店中所有的书，现在应该如何实现呢？
class BookStore { private: string name_; vector<Shelf> shelfs_; };
我们必须记录一些中间状态，比如遍历到了哪个书架，遍历到了书架的那本书，如果该书架的书遍历完了，要自动的移动到下一个书架上.
// 书店类 class BookStore { Iterator* NewIterator() const; private: vector<Shelf> shelf_; };
一种实现方式是，由BookStore负责保存各个中间状态，包括当前遍历到了哪个书架，遍历到了书架上的那本书。
这种实现方法对外还是干净的，但是对于BookStore的维护者来说却是不友好的，Iterator的中间状态不是BookStore的成员，逻辑上不应该由BookStore维护。
更好的一种实现方式是，把遍历Iterator相关的代码封装成一个类，有两个层级Shelf 和 Book，这个类的名字我们叫做TwoLevelIteator.
TwoLevelIterator的实现（示意代码，只说明原理）
TwoLevelIterator将上面我们所说的中间状态封装成一个类，而不是散落在BookStore中作为BookStore的成员变量。
typedef Iterator* (*BookFunction)(Iterator*); class TwoLevelIterator : public Iterator { public: TwoLevelIterator( Iterator* shelf_iter, BookFunction book_function); virtual ~TwoLevelIterator(); virtual void SeekToFirst(); virtual void Next(); virtual void Valid(); virtual const Book& Value() { return book_iter_->Value(); } private: BookFunction book_function_; Iterator* shelf_iter_; Iterator* book_iter_; }; TwoLevelIterator::TwoLevelIterator( Iterator* shelf_iter, BookFunction book_function) : shelf_iter_(shelf_iter), book_iter_(NULL) { } void TwoLevelIterator::SeekToFirst() { shelf_iter->SeekToFirst(); } void TwoLevelIterator::Next() { book_iter->Next(); while (!book_iter->Valid()) { if (!shelf_iter_->Valid()) { return; } shelf_iter_->Next(); book_iter = (*book_function)(shelf_iter); } }
Leveldb中的index_block data_block，index_block是data_block的索引，这里面就用到了TwoLevelIerator.[0]
附件是一个和c++ container兼容的two_level_iterator实现（已经测试过）
