由C++模板技术说开去

作者: 云中布衣   分类:  学习笔记    热度: (427℃)   时间: 2017-7-22 12:57   标签: #始于C++而不止于C++    

C++模板技术作为C++语言与众不同的特性,由它牵引出了C++中许多的东西,一直想一探究竟。趁着这个周末,花些时间好好的捋一捋~诸如模板、函数模板、类模板、泛型编程、STL技术、容器、顺序容器、关联容器、泛型算法、迭代器、适配器……接下来好好的梳理一下,它们之间的关系以及各自主要的知识点。首先用一张图来把这些概念囊括进来,刚刚画的……(参考资料《C++ Primer》《STL源码剖析》)

选区_105.png

通过上图我们可以很清楚的看到C++模板技术是实现C++ STL的基础,从实现角度来看,STL算法是一种function template(函数模板),而STL容器是一种class template(类模板)。它是泛型编程的基础,所谓泛型编程就是以独立于任何特定类型的方式编写代码。使用泛型程序时,我们需要提供具体程序实例所操作的类型或值。STL中的容器、算法和迭代器都是泛型编程的例子。每种容器(如vector)都有单一的定义,但可以定义许多不同种类的vector,他们的区别在于所包含的元素类型。

泛型编程与面向对象编程一样,都依赖某种形式的多态性。所不同的是,面向对象编程所依赖的多态性成为运行时多态,而泛型编程所依赖的多态性称为编译时多态或参数式多态性。

1.函数模板的定义

在某些情况下,我们可以为不用为每个类型定义一个新函数,而是只定义一个函数模板(function template)。函数模板是一个独立于类型的函数,可作为一种方式,产生函数的特定类型版本。例如下面名为compare的函数模板,可以比较两个值的大小,而忽略是哪种数据类型。

template <typename T>
int compare(const T &v1, const T &v2){
    if(v1 < v2) return -1;
    if(v2 < v1) return 1;
    return 0;
}
函数模板可以用与非模板函数一样的方式声明为inline。说明符放在模板形参表之后、返回类型之前,不能放在template之前。
templete <typename T> inline T min(const T&, const T&);

像函数形参一样,程序员为模板形参选择的名字没有本质含义。可以给模板形参赋予的唯一含义是区别形参是类型形参还是非类型形参。如果是类型形参,我们就知道该形参表示未知类型,如果是非类型形参,我们就知道它是一个未知值。

在函数模板形参表中,关键字typename和class具有相同的含义,可以互换使用,两个关键字都可以在同一模板形参表中使用。使用关键字typename代替关键字class指定模板类型形参也许更为直观,毕竟,可以使用内置类型(非类类型)作为实际的类型形参,而且,typename更清楚地指明后面的名字是一个类型名字。但是关键字typename是作为标准C++组成部分加入到C++中,因此旧程序更有可能只用关键字class。

2.类模板的定义

就像可以定义函数模板一样,我们也可以定义类模板。这里实现一个标准库queue类的我们自己的版本。这个自定义的Queue类必须能够支持不同类型的对象,所以将他定义为类模板(class template)。Queue类将支持的操作是标准queue类接口的子集:push、pop、front以及empty。

template <class Type> class Queue{
public:
    Queue();
    Type &front(); //return element from head of Queue
    const Type &front() const;// const member function
    void push (const Type&);
    void pop();
    bool empty() const;//true if no elements in the Queue
private:
   //...
};
类模板也是模板,因此必须以关键字template开头,后接模板形参表。Queue模板接受一个名为Type的模板形参。除了模板形参表外,类模板的定义看起来与任意其他类相似。类模板可以定义数据成员、函数成员和类型成员。也可以使用访问标号控制对成员的访问,还可以定义构造函数和析构函数等。在类和类成员的定义中,可以使用模板形参作为类型或值的占位符,在使用类时再提供那些类或值。

3.STL(Standard Template Library)

STL(Standard Template Library)亦即标准模板库,它是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov创造于1979年前后,这正是Bjarne Stroustrup创造C++的年代。虽然David R.Musser于1971年开始即在计算机几何领域中发展并倡导某些泛型程序设计观念,但早期并没有任何程序语言支持泛型编程。第一个支持泛型概念的语言是Ada。

1992年Meng Lee加入Alex的项目,成为STL的另一个主要贡献者。

1993年9月,Alexander Stepanov和它一手创建的STL,与C++标准委员会有了第一次接触。

1994年1月6日Alexander收到Andy Koening(C++标准委员会成员)来信,言明希望STL成为C++标准程序库的一部分。

1994年3月的圣地亚哥会议。STL在会议上获得很好的回应,但也有许多反对意见。

1998年9月,STL成为C++标准规格中的C++标准程序库的一大脉系。

STL虽然是一套程序库,却只是一般印象中的程序库,而是一个有着划时代意义,背后拥有先进技术与深厚理论的产品。说他是产品也可以,说他是规格也可以,说他是软件组件技术发展史上的一个大突破点,它也当之无愧。

长久以来,软件届一直希望建立一种可重复运用的东西,以及一种得以制造出可重复运用的东西的方法,让工程师/程序员的心血不至于随时间迁移、人事异动、私心欲念、人谋不藏而烟消云散。从子程序、程序、函数、类,到函数库、类库、各种组件,从结构化设计、模块化设计、面向对象设计,到模式的归纳整理,无一不是软件工程的慢慢奋斗史。STL正是在这种追求下,为了建立数据结构和算法的一套标准,并且降低其间的耦合(coupling)关系以提升各自的独特性、弹性、交互操作性(interoperability),C++社群里诞生了STL。

STL由六大组件组成,它们分别是:容器(containers)、算法(algorithms)、迭代器(iterators)、仿函数(functors)、适配器(adapters)以及配置器(allocators)。这六者的关系可以这么描述:Container 通过Allocator取得数据存储空间,Algorithm通过Iterator存取Container内容,Functor可以协助Algorithm完成不同的策略变化,Adapter可以修饰容器或仿函数或迭代器。

4.顺序容器(sequential container)

顺序容器内的元素是按其位置存储和访问。在此之前我们已经使用过一种顺序容器类型:标准库的vector类型。它将单一类型元素聚集起来成为容器,然后根据位置来存储和访问这些元素。顺序容器的元素排列次序与元素无关,而是由添加元素到容器的次序决定的。标准库定义了三种顺序容器类型:vector、list和deque。他们的差别在于访问元素的方式,以及添加或删除元素相关操作的运行代价。标准库还提供了三种容器适配器(adaptor)。实际上,适配器是根据原始的容器类型所提供的操作,通过定义新的操作接口,来适应基础的容器类型。顺序容器适配器包括:stack、queue和priority_queue类型。

容器元素的初始化(构造函数
C<T> c;
创建一个名为c的空容器。适用于所有容器)
C<T> c(c2);
创建容器c2的副本c,其中c和c2必须要有相同的容器类型。适用于所有容器
C<T> c(b,e);
创建c,其元素是迭代器b和e标示范围内元素的副本。(适用于所有容器
C<T> c(n,t);
创建c,其元素是n个值为t的序列。(只适用于顺序容器
C<T> c(n);
创建有n个值初始化元素的容器c。(只适用于顺序容器
在整个标准库中,经常使用形参为一对迭代器的构造函数。每种容器迭代器都提供若干共同工作的迭代器类型,与容器类型一样,所有迭代器具有相同接口。比如,所有容器迭代器都支持以解引用运算从容器中读入数据,而且容器也提供自增和自减操作来支持从一个元素到下一个元素的访问。C++语言使用一对迭代器标记迭代器范围(iterator range),这两个迭代器分别指向同一个容器的两个元素或超出末端的下一个位置,此类元素范围成为左闭合区间。迭代器作为容器的类型之一,它提供容器的元素的操作的基础,是STL中容器和算法的纽带。

容器定义的类型别名
size_type
无符号整型,足以存储此容器类型的最大可能容器长度
iterator
此容器类型的迭代器类型
const_iterator
元素的只读迭代器类型
reverse_iterator
按逆序寻址元素的迭代器
const_reverse_iterator
元素的只读逆序迭代器
difference_type
足够存储两个迭代器差值的有符号整型,可为负数
value_type
元素类型
reference
元素的左值类型,是value_type&的同义词
const_reference
元素的常量左值类型,等效于const value_type&
begin()、end()、rbegin()、rend()是容器的四个操作用来标记首尾位置。begin和end操作产生指向容器内第一个元素和最后一个元素的下一个位置的迭代器。

在顺序容器中添加元素的操作
c.push_back(t)
在容器c的尾部添加值为t的元素。返回void类型
c.push_front(t)
在容器c的前端添加值为t的元素。返回void类型(于list和deque容器类型)
c.insert(p,t)
在迭代器p所指向的元素前面插入值为t的新元素。返回指向新添加元素的迭代器
c.insert(p,n,t)
在迭代器p所指向的元素前面插入n个值为t的新元素。返回void类型
c.insert(p,b,e)
在迭代器p所指向的元素前面插入由迭代器b和e标记的范围内的元素。返回void

所有容器类型都提供了四种与容器大小相关的操作。

顺序容器的大小操作
c.size()
返回容器c中的元素个数。返回类型为c::size_type
c.max_size()
返回容器可容纳最多元素的个数。返回类型是C::size_type
c.empty()
返回标记容器大小是否为0的布尔值
c.resize(n)
调整容器c的长度大小,使其能容纳n个元素。如果n<c.size(),则删除多出的元素。否则添加,采用值初始化的新元素
c.resize(n,t)
调整容器c的大小,使其能容纳n个元素。所有新添加的元素值都为t
前面我们知道对容器的迭代器作解引用可以获得容器中相应元素的值。另一种情况,如果容器非空,那么容器类型front和back成员方法将返回容器内第一个或最后一个元素的引用。

访问顺序容器内元素的操作
c.back()
返回容器c的最后一个元素的引用。如果c为空,则该操作未定义
c.front()
返回容器第一个元素的引用。如果容器为空,则操作未定义
c[n]
返回下标为n的元素的引用。只适用于vector和deque容器)
c.at(n)
返回下标为n的元素的引用。如果越界则该操作未定义。只适用于vector和deque容器)
前面我们提到容器提供了通用的insert操作在容器的任何位置插入元素,并支持特定的push_front和push_back操作在容器首部或尾部插入新元素。类似的容器类型也提供了通用的erase操作和特定的pop_front和pop_back操作来删除容器内的元素。

删除顺序容器内的元素
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容器
与赋值相关的操作符都作用于整个容器。出swap操作外,下表的其他赋值操作都可以用erase和insert操作来实现。赋值操作符首先删除其左操作数容器中的所有元素,然后将右操作数容器的所有元素插入到左边的容器中。赋值后,左右两边的容器相等:尽管赋值前两个容器可能不相等,但赋值后两个容器都具有右操作数的长度。

顺序容器的赋值操作
c1=c2
删除容器c1中所有元素,然后将c2的元素复制给c1。c1和c2的类型必须相同
c1.swap(c2)

交换内容:调用完函数,c1中存放是c2原来的元素,c2中存放的则是c1原来的元素。c1和c2的类型必须相同。

c.assign(b,e)
重新设置c的元素:将迭代器b和e标记范围内的所有元素赋值到c中。b和e必须不是指向c中元素的迭代器
c.assign(n,t)
将容器c重新设置为存储n个值为t的元素

除了顺序容器,标准库还提供了三种顺序容器适配器:queue、priority和stack。适配器(adaptor)是标准库中通用的概念,包括容器适配器、迭代器适配器和函数适配器。本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已经存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如stack适配器可使任何一种顺序容器以是栈的方式工作。

适配器通用的操作和类型
size_type
一种类型,足以存储此适配器类型最大对象的长度
value_type
元素类型
container_type
基础容器的类型,适配器在此容器类型上实现
A a
创建一个新的适配器,命名为a
A a(c)
创建一个名为a的新适配器,初始化为容器c的副本
关系操作符
所有适配器都支持全部关系操作符:==、!=、<、<=、>、>=
默认的stack和queue都基于deque容器实现,而priority_queue则在vector容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型。

其中栈提供的所有的操作共五种:s.empty,s.size(),s.pop(),s.top(),s.push(item)。

队列和优先级队列支持的共同操作为:q.empty(),q.size(),q.pop(),q.push(item)。

仅适用于队列的操作为q.front(),q.back()。

仅适用于priority_queue的操作为q.top()。

4.关联容器(associative container)

标准容器另一个重要内容就是关联容器。关联容器和顺序容器的本质差别在于:关联容器通过键(key)存储和读取元素,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。关联容器的大部分行为与顺序容器相同,其独特之处在于支持键的使用。两个基本的关联容器是map和set。map的元素以键-值(key-value)对的形式组织,键用作元素在map中的索引,而值表示所存储和读取的数据。set仅包含一个键,并有效地支持关于某个键是否存在的查询。

关联容器类型
map
关联数组,元素通过键来存储和读取
set
大小可变的集合,支持通过键实现的快速读取
multimap
支持同一个键多次出现的map类型
multiset
支持同一个键多次出现的set类型
5.泛型算法(generic algorithm)

标准容器定义的操作非常的少。标准库并没有给容器添加大量的功能函数,而是提供一组算法,这些算法大都不依赖特定的容器类型(是泛型)可作用在不同类型的容器和不同类型的元素上。大部分容器都支持添加和删除元素,访问第一个和最后一个元素。获取容器的大小,并在某些情况下重设容器的大小。以及获取指向第一个元素和最后一个元素的下一位置的迭代器。可以想象,用户可能还希望对容器元素进行更多其他有用的操作:也许需要给顺序容器排序,或者查找某个特定的元素,或者查找最大或最小的元素,等等。标准库并没有为每种容器都定义实现这些操作的成员函数,而是定义了一组泛型算法(generic algorithm):因为它们实现共同的操作,所以称之为算法。而泛型指的是他们可以操作在多种容器类型上,不但可以作用于vector或list这些标准类型库,还可以用在内置数组类型、甚至其他类型的序列上。甚至自定义的容器类型只要与标准库兼容,同样也可以使用这些泛型算法。大多数算法是通过遍历由两个迭代器标记的一段元素来实现其功能。

(完)

56.8K

发表评论:

© 云中布衣 2015 | Driven by EMLOG  | SiteMap | RunTime: 7.76ms RSS  | MORE  |   | TOP

文章数量【258】 评论数量【238】 稳定运行【1208天】

Visitor IP Address【54.146.195.24】

Email:ieeflsyu#outlook.com