如何用 C++ 编写抽象迭代器。
如何在 C++ 中编写通用的类 STL 迭代器。
引言
在 C++ 中进行开发时，无懈可击的 API 是必备的：它必须尽可能简单、抽象、通用且可扩展。STL 使 C++ 开发者熟悉的一个重要的通用概念是迭代器的概念。
迭代器用于访问容器中的元素，而不暴露容器是如何实现的（例如，vector、list、红黑树、哈希集、队列等）。迭代器是泛型编程的核心，因为它们是容器和应用程序之间的接口。应用程序需要访问容器中的元素，但通常不需要知道元素是如何存储在容器中的。迭代器使得编写可操作于不同类型容器的通用算法成为可能。
例如，以下代码片段暴露了容器的性质——一个 vector。
void process(const std::vector<E>& v)
{
for (unsigned i = 0; i < v.size(); ++i) {
process(v[i]);
}
}
如果我们想让同一个函数作用于 list，我们就必须编写一个单独的函数。或者，如果我们稍后决定 list 或 hash set 作为容器更合适，我们就需要在访问 vector 的所有地方重写代码。这可能需要在许多文件中进行大量更改。将这种特定于容器的访问方案与以下方法进行对比：
template <typename Container>
void process(const Container& c)
{
typename Container::const_iterator itr = c.begin();
typename Container::const_iterator end = c.end();
for (; itr != end; ++itr) {
process(*itr);
}
}
利用迭代器的概念，我们可以对容器 'c' 进行通用处理，无论它是 vector、list、hash set，还是任何在其 API 中提供迭代器的 C++ 数据结构。甚至更好的是，我们可以编写一个仅接受迭代器范围的通用处理函数，而不假定容器具有 begin() 和 end() 方法。
template <typename Iterator>
void process(Iterator begin, Iterator end)
{
for (; itr != end; ++itr) {
process(*itr);
}
}
STL 迭代器是一种像标量类型一样工作的商品
- 它可以分配在堆上
- 它可以被复制
- 它可以按值传递
- 它可以被赋值
迭代器的本质通过以下 API 来捕获：
template <typename T>
class Itr {
public:
Itr();
~Itr();
Itr(const Itr& o); // Copy constructor
Itr& operator=(const Itr& o); // Assignment operator
Itr& operator++(); // Next element
T& operator*(); // Dereference
bool operator==(const Itr& o) const; // Comparison
bool operator!=(const Itr& o) const { return !(*this == o); }
}
通常，容器会提供 begin() 和 end() 方法，它们构建了表示容器范围的迭代器。如果容器派生自 STL 容器，如果容器有一个作为 STL 容器的数据成员，或者如果迭代器是一个标量类型（如指针或索引），那么编写这些 begin/end 方法是一项简单的任务。
如果我们想要迭代器解引用到相同类型的对象，但必须访问多个容器，可能类型不同，或者迭代器以不同方式访问容器，那么情况会更复杂。例如，假设我们有一些对象具有某个属性（例如，颜色），这些对象存储在几个容器中，其中一些容器类型不同。我们希望访问所有对象，而不管容器的数量和类型如何，或者我们希望访问具有特定颜色的对象，或者我们希望访问满足某些谓词的对象。
Itr<E> begin(); // This give the range to visit
Itr<E> end(); // all the elements of type E
Itr<E> begin(const Color& color); // Same as above but only for the
Itr<E> end(const Coir& color); // elements of the given color
class Predicate {
public:
bool operator()(const E& e);
};
Itr<E> begin(Predicate& p); // Same as above but only for the
Itr<E> end(Predicate& p); // elements that satisfy the predicate
在这种情况下，迭代器比指针或索引等标量类型更复杂：它需要跟踪它当前正在访问哪个容器，或者它需要检查哪种颜色或谓词。通常，迭代器可能有数据成员，以便它可以完成其任务。此外，我们希望对代码进行分解，并在编写更具针对性的迭代器时重用通用迭代器方法，例如，访问特定颜色的元素应该利用下一个元素方法 Itr<E>::operator++()。这可以通过使 Itr<E> 成为一个虚类，并让派生类来实现不同的迭代器来完成。例如：
class E {
public:
Color& color() const;
};
template <typename E>
class ColoredItr<E> : public Itr<E> {
private:
typedef Itr<E> _Super;
public:
ColoredItr<E>(const Color& color) : Itr<E>(), color_(color) {}
virtual ~ColoredItr<E>;
virtual ColoredItr<E>& Operator++() {
for (; _Super::operator*().color() != color_; _Super::operator++());
return *this;
}
private:
Color color_;
};
我们希望有一个满足上述所有要求的通用迭代器
- 它可以分配在堆上
- 它可以被复制
- 它可以按值传递
- 它可以被赋值
- 它解引用到相同类型的对象
- 它可以访问多个容器
- 它可以访问不同类型的容器
- 它可以以任意方式访问容器
这可以通过以下方式实现：
template<typename E>
class ItrBase {
public:
ItrBase() {}
virtual ~ItrBase() {}
virtual void operator++() {}
virtual E& operator*() const { return E(); }
virtual ItrBase* clone() const { return new ItrBase(*this); }
// The == operator is non-virtual. It checks that the
// derived objects have compatible types, then calls the
// virtual comparison function equal.
bool operator==(const ItrBase& o) const {
return typeid(*this) == typeid(o) && equal(o);
}
protected:
virtual bool equal(const ItrBase& o) const { return true; }
};
template<typename E>
class Itr {
public:
Itr() : itr_(0) {}
~Itr() { delete itr_; }
Itr(const Itr& o) : itr_(o.itr_->clone()) {}
Itr& operator=(const Itr& o) {
delete itr_; itr_ = o.itr_->clone(); return *this;
}
Itr& operator++() { ++(*itr_); return *this; }
E& operator*() const { return *(*itr_); }
bool operator==(const Itr& o) const {
return (itr_ == o.itr_) || (*itr_ == *o.itr_);
}
bool operator!=(const Itr& o) const { return !(*this == o); }
protected:
ItrBase<E>* itr_;
};
ItrBase 类是该层次结构的顶层类。Itr 只是一个指向 ItrBase 的指针的包装器，因此它可以分配在堆上——派生自 ItrBase 的类的实际实现可以具有任意大小。请注意 Itr 的复制和赋值运算符是如何通过 ItrBase::clone() 方法实现的，以便 Itr 表现得像一个标量类型。最后但同样重要的是，（非虚的）ItrBase::operator== 相等运算符首先检查类型是否相等，然后调用（虚的）equal 方法在虚拟子类上。ItrBase 不是纯虚类的原因是它可以方便地用来表示一个空范围，即范围 (ItrBase(), ItrBase()) 是空的。
类型为 E 的容器的迭代器只需要派生自 ItrBase<E>，并且一个为任何专用迭代器提供 begin() 和 end() 方法的工厂会返回类型为 Itr<E> 的对象。
例如，假设我们有一个 E 类型的容器 c，并且我们想要一个迭代器来访问
c中的所有元素，可能带有重复；c中的所有元素，不带重复。
这可以通过以下方式完成：
class E; // Let's assume it's defined somewhere
class ItrAll : public ItrBase<E> {
private:
typedef ItrAll _Self;
typedef ItrBase<E> _Super;
public:
ItrAll(Container& c) : _Super(), c_(c) {}
virtual ~ItrAll() {}
virtual void operator++() { ++itr_; }
virtual E& operator*() const { return *itr_; }
virtual ItrBase<E>* clone() const { return new _Self(*this); }
protected:
virtual bool equal(const ItrBase<E>& o) const {
// Casting is safe since types have been checked by _Super::operator==
const _Self& o2 = static_cast<const _Self&>(o);
return &c_ == &o2.c_ && itr_ == o2.itr_;
}
protected:
Container& c_;
Container::iterator itr_;
};
class ItrNoRepeat : public ItrAll {
private:
typedef ItrNoRepeat _Self;
typedef ItrAll _Super;
public:
ItrNoRepeat (Container& c) : _Super(c) {}
virtual ~ItrNoRepeat () {}
virtual void operator++() {
_Super::operator++(); // Go to the next element then
// look for an element that has not been visited yet.
for (; itr_ != c_.end(); _Super::operator++()) {
E& e = _Super::operator*();
if (visited_.find(e) == visited_.end()) {
visited_.insert(e);
return;
}
}
}
virtual E& operator*() const { return _Super::operator*(); }
virtual ItrBase<E>* clone() const { return new _Self(*this); }
protected:
virtual bool equal(const ItrBase<E>& o) const { return _Super::equal(o); }
protected:
set<E> visited_;
};
// Build the container's range w/ and w/o repetition
Itr<E> begin(Container& c, bool noRepeat = false)
{
Itr<E> o;
if (noRepeat) {
o.itr_ = new ItrNoRepeat(c);
} else {
o.itr_ = new ItrAll(c);
}
o.itr_->itr_ = c.begin();
return o;
}
Itr<E> end(Container& c, bool noRepeat = false)
{
Itr<E> o;
if (noRepeat) {
o.itr_ = new ItrNoRepeat(c);
} else {
o.itr_ = new ItrAll(c);
}
o.itr_->itr_ = c.end();
return o;
}