C/C++ 语法教程（14）——STL 简介（1）

wzf2000
2019年12月2日

C/C++ 语法教程（14）——STL 简介（1）

C++ STL

时隔 $n$ 年我又来更新啦！

STL 组成

主要就三种：容器、算法和迭代器。

听起来很高大上，然而也不用知道这么多。

C++ 常用算法

一般只需要 #include <algorithm> 即可调用（当然请不要忘记 using namespace std;，否则你可能每个函数或方法都需要前置 std::）。

一、sort()

一般的使用中 sort() 传入两个参数，分别代表首地址和尾地址后一位，在学过后面的容器之后，也可以使用对应的迭代器，如：

sort(a,a+n);
sort(b.begin(),b.end());
sort(begin(c),end(c));

这里的第一个就是将 a[0] 至 a[n-1] 从小到大排序，后两个则是使用了容器的对应迭代器，同样从小到大排序。

这里默认的排序是利用 < 进行。

当然在没有定义 < 或者需要排序依据不同时也可以传入第三个参数，也就是比较函数（可以是一般的函数，或者函数对象，或者 lambda 函数）。

比如想从大到小排序，可以有许多种写法：

bool cmp1(int x,int y)
{
    return x>y;
}
class CMP2
{
public:
    bool operator ()(int x,int y)
    {
        return x>y;
    }
};

sort(a,a+n,cmp1);

sort(a,a+n,greater<int>);

CMP2 cmp2;

sort(a,a+n,cmp2);

sort(a,a+n,[](const int &x,const int &y){ return x>y; });

这四种甚至其他更多方法都是可以的。（不知道函数对象不急，会前两种就行）

可以发现 C++ STL 的使用方法非常多样化，这是因为 STL 本身就是面向对象的，所以对于不理解的部分完全可以在学过面向对象后再来尝试阅读。

除此之外还有 stable_sort() 和 partial_sort()，它们分别可以做到：

1. 不改变原来序列中相等元素相对顺序的情况下排序。
2. 挑出最小的若干个（指定）元素，排序完并置于最前面。

具体可以自行了解。

二、nth_element()

这个函数跟 sort() 极为类似，只不过在 sort() 前两个参数之间新增了一个参数。

比如：

nth_element(a,a+i,a+n);

这代表将 a[] 数组中第 $i + 1$ 小的放至 a[i]，并使得 a[0] 至 a[i-1] 均小于等于 a[i]，a[i + 1] 至 a[n-1] 均大于等于 a[i]。

同样可以自定义比较函数。

特别注意，这个函数的时间复杂度为 $O(n)$。

三、lower_bound() 和 upper_bound()

int *ptr=lower_bound(a,a+n,x);
int i=lower_bound(a,a+n,x)-a;

这样的调用会返回 a[0] 到 a[n-1] 中第一个不小于 $x$ 的元素的指针。

当然前提是 a[] 数组已经升序排列。

这里的前两个参数还是可以跟上面所说一样，也同样可以自己给出升序的比较函数。

而 upper_bound 唯一的区别，便是变为找到第一个大于 $x$ 的元素的指针。

四、其他常用算法

比如 next_permutation()、prev_permutation()、unique()、is_sorted()、replace() 等等。

这些算法（函数）功能奇特，但是相对不那么常用，还想了解可以点这里自己学习。

迭代器

一、迭代器分类

主要分为五类：

具体来说：

1. 输入迭代器：支持 ++（前后置均可）、==、!=、*（仅作为右值（赋值语句右侧））、->。
2. 输出迭代器：支持 ++（前后置均可）、*（仅作为左值（赋值语句左侧））。
3. 前向迭代器：支持上述两种所有操作，且可以通过预先备份返回原位置，也就是可以多次访问同一位置。
4. 双向迭代器：除上述外，还支持 --（前后置均可）。
5. 随机访问迭代器：提供在常量时间内访问容器任意位置的功能，额外支持 <、>、<=、>=、+、-、+=、-=，以及两个迭代器相减可以得到距离，iter[n] 依然等价于 *(iter+n)。

二、迭代器与算法

在算法中传递的迭代器或者获得的迭代器也是会有要求，可以根据算法特点分别判断，因为具体而言太过复杂，就不写了。

三、迭代器与指针

1. 迭代器不是指针，是类模板，表现的像指针。它只是封装了某些运算符（方法之后会讲），从而表现得像指针。
2. 迭代器返回的是对象引用而不是对象的值，所以 cout 只能输出迭代器使用 * 取值后的值而不能直接输出其自身。
3. 迭代器可以提供一种在不需要暴露某个容器的内部表现形式情况下，依然能依次访问该容器中的各个元素的方法。
4. 指针能指向函数而迭代器不行，迭代器只能指向容器。
5. 有时候可以认为指针是迭代器的一种，指针只能用于某些特定的容器，而迭代器是指针的抽象和泛化。所以，指针满足迭代器的一切要求。

string 类

需要包含头文件 <string>（同样最好 using namespace std;）。

一、基础使用

定义和输入输出一个 string 类型变量可以采用：

string stuff;
cin>>stuff;
getline(cin, stuff);
cout<<stuff;

二、构造函数和析构函数

有如下几种定义并构造 string 型变量的方法：

string s; //生成空字符串
string s(str); //生成字符串 str 的复制品
string s(str, stridx); //将字符串 str 中始于 stridx 的部分作为构造函数的初值
string s(str, strbegin, strlen); //将字符串 str 中始于 strbegin、长度为 strlen 的部分作为字符串初值
string s(num, c); //生成一个字符串，包含num个c字符
string s(strs, beg, end);    //以区间 [beg, end] 内的字符作为字符串 s 的初值

最常见的就是：

string s("abc");

同样还有析构函数（大概就是销毁这个变量的方法）：

string s;
s.~string();

三、获取长度

一般使用 .size() 或者 .length() 方法即可。

比如：

string s("abc");
cout<<s.length()<<endl;

就会输出 $3$。

四、获取对应元素

可以使用 s[i] 的方法获取 string s 的第 $i$ 个字符，当然也可以使用 s.at(i) 的写法。

一般来说 s.at(i) 的写法更安全一些，当然如果保证程序无问题就不用考虑这么多。

（.at() 方法是返回引用的函数，所以也可以作为左值（赋值运算符左侧））

五、比较方法

C++ STL 中内置了 string 的 <、>、==、<=、>=、!= 的比较运算符，而且不止可以在 string 类型之间使用，还可以比较 string 和 char * 类型，可以直接使用，但是请不要对空字符串使用这些比较运算符，否则程序很可能异常退出。

当然还有专门的函数：

int compare(const basic_string& s) const;
int compare(const Ch* p) const;
int compare(size_type pos, size_type n, const basic_string& s) const;
int compare(size_type pos, size_type n, const basic_string& s,size_type pos2, size_type n2) const;
int compare(size_type pos, size_type n, const Ch* p, size_type = npos) const;

具体使用方法可以自己查询尝试。

举个例子：

#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string A ("aBcdef");
    string B ("AbcdEf");
    string C ("123456");
    string D ("123dfg");
    //下面是各种比较方法
    int m=A.compare (B); //完整的A和B的比较
    int n=A.compare(1,5,B,4,2); //"Bcdef"和"AbcdEf"比较
    int p=A.compare(1,5,B,4,2); //"Bcdef"和"Ef"比较
    int q=C.compare(0,3,D,0,3); //"123"和"123"比较
    cout << "m = " << m << ", n = " << n <<", p = " << p << ", q = " << q << endl;
    return 0;
}

结果是：

m = 1, n = -1, p = -1, q = 0

六、相关迭代器

string 类型的迭代器是随机存取迭代器，常用迭代器有：

1. string::iterator s.begin() ：表示字符串开始位置，指向 s[0]；
2. string::iterator s.end()：表示字符串结束位置，指向 s 的最后一个字符之后一位（不能用 * 运算符）；
3. string::reverse_iterator s.rbegin()：表示字符串反转（abc 反转后为 cba）后的开始位置。
4. string::reverse_iterator s.rend()：表示字符串反转后的结束位置。

七、字符串内容修改和替换

前置知识（或者叫强行插入）：

1. 可以使用 s.c_str() 方法获取将 string 转为 char * 类型后的值。

2. string::npos 表示此类型可表示最大数（因为是无符号整型，相当于值为 $-1$），可认为无穷大。

首先可以通过获取对应元素并直接赋值的方法，也可以直接使用 = 运算符赋值。

除此之外，还有 assign()、erase()、swap()、insert()、append()、replace()，详细使用方法直接看例子：（重点是掌握足够多的的方法使得无论遇到什么需求都可以应对，不是每种都需要记下来）

#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str1 ("123456");
    string str2 ("abcdefghijklmn");
    string str;
    str.assign(str1); // 把 str1 赋值给 str
    cout << str << endl;
    str.assign (str1 , 3, 3); // 从 str1[3] 开始向后取三位赋值给 str
    cout << str << endl;
    str.assign (str1, 2, str1.npos); // 从 str1[2] 开始到结束赋值给 str
    cout << str << endl;
    str.assign (5, 'X'); // 重复 5 个 'X' 字符赋值给 str
    cout << str << endl;
    string::iterator itB;
    string::iterator itE;
    itB = str1.begin ();
    itE = str1.end();
    str.assign (itB, (--itE)); // 从 str[0] 到倒数第二个字符赋值给 str
    cout << str << endl;
    str = str1; // 直接将 str1 赋值给 str
    cout << str << endl;
    str.erase(3); // 从 str[3] 开始将后面的字符删除
    cout << str << endl;
    str.erase (str.begin (), str.end()); // 删除整个字符串
    cout << ":" << str << ":" << endl;
    str.swap(str2); // 将 str 与 str2 交换
    cout << str << endl;
    string A ("ello");
    string B ("H");
    B.insert (1, A); // 在 B[1] 开始插入 A
    cout << B << endl;
    A = "ello";
    B = 'H';
    B.insert (1, "yanchy ", 3); // 在 B[1] 开始插入 "yanchy " 的前三个字符
    cout << "插入: " << B << endl;
    A = "ello";
    B = "H";
    B.insert(1, A, 2, 2); // 在 B[1] 开始插入 A[2] 开始长度为 2 的子串
    cout << "插入:" << B << endl;
    A = "ello";
    B = "H";
    B.insert (1, 5, 'C'); // 在 B[1] 开始插入 5 个 'C'
    cout << "插入:" << B << endl;
    A = "ello";
    B = "H";
    string::iterator it = B.begin () +1;
    const string::iterator itF = A.begin ();
    const string::iterator itG = A.end ();
    B.insert(it, itF, itG);
    cout<<"插入："<< B << endl; // 在 B[1] 开始 插入 A
    A = "ello";
    B = "H";
    cout << "A = " << A <<", B = " << B << endl ;
    B.append (A);
    cout << "追加：" << B << endl; // 在 B 后追加 A
    B = "H";
    cout << "A = "<< A << ", B= " << B << endl;
    B.append("12345", 2); // 在 B 后追加 "12345" 的前两个字符
    cout << "追加：" << B << endl;
    A = "ello";
    B = "H";
    cout << "A = " << A << ", B= " << B << endl;
    B.append ("12345", 2, 3); // 在 B 后追加 s="12345" 从 s[2] 开始的长度为 3 的子串
    cout << "追加：" << B << endl;
    A = "ello";
    B = "H";
    cout << "A = " << A <<", B = " << B << endl;
    B.append (10 , 'a'); // 在 B 后追加 10 个 'a' 字符
    cout << "追加:"<< B << endl;
    A = "ello";
    B = "H";
    cout << "A = " << A << ", B = " << B << endl;
    B.append(A.begin() , A.end()); // 在 B 后追加 A
    cout << "追加:" << B << endl;
    string var ("abcdefghijklmn");
    const string dest ("1234");
    string dest2 ("567891234");
    var.replace (3, 3, dest); // 将 var[3] 开始长度为 3 的子串替换为 dest
    cout << "1: " << var << endl;
    var = "abcdefghijklmn";
    var.replace (3, 1, dest.c_str(), 1, 3); // 将 var[3] 开始长度为 1 的子串替换为 dest[1] 开始长度为 3 的子串
    cout << "2: " << var << endl;
    var ="abcdefghijklmn";
    var.replace (3, 1, 5, 'x'); // 将 var[3] 开始长度为 1 的子串替换为 5 个 'X' 字符
    cout << "3: " << var << endl;
    string::iterator itA;
    string::iterator itC, itD;
    itA = var.begin();
    itB = var.end();
    var = "abcdefghijklmn";
    var.replace (itA, itB, dest); // 将原来的 var.begin() 到 var.end() 这段子串（var[0..17]）替换为 dest
    cout << "4: " << var << endl;
    itA = var.begin ();
    itB = var.end();
    itC = dest2.begin () +1;
    itD = dest2.end ();
    var = "abodefghijklmn";
    var.replace (itA, itB, itC, itD); // 将原来的 var.begin() 到 var.end() 这段子串（var[0..3]）替换为 dest2[1] 开始到结束的子串
    cout << "5: " << var << endl;
    var = "abcdefghijklmn";
    var.replace (3, 1, dest.c_str(), 4); // 将 var[3] 开始长度为 1 的子串替换为 dest[0] 开始长度为 4 的子串
    cout <<"6: " << var << endl;
    return 0;
}

输出结果是：

123456
456
3456
XXXXX
12345
123456
123
::
abcdefghijklmn
Hello
插入: Hyan
插入:Hlo
插入:HCCCCC
插入：Hello
A = ello, B = H
追加：Hello
A = ello, B= H
追加：H12
A = ello, B= H
追加：H345
A = ello, B = H
追加:Haaaaaaaaaa
A = ello, B = H
追加:Hello
1: abc1234ghijklmn
2: abc234efghijklmn
3: abcxxxxxefghijklmn
4: 1234
5: 67891234efghijklmn
6: abc1234efghijklmn

需要注意的是，以上长度不足的，大多是取到字符串结束为止，但可能有部分出入，建议具体自行尝试。

八、字符串查找

主要由 find() 和 rfind() 两种函数，分别是正向查找和逆向查找，返回值为第一次查找成功时，开始匹配上的位置（类型是 string::size_type 也就是无符号整型！），如果未能找到返回 string::npos。

除此之外的几个函数使用较少，不展开叙述。

举几个例子：

#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str_ch (" for");
    string str (" Hi, Peter, I'm sick. Please bought some drugs for me.");
    string::size_type m= str.find ('P', 5); // 从 str[5] 开始的子串中正序查找 'P'
    string::size_type rm= str.rfind('P', 5); // 从 str[5] 开始的子串中逆序查找 'P'
    cout << "Example - find() : The position (forward) of 'P' is: " << (int) m << endl;
    cout << "Example - rfind(): The position (reverse) of 'P' is: " << (int) rm << endl;
    string::size_type n = str.find (" some", 0); // 从 str[0] 开始的子串中正序查找 " some"
    string::size_type rn = str.rfind (" some", 0); // 从 str[0] 开始的子串中逆序查找 "emos "
    cout << "Example - find () : The position (forward) of 'some' is: " << (int) n << endl;
    cout << "Example - rfind () : The position (reverse) of 'some' is: " << (int) rn << endl;
    string::size_type mo = str.find (" drugs", 0, 5); // 从 str[0] 开始的子串中正序查找 " drugs" 的前 5 个字符（不足就按全串算）
    string::size_type rmo = str.rfind (" drugs", 0, 5); // 从 str[0] 开始的子串中逆序查找 "sgurd " 的前 5 个字符（不足就按全串算）
    cout << "Example - find(): The position (forward) of 'drugs' is: " << (int) mo << endl;
    cout << "Example - rfind(): The position (reverse) of 'drugs' is: " << (int) rmo << endl;
    string::size_type no = str.find (str_ch, 0); // 与上述同理
    string::size_type rno = str.rfind(str_ch, 0); // 与上述同理
    cout << "Example - find (): The position of 'for' is: " << (int) no << endl;
    cout << "Example - rfind(): The position of 'for' is: " << (int) rno << endl;
    return 0;
}

输出结果如下：

Example - find() : The position (forward) of 'P' is: 5
Example - rfind(): The position (reverse) of 'P' is: 5
Example - find () : The position (forward) of 'some' is: 35
Example - rfind () : The position (reverse) of 'some' is: -1
Example - find(): The position (forward) of 'drugs' is: 40
Example - rfind(): The position (reverse) of 'drugs' is: -1
Example - find (): The position of 'for' is: 46
Example - rfind(): The position of 'for' is: -1

理论上还有 string 的配置器等内容，然而我这个是真的啥也不会，就不献丑了。

习题

由于作者已经被这些乱七八糟的 STL 搞自闭了，所以上演习题消失大法。

行吧，这真的上面这些够练习了，不多说了，我自己先学会。

 教程 语法