模板 函数模板使用泛型来定义函数,通过将类型作为函数参数传递给模板,可以使编译器生成该类型的函数,可以使用class来来创建模板 template <typename anytype>
STL组件之容器 定义:容器就是用来存放其他对象的一种对象类型,他可以持有其他对象或者对象的指针,并且还能对这些对象进行一些操作,包含了对这些对象进行处理的一些方法。 常见容器:vector - 容器 deque-双端数组 stack-栈模型 queue-队列模型 list-链表类型 priotriy_deque 优先级队列 set与multiset - 容器 map与multimap容器 容器分类: 1.顺序容器:是一种各个元素之间有顺序关系的线性表,顺序性容器里的每个元素都有其固定的位置,顺序容器里面的元素之间的次序跟袁旭大小无关,而是由元素添加到容器里面的次序决定的,顺序容器包括vector(向量)、list(列表)、deque(队列) 2.关联容器:关联式容器是非线性的树结构,更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系,也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能,这样迭代器就能根据元素的特点“顺序地”获取元素。元素是有序的集合,默认在插入的时候按升序排列。关联容器包括:map(集合)、set(映射)、multimap(多重集合)、multiset(多重映射)。 3.本质上,适配器是使一种不同的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口,它本身不能直接保存元素,它保存元素的机制是调用另一种顺序容器去实现,即可以把适配器看作“它保存一个容器,这个容器再保存所有元素”。STL 中包含三种适配器:栈stack 、队列queue 和优先级队列priority_queue 。
1.顺序容器 vector - 是一个动态数组,在内存中具有连续的存储空间,支持快速随机访问,因为有一片连续的存储空间,所以在元素的插入和删除操作上,速率较慢。 vecor容器有多个构造函数,其中默认的构造函数是创建一个初始长度为0的空间,并且分配的数组长度是以二的倍数来分配的,在push_back()添加元素的过程中,如果出现内存不足的情况下,就会重新分配一段连续的内存空间,并且新的内存空间是原来内存的两倍,然后再将原来的元素复制到新的内存空间中。 vector的另一个问题就是clear操作,这个操作只是把vector的size设置为0,但是内存中的数据依旧存在,现在经常用的元素是用swap函数来解决
vector的基本用法:
front(); 返回头部元素的引用,可以当左值
back();返回尾部元素的引用,可以当左值
push_back();添加元素,只能尾部添加
pop_back();移除元素,只尾部移除
erase(iterator) 是根据位置进行删除,如果想要删除某个元素,需要找到当前元素的迭代器位置,再进行删除
insert();根据迭代器在相应的位置插入元素
1 vector<int> vec1; //初始化vector 2 vec1.push_back(100); //添加元素 3 int size = vec1.size(); //元素个数 4 bool isEmpty = vec1.empty(); //判断是否为空 5 cout<<vec1[0]<<endl; //获得第一个元素 6 vec1.insert(vec1.end(),5,3); //从vec1.back位置插入5个值为3的元素 7 vec1.pop_back(); //删除末尾元素 8 vec1.erase(vec1.begin(),vec1.end);//删除之间的元素,向前移动 9 cout<<(vec1 == vec2?true:false);//判断是否相等 10 vector<int>::iterator iter = vec1.begin(); //获取迭代器首地址 11 vector<int>::const_iterator c_iter = vec1.begin(); //获取const类型迭代器 12 vec1.clear(); //清空元素
vector的初始化方式:
vector<int> vec1; //默认初始化 vec为空 vector<int> vec2(vec1); //使用vec1初始化vec2 vector<int> vec3(vec1.begin(),vec1.end()); //使用vec1初始化vec3 vector<int> vec4(10); //10个值为0的元素 vector<int> vec5(10,4); //10个值为4的元素 vector<string> vec6(10,"null"); //10个值为null的元素 vector<string> vec7(10,"hello"); //10个值为hello的元素
vector的遍历有多种方式,可以根据[]或者迭代器遍历。
需要注意的是:
[]方式,如果越界或出现其他错误,不会抛出异常,可能会崩溃,可能数据随机出现
at方式,如果越界或出现其他错误,会抛出异常,需要捕获异常并处理
迭代器提供了逆向遍历,可以通过迭代器来实现逆向遍历,当然上面两种方式也可以
2.deque deque与vector类似,支持快速随机访问,不过deque支持双端插入插入数据,而vector只能在尾端插入数据。 deque内部的空间是小片连续的,小片间用链表相连,实际上内部有一个map的指针,deque重新分配空间比vector快,重新分配空间后,原有的数据不需要拷贝,与vector不同的是,deque还支持从开始端插入数据:push_front()。其余类似vector操作方法的使用。 push_back 从尾部插入元素 push_front 从头部插入元素 pop_back 从尾部删除元素 pop_front 从头部删除元素
distance
函数可以求出当前的迭代器指针it距离头部的位置,也就是容器的指针
用法: distance(v1.begin(), it)
3.list list是一个双向链表,因此他的内存空间是不连续的,通过指针来进行元素的访问,这使得list的随机存储变得十分低效,list可以支持任意地方的数据的存储和删除,十分方便,只需要移动相应的指针就行了
list的初始化方式:
list<int> list1; //创建一个空list list<int> list2(3);//创建含有三个元素的list list<int> list3(3,2);//创建含有三个元素值为2的list list<int> lst4(lst2); //使用lst2初始化lst4 list<int> lst5(lst2.begin(),lst2.end()); //同lst4
list的常见操作:
1 lst1.assign(lst2.begin(),lst2.end()); //分配值 2 3 4 lst1.push_back(10); //添加值 5 6 7 lst1.pop_back(); //删除末尾值 8 9 10 lst1.begin(); //返回首值的迭代器 11 12 13 lst1.end(); //返回尾值的迭代器 14 15 16 lst1.clear(); //清空值 17 18 19 bool isEmpty1 = lst1.empty(); //判断为空 20 21 22 lst1.erase(lst1.begin(),lst1.end()); //删除元素 23 24 25 lst1.front(); //返回第一个元素的引用 26 27 28 lst1.back(); //返回最后一个元素的引用 29 30 31 lst1.insert(lst1.begin(),3,2); //从指定位置插入3个值为2的元素 32 33 34 lst1.rbegin(); //返回第一个元素的前向指针 35 36 37 lst1.remove(2); //相同的元素全部删除 38 39 40 lst1.reverse(); //反转 41 42 43 lst1.size(); //含有元素个数 44 45 46 lst1.sort(); //排序 47 48 49 lst1.unique(); //删除相邻重复元素
选择顺序容器的原则:
1.高效的随机存储,并且不考虑插入和删除数据的效率,可以选择vector
2.大量的插入和删除操作,而不关心存储,用list
3.需要随机存储,并且关心两端的插入和删除,选择deque
2.关联容器 关联容器里面的元素是按照关键字来保存和访问的,相反,顺序容器是按照他们在容器中的位置来保存和访问的。 关联容器支持高效的关键字查找和访问,两个主要的关联容器是map和set 在使用关联容器时,它的键不但有一个类型,而且还有一个相关的比较函数。所用的比较函数必须在键类型上定义严格弱排序(strict weak ordering):可理解为键类型数据上的“小于”关系,虽然实际上可以选择将比较函数设计得更复杂。 对于键类型,唯一的约束就是必须支持 < 操作符,至于是否支持其他的关系或相等运算,则不作要求
1.map map容器提供一个键值对容器,map与multimap差别仅仅在于multiple允许一个键对应多个值,对于迭代器来说,可以修改实值的内容,不能修改key值,map容器会根据key值排序。 map 是键-值对的集合。map 类型通常可理解为关联数组:可使用键作为下标来获取一个值,正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置来获取。map内部自建一棵红黑树(一种自平衡二叉树),这棵树具有数据自动排序的功能,所以在map内部所有的数据都是有序的,以二叉树的形式进行组织。
map的定义与初始化:
1 map<k,v> m; //创建一个空的map对象,其键和值的值为k,v 2 map<k,v> m(m2);//创建m2的副本m,与m具有相同的键值 3 map<k, v>m(b, e);//创建map类型的对象m,存储迭代器b和e标记的范围内所有元素的副本。元素的类型必须能转换为pair<const k, v>
map添加元素:
1 m.insert(e);//e是一个用在m上的value_type 类型的值。如果键(e.first不在m中,则插入一个值为e.second 的新元素;如果该键在m中已存在,则保持m不变。该函数返回一个pair类型对象,包含指向键为e.first的元素的map迭代器,以及一个 bool 类型的对象,表示是否插入了该元素 2 m.insert(beg,end);//beg和end是标记元素范围的迭代器,其中的元素必须为m.value_type 类型的键-值对。对于该范围内的所有元素,如果它的键在 m 中不存在,则将该键及其关联的值插入到 m。返回 void 类型 3 m.insert(iter,e);//e是一个用在m上的 value_type 类型的值。如果键(e.first)不在m中,则创建新元素,并以迭代器iter为起点搜索新元素存储的位置。返回一个迭代器,指向m中具有给定键的元素
map删除元素:
m.erase(k);//删除m中键为k的元素。返回size_type类型的值,表示删除的元素个数 m.erase(p);//从m中删除迭代器p所指向的元素。p必须指向m中确实存在的元素,而且不能等于m.end()。返回void m.erase(b,e);//从m中删除一段范围内的元素,该范围由迭代器对b和e标记。b和e必须标记m中的一段有效范围:即b和e都必须指向m中的元素或最后一个元素的下一个位置。而且,b和e要么相等(此时删除的范围为空),要么b所指向的元素必须出在e所指向的元素之前。返回 void 类型
map遍历元素:
map提供两个函数来进行key的查找,find和equal_range;
m.count(k);//返回 m 中 k 的出现次数 m.find(k);//如果m容器中存在按k索引的元素,则返回指向该元素的迭代器。如果不存在,则返回超出末端迭代器。
map和multimap的区别:
multimap支持多个键值,multimap提供了cout函数来计算同一个key的元素个数
2.set set也是一种关联性容器,底层也是用红黑树实现的,插入删除操作只需要移动指针,不设计内存的移动和拷贝,所以效率较高 set的含义是集合,他是一个有序的容器,里面的元素都是排好序的,支持插入删除查找等操作,像一个集合一样,所有的操作都是在long时间内完成的,效率非常高。 set中的元素是唯一的,默认情况下会自动升序排列,set和multiset的区别是:set插入的元素不能相同,但是multiset可以相同。Set默认自动排序。使用方法类似list。 并且在set中,不能直接改变元素值,这样子会改变元素原本的顺序,要想改变元素值,必须先删除旧元素值,再插入新元素,不提供直接存取元素的任何操作函数,只能通过迭代器进行间接存取。
set的定义和使用:set本质上是一个有序的集合,默认的顺序是从小到大的
1 创建集合的方式: 2 set<int>创建默认的从小到大的int类型的集合 3 set<int,less<int>>创建一个从小到大的int类型的集合 4 set<int,greater<int>>创建一个从大到小的int类型的集合 5 上面的less和greater就是仿函数,集合会根据这个仿函数的返回值是否为真类进行排序。
set添加和删除元素:set提供了insert
和erase
函数,用来对元素进行插入和删除操作。
1 set<string> set1; 2 3 set1.insert("the"); //第一种方法:直接添加 4 5 set<int> iset2; 6 7 iset2.insert(ivec.begin(), ivec.end());//第二中方法:通过指针迭代器 8 9 //删除集合 10 while(!set1.empty()) 11 { 12 //获取头部 13 set<int>::iterator it = set1.begin(); 14 15 //打印头部元素 16 cout << *it << endl; 17 18 //从头部删除元素 19 set1.erase(set1.begin()); 20 }
set获取元素:不提供直接存取元素的任何操作函数,只能通过迭代器进行间接存取。
set 容器不提供下标操作符。为了通过键从 set 中获取元素,可使用 find运算。
1 set<int> iset; 2 3 for(int i = 0; i<10; i++)iset.insert(i); 4 5 iset.find(1) // 返回指向元素内容为1的指针 6 7 iset.find(11) // 返回指针iset.end() 8 9 iset.count(1) // 存在,返回1 11 iset.count(11) // 不存在,返回0
适配器(Adaptors)是标准库中的一个通用概念,容器、迭代器和函数都有适配器。本质上,一个适配器是一种机制,能使某种事物的行为看起来像另外一种事物一样。
一个容器适配器(Container adaptors)接受一种已有的容器类型,使其行为看起来像一种不同的类型。标准库定义了三个序列容器适配器:stack、queue和priority_queue。