C++学习笔记：Container和Iterator

时间：2010-09-14 来源：weichsel

C++学习笔记：Container和Iterator
2010-5-26

为什么需要Container

Container和动态对象创建结合起来，实现对大量、数目未知对象的创建、管理。
通常的用法是：根据需要New一个对象；将对象指针保存到Container中；需要访问对象的时候，从Container中获取对象指针。
另外一种管理对象的方法是静态方式，预先创建大规模的对象数组，数量满足系统的最大需要。这种方法会带来性能方面的问题。大量对象创建时要执行构造函数，性能的开销很大。

如何让Container支持不同类型的对象

方法1：Object-Based Hierachy

所有的类都直接或间接地从唯一的根类派生，所有的对象形成单根层级关系。这种方法被很多语言支持，比如Delphi。

对于C++来说，由于支持多继承，不能保证单根对象层次关系，这种方法存在问题。

方法2：Template

将类型参数化，代码与具体的类型无关，实现代码的重用。

对于程序员来说，Template的使用更为简单。

Template的一些特点：

由编译器完成具体类型的替换；
定义、声明总是放在头文件中；
参数分为class type和Built-in type，后者是compile-time 常量。

Iterator实现

为Container提供一种遍历访问内部元素的机制。Iterator提供了类似指针的行为，使用者可以像访问数组一样访问Container内部的元素，而不必关心Container内部的实现。
Iterator使得不同Container具备相同的元素访问接口。那么，对元素的处理函数可以保持独立，不依赖与具体的Container。元素的处理函数在STL中被称为算法，可以说Iterator机制是STL中算法的基石。

Iterator典型的用法：
vector s;
vector::iterator it;
for (it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}

从这段代码，我们可以了解到iterator实现上的一些功能要求：

iterator内嵌于Container中；
Container的begin(), end() 函数创建iterator对象；
iterator要支持运算符=, !=, ++, *；

下面是一个iterator实现的简单例子：

using namespace std;
template
class PStack {
struct LINK {
T* data;
LINK* next;
LINK(T* v, LINK* lk): data(v), next(lk) {}
}* head;
public:
PStack(): head(NULL) {}
~PStack() {
while (!head) {
delete pop();
}
}
void add(T* val) {
head = new LINK(val, head);
}
T* pop() {
if (head == NULL) {
return NULL;
}
T* data = head->data;
LINK* old = head;
head = head->next;
delete old;
return data;
}
class iterator;
friend class iterator;
class iterator {
PStack* s;
LINK* p;
public:
iterator(): s(NULL), p(NULL) {}
iterator(PStack* v): s(v), p(v->head) {}
iterator(PStack* v, bool): s(v), p(NULL) {}
// copy constructor
iterator(const iterator& it) {
s = it.s;
p = it.p;
}
// =
iterator& operator=(const iterator& it) {
s = it.s;
p = it.p;
return *this;
}
// !=
bool operator!= (const iterator& it) {
return (p != it.p);
}
// ++
void operator++(int) {
if (p != NULL) {
p = p->next;
}
}
// *
T* operator*() {
if (p == NULL) {
return NULL;
}
return p->data;
}
};
// create an iterator object
iterator begin() {
return iterator(this);
}
// create an iterator object
iterator end() {
return iterator(this, true);
}
};
int main() {
PStack s;
PStack::iterator it;
s.add(new int(2));
s.add(new int(4));
s.add(new int(1));
s.add(new int(3));
for (it = s.begin(); it != s.end(); it++) {
cout << *it << ":" << **it << endl;
}
return 0;
}

#include <iostream>