容器与迭代器.pptVIP

第16章 容器和迭代器 容器是特定类型的对象的集合，也就是为了保存一组对象而设计的类 容器一般提供插入、删除、查找以及访问容器中的所有对象等功能 用户不必关心容器中的对象是如何保存的。用户只需要使用容器提供的插入操作将对象放入容器，用删除操作将对象从容器中删除 数组是容器的一种实现，链表也是容器的一种实现 迭代器 给出数组的下标可以访问数组的某一元素，给出一个指向某一结点的指针可以访问链表中的一个元素。 访问一个容器中的对象必须有一个指向容器中某一个对象位置的信息 容器中的对象位置是什么类型的信息？如果容器是用数组实现，则是一个整型数。如果容器是用单链表实现，则是一个指向单链表结点的指针。 对象位置的类型与容器的实现方式有关。因此，通常为每种容器定义一个表示其中变量位置的类型，称为迭代器。 迭代器 迭代器常常与容器一起使用。迭代器对象相当于是指向容器中对象的指针。 迭代器对象“穿行”于容器，容器中的某一元素执行某种操作。 可以将迭代器看成一种抽象的指针，迭代器进一步隐藏数据的存储方式。 迭代器常用操作 迭代器对象赋值 迭代器对象的比较 让迭代器移动到当前对象的下一对象 取迭代器指向的对象 在数组中，要访问所有结点可以用 For (i=1;i=length;++i) cout array[i] endl; 在链表中，可以用 For (node *p=head; p!=NULL；p=p-next) cout p-data endl; 各种结构的抽象实现就是采用迭代器 For (itr＝ListSeq.begin();itr!=ListSeq.end(); ++itr) cout *itr endl; 与某一元素相关的操作可以让迭代器完成，容器类只完成对表整体的操作。迭代器一般作为相应类的友元类或内嵌类。 迭代器实例 –顺序表中的迭代器 设计一个用数组实现的容器。该容器可以通过简单的[] 运算符重载达到同时访问表元素的问题，但也可以用迭代器访问。 功能： 可以将数据依次放入容器。当数组不够大时，容器自动扩展数组。（动态） 删除最后放入的对象 在迭代器指出的位置插入一对象 删除迭代器指出的位置的对象 迭代器的常规操作：设置迭代器的初始位置，向后移一位置，判断迭代器指向的位置是否有对象，取迭代器指向的对象。 设计考虑 将迭代器类设置成容器类的内嵌类 容器的行为： 放入一对象 删除一对象 在指定位置放入一对象 删除指定位置的对象 取容器的首尾位置 迭代器的行为 设置迭代器的值 迭代器向后移动 比较两迭代器是否相同 容器类的设计 template class T //可以存放任意类型的数据 class seqlist { private: int size; //最大存储规模 int current_size; //当前存放的规模 T *storage; //数组的起始地址 void doubleSpace(); //将数组容量扩大一倍 public: seqlist(int s = 10):size(s) //构造函数 { storage = new T[size]; current_size = 0;} ~seqlist() {delete [] storage;} void push_back(const T x) //在容器尾添加对象 { if (size == current_size) doubleSpace(); //把数组空间放大一倍 storage[current_size++] = x; } void pop_back( ) //删除容器尾的对象 { if (current_size == 0) cerr 这是一个空容器\n; else --current_size; } T operator[](int i) //下标运算符重载 { return storage[i]; } class Itr { //迭代器类的定义 T *pos; //指向容器中的某一对象 public: Itr(T *obj = NULL) //默认值为null {pos = obj;} Itr operator++() //指向容器中的下一个对象 { ++pos; return *thi