[C++知识库]C++ Primer Plus 笔记（16章：string类和标准模板库）

16 string类和标准模板库

16.1 string类

16.1.1 构造字符串

常见的字符串书中给了7个，另外还有两个在C++11里新增的（NTBS）表示以空字符结束的传统字符串

下面进行一下测试：

int main()
{
    string date("2021.9.18");
    cout << date[0] << endl;//重载[]，使其可以使用数组表示法来访问string对象
    string divide(15, '#');//由15个#组成的对象
    cout << divide << endl;
    string day(date,5);//从位置5开始复制字符串
    day += " is a meaningful day";//重载+=
    string empty;//空
    empty = date + " , " + day;
    cout << empty << endl;
    char alls[] = "fuck you,Japanese";
    string words(alls, 14);//只取到位置14
    cout << words << endl;
    string word(alls + 9, alls + 14);//数组相当于指针，分别指向J和n后面的e，前闭后开
    cout << word << endl;
}
?
?
输出：
2
###############
2021.9.18 , 9.18 is a meaningful day
fuck you,Japan
Japan

关于新增特性的用法：

• string(string & str)noexcept 不保证str为const，被称为移动构造函数，后面还会提到

• string(initializer_list<char>il) 将列表初始化的语法用于string类，不过应该没啥用（可以用C风格字符串）

string master = {'A','L','P','H','A'}

16.1.2 string类输入

C风格字符串有三种方法：

char info[100];
cin >> info;
cin.getline(info,100,'#');//读一行，抛掉‘#’
cin.get(info,100);//保留'/n'

string对象则有两种：

string stuff;
cin >> stuff;
getline(cin,stuff);//读一行，抛掉‘/n’
getline(stuff，'#');

两者的getline都可以加上控制分界字符的参数，但string版的可以自动调节大小

string版本的getline()停止读取字符的条件有三种：

• 达到文件尾

• 遇到分界符

• 读取的字符数达到最大允许值

下面测试一下第一种情况：

int main()
{
    ifstream dog_list;
    dog_list.open("D:\\Desktop\\dog.txt");//windows中双斜杠代表'\'
    if (dog_list.is_open() == false)
    {
        cerr << "oh,shit!" << endl;
        exit(EXIT_FAILURE);
    }
    string name;
    int count = 0;
    while (dog_list)
    {
        getline(dog_list, name, '#');
        count++;
        cout << count << ":" << name << endl;
    }
    cout << "Done!";
    dog_list.close();
    return 0;
}

16.1.3 使用字符串

书上给了一个猜字母的程序，我稍微改了一下：

#include<iostream>
#include<string>
#include<fstream>
#include<cstdlib>
#include<ctime>
#include<cctype>
using namespace std;
const int NUM = 10;
const string wordlist[NUM] = { "bed","bag","bit","bee","beef","beat","boss","byd","born","burn" };
?
int main()
{
    std::srand(std::time(0));
    char play;
    cout << "玩不？<y/n>";
    cin >> play;
    play = tolower(play);
    while (play == 'y')
    {
        string target = wordlist[std::rand() % NUM];
        int length = target.length();
        string attempt(length, '-');
        attempt[0] = 'b';
        string wrongchars;
        int guesses = 6;
        cout << "首字母为b,一共有" << length
            << "个字母，可以猜6次，一次猜一个字母"
            << "你现在有" << guesses << "次机会" << endl;
        cout << "你目前的答案是：" << attempt << endl;
        while (guesses > 0 && attempt != target)
        {
            char letter;
            cout << "猜一个：";
            cin >> letter;
            if (wrongchars.find(letter) != string::npos || attempt.find(letter) != string::npos)//判断是否包含
            {
                cout << "猜过了，换一个\n";
                continue;
            }
            int loc = target.find(letter);
            if (loc == string::npos)
            {
                cout << "猜错了！\n";
                guesses--;
                wrongchars += letter;
            }
            else
            {
                cout << "猜对了\n";
                attempt[loc] = letter;
                //接下来判断是否有重复
                loc = target.find(letter, loc + 1);
                while (loc != string::npos)
                {
                    attempt[loc] = letter;
                    loc = target.find(letter, loc + 1);
                }
            }
            cout << "你现在的答案：" << attempt << endl;
            if (attempt != target)
            {
                if (wrongchars.length() > 0)
                    cout << "错误选项：" << wrongchars << endl;
                cout << "剩余" << guesses << "次机会" << endl;
            }
        }
        if (guesses > 0)
            cout << "全对！" << endl;
        else
            cout << "抱歉，答案是：" << target << endl;
        cout << "还来吗？<y/n>";
        cin >> play;
        play = tolower(play);
    }
    cout << "滚吧！";
    return 0;
}

npos变量是一个常数，对应string所能存储的最大字符数，可以用来查找字符或字符串，并将相应位置存在loc中

不过，因为有可能有重复，所以还要再进行一次循环，继续查找

除此之外，string还提供了一些其他功能，之后遇到再说

16.2 智能指针模板类

智能指针是行为类似于指针的类对象，常规指针删除后不会释放该指针所指向的内存，智能指针可以在对象过期时，让它的析构函数删除指向的内存

16.2.1 使用智能指针

基本形式如下：

auto_ptr<double> pd(new double)

其中，new double是new返回的指针，作为构造函数auto_ptr<double>的实参

下面使用另两个指针，注意要支持C++11。每一个智能指针都放在一个代码块里，这样离开代码块时，指针将过期Report负责报告对象的创建与销毁

#include<iostream>
#include<string>
#include<memory>//必须包含该头文件
using namespace std;
?
class Report
{
 ? ?private:
 ?      string str;
 ? ?
 ? ?public:
 ?      Report(const string s) : str(s)
 ? ? ?  {cout << "对象创建" << endl;}
 ?      ~Report(){cout << "对象销毁" << endl;}
 ?      void comment() const{cout << str << endl;}
};
int main()
{
 ?  { ? ?
 ? ? ? ?unique_ptr<Report> ps (new Report("使用unique"));
 ?      ps -> comment();//调用成员函数
 ?  }
 ?  {
 ? ? ? ?shared_ptr<Report> ps (new Report("使用shared"));
 ?      ps -> comment();
 ?  }
 ? ?return 0;
}

16.2.2 有关智能指针的注意事项

对于常规指针，如果两个指针指向同一个对象，删除时有可能删两次。为了避免，方法有多种：

• 定义赋值运算符，使之执行深复制，这样两个指针将指向不同的对象，其中一个对象是另一个对象的副本

• 建立所有权概念，对于特定的对象，只能有一个智能指针可拥有它，这样只有拥有对象的只能指针的构造函数会删除该对象，然后让赋值操作转让所有权。（auto_ptr和unique_ptr的策略）

• 创建更高级的指针，跟踪引用特定对象的智能指针数（称为引用计数）例如，赋值时，计数将加1，而指针过期时，计数将减1.只有当最后一个指针过期时，才调用delete，这是shared_ptr的策略

下面举一个例子：

int main()
{
 ? ?using namespace std;
 ? ?auto_ptr<string> names[5] = 
 ?  {
 ? ? ? ?auto_ptr<string> (new string("约翰塞纳")),
 ? ? ? ?auto_ptr<string> (new string("兰迪奥顿")),
 ? ? ? ?auto_ptr<string> (new string("艾吉")),
 ? ? ? ?auto_ptr<string> (new string("罗曼雷恩斯")),
 ? ? ? ?auto_ptr<string> (new string("德鲁"))
 ?  };
 ? ?auto_ptr<string> pwin;
 ? ?pwin = names[2];
 ? ?
 ? ?cout << "WWE年度超级巨星提名有：";
 ? ?for(int i = 0;i<5;i++)
 ? ? ? ?cout << *film[i] << endl;
 ? ?cout << "获得WWE年度巨星称号的是：" << *pwin << '!' << endl;
 ? ?cin.get();
 ? ?return 0;
}

上述程序会出问题，因为pwin夺走了names[2]的对象所有权，使其不能再调用原本存储的数据

所以，将中间部分改为下列代码：

shared_ptr<string> pwin;
pwin = names[2];

这样，引用计数为2，pwin调用析构函数后，计数为1，names[2]仍可以继续使用，直到它也调用析构函数，计数降为0，才会释放以前分配的空间

16.2.3 unique_ptr为何优于auto_ptr

两者都采用所有权模型，但如果所有权被剥夺，unique_ptr会主动判断为非法，而auto_ptr不会，比如：

unique_ptr<string> p3(new string("auto"));
unique_ptr<string> p4;
p4 = p3;

此时，编译器会认为语句非法

16.2.4 选择智能指针

如果程序要使用多个指向同一个对象的指针，应选择shared_ptr，例如：

• 有一个数组，使用一些辅助指针来标识特定的元素，如最大的元素和最小的元素

• 两个对象包含都指向第三个对象的指针

• 包含指针的STL容器

如果程序不需要多个指向同一个对象的指针，则可使用unique_ptr。如果函数使用new分配内存，并返回指向该内存的指针，则可将其声明为unique_ptr，这样，所有权将转让给接收返回值的unique_ptr，而智能指针将负责调用delete。

最后，尽量不要使用auto_ptr（行为不确定）

16.3 标准模板库

STL提供了一组表示容器，迭代器，函数对象和算法的模板。

其中，容器可以存储类型相同的值，类似于数组；迭代器用于遍历对象，是广义指针；函数对象是类似于函数的对象，可以是类对象或函数指针

STL不是面向对象编程，而是一种不同的编程模式——泛型编程

16.3.1 模板类vector

要创建模板对象，可使用通常的<type>表示法来指出类型，同时，vector使用动态内存分配

#include vector
using namespace std;
vector<int> rating(5);
int n;
cin >> n;
vector<double> scores(n);

16.3.2 可对vector执行的操作

STL容器都提供了一些基本的方法：

• size()——返回容器所含元素数

• swap()——交换两容器的内容

• begin()——返回指向容器第一个元素的指针

• end()——返回一个超过容器尾的指针

要为vector的double类型声明一个迭代器，可以这样做：

vector<double>::iterator pd;

vector<double> scores;
pd = scores.begin();
*pd = 22.3;
pd++;

C++11还有一种新方法：

auto pd = scores.begin();

另外，还有一些方法是某些容器所特有的：

• push_back()——将元素添加至vector尾部，并增加其长度（无需了解元素数目与容器大小）

• erase()——接收两个参数，删除给定区间的元素，前闭后开

• insert()——接收三个参数，用来确定插入位置以及插入区间

下面同时使用这些方法：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
?
struct Review
{
    string title;
    int rating;
};
bool FillReview(Review& rr);
void ShowReview(const Review& rr);
?
int main()
{
    vector<Review> books;
    Review temp;
    while (FillReview(temp))
        books.push_back(temp);
    int num = books.size();
    if (num > 0)
    {
        cout << "您将进入下面几本书：" << endl;
        for (int i = 0; i < num; i++)
            ShowReview(books[i]);
        cout << "重复：" << endl;
        vector<Review>::iterator pr;
        for (pr = books.begin(); pr != books.end(); pr++)
            ShowReview(*pr);
        vector<Review> oldlist(books);//复制使用的结构体
        if (num > 3)
        {
            //删去两个
            books.erase(books.begin() + 1, books.begin() + 3);
            cout << "删除后：" << endl;
            for (pr = books.begin(); pr != books.end(); pr++)
                ShowReview(*pr);
            //插入一个
            books.insert(books.begin(), oldlist.begin() + 1, oldlist.begin() + 2);
            cout << "插入后：" << endl;
            for (pr = books.begin(); pr != books.end(); pr++)\
                ShowReview(*pr);
        }
        books.swap(oldlist);
        cout << "交换后：" << endl;
        for (pr = books.begin(); pr != books.end(); pr++)
            ShowReview(*pr);
    }
    else
        cout << "Nothing entered,nothing gained.\n";
    return 0;
}
?
bool FillReview(Review& rr)
{
    cout << "输入书名：(输入quit退出)";
    getline(cin, rr.title);
    if (rr.title == "quit")
        return false;
    cout << "输入编号：";
    cin >> rr.rating;
    if (!cin)
        return false;//避免多余的输入行
    while (cin.get() != '\n')
        continue;
    return true;
}
?
void ShowReview(const Review& rr)
{
    cout << rr.rating << '\t' << rr.title << endl;
}
?
?
输出结果：
您将进入下面几本书：
1 ? ? ? www
4 ? ? ? ddd
3 ? ? ? hhh
5 ? ? ? iii
重复：
1 ? ? ? www
4 ? ? ? ddd
3 ? ? ? hhh
5 ? ? ? iii
删除后：
1 ? ? ? www
5 ? ? ? iii
插入后：
4 ? ? ? ddd
1 ? ? ? www
5 ? ? ? iii
交换后：
1 ? ? ? www
4 ? ? ? ddd
3 ? ? ? hhh
5 ? ? ? iii

16.3.3 对vector的其他可执行操作

下面介绍三个有代表性的STL函数

for_each()

for_each()函数可以将被指向的函数应用于容器区间中的各个元素，因此可以代替for循环

但是，它不可以改变元素的值

for_each(books.begin(),books.end(),ShowReview)//接上一个例子

random_shuffle()

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

random_shuffle(books.begin(),books.end());

该函数要求容器必须允许随机访问（如vector）

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;
}
//接上上例，由于结构体为公有，可以直接使用
sort(books.begin(),books.end());

16.3.4 基于范围的for循环

前面提到，for_each()不能改变元素的值，但是基于范围的for循环可以

void InflateReview(Review& r){r.rating++;}
for(auto& x : books)InflateReview(x);

16.4 泛型编程

面向对象编程关注的是编程的数据方面，而泛型编程聚焦于算法层面，旨在编写独立于数据类型的代码。

16.4.1 为何使用迭代器

我们以链表为例，首先用面向对象的思维编写

struct Node
{
 ? ?double item;
 ? ?Node* p_next;
};
?
Node* find_ll(Node* head, const double& val)
{
    Node* Start = head;
 ? ?for(start; start!=0; start = start->p_next)
 ? ? ? ?if(start->item == val)
 ? ? ? ? ? ?return start;
 ? ?return 0;
}

可以看出，这种算法并没有摆脱特定的数据结构，而要实现find函数，迭代器应具备下面四个特征：

• 定义*（解除引用），来访问它的值

• 定义=（赋值），将一个赋给另一个

• 定义==和！=，用于比较

• 定义++p或者p++，用于遍历

于是，我们可以定义一个iterator类，来实现这些需求：

class iterator
{
 ? ?Node* pt;
 ? ?
 ? ?public:
 ? ?iterator():pt(0){}
 ? ?iterator(Node* pn):pt(pn){}
 ? ?double iterator*(){return pt->item;}
 ? ?iterator& operator++()//定义++p
 ?  {
 ? ? ? ?pt = pt->next;
 ? ? ? ?return *this;
 ?  }
 ? ?iterator operator++(int)//定义p++
 ?  {
 ? ? ? ?iterator tmp = *this;
 ? ? ? ?pt = pt->next;
 ? ? ? ?return tmp;
 ?  }
}

接下来，就可以正式编写find函数了

iterator find_ll(iterator head, const double& val)
{
 ? ?iterator start;
 ? ?for(start = head; start!=0; start++)
 ?      if(*start == val)
 ? ? ? ? ? ?return start;
 ? ?return 0;
}

所以，在设计迭代器和容器时，要基于算法的需求。而算法要尽可能的用通用的术语来表达，使之独立于数据类型和容器类型之上

16.4.2 迭代器类型

STL定义了5种迭代器类型，分别是：

• 输入迭代器

• 输出迭代器

• 正向迭代器

• 双向迭代器

• 随机访问迭代器

这5种迭代器都有*，==，！=操作，另外两相同迭代器解除引用后仍相同，即：

iter1 == iter2;
*iter1 == *iter2;

输入迭代器

输入迭代器必须能够访问容器中的所有值（通过++来实现）

若将其指向第一个元素，可递增至超尾

基于输入迭代器的算法必须是单同行的，因为它既不能保证第二次遍历容器时顺序不变（不依赖与前一次遍历是的迭代器值），也不能保证先前的值可以解除引用（不依赖与本次遍历中前面迭代器的值）

输出迭代器

与前者类似，但只能解除引用来修改元素的值，不能读取

单通行，只读算法，可以使用输入迭代器；单通行，只写算法，可以使用输出迭代器

正向迭代器

与前两者不同的是，它可以按相同的顺序遍历一系列的值，并对前面的迭代器的值解除引用（如果保存了它），获得相同的值。因此，它可以实现多次通行算法

同时，正向迭代器读写皆可：

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

双向迭代器

它拥有正向迭代器的所有特性，并且支持两种（前后缀）递减符

随机访问迭代器

随机访问，指直接跳到容器中的任一元素，它在拥有双向迭代器所有特性的同时，还支持随机访问操作和用于对元素进行排序的关系运算符

16.4.3 迭代器层次结构

编写算法是尽可能使用要求低的迭代器，比如find()函数使用的是级别最低的输入迭代器，可用于任何包含可读值的函数，而sort()则由于需要随机访问迭代器，因此只能用于支持这种迭代器的容器

下面是五种迭代器的性能总结：

16.4.4 概念，改进和模型

将指针用作迭代器

迭代器即是广义指针，又是STL算法的接口，因此STL算法可使用迭代器来对基于常规指针的非STL容器进行操作

例如，将STL算法用于数组：

const int SIZE;
double receipts[SIZE];
?
sort(receipts,receipts+SIZE);//将其进行排序

copy()算法用于复制，它有三个迭代器参数，分别表示复制的范围和要粘贴到的位置，如：

int casts[10] = {1,2,3,4,5,6,7,8,9,0};
vector<int> dice(10);
copy(casts,casts+10,dice.begin());

ostream_iterator是一个输出迭代器的模板，也是一个适配器（类或函数）

#include<iterator>
...
ostream_iterator<int,char>out_iter(cout," ");

第一个模板参数为发送给输出流的类型，第二个模板参数为输出流使用的类型，构造函数的第一个指明了要使用的输出流，第二个是发送给每个数据项后显示的分隔符，因此，下面两个等效：

cout << 15 << " ";
*out_iter++ = 15;//将15发送给输出流，并为下一个输出流做好准备

所以，如果要将dice容器的内容复制到输出流中，在显示器上显示，可以这样：

copy(dice.begin(),dice.end(),out_iter);

当然，也可以采用匿名迭代器:

copy(dice.begin(),dice.end(),ostream_iterator<int,char>(cout," "));

同理，istream_iterator也可以这么玩：

copy(istream_iterator<int,char>(cin),
     istream_iterator<int,char>(),dice.begin());

其中，第一个参数为要读取的类型，第二个为输入流使用的类型，cin意味着通过cin管理输入流，第二行省略构造函数表示输入失败，使其停止读取

其他有用的迭代器

先来介绍一下reverse_iterator。对reverse_iterator执行递增会导致它递减，这样做当然不是因为闲的蛋疼，而是为了减少对已有函数的使用

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

int cast[4] = {1,2,3,4};
vector<int> dice(10);
copy(cast,cast+4,dice.begin());
ostream_iterator<int,char>out_iterator(cout," ");
copy(dice.rbegin(),dice.rend(),out_iterator);//隐式地使用
//下面为显式地使用
vector<int>::reverse_iterator ri;
for(ri = dice.rbegin();ri!=dice.rend();++ri)
 ? ?cout << *ri << ' ';

另外三种迭代器，包括back_insert_iterator，front_insert_iterator和insert_iterator，

#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>
?
void output(const std::string& s) { std::cout << s << " "; }
?
int main()
{
    using namespace std;
    string s1[4] = { "cena","roman","uzi","faker" };
    string s2[2] = { "yeah","noo" };
    string s3[2] = { "silly","singer2" };
    vector<string> words(4);
    copy(s1, s1 + 4, words.begin());
    for_each(words.begin(), words.end(), output);
    cout << endl;
    copy(s2, s2 + 2, back_insert_iterator<vector<string>>(words));
    for_each(words.begin(), words.end(), output);
    cout << endl;
    copy(s3, s3 + 2, insert_iterator<vector<string>>(words, words.begin()));
    for_each(words.begin(), words.end(), output);
    cout << endl;
    return 0;
}

16.4.5 容器种类

7种STL容器类型都是序列，下面是序列的一些创建方式和基本函数：

一些容器还有自己的特殊函数：

vector

vector是数组的一种类表示，它提供了自动内存管理的功能，可以动态地改变vector对象的长度，并随着元素的增加与删除而增大或缩小，它还提供了随机访问，结尾增删时间固定，开头及中间的复杂度为线性时间

同时，vector还可以是可反转容器，并且有两个类方法：rbegin()和rend()，分别返回反转序列的第一个元素的迭代器和超尾迭代器

for_each(dice.begin(),dice.end(),Show);
cout << endl;
for_each(dice.rbegin(),dice.rend(),Show);

deque

双端队列，与vector的区别：开头与结尾的增删都为固定时间

list

双向链表，任一位置增删为固定时间，但不支持数组表示法和随机访问。下面是list的成员函数：

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;
?
void outint(int n) { cout << n << " "; }
?
int main()
{
    list<int> one(5, 2);
    int stuff[5] = { 1,2,4,8,6 };
    list<int> two;
    two.insert(two.begin(), stuff, stuff + 5);
    int more[6] = { 6,4,2,4,6,5 };
    list<int> three(two);
    three.insert(three.end(), more, more + 6);
?
    cout << "list one: ";
    for_each(one.begin(), one.end(), outint);
    cout << endl << "list two: ";
    for_each(two.begin(), two.end(), outint);
    cout << endl << "list three: ";
    for_each(three.begin(), three.end(), outint);
    three.remove(2);//移除所有2
    cout << endl << "list three minus 2s: ";
    for_each(three.begin(), three.end(), outint);
    three.splice(three.begin(), one);
    cout << endl << "list three after splice: ";
    for_each(three.begin(), three.end(), outint);
    three.unique();//删去重复项
    cout << endl << "list three after unique: ";
    for_each(three.begin(), three.end(), outint);
    three.sort();
    cout << endl << "list three after sort: ";
    for_each(three.begin(), three.end(), outint);
    three.merge(two);
    //cout << endl << "Sorted two merged into three: ";
    //for_each(three.begin(), three.end(), outint);
    cout << endl;
?
    return 0;
}

forward_list(C++11)

相当于单链表，只需要正向迭代器，不需要双向，因此不能反转。

queue

相当于队列，相较于deque，不允许随机访问和遍历，只允许队尾添加和队首删除

stack

相当于栈，相较于stack，不允许随机访问和遍历，只允许在栈顶压入和弹出

16.4.6 关联容器

STL提供了4种关联容器：set，multiset，map，mutimap

set

set是关联集合，可反转，可排序，且键是唯一的（不能存储多个相同值）

既然是集合，那必然少不了相关的算法，比如求a,b的并集，打印出来：

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

如果要将并集放到c中，最后一个参数不能用c.begin( )，原因有二：

• 关键集合将键看作常量，所有c.begin()返回一个常量迭代器，而非输出迭代器

• set_union与copy类似，容器中必须有足够空间，可以进行覆盖，但不能为空

所以正确答案是创建一个insert_iterator（可以将复制转换为插入），将信息复制给C：

set_union(a.begin(),a.end(),b.begin(),b.end(),
 ? ?insert_iterator<set<string>>(c,c.begin()));

set_intersection()和set_difference()分别为交集和差集

此外，set还有两个是用的方法：lower_bound和upper_bound。前者返回一个迭代器，该迭代器指向第一个不小于键参数的成员，后者则是返回指向第一个不大于键参数的成员的迭代器

示例：

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;
const int N = 6;
?
?
int main()
{
    string s1[N] = { "dd","shiiit","bb","asxas","xs","ee" };
    string s2[N] = { "aa","bb","cc","dd","ee","ff" };
?
    set<string>a(s1, s1+ N);
    set<string>b(s2, s2+ N);
?
    ostream_iterator<string, char>out(cout, " ");
    cout << "Set a: ";
    copy(a.begin(), a.end(), out);
    cout << endl;
    cout << "a和b的差集：";
    set_difference(a.begin(), a.end(), b.begin(), b.end(), out);
    set<string>c;
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), insert_iterator<set<string>>(c, c.begin()));
    cout << endl << "a和b的交集：";
    copy(c.begin(), c.end(), out);
?
    cout << endl << "随机：";
    copy(c.lower_bound("cc"), c.upper_bound("ee"), out);
}

multimap

与set相似，mutimap也可以是反转的，经过排序的关联容器，但键和值的类型不同，且同一个键可能与多个值相关联

假如要用区号作为键来储存城市名，一种方法是创建一个pair再将它插入：

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

也可以创建匿名pair对象并将它插入：

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

对于pair对象，可以使用first和second访问它的两部分：

pair<const int,string>item(213,"Los Angeles");
cout << item.first << item.second << endl;

下面我们进行演示：

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef int KeyType;
typedef pair<const KeyType, string>Pair;
typedef multimap<KeyType, string>MapCode;
?
int main()
{
    MapCode codes;
?
    codes.insert(Pair(415, "San Francisco"));
    codes.insert(Pair(510, "Oakland"));
    codes.insert(Pair(718, "Brooklyn"));
    codes.insert(Pair(718, "Staten Island"));
    codes.insert(Pair(415, "San Rafael"));
    codes.insert(Pair(510, "Berkeley"));
?
    cout << "带415的城市有" << codes.count(415) << "个" << endl;
    cout << "带718的城市有" << codes.count(718) << "个" << endl;
    cout << "带510的城市有" << codes.count(510) << "个" << endl;
?
    MapCode::iterator it;
    for (it = codes.begin(); it != codes.end(); ++it)
        cout << " " << (*it).first << " " << (*it).second << endl;
    pair<MapCode::iterator, MapCode::iterator> range = codes.equal_range(718);
    for (it = range.first; it != range.second; it++)
        cout << (*it).second << endl;
    return 0;
}

16.5 函数对象

函数对象，也叫函数符，其实就是重载了()的类对象，使用时与函数功能类似

16.5.1 函数符概念

• 生成器是不用参数就可以调用的函数符

• 一元函数是一个参数

• 二元函数时两个参数

当然，这些概念还有改进版：

• 返回bool值的一元函数叫谓词

• 返回bool值的二元函数叫二元谓词

举个例子，假设要删除另一个链表中所有大于200的值，可以设计一个TooBig类，使用类成员而非函数参数来传递“200”这个信息：

template<class T>
 ? ?class TooBig
 ?  {
 ? ? ? ?private:
 ? ? ?      T cutoff;
 ? ? ? ?public:
 ? ? ?      TooBig(const T & t) : cutoff(t){}
 ? ? ?      bool operator()(const T & v){return v > cutoff;}
 ?  };

这里，v作为函数参数传递，cutoff是由类构造函数设置的。这样，在调用list的成员函数remove_if（将谓词作为参数，返回true则删除该元素）时，就可以像下面这样做：

TooBig<int> f100(100);
list<int> fff = {1,2,3,4,31,2};
list<int> ggg = {5,3,2,123,6,9};
fff.remove_if(f100);
ggg.remove_if(TooBig<int>(200));//匿名使用

16.5.2 预定义的函数符

STL定义了多个基本函数符，来支持将函数作为参数的STL函数，例如，transform()函数有两个版本。第一个版本可传递4个参数，前两个参数为容器区间，第三个为复制到哪里，第四个为函数符，对每个元素进行操作：

const int LIM = 5;
double arr[LIM] = {16,25,36,49,64,81};
vector<double> gr(arr,arr+6);
ostream_iterator<double,string>out(cout," ");
transform(gr.begin(),gr.end(),out,sqrt);

第二个版本则在第二个参数后再加一个参数，用于表示第二个区间的起始位置

假设mean(double,double)函数会返回两个参数的平均值，mr也是一个vector，则有：

transform(gr.begin(),gr.end(),mr.begin(),out,mean);

如果要执行相加操作，可以使用plus<>类来完成常规类型的相加运算

plus<double> add;
transform(gr.begin(),gr.end(),mr.begin(),out,add);
transform(gr.begin(),gr.end(),mr.begin(),out,plus<double>());

运算符和相应的函数符：

16.6 算法

对于算法函数设计，有两个主要的通用部分。首先，它们都使用模板来提供泛型；其次，它们都使用迭代器来提供访问容器中数据的通用表示

16.6.1 算法组

STL将算法库分成4组：

• 非修改式序列操作：对区间中的每个元素进行操作。这些操作不修改容器的内容，例如：find()和for_each()

• 修改式序列操作：可以修改内容，修改值以及排列顺序，如transform() , random_shuffle() , copy()

• 排序和相关操作：包括多个排序函数（如sort()）和其他各种函数，如集合操作

• 通用数字运算：包括内容累积，计算两个容器的内部乘积，计算小计，计算相邻对象差的函数，一般为数组的操作特性，故常见与vector

16.6.2 使用STL

假设要编写一个程序，让用户输入单词，并记录每个单词背输入的次数。

输入和保存单词列表很简单：

vector<string> words;
string input;
while(cin << input && input != "quit")
 ? ?word.push_back(input);

接下来，可以使用sort()和unique()来得到按字母顺序排列的单词表，但会覆盖原数据，故还可以创建一个set<string>对象，将内容复制进集合，再进行排序。另外，集合的键是惟一的，省去了unique

set<string> wordset;
transform(words.begin(),words.end(),insert_iterator<set<string>>(wordset,wordset.begin()),ToLower);

其中，ToLower函数用于转小写，代码如下：

string & ToLower(string * st)
{
 ? ?transform(st.begin(),st.end(),st.begin(),tolower);
 ? ?return st;
}

然后，利用count函数，将一个区间和一个值作为参数，返回这个值在区间出现的次数。为了关联单词和计数，可将pair<const string,int>对象存储在map中：

map<string,int>wordmap;
set<string>::itreator si;
for(si = wordset.begin();si!=wordset.end();si++)
 ? ?wordmap.insert(pair<string,int>(*si,count(words.begin(),words.end(),*si)));

map可以用数组表示法来表示与键关联的值，所以输出结果也可以这样写：

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

16.7 其他库

16.7.1 模板initializeer_list

它是C++11新增的，可以使用初始化列表语法将STL容器初始化为一系列值：

std::vector<double> payments{45.11,43.22,41.33,51.22};

这将创建一个包含4个元素的容器，并使用列表中的4个值来初始化这些元素

另外，还有一个问题：

std::vector<int> vi{10}

上面标示的是下面哪个构造函数呢？

std::vector<int> vi(10);//包含10个未初始化的元素
std::vector<int> vi({10});//包含1个初始化值为10的元素

答案应该是第二个

最后，简单地使用一下它：

#include <iostream>
#include <initializer_list>
using namespace std;
?
double sum(initializer_list<double> il);
double average(const initializer_list<double>& ril);
?
int main()
{
    cout << "sum = " << sum({ 2,3,4 }) << ",ave = " << average({ 2,3,4 }) << endl;
    return 0;
}
?
double sum(initializer_list<double> il)
{
    double tot = 0;
    for (auto p = il.begin(); p != il.end(); p++)
        tot += *p;
    return tot;
}
?
double average(const initializer_list<double>& ril)
{
    double tot = 0;
    int n = ril.size();
    double ave = 0.0;
    if (n > 0)
    {
        for (auto p = ril.begin(); p != ril.end(); p++)
            tot += *p;
        ave = tot / n;
    }
    return ave;
}