C++程序设计课程介绍-第16章 容器和迭代器.ppt

第16章 容器和迭代器,容器是特定类型的对象的集合，也就是为了保存一组对象而设计的类 容器一般提供插入、删除、查找以及访问容器中的所有对象等功能 用户不必关心容器中的对象是如何保存的。用户只需要使用容器提供的插入操作将对象放入容器，用删除操作将对象从容器中删除 数组是容器的一种实现，链表也是容器的一种实现,迭代器,给出数组的下标可以访问数组的某一元素，给出一个指向某一结点的指针可以访问链表中的一个元素。 访问一个容器中的对象必须有一个指向容器中某一个对象位置的信息 容器中的对象位置是什么类型的信息？如果容器是用数组实现，则是一个整型数。如果容器是用单链表实现，则是一个指向单链表结点的指针。 对象位置的类型与容器的实现方式有关。因此，通常为每种容器定义一个表示其中变量位置的类型，称为迭代器。,迭代器,迭代器常常与容器一起使用。迭代器对象相当于是指向容器中对象的指针。 迭代器对象“穿行”于容器，容器中的某一元素执行某种操作。 可以将迭代器看成一种抽象的指针，迭代器进一步隐藏数据的存储方式。,迭代器常用操作,迭代器对象赋值 迭代器对象的比较 让迭代器移到当前对象的下一对象 取迭代器指向的对象,迭代器的优点,在数组中，要访问所有结点可以用 for (i=1;inext) cout data endl; 各种结构的抽象实现就是采用迭代器 for (listitr itr(l); +itr; +itr) cout itr() endl; 与某一元素相关的操作可以让迭代器完成，容器类只完成对表整体的操作。迭代器一般作为相应类的友元类或内嵌类。,迭代器实例 顺序表中的迭代器,设计一个用数组实现的容器。该容器可以通过简单的 运算符重载达到同时访问表元素的问题，但也可以用迭代器访问。 功能： 可以将数据依次放入容器。当数组不够大时，容器自动扩展数组。 删除最后放入的对象 在迭代器指出的位置插入一对象 删除迭代器指出的位置的对象 迭代器的常规操作：设置迭代器的初始位置，向后移一位置，判断迭代器指向的位置是否有对象，取迭代器指向的对象。,设计考虑,将迭代器类设置成容器类的内嵌类 容器的行为： 放入一对象 删除一对象 在指定位置放入一对象 删除指定位置的对象 取容器的首尾位置 迭代器的行为 设置迭代器的值 迭代器向后移动 比较两迭代器是否相同,类的设计,template class seqlist private: int size; int current_size; t *storage; void doublespace(); public: seqlist(int s = 10):size(s) storage = new tsize; current_size = 0; seqlist() delete storage;,void push_back(const t ,class itr t *pos; public: itr(t *obj = null) pos = obj; itr ,itr begin() return itr(storage); itr end() return itr(storage + current_size); void insert(itr ,doublespace,template void seqlist:doublespace() t *tmp = storage; size *= 2; storage = new tsize; for (int i = 0; i current_size; +i) storagei = tmpi; delete tmp; ,insert,template void seqlist:insert( itr ,erase,template void seqlist:erase(const itr ,应用,int main() seqlist sq(10); seqlist:itr itr1; for (int i = 0; i 10; +i) sq.push_back(2 * i + 1); cout “用下标运算符输出:n“; for (i = 0; i 10; +i) cout sqi t; cout “用迭代器输出:n“; for (itr1 = sq.begin() ; itr1 != sq.end(); +itr1) cout *itr1 t;,输出,用下标运算符输出： 1 3 5 7 9 11 13 15 17 19 用迭代器输出: 1 3 5 7 9 11 13 15 17 19,/ 插入0,2,4,6,8,10,12,14,16,18 for (itr1 = sq.begin(), i = 0 ; i 20; +itr1, +itr1, i += 2) sq.insert(itr1, i); cout “插入0,2,4,6,8,10,12,14,16,18:n“; for (itr1 = sq.begin() ; itr1 != sq.end(); +itr1) cout *itr1 t;,输出,插入0,2,4,6,8,10,12,14,16,18： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,/删除0，2，4，6，8，10，12，14，16，18 for (itr1 = sq.begin(); itr1 != sq.end(); +itr1) sq.erase(itr1); cout “删除0，2，4，6，8，10，12，14，16，18:n“; for (itr1 = sq.begin() ; itr1 != sq.end(); +itr1) cout *itr1 t; return 0; ,输出,删除0，2，4，6，8，10，12，14，16，18： 1 3 5 7 9 11 13 15 17 19,迭代器实例 单链表中的迭代器,设计一个用单链表实现的容器。可以用迭代器访问 功能： 在迭代器指出的位置后插入一对象，迭代器指向新插入对象 删除迭代器指出的位置后的对象 迭代器的常规操作：设置迭代器的初始位置，向后移一位置，判断迭代器指向的位置是否有对象，取迭代器指向的对象。,设计考虑,链表中的每一元素存储在一个结点中，因此需要一个结点类。结点类是链表专用的，可设计成链表类的内嵌类。 与容器相关的还有一个迭代器。迭代器也是容器专用的，因此也可以设计成链表的内嵌类。,类的设计,template class linklist private: struct node elemtype data; node *next; node(const elemtype ,private: node *head; void makeempty(); public: linklist() head = new node; linklist() makeempty(); delete head;,class itr private: node *current; public: itr(node *p) current = p; bool operator()() const return current != null; bool ishead() const return current = head; const elemtype ,void insert(itr ,makeempty,template void linklist:makeempty() node *p, *q; p = head-next; head-next = null; while ( p != null) q=p-next; delete p; p = q; ,应用,int main() linklist lq; linklist:itr itr1 = lq.gethead(); for (int i = 0; i 10; +i) lq.insert(itr1, 2 * i + 1); cout “用迭代器输出:n“; for (itr1 = lq.begin() ; itr1(); +itr1) cout *itr1 t;,输出与数组实现相同,/ 插入0,2,4,6,8,10,12,14,16,18 for (itr1 = lq.gethead(), i = 0 ; i 20; +itr1, i += 2) lq.insert(itr1, i); cout “插入0,2,4,6,8,10,12,14,16,18:n“; for (itr1 = lq.begin() ; itr1(); +itr1) cout *itr1 t; /删除0，2，4，6，8，10，12，14，16，18 for (itr1 = lq.gethead(); itr1(); +itr1)