c教程-容器和算法.ppt

C+编程 2 第三部分 容器和算法 预习检查: 1 标准库定义那几种顺序容器? 2 list容器支持随机访问吗? 3 第三部分 容器和算法 第一节 顺序容器（sequential container）。它将单一类型元素 聚集起来成为容器，然后根据位置来存储和访问这些元 素，这就是顺序容器 标准库定义了三种顺序容器类型：vector、list 和deque Vector相当于c语言中的数组, list相当于c语言中的链表, 而deque则是双端可以插入的vector 4 第三部分 容器和算法 5 第三部分 容器和算法 容器的容器 vector lines; / vector of vectors 迭代器和迭代器范围 *iter 返回迭代器 iter 所指向的元素的引用 iter-mem 对 iter 进行解引用，获取指定元素中名 为 mem 的成员, 等效于(*iter).mem 6 第三部分 容器和算法 vector 和 deque支持通过元素位置实现的随机访问， 因此它们的迭代器可以有效地实现算术和关系运算 用于计算 vector 对象的中点位置： vector:iterator iter = vec.begin() + vec.size()/2; 7 第三部分 容器和算法 list 容器的迭代器既不支持算术运算（加法或减法）， 也不支持关系运算（=, ），它只提供前置和后 置的自增、自减运算以及相等（不等）运算。 /copy elements from vec into ilist list ilist(vec.begin(), vec.end(); ilist.begin() + ilist.size()/2; / error: no addition on list iterators 8 第三部分 容器和算法 在顺序容器中的操作 将元素值复制到容器里 c.push_back(t) /顺序容器都支持的操作 c.push_front(t) 只适用于 list 和 deque 容器类型. c.insert(p,t) 在迭代器 p 所指向的元素前面插入值为 t 的新元素 9 第三部分 容器和算法 访问元素 访问顺序容器内元素的操作 c.back() 返回容器 c 的最后一个元素的引用。 c.front() 返回容器 c 的第一个元素的引用 cn 返回下标为 n 的元素的引用只适用于 vector 和 deque 容器 c.at(n) 返回下标为 n 的元素的引用 只适用于 vector 和 deque容 器 程序员必须保证在指定下标位置上的元素确实存在。下标操作符 本身不会做相关的检查 10 第三部分 容器和算法 删除元素 c.erase(p) 删除迭代器 p 所指向的元素 返回一个迭代器，它指向 被删除元素后面的元素 c.erase(b,e) 删除迭代器 b 和 e 所标记的范围内所有的元素 c.clear() 删除容器 c 内的所有元素。返回 void c.pop_back() 删除容器 c 的最后一个元素。返回 void。 c.pop_front() 删除容器 c 的第一个元素。返回 void。 只适用于 list 或 deque 容器 删除容器内的一个元素 删除一部分元素erase 操作也不ty会检查它 的参数。程序员必须确保用作参数的迭代器或迭代器范围是有效 的 11 第三部分 容器和算法 赋值与swap c1 = c2 删除容器 c1 的所有元素，然后将 c2 的元素复制给 c1 c1.swap(c2) 交换内容：调用完该函数后，c1 中存放的是 c2 原来 的元素，c2 中存放的则是 c1 原来的元素。c1 和 c2 的类型必须 相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快 12 第三部分 容器和算法 选择容器类型的法则： 1. 如果程序要求随机访问元素，则应使用 vector 或 deque 容器。 2. 如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。 3. 如果程序不是在容器的中间位置，而是在容器首部或尾部插入 或删除元素，则应采用 deque 容器。 13 第三部分 容器和算法 容器的总结 标准库的顺序容器有三个类型 vecotor : 支持随机访问 list: 不支持随机访问 deque: 支持随机访问 容器的常用操作 插入: push_back(), insert() 删除: erase() 访问: back() 14 第三部分 容器和算法 使用泛型算法必须包含 algorithm 头文件：#include 标 准库还定义了一组泛化的算术算法 #include 算法accumulate int sum = accumulate(vec.begin(), vec.end(), 42); /sum 设置为 vec 的元素之和再加上 42 string sum = accumulate(v.begin(), v.end(), string(“); 算法replace replace(ilst.begin(), ilst.end(), 0, 16);/把0替换为16 算法count int times = count(ivec.begin(), ivec.end(), 0); /统计出现的次数 15 第三部分 容器和算法 排序算法 bool cmp(int i, int j) return ij; int main() vector vec; for(int i=10; i-1; i-) vec.push_back(i); sort(vec.begin(), vec.end(), cmp); for(int i=0; ij; int main() vector vec; for(int i=10; i-1; i-) vec.push_back(i); sort(vec.begin(), vec.end(), cmp); for(int i=0; i vec; for(int i=0; i:iterator it = find_if(vec.begin(), vec.end(), find_5); if(it!=vec.end() cout j; int main() vector vec; for(i