《set,map和vector讲解课件》由会员分享，可在线阅读，更多相关《set,map和vector讲解课件（36页珍藏版）》请在金锄头文库上搜索。
1、衡阳师范学院计算机系,1,STL在C+中称为标准模板库。STL定义了一系列用途广泛的模板类和模板函数，它们可以用来实现许多通用的算法和数据结构。,衡阳师范学院计算机系,2,标准模板库STL的核心内容是3个基本组件：容器、算法和迭代器。STL将这些组件结合在一起为许多程序设计难题提供实际可行的解决办法。,衡阳师范学院计算机系,3,Set集合容器,衡阳师范学院计算机系,4,set集合容器实现了红黑树(Red-Black Tree)的平衡二叉树的数据结构，在插入元素时，它会自动调整二叉树的排列，把该元素放到适当的位置。以确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树的键值；另外，还得
2、确保左子树的高度与右子树的高度相等，这样，二叉树的高度最小，从而检索速度最快。 注意：set集合不会重复插入相同键值的元素，采取忽略处理。,衡阳师范学院计算机系,5,26,12,37,6,16,29,32,2,15,20,30,80,上图是一个典型的平衡检索二叉树,衡阳师范学院计算机系,6,平衡二叉检索树的检索使用中序遍历算法，检索效率高于vector、deque和list等容器。,Set 的特点,set容器中，插入元素时，就会自动将元素按键值由小到大的顺序排列，并没有重复的键值。 对于set容器中的键值，不可直接去修改。所以，构造set集合的主要目的就是为了快速检索。,衡阳师范学院计算机系,
3、8,创建一个set集合对象 #include using namespace std; set v1; set v2;,衡阳师范学院计算机系,9,采用insert()方法插入元素 采用insert()方法把元素插入集合中去，插入的具体规则在默认的比较规则下，是按元素值从小到大插入。 set1-1.cpp,衡阳师范学院计算机系,10,采用insert()方法插入元素 采用insert()方法把元素插入集合中去，如果自己指定了比较规则的函数，则按自定义比较规则函数插入。 set1-2.cpp,衡阳师范学院计算机系,11,采用insert()方法插入元素 如果元素是结构体，可以直接把比较函数写在结构
4、体内。 set1-3.cpp,衡阳师范学院计算机系,12,元素的反向遍历 使用反向迭代器reverse_iterator可以反向遍历元素，输出的结果正好是集合元素的反向排序结果。它需要用到rbegin()和rend()两个方法，它们分别给出了反向遍历的开始位置和结束位置。 set2.cpp,衡阳师范学院计算机系,13,元素的删除遍历 与插入元素的处理一样，集合具有高效的删除处理功能，并自动重复调整内部的红黑树的平衡。删除的对象可以是某个迭代器位置上的元素、等于某键值的元素、一个区间上的元素和清空集合。 set3.cpp,衡阳师范学院计算机系,14,元素的检索 使用find()方法对集合进行搜索
5、，如果找到查找的键值，则返回该键值的迭代器位置，否则，返回集合最后一个元素后面的一个位置，即end()。 set4.cpp,衡阳师范学院计算机系,15,Map映照容器,衡阳师范学院计算机系,16,map容器中的元素数据是由一个键值和一个映照数据组成的，键值与映照数据之间具有一一映照的关系。插入元素的键值不允许重复，比较函数只对元素的键值进行比较。元素的各项数据可通过键值检索出来。,衡阳师范学院计算机系,17,map映照容器的内部结构也是平衡二叉检索树。元素数据按照从小到大的顺序排列。,衡阳师范学院计算机系,18,使用map容器，需要头文件包含声明“#include”。,衡阳师范学院计算机系,1
6、9,Map创建、元素插入和遍历访问 创建map对象，键值与映照数据的类型由自己定义。在没有指定比较函数时，元素的插入位置是按键值从小到大的。 map1.cpp,衡阳师范学院计算机系,20,删除元素 map映照容器用erase()删除元素函数可以删除某个迭代器位置上的元素、等于某个键值的元素、一个迭代器区间上的所有元素，当前，也可以用clear()方法清空map映照容器。 map2.cpp,衡阳师范学院计算机系,21,元素反向遍历 可以用反向迭代器reverse_iterator反向遍历map映照容器中的数据，它需要rbegin()方法和rend()方法指出反向遍历的起始位置和终止位置。 map
7、3.cpp,衡阳师范学院计算机系,22,元素的搜索 使用find()方法来搜索某个键值，如果搜索到了，则返回该键值所在的迭代器的位置，否则，返回end()迭代器的位置。由于map采用平衡搜索二叉树数据结构来实现，所以搜索速度是极快的。 map4.cpp,衡阳师范学院计算机系,23,自定义比较函数 在定义map的时候，如果没有指定比较函数，那么采用默认的比较函数，即按键值由小到大的顺序插入元素。在很多情况下，可以根据需要自己编写比较函数。 map5.cpp,衡阳师范学院计算机系,24,Vector容器,衡阳师范学院计算机系,25,动态数组vector容器 动态数值是指可以根据需要改变大小的数组。
8、虽然在C+中数组的大小在编译时是固定的，因为程序在运行时不能改变数组的大小来适应程序需求。然而，vector可以根据需要来分配内存，从而解决这个问题。虽然vector是动态的，你仍然可以使用标准的数组下标运算来访问数组中的元素。,衡阳师范学院计算机系,26,创建一个vector对象 #include using namespace std; vector v1; vector v2; vectorv3;,衡阳师范学院计算机系,27,向vector对象中添加数值 v1.push_back(0); v1.push_back(1); for (i=2; i=10;i+) v1.push_back(i
9、);,衡阳师范学院计算机系,28,获得vector对象的大小 v1.size() for (i=0; iv1.size();i+) cout v1i “ “;,衡阳师范学院计算机系,29,创建vector对象的迭代器 #include using namespace std; vector:iterator p,衡阳师范学院计算机系,30,获得vector对象中第一个和最后一个元素 vector:iterator p = v1.begin(); vector:iterator p = v1.end();,衡阳师范学院计算机系,31,在vector对象中插入元素； vector:iterator
10、 p = v1.begin(); p = p+2; int a10; v1.insert(p, a , a+10);,衡阳师范学院计算机系,32,在vector对象中删除元素； v1.erase(p, p+3); v1.pop_back();,衡阳师范学院计算机系,33,修改vector对象中的内容； v11 = v11 * v11 v12 = v12 + 100,衡阳师范学院计算机系,34,使用sort排列算法 #include sort(v.begin(),v.end();,衡阳师范学院计算机系,35,使用reverse反向排列算法 #include reverse(v.begin(),v.end();,衡阳师范学院计算机系,36,清除vector对象中的所有内容； v.clear(),
