c++模板概述
一、模板简介
- 模板引入一种全新的编程思维方式,称为“泛型编程
- 强类型程序设计中,参与运算的所有对象的类型在编译时即确定下来,并且编译程序将进行严格的类型检查。为了解决强类型的严格性和灵活性的冲突。
- 强类型(静态)程序设计语言: C C++ Java C#
- 弱类型 ----->Javascript PHP lua python
-
- 弱类型(动态)程序设计语言
- 建议:每隔一年去学一种新的语言,最好是强类型和弱类型相结合。
- 为了解决强类型的严格性和灵活性的冲突。有以下3中方式解决:
-
- 为了解决强类型的严格性和灵活性的冲突。有以下3中方式解决:
-
- 带参数宏定义(原样替换)
- 重载函数(函数名相同,函数参数不同)
- 模板(将数据类型作为参数)
二、模板使用
- 模板的定义
-
- template<typename T> ---->建议使用
- template <class T>
- 1、函数模板
template <模板参数表>
返回类型 函数名(参数列表)
{
//函数体
}
- 关键字template放在模板的定义与声明的最前面,其后是用逗号分隔的模板参数表,用尖括号(<>)括起来。模板参数表不能为空。
- 模板参数的形式有两种:
-
- 类型参数,使用typename/class
- 非类型参数,整形数据,代表常量。
- 非类型参数表达式,必须是int类型,使用已知类型符,代表一个常量 。eg : template<typename T ,int num> 表示第二个参数不确定。
template <typename T>
T add(const T &a, const T &b)
{
return a + b;
}
- 模板有函数模板和类模板之分。通过参数实例化构造出具体的函数或类,称为模板函数或模板类。
- 函数模板 到 模板函数 (实例化) 需要模板参数推导,它是根据实参传递时的类型自动推导,可以理解为模板-->代码生成器。
- 函数模板是可以设置默认参数的。
- 在使用之时,若不申明类型,称隐式实例化,反之,显式实例化。add <double> (da,db) ,最好显式调用。
- 函数模板和函数是可以进行重载的。重载时,会优先执行普通函数。函数模板与函数模板之间也是可以重载的。
- 对于模板而言就可以使用, #include<add. cc>
-
- 或者在头文件里面加上 # include “add . cc”
- 对于模板而言,可以分成头文件和实现文件,但在用函数时,必须能够看到其全部的实现。
- 模板还有一种用法,模板特化(把所有的模板参数固定下来)。template < > 然后在加重载函数。另一种是,模板的偏特化(把部分模板参数固定下来)。
- 2、类模板
- 模板的套嵌可以理解成在另外一个模板里面定义一个模板。以模板(类,或者函数)作为另一个模板(类,或者函数)的成员,也称成员模板。
-
- 成员模版是不能声明为virtual的。
- 对于模板,可以深入,可参见 prime
- 模板形式的单例模式,----->面试题。
二、STL简介
- STL库是用模板(template)写出来的,模板是STL库的基础。STL大致由以下几部分组成:
-
- 容器(container) --->数据结构
- 迭代器(iterator) --->泛型的指针
- 适配器(Adapter) 又有几种适配器
- 算法(algorithm) 通过迭代器操作数据,函数模板。
- 函数对象(functor)
- 配置器(allocator) 空间内存的分配,
- 容器(container)主要介绍
-
- 序列式容器(sequential container)
- 关联式容器(associative container)
- 无序关联式容器 (Unordered associative containers)
- 容器适配器 (Container adaptors)
- 主要讨论序列式容器vector、list和deque的用法
-
- Vector(数组) deque(双端队列) list(链表)
-
- 迭代器的范围是一个左闭右开的区间。原生指针也是一种迭代器。
- vector<int>::iterator it; //该迭代器能够修改元素的值得,如果不想变化,我们一般使用,vector<int>::const_iterator it; 进行遍历。
- deque
-
- deque<int> dequeInt{1,2,3,4,5}
- deque 可以直接用下标运算符访问,[ ]
- 迭代器也可以逆序访问
- list <float> listFloat(3,5);
- list 不支持下标访问运算符。
- vector/deque 他们都实现了operator[ ],支持随机访问,说明他们能在O(1)时间找到元素。
- list不支持operator[ ] ,因为它是链表,只支持双向迭代器,访问,不能随机访问。
- 而且容器对象都能随着元素的插入和删除自动地增大,可以调用函数进行变小。()
- 类型的萃取技术。自己研究。
- 下面介绍5类相关函数
-
- 在容器尾部进行插入和删除(list、deque和vector都适用): void push_back(t)和void pop_back(void)
- 在容器头部进行插入和删除(list和deque适用,vector不适用): void push_front(t)和void pop_front(void)
- 获取容器头部和尾部元素(list、deque和vector都适用): front(void)和back(void),
- 在容器中间插入元素。有如下3种重载形式:
-
- 将元素t插到p之前,返回的迭代器指向被插入的元素。 iterator insert(iterator p, elemType t);
- 在p之前插入n个t,无返回值。 void insert(iterator p, int n, elemType t);
- 在p之前插入[first, last)之间的所有元素。 void insert(iterator p, iterator first, iterator last);
- 通过insert 可以在vector的头部可以添加元素,但不推荐,这样的时间复杂度是O(n)
- 对于deque来说,执行insert方法的时间复杂度与元素个数相关的。
- 对于list的添加元素,很快,insert 时间复杂度是O (1);
- typename 不可少
- erase删除操作,有2种重载形式:
-
- 删除迭代器p所指向的元素,返回p指向的下一个迭代器: iterator erase(iterator p);
- 删除[frist,last)之间的所有元素,返回last指向的下一个迭代器: iterator erase(iterator first, iterator last);
- clear操作:用于将容器对象清空。 void clear(void); 用法很简单。注意:对于vector而言,只清空元素,不清空内存。capacity( )函数方法只有vector 才有的方法。能用vector就用它。
- 总结:
-
- vector,类似于数组。vector是数组的类表示,它提供了自动管理内存的功能,可以动态改变vector对象的长度,并随着元素的增删而增大。提供了对元素的随机访问,和数组一样,在vector尾部添加和删除元素(push_back和pop_back)的时间是固定的,但在vector中间或头部增删元素(insert,erase)的时间和复杂度线性正比于vector容器对象中元素的多少。
- deque双端队列。deque容器对象支持下标随机访问,在deque头部和尾部添加删除元素时的时间都是固定的,因此,如果有很多操作是针对序列的头部位置的,建议使用deque容器。但是,如果是在deque的中间进行元素的增删处理,操作的复杂度和时间正比于deque对象中元素的多少。
- list类模板表示双向链表,除了首尾元素外,list容器对象中的每个元素都和前面的元素相链接。list不支持下标随机访问,只能通过迭代器双向遍历。 和vector和deque不同的是,在list的任何位置增删元素的时间都是固定的。
2、关联式容器(associative)-->有序 -->二分查找
- 关联式容器为什么要使用红黑树? 为了查找元素高效。
- 实现是 动态平衡二叉树 ----> 红黑树
-
- 特点:左右子树的高度差的绝对值不超过1
- 4种联合容器类模板:set、map、multiset和multimap。
- set中仅仅包含关键字,而没有值的概念,map中存储的是“关键字――值”对
- 4种关联式容器都会根据指定的或默认的排列函数,以关键字为索引,对其中的元素进行排序。
- set容器
-
- set内部不能存放相同的关键字,内部元素是唯一,默认情况下升序排序。比较器是 less< >
- set之中的元素都是只读的,不能进行修改。
- 可以自设定排序方式:set<int, greater<int> >
- STL提供了3种创建set的方式:
-
- 创建空set容器对象,如:set<int> obS;
- 将迭代器的区间作为参数的构造函数,如: int sz[9]={1,2,3,4,5,6,3,5,6}; set<int> A(sz,sz+9);
- 根据已有同类型的容器创建新容器,如 set<int> B(A);
- set不支持[ ]下标式的随机访问,必须通过双向迭代器访问元素。
- multiset容器
-
- 使用multiset需要包含头文件<set>。 multiset的创建方式与也是3种方式。
- multiset与set不同之处在于其允许出现相同的关键字。
- map容器
-
- 头文件<map>
- map的元素是一对对的“关键字-值”组合,“关键字”用于搜寻,而“值”用来表示我们要存取的数据。 默认情况下按照关键字以升序的方式进行排列。
- 每个关键字只能出现一次,不能重复。 可使用类模板pair<class T1,class T2>来表示map容器中形如“关键字-值”的每个元素。
- eg:pair<const int, string> t(600036,”招商银行”); cout << t.first << t.second << endl;
- //t.first表示600036,t.second表示,”
- 招商银行” 也可创建pair<class T1,class T2>的匿名元素: pair<const int, string>(600036,”招商银行”); const表示关键字是只读的。
- map支持[ ]下标式的随机访问,也支持迭代器访问元素。 重载了下标访问符,但不是随机访问,时间复杂度是log(N),于是可以通过下标访问符,添加数据。或进行修改。
- multimap容器
-
- multimap与map不同之处在于其允许出现相同的元素。此时不支持[ ]随机操作。
- 元素的插入:
- pair<iterator, bool> ob.insert(t)
-
- 适用于map和set容器。返回一个pair<iterator,bool>值,当ob中不包含t时,将t插入ob中,bool为true;否则不进行插入,bool为false。
- 创建pair时,也可以用make
- 对于比较繁琐的类型可以使用auto
- STL为所有容器定义了下列类型:
- 适配器 ----> 是一种设计模式
-
- 容器或函数对象无法直接应用于算法,因此,必须有一种中间过渡机制来实现两者的匹配,这就是适配器,本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。
- 容器适配器
-
- 标准库提供了三种默认序列容器适配器: stack(deque,list)、 queue(deque,list)、 priority_queue(vector, deque)。
- priority_queue --->堆排序 --->必须掌握
-
- 默认情况下,按照std::less 进行比较的,但元素出队时是降序排序,--->原因是优先级队列的底层是堆排序。 ---->每一次比较,都是拿堆顶元素与新元素进行比较,当满足条件时,就用新元素替换堆顶元素,
- 排 序 :
-
- 内部排序:知道所有的元素,需全部加载
内存
-
-
- 冒泡 ---> (优化)快排
-
插入排序 ----> (优化) 希尔排序
简单选择排序
归并排序
基数排序
-
- 外部排序 :不能把所有的元素全部加载到
内存
在使用模板时,可以二次赋值,因为调用的时候,需无参构造。
- 树的遍历方式: 前序遍历 中序遍历 后序遍历
- 迭代器
-
- 是容器的又高一层的抽象,迭代器是种更高层次的抽象,它使得算法独立于容器,这使得算法独立于类型。
- 迭代器对象应具备以下功能:
-
- 间接访问(*p),即deference,在迭代器类中必须对一元*操作符定义。
- 迭代器对象之间的赋值,如p=q,在迭代器类中必须对赋值操作符定义。
- 迭代器对象间的比较,比较两个迭代器是否相等,因此,在迭代器类内必须对关系运算符==和!=进行定义,原则上讲,不需要对迭代器进行大小比较(<、>)等,就像比较指针实际上是比较其中存储的地址大小一样,没有意义。
- 能使用迭代器遍历容器中所有的元素,在本章已给出的示例代码中已经大量应用了诸如“p++”之类的操作,因此,在迭代器类必须对前缀增1和后缀增1进行定义。
分类有:
不同的算法对迭代器的要求不同,为此,STL定义了5种迭代器,分别是
随机访问迭代器(RandomAccessIterator)
双向迭代器(BidirectionalIterator)
前向迭代器(ForwardIterator) 输出迭代器(OutputIterator) 输入迭代器(InputIterator)
- 随机访问迭代器 vector deque
- 双向迭代器 list ,set/map nultiset/multimap
- 前向迭代器
-
- 把输入输出流当成容器来看待
- 输出迭代器
-
- ostream_iterator
- 输入迭代器
-
- istream_iterator
- 不同的算法要求的迭代器类型不同,之所以定义了5种迭代器,是为了使用“最合适”的工具,从图中看,依照箭头的方向,迭代器实现的功能越来越少,除了输出迭代器和输入迭代器是功能相反的并列关系外,箭头左侧的迭代器不仅都实现了右侧迭代器所有的功能,而且在其基础上增加了一些功能。
- 所以说,箭头左侧的迭代器“适应”于箭头右侧的迭代器,因此,如果某个算法的形参为前向迭代器,则实参可以是双向迭代器和随机访问迭代器,但不能是输出迭代器或输入迭代器。
- 种容器迭代器中,vector和deque是随机访问迭代器,其他5种均为双向迭代器。
-
- 7种容器迭代器p均支持如下操作: *p读,*p写,++p,p++,--p,p--
- 只有vector和deque迭代器p支持如下操作:p += n和p -= n
- 输出流迭代器
- 输出流迭代器的定义为:
- ostream_iterator<class T1, class T2=char> 迭代器名(ostream_type &ost, const T2 *p=0);
- 如:ostream_iterator<int> osi(cout, "\n");
- 现在osi就是一个输出流迭代器,通过osi可使用cout输出int类型的数据,结束符为换行符。
- 输入流迭代器
- 输入流迭代器的定义为:istream_iterator<class T1,class T2=char> 迭代器名(istream_type& ist);
- 如: istream_iterator<int,char> isi(cin);
- 现在isi就是一个输入流迭代器,通过isi可使用cin接收int数据类型的键盘输入,结束符为非数字字符。
设计模式之适配器
- 泛 型 算 法
-
- STL类库中提供的一些通用的非成员函数操作。这些算法可以操作在多种容器类型上,所以称为“泛型”,泛型算法不是针对容器编写,而只是单独依赖迭代器和迭代器操作实现。
- 使用泛型算法必须先包含algorithm头文件,使用泛化的算术算法则必须包含numeric头文件: #include <algorithm> #include <numeric>
- 函数对象是可以以函数方式与( )结合使用的任意对象,包括:(functor-仿函数) 函数名; 指向函数的指针; 重载了( )操作符的类对象(即定义了函数operator( )( )的类)。
- STL将算法库分为4组,前3个在algorithm头文件中描述,而第4个在numeric头文件中描述:
-
- 非修改式序列操作:不改变容器的内容,如find()、for_each()等。
- 修改式序列操作:可以修改容器中的内容,如transform()、random_shuffle()、copy等。
- 排序和相关操作:包括各种排序函数等,如sort()等。
- 通用数字运算:计算两个容器的内部乘积等。
- lambda表达式 --->匿名函数
-
- [ ]( ){ //...... }
- remoe - erase惯用法 或者写在一起。
- 在便利容器的过程中,不建议做删除或添加元素的操作,因为,有可能导致迭代器失效。
- erase 和 remove 惯用法,常放在一起使用
- 非修改式序列操作
- for_each():将一个非修改式函数用于指定区间中的每个成员
- find():在区间中查找某个值首次出现的位置 (O(N)) 元素有序不推荐
- find_if():在区间中查找第一个满足断言测试条件的值
- find_end():在序列中查找最后一个与另一个序列匹配的值。匹配时可使用等式或二元断言
- find_first_of():在第二个序列中查找第一个与第一个序列的值匹配的元素。匹配时可使用等式或二元断言。
- adjacent_find():查找第一个与其后面的元素匹配的元素。匹配时可使用等式或二元断言。
- count():返回特定值在区间中出现的次数。
- count_if():
- mismatch():
- equal():
- search():
- search_n():
- 修改式序列操作
- copy():
- copy_backword():
- swap():
- swap_ranges():
- iter_swap():
- transform():
- replace():
- replace_if()
- remove/remove_if
- 排序和相关操作
- sort():
- stable_sort():
- partial_sort():
- nth_element():
- lower_bound():
- upper_bound():
- equal_range():
- 函数适配器
-
- bind(函数对象,指定值
- 绑定的参数的个数不受限制;对于不事先绑定的参数,需要传std::placeholders进去,从_1开始,依次递增
- bind提前绑定参数时,未提前绑定的参数所在位置需要使用站位符占住。常与function联合使用。可以把function看成是函数类型的容器。
- int (int, int)函数标签,可以看成回调函数的注册。(用函数类型创建的一个函数对象)
- 如果bind要绑定一个成员函数,需要加上取地址符号 &
- 包装器 std::cref( n) ,
- bind的占位符所在的位置代表的是形参的位置。占位符本身的数字代表的是实参传递时要绑定的实参的位置。
- bind绑定参数时,采用的是值传递,会进行复制。所以在绑定成员函数时,第一个参数尽量用对象的地址进行传递。
- 如果采用auto关键字接受bind的返回值,实参传递时个数不受限制,多余的实参是无效参数。
- bind除了能够绑定到普通函数,成员函数外还可以绑定到变量上。