C++课件第8章泛型2

第八章泛型2----数组与字符串这一章的内容包括：数组：C/C++数组的一些特性向量：了解STL。字符串：了解STL。一、数组1.C语言数组的基本特性C语言数组有以下一些特性：数组的长度是固定的，数组一经创建，就不允许动态的修改长度。数组的本质是指针。可以使用下标和指针遍历和检索数组中的元素。这两种方式都不检查数组越界，这即带来灵活性又带来内存安全隐患。如果需要更改数组的长度,就必须再声明一个更大的数组（如果该数组即未指定长度也未初始化，或干脆用指针变量代替该数组，还要用malloc（）为其分配内存）,把原来数组的内容copy到新数组中去。否则可能会产生内存安全隐患。数组a的内容复制给数组b，不能用b=a（数组浅拷贝）。应该用标准库函数strcpy（）进行复制（数组深拷贝）。比较b和a的内容是否相同，不能用if(b==a)来判断，应该用标准库函数strcmp（）进行比较。2.C语言数组的内存分配在用C语言实际编程时，常要建立很大的数组（比如电子游戏地图），我们必需要对C语言数组内存分配有了解。看下面的例子：//全局（变量）数组，编译器在堆中分配内存inta1[100000];//全局（变量）数组，编译器在堆中分配内存staticinta2[100000];main(){//局部数组，编译器在栈中分配内存inta3[100];//局部静态数组，编译器在堆中分配内存ststicinta4[100];}intfun(){//局部数组，编译器在栈中分配内存inta5[100];//局部静态数组，编译器在堆中分配内存ststicinta6[100];}//上面例子的数组都是由编译器分配/去配内存，不用程序员干预。程序员干预数组内存分配会怎么样？可以用malloc（）为数组分配内存，free（）去配内存。凡是使用malloc（）分配内存的，无论是全局数组还是局部数组，都是堆分配。上面的例子告诉我们，对大数组内存分配不当容易造成栈溢出。解决办法有两个：或将数组定义为全局的（堆分配），或使用malloc（）为数组分配内存（此时数组可以是局部的）Q1：了解C语言大数组内存分配的两种解决办法。3.C++数组的基本特性C++数组保留了上述C语言数组的特性，还有一些面向对象的升级，主要有：可以用new为数组分配内存，用delete去配内存。比如：char*p1=newchar[10000];deletep1；其使用条件和原则与使用malloc（）基本一致。用new分配内存的数组建在堆上，无论数组是全局的还是局部的。可以定义对象数组，即数组元素都是对象。不推荐使用。二、向量（vector）因为数组存在内存安全隐患，所以C++最好使用vector，避免使用低级的数组和指针，只有在强调速度时，才使用它们。vector是C++STL（标准模板库）的一部分，通过对vector的学习，有助于了解STL。1STL概念STL包括广义上分为三类：algorithm（算法）、container（容器）和iterator（迭代器）。三者的关系是：容器包含数据结构，算法可以操纵容器，而操纵容器又必需通过迭代器。Q2什么是容器？容器也叫集合(collection)。C++中容器被定义为：在数据存储上，有一种对象类型，它可以持有其它对象或指向其它对像的指针，这种对象类型就叫做容器。简单说，容器就是保存其它对象的对象。数组也是一种容器，但C++容器比数组更抽象。C++容器的概念也基本适合于其它面向对象平台，比如JAVA/.NET，这两种平台的类库中也内置了一些功能与C++差不多的集合（容器）类。容器还有一个特点是容器可以自行扩展。在解决问题时我们常常不知道我们需要存储多少个对象，也就是说我们不知道应该创建多大的内存空间来保存我们的对象。显然，数组在这一方面力不从心。而容器不需要预先告诉它要存储多少对象，只要创建一个容器对象，并合理的调用它所提供的方法，所有的处理细节将由容器来自身完成。容器是随着面向对象语言的诞生而提出的。现在几乎所有的面向对象的语言中也都伴随着一个容器集，在C++中，就是标准模板库（STL）。STL对定义的通用容器分三类：顺序性容器、关联式容器和容器适配器。顺序性容器：是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。关联式容器：关联式容器是非线性的树结构，更准确的说是二叉树结构。关联式容器另一个显著的特点是它是以键值的方式来保存数据，就是说它能把关键字和值关联起来保存。容器适配器：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制，其实仅是发生了接口转换。可以把它理解为容器的容器，它实质还是一个容器，只是他不依赖于具体的标准容器类型。（对容器适配器，可以想象成一个电源转接变换插头）。下表列出STL定义的三类容器所包含的具体容器类（该表在课件第7章中也出现过）：数据结构实现头文件向量(vector)顺序性容器vector列表(list)顺序性容器list双队列(deque)顺序性容器deque集合(set)关联容器set多重集合(multiset)关联容器set栈(stack)容器适配器stack队列(queue)容器适配器queue优先队列(priority_queue)容器适配器queue映射(map)关联容器map多重映射(multimap)关联容器mapQ3什么是叠代器？迭代器是一种允许程序员检查容器内元素，并实现元素遍历的数据类型（类）。C++标准库为每一种标准容器定义了一种迭代器类型。迭代器类型提供了比下标操作更一般化的方法：所有的标准库容器都定义了相应的迭代器类型，而只有少数的容器（比如数组）支持下标操作。因为迭代器对所有的容器都适用，现代C++程序更倾向于使用迭代器而不是下标操作访问容器元素。迭代器从作用上来说是STL最基本的部分，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。迭代器部分主要由头文件utility,iterator和memory组成。2vector模板类简介向量（vector）是STL中的一种顺序性容器类，因为数组存在内存安全隐患，所以C++最好使用vector和迭代器，避免使用低级的数组和指针，只有在强调速度时，才使用它们。vector类模板的原型为：templatetypename_Tp,typename_Alloc=allocator_Tpclassvector:protected_Vector_base_Tp,_Alloc{//此处省略了内部成员变量、成员函数、构造函数等声明}可以看出：vector类模板有两个模板参数：_Tp和_Alloc。_Alloc指定了默认值allocator_Tp，该默认值也是一个类模版，allocator类模板用来封装内存分配与归还的某些细节。classvector继承了另一个类模板_Vector_base_Tp,_Allocvector类模板的构造函数原型为：vector()//空的vector(al)//指定一种allocatorvector(n)//用默认T()初始化n个元素vector(n,val)//用Val初始化n个元素vector(n,val,al)//用val初始化n个元素，用al做分配器vector(first,last)//从己有的first到last复制生成vector(first,last,al)//从己有的first到last复制生成，用al做分配器vector模板类的成员函数结合后面的例子做介绍。3在程序中使用vector模板类首先，程序要做以下声明#includevectorusingstd::vector;或#includevectorusingnamespacestd然后，可以声明模版类对象：vectorintivec1;//int替换了模版参数_Tp，ivec为对象名vectorstringivec2;//string替换了模版参数_Tp下面可以参考前面介绍的vector类模板的构造函数原型，实例化对象：vectorintv3(10,-1);//v3有10个元素,均初始化为1vectorstringv4(10,hi!);//v3有10个元素,均初始化为hi!从上述两行实例化的语法可以看出，v3v4都是栈对象。如果要创建堆对象，用new操作符:vectorstring*p;p=newvectorstring（10，“hi!”）;或string*p=newvectorstring（10，“hi!”）;最后，可以使用vector对象的成员函数添加、删除、修改、遍历对象的元素，不用担心内存安全隐患，因为vector是内存安全的（而C/C++数组由于其指针特性，内存不安全）。vector类常用的成员函数和操作有（假定模板类vector的对象名为v）：v.empty()如果v为空，则返回true,否则返回false。v.size()返回v中元素的个数。v.push_back(t)在v的末尾增加一个值为t的元素。v[n]返回v中位置为n的元素,这是个下标操作。v1=v2深拷贝v1==v2如果v1与v2元素一一相等（而不仅是首地址相等），则返回true。!=,,=,,=保持这些操作符惯有的含义。Q4：使用vector对象与使用数组相比，好处在哪？坏处在哪？答：好处是内存安全，元素动态增长，有很多现成的函数可用。坏处是效率不如数组高。上机习题1（选做）使用vector类模板创建可动态增长的int集合，可用循环对集合元素进行遍历、添加、删除、修改。需要用到的vector类的成员函数，可以上网查找。二、字符串C语言字符串是字符数组，而数组的本质是指针，所以字符数组本质是：char*a=Iamapointer;另外，C语言还有一些关于字符串运算的标准库函数，比如stpcpy()，这些内容在谭浩强的课本讲过，不再重复。需要补充的是，在C语言中,char类型是一个字节,双字节字符类型是wchar_t;但wchar_t不是内置类型,定义在stddef.h中.给wchar_t类型的字符或字符数组(也就是字符串)赋值要冠以L;格式化输出(如printf)wchar_t类型的字符串,要用%S(而非%s)标识。#includestdio.h#includestddef.hintmain(void){wchar_twc=L'A';wchar_tws[]=LC++Builder2009;。。。。。。}因为C语言字符串（本质是指针）内存不安全，所以C++标准库增加了“内存安全”的字符串类string,使用该类前要includestring。string的使用不做具体介绍了。Q5：C++标准库处理定长字符串的类是什么？与C语言的字符串相比有什么优点和缺点？string只能处理定长字符串，处理变长字符串要用到另一个类：StringBuilder，它是基于std::vector实现的，具体使用也不做介绍了。课后习题：本章Q1—Q5