第五部分 – 标准库的使用

SECTION 1 string类

·头文件:string

·名称空间:std

·特性:

1. string是模板具体化basic_string的一个typedef.

2. size_type是一个依赖实现的整型，位于头文件string

3. string::npos为字符串的最大长度，通常为unsigned int的最大值.

·基础方法

·构造函数

·string版getline()用法:getline(输入流对象，string对象)；

该函数自动调整string大小

当读取的字符数达到最大值,设置failbit

·string的逻辑运算符均被重载。

·字符搜素:find()方法：

(1) size_type find(const string &str,size_type pos=0) const;

(2) size_type find(const char *s,size_type pos=0) const;

(3) size_type find(const char ch,size_type pos=0) const;

从字符串的pos位置查找子字符串str(或s)或字符ch的位置。

若找到，返回其首地址，否则返回 string::npos。

(1) (2)（3）用法:find(string字符串或C风格字符串或字符，开始位置=0);

(4)size_type find(const char *s,size_type pos,size_type n) ;从字符串的pos位置开始，查找s的前n个字符组成的字符串，返回方式同(1)(2).

用法:find(待取的C风格字符串,查找的开始位置,取的字符数);

·其他搜索:与find()的重载特征都相同

(1) rfind()查找子字符(串)最后一次出现的位置.

(2) find_first_of()查找参数中任何一个字符首次出现的位置

(3) find_last_of() 与（2）相仿，但查找最后一个

(4) find_first_not_of()查找第一个不包含在参数中的字符

(5) find_last_not_of()与（4）相仿，但查找最后一个

·其他方法:

capacity() 返回当前分配给字符串的内存块的大小

reserve(长度) 请求内存块的最小长度

c_str()返回对应的C风格字符串

**注:

模板basic_string有4个具体化，每个具体化都有一个typedef名称:

typedef basic_string string;

typedef basic_string wstring;

typedef basic_string u16string;//C++11

typedef basic_string u32string;//C++11

其原型如下：

template,

class Allocator=allocator > basic_string;

charT是字符类型，traits是其特征，Allocator管理内存分配(使用 new和delete)

SECTION 2 智能指针

·头文件：memory

·模板：auto_ptr(C++98提出C++11废弃)、shared_ptr、unique_ptr

1. 共同特点：定义了类似指针的对象，可以将从new获得的地址赋给这种对象。过期后会自动使用delete删除。因此不能用于非堆空间。若使用了new[]分配内存，只能用unique_ptr

2. 创建和使用

auto_ptr模板的定义如下

template class auto_ptr{public:explicit auto_ptr(X *p=0) throw();…}；

其他两个模板类似。

其不会自动将指针转换为智能指针对象。声明X类型的智能指针方法:

智能指针模板名 指针对象名(指针);

智能指针支持常规的指针操作，能赋给相同类型的常规指针，还能赋给相同类型的智能指针。

3. 注意事项：

(1) 所有权：对于auto_ptr和unique_ptr,赋值会转让所有权，auto_ptr和unique_ptr只有一个智能指针可以拥有特定的对象，该指针才能删除对象。

(2) shared_ptr会跟踪引用智能指针，进行引用计数。仅在最后一个指针过期时才使用delete。

(3) auto_ptr转让所有权后不能使用它访问对象,auto能够直接使用=,但会带来悬空指针

(4) unique_ptr在转让所有权时，原指针不再指向有效数据，不能使用=进行赋值。

若原对象是一个临时右值(如函数返回时会创建临时对象,此时会立马剥夺临时对象的所有权并且立马销毁临时对象)，允许进行赋值，如果将存在一段时间，则不能(以防止指针悬空)。

(5) std::move()将一个unique_ptr转换后返回，此时便可赋给另一个。用法move(源指针)。

(6) 模板auto_ptr使用new和delete；unique_ptr有使用new[] delete[]的版本,示例:

unique_ptr pda(new double(5));

SECTION 3 STANDARD TEMPLATE LIBRARY(STL,标准模板库)

·基础知识

1. STL包括了一组表示容器(类似数组)、迭代器(能够用来遍历容器的对象，与能够遍历数组的指针相似，是一个广义指针)、函数对象(类似于函数的对象)和算法(完成特定任务的过程)的模板。

2. 分配器：各种STL容器模板都接受一个可选的模板参数，该参数指定了使用哪一个分配器对象来管理内存。(使用的是new和delete)

3. 所有的STL容器提供的基本方法：

.size()容器中的元素个数

.swap()交换两个容器的内容

.begin()返回一个指向容器第一个元素的迭代器

.end()返回一个表示超过容器尾的指针

4. 每一个容器都定义了一个迭代器，为一个名为iterator的typedef，作用域为类。声明一个迭代器方法：

类名::iterator 迭代器名;

其可以：解除引用 operator*()、自增operator++()

E.g. vector::iterator

5. 超过结尾(past_the_end):指向容器最后一个元素后面的元素的迭代器

6. 某些STL容器特有的方法:

(1) push_back(追加的元素)将元素添加到末尾，并增加长度

(2) erase(开始迭代器，结束迭代器)删除制定区间的元素，接受两个迭代器(包含operator+()方法),包括开始不包括结束。

(3) insert(新元素的插入位置迭代器，被插入区间开始迭代器，被插入区间结束迭代器);用于插入元素，接受3个迭代器，包括开始不包括结束。

e.g.new_v.insert(new_v.begin(),old_v.begin(),old_v.end())；

将矢量old_v的内容插入到矢量new_v的第一个元素前面

·算法 (头文件algorithm)

for_each(开始迭代器，结束迭代器，要应用的函数指针);前两个是一个容器的区间(不包括结束)，最后是函数指针，会被应用于区间的各个元素，被指向的函数不能修改元素值。

random_shuffle(开始迭代器，结束迭代器);随机排列区间的元素，要求容器随机访问。

sort(开始迭代器，结束迭代器)

(开始迭代器，结束迭代器,自定义排序函数)

只接受区间时，使用<运算符，对区间升序排序。(要有对应的operator<()函数)

接受区间和函数指针时，函数返回值为false表示排序不正确.

·迭代器:

1. C++将operator++()作为前缀版本，将operator++(int)作为后缀版本。其中的参数根本不会使用，因此无需指定名称

2. 迭代器都能进行解除引用和比较

3.迭代器的类型：

(1) 输入迭代器：来自容器的信息被称为输入，可被程序用来读取容器中的信息，但不一定让程序修改，该种算法不修改值。(只读不写)

基于输入迭代器的任何算法都是单通行的，可以递增，不可倒退。

(2) 输出迭代器：将信息从程序传输给容器的迭代器。只能解除引用修改容器值，不能读取。(只写不读)输出迭代器是单通行的。

(3) 正向迭代器：与输入迭代器和输出迭代器相似，只用++运算符遍历容器。每次沿容器向前移动一个元素。总是按照相同的顺序遍历一系列的值。仍可以对以前的值解除引用，能够读写数据，也可只读数据。

(4) 双向迭代器：包含了正向迭代器的特性，支持–运算符。

(5) 随机访问迭代器:能够直接跳转到任意元素（随机访问），包含了双向迭代器的特性，支持随机访问。

随机访问迭代器操作：a、b为迭代器值，n为整数，r为随机访问迭代器的变量或引用。这些表达式只有在容器区间内（包括超尾）才合法。其操作如下：

a+n 或 n+a:指向a所指向的元素后的第n个元素;

a-n:指向a所指向的元素前的第n个元素;

r+=n、r-=n：复合运算符；

a[n]同*(a+n);b-a减法;ab,a<=b,a>=b用来比较地址。

(6) 迭代器的性能

4.概念、改进与模型：

概念是一系列的要求；改进是概念上的继承（因为其无法使用C++的类继承来描述，如将指针用作迭代器）；模型是概念的具体实现。

以下算法使用头文件algorithm

(1) STL std::sort()函数：接受指向容器（数组）的第一个元素的迭代器（指针）和指向超尾的迭代器（指针）,用于排序。

用法：sort(首迭代器，超尾迭代器);

(2) STL std::copy()函数：从一容器复制元素到另一迭代器，前两个迭代器指出要复制的元素范围（输入迭代器），最后一个迭代器（输出迭代器）指出要将第一个元素复制到的位置（目的地）。

注意：目标容器要足够大。复制不同于插入，其会覆盖原有的数据。

用法copy(开始，结束，目的地)；

头文件：iterator

(3) 将信息复制到输入输出和其他迭代器

适配器:用于将其他接口转为STL接口

①表示输出流的迭代器：ostream_iterator模板，其是一个适配器，可将其他的接口转换为STL接口用法：

ostream_iterator<被发送给输出流的数据类型，输出流所使用的字符类型>

迭代器名(输出流名称，每个数据的分隔符(字符串));

如：ostream_iterator cout_iter(cout,” ”);

使用*cout_iterator++ =15即可复制，等价于cout<<15<<” ”;

可复制到输出流内使用数据，可以创建无名迭代器。

如：copy(dict.begin(),dict.end(),ostream_iterator(cout,””));

//ostream_iterator(cout,””))也可以换为一个具体的名称。

②istream_iterator使istream输入可用作迭代器接口，拥有两个模板参数，声明方法：istream_iterator<读取的数据类型，输入流使用的字符类型>迭代器名(输入流名)，使用cin代表cin管理输入流，省略构造函数表示输入失败。可将其运用到copy()算法中，直到EOF、不匹配或其他问题为止。样例：

copy(istream_iterator(cin),istream_iterator(),dict.begin);

③reverse_iterator(反向迭代器):对反向迭代器递增操作将导致其被递减。

vector类有rbegin()和rend()的成员函数，rbegin()返回指向超尾元素的反向迭代器(vector::reverse_iterator)，rend()返回第一个元素的反向迭代器。

若要反着打印容器内容，可以进行如下操作:

copy(dice.rbegin(),dice.rend(),ostream_iterator(cout,””));

反向指针通过先递减再解除引用解决问题。(即*rp将在*rp的当前值之前对迭代器解除引用。)

④插入迭代器:添加新的元素，不会覆盖已有的数据，并会自动分配内存来容纳新的内容

back_insert_iterator将容器插入到容器尾部

front_insert_iterator:插入到容器的前端

insert_iterator:将元素插入到其构造函数指定的位置前面

可以直接使用copy()函数。

限制如下：back_insert_iterator需要允许在尾部快速插入的容器(插入操作的时间复杂度为常数,如vector)，front_insert_iterator需要允许在起始位置做时间固定插入的容器类型(如queue)，insert_iterator没有限制。

这些迭代器将容器类型作为模板参数。back_insert_iterator的构造函数假设传递给它的类型有push_back()方法。声明front_insert_iterator大同小异。insert_iterator需要指出位置。他们的声明格式为：

back_insert_iterator <容器类型> 迭代器名(容器名);

front_insert_iterator <容器类型> 迭代器名(容器名);

insert_iterator<容器类型> 迭代器名(容器名,插入位置);

·容器：早期的11个容器类型：deque、list、queue、stack、vector、map、multimap、set、multiset和bitset。C++11新增容器：forward_list、unordered_map、unordered_mulitmap、unordered_set和unordered_mulitset。

1.容器的基本特征：

X表示容器；T表示存储在容器中的对象类型;a、b表示类型为X的值；r表示类型为X&的值；u表示类型为X的标识符。

复杂度描绘了执行操作所需要的时间。从快到慢依次为：编译时间、固定时间、线性时间。

2.C++11 新增的容器要求：rv表示类型为X的非常量右值

移动操作可能修改源对象，还可能转让所有权，而不做任何复制。

3. 序列容器：(7种STL容器：deque、forward_list、queue、priority_queue、stack和vector)

(1) queue队列能够能够在队尾添加元素，在队首删除元素；deque表示双端队列允许在两端添加或删除元素（array也被归为序列容器）。

(2) 特征：按线性顺序排列，即存在第一个元素，最后一个元素，除了该两个元素处其他的元素前后都分别有一个元素。

(3)序列的要求：t表示类型为T的值，n表示整数，p、q、i、j表示迭代器（T可做存储在容器中值的类型）

①基本操作[注：区间[x,y）的范围包括x(起始)不包括y(结束)]

②可选要求:在允许的情况下，时间复杂度为固定时间。

注意：at()方法会检查边界，若越界则引发out_of_range异常。

(4)序列容器的详解

4.关联容器：对容器概念上的另一改进。

关联容器将值与键关联起来，并使用键来查找值。

对于容器X，X::value_type指出了存储在容器中的值的类型，X::key_type指出了键的类型。提供了对元素的快速访问。允许插入新元素，但不能指定插入的位置。使用树实现，根节点链接1到2个节点，每个节点都如此，从而形成分支结构。STL提供4个关联容器：set、multiset(位于set头文件)、map、multimap(位于map头文件)；set的值与键类型相同，键是唯一的，set的值就是键。multiset与set相似，只是可能有多个值相同。

在map中，值与键的类型不同，键是唯一的，每个键对应一个值，

multimap类似，只是一个键可以对应多个值。

他们表示的区间与该键匹配。该方法将两个值封装在一个pair对象中，这个pair的两个模板参数均为迭代器。

5.无序关联容器：对容器概念的另一种改进。底层差别在于其基于数据结构哈希表，提供了效率。共4种：unordered_set、unordered_multiset、unordered_map、unordered_multimap.

·函数对象

函数对象，也叫函数符。主要以函数方式与operator()结合使用的任意对象。包括了函数名、函数指针和重载了operator()的类对象。

1.概念：

(1) 生成器：不用参数的函数符

(2) 一元函数：接受一个参数的函数符

(3) 二元函数：接受两个参数的函数符

(4) 返回bool的一元函数叫一元谓词

(5) 返回bool的二元函数叫二元谓词

提供给for_each()的函数符应是一元函数；sort()的其中一个版本将二元谓词作为第三个参数；list模板有一个将谓词作为参数的remove_if()成员，该函数将谓词应用于区间中的每个元素，如果谓词为true，则删除元素。即remove_if(表示删除条件的谓词);

E. g scores.remove_if(too_big);//too_big是谓词

2.预定义的函数符：

函数std::transform() 两个版本：

(1) 接受4个参数。前两个参数指定容器区间的迭代器，第三个指定结果复制到哪。最后一个参数是一元函数符，应用于区间每个元素，生成结果中的新元素。

即：transform(开始应用位置，结束位置/[应用区间],结果保存位置，要应用的函数符);

(2) 使用一个二元函数符，并将该函数应用于两个区间中的元素。它用第三个参数表示第二个区间的开始位置(没有结束位置，因为第一个区间表明了长度)

即：transform(开始应用位置，结束位置/[应用区间],第二个区间开始位置，结果保存位置，要应用的函数符);

E.g m8,gr8是vector对象，mean(double,double)返回两数平均值，则transform(gr8.begin(),gr8.end(),m8.begin,

ostream_iterator(cout,” ”),mean);

输出m8与gr8的每个元素的平均值。

(3) 运算符与对应函数符（头文件funtional）：定义了多个模板类函数对象，即：函数符<类型>()；如：plus()。

对于内置的运算符和重载的运算符均有函数符：

3.自适应函数符与函数适配器

自适应函数符：携带了标识参数类型与返回类型的typedef成员。这些成员的名称：result_type、first_argument_type、second_argument_type.

如：plus::result_type是int的typedef.

意义：函数适配器对象可以使用函数对象，并认为存在这些typedef成员。

STL使用binder1st和、binder2nd类自动完成将自适应二元函数转换为一元函数(函数适配器)

(1) binder1st若有一个自适应二元函数对象，则可以创建一个binder1st对象，该对象与一个将被用做该函数的第一个参数的值相关联。即：binder1st(自适应二元函数，关联的值) 函数符名;

如：binder1st(f2,val) f1;则f1(x)等价于f2(val,x)

bind1st函数可以简化过程，其返回一个函数符。用法：

bind1st(要转换的函数符，要绑定的第一个参数)。

(2) binder2nd类和bind2nd：与binder1st和bind1st类似，但是关联第二个参数。

·算法

1.非成员函数算法[STL函数可用于常规数组]概论:

可以用==比较不同容器，重载的运算符使用迭代器来比较内容。

算法分为4组：非修改式序列操作、修改式序列操作、排序和相关操作(头文件algorithm)、通用数字运算(头文件numeric)

2.算法：

(1) 就地算法：结果在原容器中；

(2) 复制算法：将结果拷贝到另一位置;

(3) 有些算法有就地与复制两个版本。复制版本以_copy,将额外接受一个输出迭代器参数，作为结果存放的位置。

(4) replace()函数原型：

template

void replace(ForwardIterator first,ForwardIterator last,

const &T old_vaule,const &T new_vaule);

所有的old_vaule将被替换为new_vaule.

即：replace(开始位置，结束位置/[应用区间],待替换的旧值，替换后的新值);

template

OutputIterator replace(InputIterator first,

InputIterator last,OutputIterator result,

const &T old_vaule,const &T new_vaule);

复制版本在第三个参数指定了一个名为result的新位置，将结果复制过去。对于复制算法，返回一个迭代器，指向复制的值的超尾。

即：输出迭代器 replace(开始位置，结束位置/[应用区间],输出的位置,待替换的旧值，替换后的新值);

以if结尾的版本将函数应用于容器元素的结果来执行操作，如果将函数应用于旧值中，返回值为true则replace_if()把旧值替换为新值。原型如下

template

void replace(ForwardIterator first,ForwardIterator last,

Predicate pred,const &T new_vaule);

即：replace(开始位置，结束位置/[应用区间],判断是否替换的谓词，替换后的新值);

(5) STL和string类：string类包括了begin()、end()、rbegin()、rend()等成员，可使用STL接口。next_permutation()算法将区间内容转为下一种排列方式。对于字符串，排列按照字母递增的顺序进行。如果成功，返回true;如果该区间已经处于最后的序列中，该算法返回false.要得到所有的排列，应先排序。

用法:next_permutation(开始排列位置，结束位置/[排列的区间])；

(6) 如果la和lb均为list对象，则以下调用等价：

la.remove(4);remove(lb.begin(),lb.end(),4);

list链表使用remove()来删除某一实例,STL remove()函数接受区间并删除实例，但其不能调整容器长度。它将没有删除的元素放在链表开头，并返回新的超尾值。

(7) 使用STL：count()函数，将一个区间和一个值作为参数，并返回这个值在出现的次数。即count([区间],值)；

map类可以用数组表示法将键作为索引访问存储值。

·其他库

1.vector、valarray、array

valarray不是STL的一部分，array提供了STL的方法

valarray重载了所有的算术运算符，如+表示每个元素相加，*表示每个元素相乘，其他的大体相似。

valarray重载了许多数学函数，其接受一个valarray对象并返回结果。如valarray (6)={1,1,4,5,1,4};log(va3);

也可以使用apply()方法，传入函数进行运算，其不修改调用对象，返回一个包含结果的新对象。

valarray有resize()方法，不能自动调整大小。

C++11提供了接受valarray对象作为参数的begin()和end()，满足STL的区间要求。

如果numbers是valarray对象，则下面语句中的vbool[i]将被设为numbers[i]>9的bool值。

valarray vbool=numbers>9;

下标指定slice类：用作下标索引，被初始化为3个整数值:

起始索引，索引数，步长(元素的距离)。如slice(1,4,3)指索引1，4，7，10.

头文件：initializer_list

2.initializer_list类[C++11]

(1) 如果类包含接受initializer_list作为参数的构造函数，则{}表示法会调用它。

(2) 所有initializer_list元素的类型必须相同。

(3) 使用：该模板包含begin()、end()、size()。

声明：initializer_list<类型> 名称={列表}；

可以按值或引用传递。函数参数可以是initializer_list字面量，也可以是其变量。其迭代器类型为const，不能修改值，但可以互相赋值。

SECTION 4 标准输入输出、文件I/O

<暂缺>