C++面向对象程序设计-北京大学-郭炜【课程笔记（十一）】

1、string（重要知识点）
- 1.2、string的赋值和链接
- 1.3、比较string
- 1.4、子串
- 1.5、交换string
- 1.6、寻找string中的字符
- 1.7、删除string中的字符
- 1.8、替换string中的字符
- 1.9、在string中插入字符（重要）
- 1.10、转换成C语言式char * 字符串
- 1.11、字符串流处理
- 1.12、字符串流处理-字符串输出流istringstream
2、标准模板库STL
- 1.1、STL的基本概念
- 1.2、容器概述
- 2.3、顺序容器
3、迭代器
- 2.1、迭代器的定义与使用
- 2.2、双向迭代器
- 2.3、随机访问迭代器
4、算法简介
- find()函数原型
- 参数
- 返回值
- 使用方法
- 示例
- - 示例1：在 `vector` 中查找元素
  - 示例2：在 `list` 中查找元素
  - 示例3：在数组中查找元素
  - 注意事项
  - 小结
5、STL中“大” “小”的概念
- 5.1、重要说明

做毕业答辩变PPT脱了几天，终于要结束读书生涯了，哈哈。
开始课程：P40 1_1. string类
课程链接：程序设计与算法（三）C++面向对象程序设计北京大学郭炜
课程PPT：github提供的对应课程PPT

1、string（重要知识点）

学了string类就可以不用char*类当字符串用了。

string类：

string类是模板类
- typedef basic_string<char> string;
使用string类要包含头文件#include<string>
string对象的初始化：
- string s1(“Hello”);
- string month = “March”;
- string s2(8, ‘x’); // 8个x

注意事项：错误的初始化方式：

string error1 = 'c'; // 错（直接用一个字符初始化一个string对象是不可以的）
可以将字符赋值给string对象；
- string s;
- s = ‘c’; // OK
string error2(‘u’); // 错
string error3 = 22; // 错
string error4(8); // 错

#include<iostream>
#include<string>
using namespace std;

int main(int argc, char * argv[])
{
    string s1("hello");
    cout << s1 << endl;      // hello
    string s2(8, 'x');       
    cout << s2 << endl;      // xxxxxxxx
    string month = "March"; 
    cout << month << endl;   // March
    string s;
    s = 'n';
    cout << s << endl;       // n

    return 0;
}

string对象的长度用成员函数length()读取；
- string s(“hello”);
cout << s.length() << endl;
string支持流读取运算符
- string stringObject；
- cin >> stringObject;
string支持getline函数
- string s；
- getline(cin, s);
用 = 赋值
- string s1(“cat”), s3;
- s2 = s1;
用assign长远函数赋值
- string s1(“cat”), s3;
- s3.assign(s1);
用assign成员函数部分复制
- string s1(“catpig”), s3;
- s3.assign(s1, 1, 3);
- // 从s1中下标为1的字符开始复制3个字
耽搁字符复制
- s2[5] = s1[3] = ‘a’;
逐个访问string对象中的字符
- string s1(“Hello”);
- for(int i=0; i<s1.length(); i++)
- {cout << s1.at(i) << endl;}
成员函数at会做范围检查，如果超出范围，会抛出out_of_renge异常，而下标运算符[]不做范围检查。

1.2、string的赋值和链接

用+运算符连接字符串
- string s1(“good”), s2(“morning!”);
- s1 += s;
- cout << s1;
用成员函数append连接字符串
- string s1(“good”), s2(“morning!”);
- s1.append(s2);
- cout << s1;
- s2.append(s1, 3, s1.size()); //s1.size(), s1字符数
- cout << s2;
- // 下标为3开始，s1.size()个字符，如果字符穿内没有足够字符，则复制到字符串最后一个字符

1.3、比较string

用关系运算符比较string的大小
- 返回值都是bool类型，成立返回true，否则返回false
- 例如：

#include<iostream>
#include<string>
using namespace std;

int main(int argc, char * argv[])
{
    string s1("hello"), s2("hello"), s3("hello");
    bool b = (s1 == s2);
    cout << b << endl;
    b = (s1 == s3);
    cout << b << endl;
    b = (s1 > s3);
    cout << b << endl;

    return 0;
}
// OUT
1
1
0

用成员函数compare比较string的大小
例题1:

#include <iostream>
#include <string>
#include <cctype>
using std::cout;
using std::endl;
using std::cin;
using std::string;
int main(void){
	string str1="hi,test,hello";
	string str2="hi,test";
	//字符串比较
	if(str1.compare(str2)>0)
		printf("str1>str2\n");
	else if(str1.compare(str2)<0)
		printf("str1<str2\n");
	else
		printf("str1==str2\n");
	
	//str1的子串（从索引3开始，包含4个字符）与str2进行比较
	if(str1.compare(3,4,str2)==0)
		printf("str1的指定子串等于str2\n");
	else
		printf("str1的指定子串不等于str2\n");
	
	//str1指定子串与str2的指定子串进行比较
	if(str1.compare(3,4,str2,3,4)==0)
		printf("str1的指定子串等于str2的指定子串\n");
	else
		printf("str1的指定子串不等于str2的指定子串\n");
	
	//str1指定子串与字符串的前n个字符进行比较
	if(str1.compare(0,2,"hi,hello",2)==0)
		printf("str1的指定子串等于指定字符串的前2个字符组成的子串\n");
	else
		printf("str1的指定子串不等于指定字符串的前2个字符组成的子串\n");
	return 0;
}
// OUT:
str1>str2
str1的指定子串不等于str2
str1的指定子串等于str2的指定子串
str1的指定子串等于指定字符串的前2个字符组成的子串

例题2:

#include<iostream>
#include<string>
using namespace std;

int main(int argc, char * argv[])
{
    string s1("hello"), s2("hello"), s3("hell");
    int f1 = s1.compare(s2);   // 0  // hello == hello
    int f2 = s1.compare(s3);   // 1  // hello > hell
    int f3 = s3.compare(s1);   // -1 // hell < hello
    int f4 = s1.compare(1, 2, s3);    // -3 
    int f5 = s1.compare(0, s1.size(), s3);  // 1

    cout << f1 << endl << f2 << endl << f3 << endl;
    cout << f4 << endl << f5 << endl;

    return 0;
}

注意事项：C++中int f4 = s1.compare(1, 2, s3);结果显示为-3，为什么

在 C++ 的 std::string 类中，compare 函数的第一个参数是起始位置，第二个参数是要比较的长度，第三个参数是要比较的字符串。当调用 s1.compare(1, 2, s3) 时，表示从 s1 的索引位置 1 开始，比较长度为 2 的子字符串与 s3 的内容。如果 s1 的子字符串小于 s3，则返回值为负数，且返回值的绝对值表示两个字符串第一个不相等字符的 ASCII 码差值的相反数。因此，结果为 -3 表示在比较的过程中，第一个不相等字符在 ASCII 码上 s1 的子字符串要小于 s3。

1.4、子串

成员函数substr

string s1("hello world"), s2;
s2 = s1.substr(4,5);  // 下标4开始5个字符
cout << s2 << endl;  // 输出：o wor

1.5、交换string

成员函数swap

string s1("hello world"), s2("really");
s1.swap(s2);
cout << s1 << endl;  // really
cout << s2 << endl;  // hello world

1.6、寻找string中的字符

成员函数find()
- string s1(‘hello world’);
- s1.find(“lo”);
- 在s1中从前向后查找“lo“第一次出现的地方，如果找到，返回”lo“开始的位置，即I所在的位置下标。如果找不到，返回string::npos（string 中定义的京塔常量）。

请添加图片描述

1.7、删除string中的字符

成员函数erase()
- string s1(“hello world”);
- s1.erase(5);
- cout << s1; // hello
- cout << s1.length(); // 5
- cout << s1.size(); // 5
  // 去掉下标5及之后的字符
  // 输出：hello55

1.8、替换string中的字符

成员函数replace()
- string s1(“hello world”);
- s1.replace(2,3, “haha”);
- cout << s1; // hehaha world
- // 将s1中下标2开始的3个字符换成“haha”

1.9、在string中插入字符（重要）

请添加图片描述

1.10、转换成C语言式char * 字符串

在C++中，c_str()函数用于返回一个指向以空字符结尾的数组的指针，该数组包含了作为 std::string 对象内容的字符序列的副本。这个函数通常用于将 std::string 对象转换为 C 风格的字符串（以空字符结尾的字符数组），以便与需要使用 C 风格字符串的函数进行交互。注意，返回的指针指向的字符数组是 const char* 类型的，因此不能直接修改该数组的内容。

在C++中，data()函数用于返回一个指向 std::string 对象中存储的字符数据的指针。与c_str()函数不同，data()函数不会在字符串的末尾添加空字符(‘\0’)，因此返回的指针可以用于修改字符串的内容。需要注意的是，在修改返回的指针所指向的字符串时，要确保不会超出字符串的长度，否则会导致未定义的行为。

1.11、字符串流处理

请添加图片描述

#include<string>
#include<iostream>
#include<sstream>
using namespace std;

int main()
{
    string input("Input test 123 4.7 A");
    istringstream inputString(input);
    string string1, string2;
    int i;
    double d;
    char c;
    inputString >> string1 >> string2 >> i >> d >> c;
    cout << string1 << endl << string2 << endl;
    cout << i << endl << d << endl << c << endl;
    long L;
    if(inputString >> L)
    {
        cout << "long\n";
    }
    else cout << "empty\n";
}
// OUT
Input
test
123
4.7
A
empty

这段代码使用了C++的字符串流类istringstream来解析一个字符串input。下面是对代码的逐行解释：

#include<string>：包含了C++标准库中的string头文件，提供了字符串操作的功能。
#include<iostream>：包含了C++标准输入输出流的头文件，提供了输入输出功能。
#include<sstream>：包含了C++标准库中的字符串流头文件，提供了字符串流的功能。
using namespace std;：使用了命名空间std，这样就可以直接使用标准库中的类和函数，而不需要加上std::前缀。
string input("Input test 123 4.7 A");：定义了一个字符串input，内容为"Input test 123 4.7 A"。
istringstream inputString(input);：定义了一个字符串流inputString，并将input作为初始化参数。
string string1, string2;：定义了两个字符串变量string1和string2。
int i;：定义了一个整型变量i。
double d;：定义了一个双精度浮点型变量d。
char c;：定义了一个字符型变量c。
inputString >> string1 >> string2 >> i >> d >> c;：使用字符串流inputString依次读取字符串、字符串、整型、双精度浮点型和字符，分别赋值给string1、string2、i、d和c。
cout << string1 << endl << string2 << endl;：输出变量string1和string2的值，并换行。
cout << i << endl << d << endl << c << endl;：输出变量i、d和c的值，并换行。
long L;：定义了一个长整型变量L。
if(inputString >> L)：尝试从字符串流inputString中读取一个长整型值到变量L中，如果成功读取则执行下面的代码块，否则执行else中的代码块。
{ cout << "long\n"; }：如果成功读取了长整型值，则输出"long"并换行。
else cout << "empty\n";：如果未能成功读取长整型值，则输出"empty"并换行。

这段代码的功能是将字符串input中的各个部分分别解析为不同类型的变量，并输出它们的值。

1.12、字符串流处理-字符串输出流istringstream

#include<string>
#include<iostream>
#include<sstream>
using namespace std;

int main()
{
    ostringstream outputString;
    int a = 10;
    outputString << "This" << a << "ok" << endl;
    cout << outputString.str();  //This10ok

    return 0;
}
// OUT
This10ok

这段代码演示了如何使用 ostringstream 类来构建一个字符串流，并将各种类型的数据写入其中，最后将其作为一个字符串输出到标准输出流中。

ostringstream outputString;：创建一个 ostringstream 对象 outputString，用于构建一个字符串流。
outputString << "This" << a << "ok" << endl;：使用 << 操作符将字符串 "This"、整数 a 和字符串 "ok" 以及换行符 endl 依次写入到 outputString 中。
cout << outputString.str();：使用 str() 方法获取 outputString 中的字符串内容，并将其输出到标准输出流 cout 中。
return 0;：返回主函数的结束。

2、标准模板库STL

请添加图片描述

1.1、STL的基本概念

请添加图片描述在这里插入图片描述

1.2、容器概述

在这里插入图片描述

2.3、顺序容器

在这里插入图片描述
请添加图片描述

3、迭代器

2.1、迭代器的定义与使用

定义一个容器类的迭代器的方法可以是：

容器类名::iterator 变量名；
容器类名::const_iterator 变量名；

访问一个迭代器指向的元素：

* 迭代器变量名

迭代器上可以执行++操作，以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，则会报错，类似于使用NULL或未初始化的指针一样。
例题：

#include<vector>
#include<iostream>
using namespace std;

int main()
{
    vector<int> v;  // 一个存放int元素的数组，一开始里面没有元素
    v.push_back(1); v.push_back(2); 
    v.push_back(3); v.push_back(4);

    vector<int>::const_iterator i;  // 常用迭代器
    for(i = v.begin(); i != v.end(); i++)
    {
        cout << *i << ",";   // 1,2,3,4,
    }
    cout << endl;
    
    vector<int>::reverse_iterator r;  // 反向迭代器
    for(r = v.rbegin(); r!=v.rend(); r++)
    {
        cout << *r << ",";  // 4,3,2,1,
    }
    cout << endl;
    
    vector<int>::iterator j; // 非常量迭代器
    for(j=v.begin(); j != v.end(); j++)
        *j = 100;  // 容器中数组每个元素赋值100
    for(i=v.begin(); i != v.end(); i++)
        cout << *i << ",";   // 100,100,100,100
}
// OUT
STL % ./1
1,2,3,4,
4,3,2,1,
100,100,100,100

2.2、双向迭代器

在这里插入图片描述

2.3、随机访问迭代器

在这里插入图片描述

p<p1的含义：p指向的这个元素他在p1所指向这个元素的前面。

vector的迭代器是随机迭代器，遍历vector可以有以下几种做法（deque亦然）：

#include<vector>
#include<iostream>
using namespace std;

int main()
{
    vector<int> v(5); // 创建一个包含100个元素的整数向量，默认初始化为0
    int i;
    for(i=0;i<v.size();i++) // 使用下标遍历vector
        cout << v[i];  // 根据下标随机访问，并输出每个元素
    cout << ";" << endl;
    // 定义一个常量迭代器ii，通过for循环遍历向量v，并输出每个元素。
    vector<int>::const_iterator ii; 
    for(ii=v.begin(); ii != v.end(); ii++) // 使用常量迭代器遍历vector
        cout << *ii;  // 输出迭代器指向的元素
    cout << ";" << endl;
    for(ii = v.begin(); ii < v.end(); ii++) // 使用常量迭代器遍历vector（条件使用<）
        cout << *ii;  // 输出迭代器指向的元素
	cout << ";" << endl;
    // 间隔一个元素输出
    ii= v.begin();
    while(ii < v.end()) // 迭代器方式间隔输出
    {
        cout << *ii;  // 输出当前迭代器指向的元素
        ii = ii + 2;  // 将迭代器向前移动两个位置
    }
    
    return 0;
}
// OUT
00000;
00000;
00000;
0
0
0

list的迭代器是双向迭代器，正确遍历list的方法如下：

请添加图片描述

4、算法简介

在这里插入图片描述

C++ 中的 find() 函数用于在容器（如数组、vector、list 等）中查找特定元素。它是 <algorithm> 头文件中的一个标准算法。下面是 find() 函数的详细介绍，包括其使用方法和例子。

find()函数原型

find() 函数有多个重载版本，最常用的版本如下：

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

参数

first：指向输入范围的起始位置的迭代器。
last：指向输入范围的结束位置的迭代器（不包含在范围内）。
value：要查找的元素的值。

返回值

如果找到匹配的元素，返回指向该元素的迭代器。
如果没有找到匹配的元素，返回 last。

使用方法

find() 函数遍历从 first 到 last 范围内的元素，比较每个元素与 value 是否相等。如果找到相等的元素，则返回一个指向该元素的迭代器；否则，返回一个指向 last 的迭代器。

示例

以下是 find() 函数的几个使用示例。

示例1：在 `vector` 中查找元素

#include <iostream>
#include <vector>
#include <algorithm> // 包含 find() 函数的头文件

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 查找元素3
    auto it = std::find(vec.begin(), vec.end(), 3);
	
	// std::distance(vec.begin(), it) 是 C++ 标准库中的一个实用函数，用于计算两个迭代器之间的距离（即元素的数量）。
    if (it != vec.end()) {
        std::cout << "Found element 3 at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Element 3 not found." << std::endl;
    }

    return 0;
}

输出：

Found element 3 at position: 2

示例2：在 `list` 中查找元素

#include <iostream>
#include <list>
#include <algorithm> // 包含 find() 函数的头文件

int main() {
    std::list<int> lst = {10, 20, 30, 40, 50};

    // 查找元素30
    auto it = std::find(lst.begin(), lst.end(), 30);

    if (it != lst.end()) {
        std::cout << "Found element 30." << std::endl;
    } else {
        std::cout << "Element 30 not found." << std::endl;
    }

    return 0;
}

输出：

Found element 30.

示例3：在数组中查找元素

#include <iostream>
#include <algorithm> // 包含 find() 函数的头文件

int main() {
    int arr[] = {5, 10, 15, 20, 25};

    // 查找元素20
    auto it = std::find(std::begin(arr), std::end(arr), 20);

    if (it != std::end(arr)) {
        std::cout << "Found element 20 at position: " << (it - std::begin(arr)) << std::endl;
    } else {
        std::cout << "Element 20 not found." << std::endl;
    }

    return 0;
}

输出：

Found element 20 at position: 3

#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

int main()
{
    // find 算法示例
    int array[10] = {10,20,30,40};
    vector<int>v;
    v.push_back(1); v.push_back(2);
    v.push_back(3); v.push_back(4);

    vector<int>::iterator p;
    p = find(v.begin(), v.end(), 3);
    if(p != v.end())
    {
        cout << *p << endl;  // 输出3
    }
    p = find(v.begin(), v.end(), 9);
    if(p==v.end())
        cout << "not found " << endl;
    p = find(v.begin()+1, v.end()-2, 1); // 整个容器：[1,2,3,4],查找区间：[2,3)

    if(p != v.end())
        cout << *p << endl;
    
    int *pp = find(array, array+4, 20);  // 数组名是迭代器
    cout << * pp << endl;
}

输出：
3
not found 
3
20

注意事项

find() 函数使用的是元素的相等比较运算符 ==，因此要查找的元素类型必须支持该运算符。
find() 函数只能用于支持输入迭代器的范围。
如果要查找的容器是有序的，可以考虑使用更高效的算法，如 std::binary_search 或 std::lower_bound。

小结

find() 函数是一个简单而强大的工具，用于在各种容器中查找元素。它的使用非常直观，通过传递开始和结束迭代器，以及要查找的值，即可轻松找到目标元素。在实际应用中，可以结合其他算法和数据结构，根据具体需求选择合适的查找方法。

5、STL中“大” “小”的概念

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;

class A
{
    int v;
public:
    A(int n) : v(n) {}
    bool operator < (const A& a2) const
    {
        cout << v << "<" << a2.v << "?" << endl;
        return false;
        // return v < a2.v; // 修改返回值为比较实际数值
    }
    bool operator == (const A& a2) const
    {
        cout << v << "==" << a2.v << "?" << endl;
        return v == a2.v;
    }
};

int main()
{
    A a[] = {A(1), A(2), A(3), A(4), A(5)};
    // 修改为搜索整个数组范围
    // boolalpha：使 cout 输出布尔值时，显示 true 或 false 而不是 1 或 0。
    cout << boolalpha << binary_search(a, a + 5, A(9)) << endl; // 折半查找

    return 0;
}

代码逐行解释：
下面是对你提供的代码进行逐行解释：

#include <iostream>
#include <algorithm>
using namespace std;

#include <iostream>：包含输入输出流的头文件，用于输入输出操作，如cout。
#include <algorithm>：包含标准库算法的头文件，用于调用binary_search函数。
using namespace std;：使用标准命名空间，避免在使用标准库对象时每次都加std::前缀。

class A
{
    int v;
public:
    A(int n) : v(n) {}
    bool operator < (const A& a2) const
    {
        cout << v << "<" << a2.v << "?" << endl;
        return false;
        // return v < a2.v; // 修改返回值为比较实际数值
    }
    bool operator == (const A& a2) const
    {
        cout << v << "==" << a2.v << "?" << endl;
        return v == a2.v;
    }
};

定义一个类 A，表示一个包含整数成员变量 v 的类。
int v;：私有成员变量，存储整数值。
A(int n) : v(n) {}：构造函数，初始化成员变量 v 为传入的参数 n。
bool operator < (const A& a2) const：重载小于运算符，用于比较两个 A 对象。输出比较信息，但总是返回 false（此处注释掉了实际的比较逻辑 return v < a2.v;）。
bool operator == (const A& a2) const：重载等于运算符，用于比较两个 A 对象。输出比较信息，并返回两个对象的 v 值是否相等。

int main()
{
    A a[] = {A(1), A(2), A(3), A(4), A(5)};
    // 修改为搜索整个数组范围
    cout << boolalpha << binary_search(a, a + 5, A(9)) << endl; // 折半查找

    return 0;
}

int main()：主函数，程序执行的入口。
A a[] = {A(1), A(2), A(3), A(4), A(5)};：创建一个 A 对象数组，包含五个元素，每个元素的 v 值分别为 1, 2, 3, 4, 5。
cout << boolalpha << binary_search(a, a + 5, A(9)) << endl;：
- binary_search(a, a + 5, A(9))：在数组 a 中使用二分查找法查找是否存在值为 9 的 A 对象。
- boolalpha：使 cout 输出布尔值时，显示 true 或 false 而不是 1 或 0。
- 将查找结果输出到控制台，并换行。

5.1、重要说明

当前的 operator < 函数总是返回 false，这会导致 binary_search 函数无法正确比较对象，因此始终返回 false。要使 binary_search 函数正常工作，需将 operator < 的实现改为实际比较数值，如下所示：
```
bool operator < (const A& a2) const
{
    cout << v << "<" << a2.v << "?" << endl;
    return v < a2.v;
}
```
这样可以正确地进行比较，并使二分查找能够正确地工作。