《C++ Primer Plus》学习笔记10

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
第16章 string类和标准模板库
主要内容：
1）标准的C++string类
2）auto_ptr模板
3）标准模板库(STL)
4）容器类
5）迭代器
6）函数对象
7）STL算法
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1、string类
1）构造字符串

//初始化为常规的C-风格的字符串
string one ("Lottery Winner!");

//初始化为由20个$字符组成的字符串
string two(20, ‘$‘); 

//复制构造函数将string对象three初始化为string对象one
string three(one); 

//重载的+=操作符将字符串”Oops!“附加到字符串one的后面
one += “ Oops!“; 

//+=操作符可以被多次加载，以便能够附加string对象和单个字符
one += two;
one += ‘! ‘;

//=操作符也可以被重载，以便可以将string对象、C——风格字符串或char值赋给string对
two = "Sorry! That was";
two = one;
two = ‘?’;

//+操作符创建了一个临时string对象,之后使用重载的=操作符将它赋给对象four
string four;
four = two + three;

//构造函数将一个C风格字符串和一个整数作为参数，其中的整数参数表示要复制多少个字符   
char alls[] = "All‘s well that ends well";
string five(alls, 20);

//构造一个模板参数意味着包含begin不包含end在内的区间，记住最后一位指向的是后面的空格
template<class Iter>string(Iter begin, Iter end);
string six(alls + 6, alls + 10);
string seven(&five[6], &five[10]);

2）string类输入
补充：
cin
1）输入一个数字
2）接受一个字符串，遇到空格、TAB、回车都结束
cin.get()
1）cin.get(ch)用来接收字符

char ch; cin.get(ch);

2）cin.get(s,n)用来接收一行字符串，可以接收空格 这个类似于getline 可以输入多个单词用空格隔开

char a[20]; cin.get(a,20);

cin.getline()
接受一个字符串，可以接收空格。这个和cin(s,n)都需要注意

char m[20] = jklkjilj;
cin.getline(m,5);
cout << m << endl; //这里输出结果为jklk 因为最后一个字符为‘0’

这就可以知道直接上cin.getline()有三个参数，接收字符串到m,接收个数,结束符（当省去的时候我们就默认为‘\0‘或者‘/n’）

char a[20]; cin.getline(a,5);

getline()
接收一个字符串，可以接收空格并输出，需要包含头文件#include<string>
注意，getline()属于string流，所以只有把字符串定义为string型，我们才可以用，否则只能用istream流的cin.getline(m,20)
gets()
接收一个字符串，可以接收空格并输出，但是需要加上头文件#include<string>
而且需要注意不能写成m = gets();应该为gets(m)
getchar()
接收一个字符，需要有头文件#include<string>
这几需要注意，不能写成getchar(ch)；应该写成ch = getchar(); getchar()是C语言的函数，C++也兼容，但是少用。
综上所述，根据我的习惯，C++以后碰到需要输入带空格的字符时用char ch; cin.get(ch)
字符串#include<string> gets(str)
3）使用字符串

string str1("cobra");
string str2("coral");
str1.length() == str2.size

确定字符的长度size()和length()成员函数都返回字符串中的字符数；length来自于较早版本的string类，size()则是为提供STL兼容性而添加的
find的四个版本 string::npos 是字符串可储存的最大字符数
①size_type find (const string &str, size_type pos = 0) const
从字符串的pos开始，查找子字符str。如果找到，则返回该子字符首次出现时其首字符的索引，否则返回string:: npos
②size_type find(const char *s, size_type pos = 0) const
从字符串的pos开始，查找子字符串s，如果找到，则返回该子字符首次出现时其首字符的索引，否则返回string:: npos
③size_type find(const char *s, size_type pos = 0, size_type n)
从字符串的pos位置开始，查找s的前n个字符组成的子字符串，如果找到，则返回该子字符串首次出现时其首字符的索引，否则返回string::npos
④size_type find(char ch, size_type pos=0) const
从字符串的pos位置开始，查找字符ch，如果找到，则返回该字符首次出现的位置，否则返回string::npos
4）string还提供了哪些功能
①自动调整大小的功能
每当程序将一个字符附加到字符串末尾时将发生什么呢？
不能仅仅将已有的字符串加大了，因为相邻的内存可能被占用了，因此可能需要一个新的内存块，并将原来的内容复制到新的内存单元中。
方法capacity()返回当前分配给字符串的内存块的大小，而reseve()方法让您能够请求内存块的最小长度
2、auto_ptr类
是一个模板类，用于管理动态内存分配的用法。
auto_ptr模板定义了类似指针的对象，可以将new获得(直接或者间接)的地址赋给这种对象，当auto_ptr对象过期时候，其析构函数将使用detele来释放内存，因此如果将new返回的地址赋给auto_ptr对象时，无须记住稍后释放这些内存，它过期之后，会自动释放。
*使用auto_ptr类注意事项：
1）记得要包含memory头文件#include<memory>
2）只能对new分配的内存使用auto_ptr对象，而不要对由new[]分配的或通过声明变量分配的内存使用它。

auto_ptr<int> pi (new int [200]); //No

3、STL
STL提供了一组表示容器、迭代器、函数对象、算法的模板。
容器是一个与数组类似的单元，可以存储若干个值；算法是完成特定任务的处方；迭代器能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针；函数对象是类似于函数的对象，可以是类对象或函数指针
1）vector模板类

#include vetor
using namespace std;
vector<int> ratings(5);//5个整型的矢量
int n;
cin >> n;
vector<double> scores(n);//n个double的矢量
ratings[0] = 9;
for(int i = 0; i < n; i++)
    cout << scores[i] << endl;

2）可对矢量执行的操作

size()——返回容器中元素的数目
swap()——交换两个容器的内容
begin()——返回一个指向容器中第一个元素的迭代器
end()——返回一个表示超过容器尾的迭代器

迭代器，要为vector的double类型规范声明一个迭代器

vector<double>::iterator pd;
vector<double> scores;//scores是一个vector<double>对象
pd = scores.begin();//初始地址
*pd = 22.3;//第一个元素的值
++pd;

遍历整个容器的内容：

for(pd = scores.begin(); pd != scores.end(); pd++)
    cout << *pd << endl;

push_back()是一个方便的方法，它将元素添加到矢量末尾，它负责内存管理，增加矢量的长度，使之能容纳新的成员

vector<double>scores;//创建一个空的向量
double temp;
while(cin>>temp && temp >= 0)
    scores.push_back(temp);
cout << "You entered" << scores.size() << " scores.\n";

erase()方法删除矢量中给定区间的元素，它接受两个迭代器参数，这些参数定义了要删除的区间，第一个迭代器指向区间的起始处，第二个迭代器位于区间终止处的后一个位置

scores.erase(scores.begin(), scores.begin() + 2);//即删除了begin()和begin()+1指向的元素

记住：区间[it1, it2]由迭代器it1和it2指定，其范围为it1到it2不包括it2
insert()方法与erase()相反，它接受3个迭代器参数，第一个参数指定了新元素的插入位置，第二个和第三个参数定义了被插入区间

old.insert(old.end(),new.begin()+1,new.end());//将矢量new中除第一个元素以外的所有元素插入到old矢量的第一个元素的前面

3）对矢量可执行的其他操作
搜索、排序、随机排序
for_each()函数用于许多容器类，它接受3个参数，前两个是定义容器中区间的迭代器，最后一个是指向函数的指针，被用来指向函数应用与容器区间中的各个元素，被指向的函数不能修改容器元素的值;可以用for_each循环代替for循环

vector<Review>::iterator pr;
for(pr = books.begin();pr != books.end(); pr++)
    ShowReview(*pr);

替换为

for_each(books.begin(),books.end()，ShowReview);//这样避免显式地使用迭代器变量

Random_shuffle()函数接受两个指定区间的迭代器参数，并且随机排列该区间中的元素

random_shuffle(books.begin(), books.end());//随机排列books矢量中的所有元素

sort()也要求容器支持随机访问

//版本一接受两个迭代器参数
vector<int> coolstuff;
……
sort(coolstuff.begin(),coolstuff.end());//升序
//版本二如果容器元素是用户定义的对象，必须定义能够处理类型对象的operator<()函数
bool operator< (const Review & r1, const Review & r2)
{
    if(r1.title < r2.title)
        return true;
    else if(r1.title == r2.title && r1.rating < r2.rating)
        return true;
    else
        return false;
}

有了这样的函数之后，我们就可以对包含Review对象如books的矢量进行排序

sort(books.begin(), books.end());//升序排序，全排序

上述版本是按照title成员的字母顺序排序，如果title成员相同，则按照rating排序

bool WorseThan (const Review & r1, const Review & r2)
{
    if(r1.title < r2.title)
        return true;
    else
        return false;
}

有了这个函数，就可以将包含Review对象的books的矢量按rating升序排列

sort(books.begin(), books.end(), WorseThan);//升序排序，完全弱排序

4、通用编程技术
STL是一种通用编程技术，面向对象编程关注的是编程的数据方面，而通用编程技术关注的是算法，共同之处是抽象和创建可重用的代码。
通用编程技术旨在编写独立于数据类型的代码，在C++中，完成通用程序的工具是模板
1）模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型，它们都是STL通用方法的重要组成部分
2）为什么要使用迭代器？
目的是为了编写算法时，尽可能使用要求最低的迭代器，并让它适用于容器的最大区间。这样通过使用级别最低的输入迭代器，find()函数便可用于任何包含可读取值的容器，sort()函数由于需要随机访问迭代器，所以只能用于支持这种迭代器的容器。

//在一个double数组中搜索特定值的函数
double * find_ar(double * ar, int n, const double & val)
{
    for(int i = 0; i < n; i++)
        if(ar[i] == val)
            return &ar[i];
        return 0;
}

使用迭代器

typedef double * iterator;
iterator find_ar(iterator begin, iterator end, const double & val)
{
    iterator ar;
    for(ar = begin; ar != end; ar++)
        if(*ar == val)
            return ar;
        return end;
}

总结下STL方法，首先是处理容器的算法，应尽可能用通用的术语来表达算法，使之独立于数据类型和容器类型，为使通用算法能够适用于具体情况，应定义能够满足算法需求的迭代器，并把要求加到容器设计上，所以要设计基本迭代器的特征和容器特征。
3）迭代类型
①输入迭代器——被程序用来读取容器中的信息
单向迭代器，只读，只能递增，不能倒退。
②输出迭代器——将信息从程序传输给容器的迭代器，程序的输出就是容器的输入
单向迭代器，只写
③正向迭代器——使用++操作符来遍历容器，正向迭代器既可以使得能够读取和修改数据，也可以使得只能读取数据

int * pirw;//读写迭代器
const int * pir;//只能读取迭代器

④双向迭代器——具有正向迭代器所有特性，同时支持两种递减操作符
reverse函数可以交换第一个元素和最后一个元素，将指向第一个元素的指针加1、将指向第二个元素的指针减去1，并且重复这种处理过程。
⑤随机访问迭代器——具有双向迭代器所有特性，同时添加了支持随机访问的操作
X表示随机迭代器类型，T表示被指向的类型，a和b是迭代器值，n为整数，r为随机迭代器变量或引用
随机访问迭代器操作：

a+n 指向a所指向元素后的第n个元素
a-n 指向a所指向元素前的第n个元素
a[] 等价于*(a+n)

4）概念、改进和模型
概念的具体实现被称为模型
①将指针用作迭代器
迭代器是广义的指针，指针满足所有迭代器的要求，迭代器是STL算法的接口，而指针是迭代器，所有STL算法可用于常规数组。
copy()、ostream_iterator和istream_iterator
copy() 将数据从一个容器复制到另一个容器中

int casts[10] = {6, 7, 2, 9, 4, 11, 8, 7, 10, 5};
vector<int> dice[10];
copy(casts, casts + 10, dice.begin());//前两项是复制的范围，后面是复制到什么位置

使用注意事项：
前两个参数最好是输入迭代器，最后一个参数最好是输出迭代器；
copy()函数将覆盖目标容器中已有的数据，我们不能将数据放入空矢量中；
ostream_iterator
是输出迭代器概念的一个模型，它是一个适配器(adapter)一个类或函数，可以将一些其他接口转换为STL使用的接口。

#include<iterator>
……
ostream_iterator<int,char> out_iter(cout, " ");//第一个参数指出被发送给输出流的数据类型，第二个参数指出输出流使用的字符类型
copy(dice.begin(),dice.end(),out_iter);

istream_iterator
是istream输入可用做迭代器接口，它是一个输入迭代器概念的模型，使用两个istream_iterator对象来定义copy()的输入范围
copy(istream_iterator<int,char>(cin), istream_iterator<int, char>(), dice.begin());//第一个参数指出要读取的数据类型，第二个参数指出输入流使用的字符类型
现在假设反向打印容器的内容，vector类有一个名为rbegin()的成员函数和一个名为rend()的成员函数，前者返回一个指向超尾的反向迭代器，后者返回一个指向第一个元素的反向迭代

copy(dice.rbegin(), dice.rend(), out_iter);//反向显示内容

记住rbegin()和end()返回相同的值，但类型不用（reverse_iterator和iterator）同样rend和返回相同的值（指向第一个元素的迭代器）,但类型不同。
5）序列
6种STL容器类型，deque、list、queue、priority_queue、stack和vector都是序列，队列能够在队尾添加元素，在队首删除元素，Deque表示的双端队列允许在两端添加和删除元素。
数组和链表都是序列，但分支结构（其中每个节点多指向两个子节点）不是序列。

Xa(n,t); //声明一个名为a的、由n个t值组成的序列
X(n,t); //创建一个由n个t值组成的匿名序列
Xa(i,j);//声明一个名为a的序列，并将其初始化为区间[i,j)的内容
X(i,j);//创建一个匿名序列，并将其初始化为区间[i,j)的内容
a.insert(p,t) //将t插入到p的前面
a.insert(p,n,t) //将n个t插入到p的前面
a.insert(p,i,j) //将区间[i,j)中的元素插入到p的前面
a.erase(p) //删除p指向的元素
a.erase(p,q) //删除区间[p,q]中的元素
a.clear() //等价于erase(begin(),end())

6）下面详细介绍6种序列容器类型
vector
vector是数组的一种类表示，它提供了自动内存管理功能，可以动态地改变vector对象的长度，并随着元素的添加和删除而增大和缩小，它提供了对元素的随机访问，在尾部添加和删除袁术的时候是固定的，但在头部或中间插入和删除元素的复杂度为线性时间。
deque
deque模板类表示双端队列，类似于vector主要区别在于从deque对象的开始位置插入和删除元素的时间是固定的，而不像vector中那样是线性时间。
list
表示双向链表，出了第一个和最后一个元素外，每个元素都与前后的元素相链接，这就意味着可以双向遍历链表。list和vector之间的区别在于list在链表中任一个位置进行插入和删除的时间是固定的，vector强调的是通过随机访问进行快速访问，而list强调的是元素的快速插入和删除。
与vector相似，list也是可以反转容器的，不同的是list不支持数组表示法和随机访问，
queue
queue模板的限制比deque多，它不仅不允许随机访问队列元素，甚至不允许遍历队列。
queue的操作

bool empty() const //如果队列为空，则返回true;否则返回false
size_type size() const //返回队列中元素的数目
T& front() //返回指向队首元素的引用
T& back()  //返回指向队尾元素的引用
void push(const T & x) //在队尾插入x
void pop() //删除队首元素

记住如果要使用队列中的值，应首先使用front()来检索这个值，之后我们再用pop()将它从队列中删除。
priority_queue
另一个适配器类，它支持的操作与queue相同，在priority_queue中，最大的元素被移到队首。
stack
记住在头文件中得加上#include<stack>也是一个适配器类，给底层类提供了典型的堆栈接口。

bool empty() const //如果堆栈为空，则返回true;否则返回false
size_type size() const //返回堆栈中元素的数目
T& top() //返回指向栈顶元素的引用
T& back()  //返回指向队尾元素的引用
void push(const T & x) //在堆栈顶部插入x
void pop() //删除栈顶元素

如果要使用堆栈中的值，必须首先使用top()来检索这个值，之后使用pop()将它从堆栈中删除。
7）联合容器
优点在它提供了对元素的快速访问，与序列相似，联合容器也允许插入新元素，不过不能指定元素插入位置，原因为联合容器通常包含用于确定数放置位置的算法，以便能够很快的检索信息。
四种：set、multiset、map、multimap
前两个是在头文件#include<set>
后两个是在头文件#include<map>
set
可反转，可排序，关键字是唯一的，所以只能存储同一种类型的值

 set<string> A;

将集合初始化为数组内容的简单方法：

const int N = 6;
string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};
set<string> A(s1, s1 + N);//初始化 记住区间的最后一个位置是超尾，s1 + N指向数组尾部后面的一个位置，集合被排序
ostream_iterator<string,char> out(cout, " ");
copy(A.begin(), A.end(), out);

求两个集合的并集

set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<string, char> out(cout, " "));

补充：set.intersection()和set_difference()函数查找交集(两个集合公有的元素)和获得两个集合的差(第一个集合减去两个集合公有的元素)
两个有用的set方法分别是lower_bound()和upper_bound()
lower_bound()方法将关键字作为参数并返回一个迭代器，该迭代器指向集合中第一个不小于关键字参数的成员，同样，upper_bound()返回的位第一个大于关键字参数的成员
multimap
可反转，可排序，关键字是可以与多个值关联
创建一个multimap对象，其中关键字的类型是int,所存储的值的类型为string

 multimap<int, string>codes;

为了将信息结合在一起，实际的值类型将关键字类型和数据类型结合为一对，STL使用pair<class T, class U>模板类将这两种值存储到一个对象中，如果keytype是关键字类型，而打她type是被存储的数据类型

pair<const keytype, datatype>

创建一个匿名pair对象，并将它插入

codes.insert(pair<const int, string> (213, "Los Angeles"));

5、函数对象
1）list模板中又一个将断言作为参数的remove_if()成员，该函数将断言应用与区间的每一个元素如果为true，则删除这些元素。

//删除链表three中所有大于100的元素
bool tooBig(int n){return n > 100;}
list<int> scores;
……
scores.remove_if(tooBig);

2）预定义的函数数
tranform()
前两个参数是指定容器区间的迭代器，第3个参数是指定将结果复制到哪里的迭代器，最后一个参数是一个函数符，它被应用于区间中的每个元素，生成结果中的新元素。

transform(gr8.begin(), gr8.end(), out, sqrt);

6、算法
STL将算法库分成4组
①非修改式序列操作
②修改式序列操作
③排序和相关操作
④通用数字运算
1）函数与容器的方法
首先它更适合于特定的容器，其次作为成员函数，它可以使用模板类的内存管理工具，从而在需要时调整容器的长度。
例如la是一个list<int>对象，使用链表的remove()方法：

la.remove(4);//链表中所有值为4的元素将被删除

还有一种形式

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

由于该remove()函数不是成员，因此不能调整链表的长度，它将没有删除的元素放在链表的开始位置，并返回一个指向新的超尾值的迭代器，这样，便可以用迭代器来修改容器的长度
链表中还可以使用erase来删除一个区间

lb.erase(last,lb.end());

2）使用STL

//用于显示3个容器，包含输入内容的矢量，包含单词列表的集合和包含单词计数的映象内容.cpp
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <algorithm>
#include <cctype>
using namespace std;

//忽略大小写，转换为小写由于tolower()函数被定义为int tolower(int)编译器希望为char，我们可以用toLower代替tolower
char toLower(char ch)
{
    return tolower(ch);
}

string & ToLower(string & st);
void display(const string & s);

int main()
{
    //创建一个vector<string>对象，并用push_back()将输入的单词添加到矢量中
    vector<string> words;
    string input;
    while(cin >> input && input != "quit")
        words.push_back(input);

    //全部一行显示输出的单词,每个单词空一个空格
    for_each(words.begin(), words.end(), display);
    cout << endl;

    //使用transform将矢量中的数据复制到集合中，使用一个转换函数将字符串转换成小写,并且我们要排序，且将相同的只显示一次
    set<string> wordset;
    transform(words.begin(), words.end(), 
        insert_iterator<set<string>>(wordset,wordset.begin()),
        ToLower);
    for_each(wordset.begin(),wordset.end(), display);
    cout << endl;

    //单词和计数作为pair<const string, int>对象存储在map对象中
    map<string, int>wordmap;
    set<string>::iterator si;
    for(si = wordset.begin(); si != wordset.end(); si++)
        wordmap[*si] = count(words.begin(), words.end(), *si);

    for(si = wordset.begin(); si != wordset.end(); si++)
        cout << *si << ": " << wordmap[*si] << endl;

    return 0;
}

string & ToLower(string & st)
{
    transform(st.begin(), st.end(), st.begin(), toLower);
    return st;
}

void display(const string & s)
{
    cout << s << " ";
}

运行结果：