C/C++ 语法教程(14)——STL 简介(1)

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() 等等。

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

迭代器

一、迭代器分类

主要分为五类:

迭代器类型迭代器特征
Input iterator(输入迭代器)读,不能写;只支持自增运算
Output iterator(输出迭代器)写,不能读;只支持自增运算
Forward iterator(前向迭代器)读和写;只支持自增运算
Bidirectional iterator(双向迭代器)读和写;支持自增和自减运算
Random access iterator(随机访问迭代器)读和写;支持完整的迭代器算术运算

具体来说:

  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 类型之间使用,还可以比较 stringchar * 类型,可以直接使用,但是请不要对空字符串使用这些比较运算符,否则程序很可能异常退出。

当然还有专门的函数:

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 搞自闭了,所以上演习题消失大法。

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

 

点赞 0

No Comments

Add your comment