目录

注意

  1. 以下代码均在 using namespace std; 下执行
  2. 每个示例均为单独的示例。如下示例 pop_back 和 push_back 均单独对 res 进行操作，互不影响
// 修改 - pop_back
res.pop_back();                 // 弹出最后一个元素，还剩 1,2,3,4
// 修改 - push_back
res.push_back(6);               // 在末尾追加一个元素，1,2,3,4,5,6

常用数据结构及其常用操作

vecotor

  1. 头文件：<vector>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化 列表初始化
初始化 构造函数初始化
容量 size 返回容器实际使用的大小 返回容器实际使用的大小
容量 capacity 返回容器总容量大小 返回容器总容量大小
容量 empty 判断容器是否为空 若为空返回 true，否则返回 false
访问 [] 查找下标的元素值，无边界检查 返回值
访问 at 查找下标的元素值，有边界检查 返回值
访问 back 查找尾部元素 返回值（引用）
访问 front 查找头部元素 返回值（引用）
操作 push_back 在容器末尾追加元素 √
操作 emplace_back 在容器末尾追加元素，比 push_back 效率更高 √
操作 pop_back 在容器末尾弹出最后一个元素 √
操作 insert 通过迭代器，在指定位置插入元素 √
操作 earse 移除容器中的元素 被删除元素下一位置的有效迭代器 √
操作 clear 清除容器中所有元素 √
操作 swap 交换两个 vector 容器的内容，两个容器的大小可以不同，但数据类型要相同 √

初始化

	// 构造函数初始化
    vector<int> res(10, -1); 		// 初始化 10 个 -1
    vector<int> res(10); 	 		// 初始化 10 个 0
    vector<int> res2;               // size 为 0
    // 列表初始化
    vector<int> vec{};              // 使用{},此时 size 为 0
    vector<int> res = {1,2,3,4,5}; 
    vector<string> articles = {"a", "an", "the"};
    // 二维 vector 初始化
    vector<vector<int> > empty; // 一个空的二维 vector
    vector<vector<int> > newOne(num1, vector<int>(num2, 0)); // 二维 vector 初始化，num1 和 num2 表示初始化的数量
	// 初始化中的设计缺陷
	vector<string> v7(10); // 这里的类型是 string，10 在此表示 10 个空字符串
	vector<string> v8{10, "hi"} // 这里的类型是 string，虽然是花括号，但 10 为 int，推断出是表示数量

容量

	// size
    cout << res.size() << endl;     // vector 的实际使用数量 5
    // capacity
    cout << res.capacity() << endl; // vector 的总容量 5
    // empty
    cout << res.empty() << endl;   // 0，表示 false，即不为空；1 表示 true，即为空

访问

    // []
    cout << res[1] << endl; // 2
    cout << res[5] << endl; // 危险!超出边界也可以访问
    // at
	cout << res.at(1) << endl; 	  // 2
	// cout << res.at(5) << endl; // at 会进行边界检查，超过边界抛出异常
    // back
    cout << res.back() << endl;     // 5
    // front
    cout << res.front() << endl;    // 1

操作

    // pop_back
    res.pop_back();                 // 弹出最后一个元素，还剩 1,2,3,4
    // push_back
    res.push_back(6);               // 在末尾追加一个元素，1,2,3,4,5,6
    // insert
    res.insert(++res.begin(), 100);    // 在 vector 下标为 1 处插入元素 100，vector 变为 1 100 2 3 4 5
    res.insert(++res.begin(), 2, 100); // 在 vector 下标为 1 处插入两个元素 100，vector 变为 1 100 100 2 3 4 5
    res.insert(++it, {100, 100, 100}); // 在 vector 下标为 1 处插入一个列表结构，结构中包含 3 个为 100 的元素，vector 变为 1 100 100 100 2 3 4 5
    res.insert(res.end(), res2.begin(), res2.end()); // 将 res2 拼接到 res 尾部
    // insert 实现头插
    for (int i = 0; i < 10; i++) {
	    icon.insert(newRes.begin(), i); // 9 8 7 6 5 4 3 2 1 0
	}
    // erase
    res.erase(it);          // 移除 it 迭代器所在位置的元素（移除一个）
    res.erase(first, last); // 移除一个范围迭代器所在位置的元素，first 和 last 表示迭代器
    // clear
    res.clear(); // 清除容器中所有元素size 为 0， capacity 为 5 
    // 交换
    res.swap(res2); // res 变为空，res2 变为 1 2 3 4 5

【注】push_back 可以用来实现尾插，而 insert 可以用来实现头插
遍历

map

  1. 头文件：<map>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化 列表初始化
初始化 insert 初始化时赋值
初始化 make_pair 初始化时赋值
初始化 [] 初始化时赋值
容量 size 返回容器大小 返回容器大小
容量 empty 判断容器是否为空 若为空返回 true，否则返回 false
访问 [] 访问不存在的 key 时，自动插入该 key，size 自增 1
访问 at 访问不存在 key 时，抛出异常
查找 find 查找是否存在 key，若存在返回指向该 key 的迭代器，否则返回 end 迭代器
查找 count 查找 key 在 map 中的数量，由于 map 中 key 是唯一的，所以只会返回 1 数量值
操作 insert 插入一个容器的元素 √
操作 erase 删除元素 √
操作 clear 清除容器中所有元素，size 变为 0 √

查找 key 在 map 中的数量，由于 map 中 key 是唯一的，所以只会返回 1
初始化

// 列表初始化
map<string, int> studentGrade1 = {{"zhangsan", 100}, {"lisi", 95}, {"wangwu", 90}};

// insert 初始化并赋值
map<string, int> studentGrade2;
studentGrade2.insert({"zhangsan", 100});
studentGrade2.insert({"lisi", 95});
studentGrade2.insert({"wangwu", 90});

// make_pair 初始化并赋值
studentGrade3.insert(make_pair("zhangsan", 100));
studentGrade3.insert(make_pair("lisi", 95));
studentGrade3.insert(make_pair("wangwu", 90));

// [] 初始化并赋值
map<string, int> studentGrade3;
studentGrade4["zhangsan"] = 100;
studentGrade4["lisi"] = 95;
studentGrade4["wangwu"] = 90;

容量

// empty
cout << studentGrade2.empty() << endl; // 0，即 false，表示不为空，否则为 true
// size
cout << studentGrade2.size()  << endl; // 3

访问

// []
cout << studentGrade2["zhangsan"] << endl; // 100
// [] - 访问不存在的 key 时，自动插入该 key，size 自增 1
cout << studentGrade2["zhaoliu"] << endl;  // 100，此时 studentGrade2.size() 为 4
   
// at
cout << studentGrade2.at("lisi") << endl; // 95
// at - 访问不存在 key 时，抛出异常
// cout << studentGrade2.at("zhuqi") << endl; // 95

// find
cout << studentGrade2.find("zhangsan")->first << " " << studentGrade2.find("zhangsan")->second << endl; // zhangsan 100

查找

// find - 查找是否存在 key，若存在返回指向该 key 的迭代器，否则返回 end
cout << studentGrade2.find("zhangsan")->first << " " << studentGrade2.find("zhangsan")->second << endl; // zhangsan 100

// count - 查找 key 在 map 中的数量，由于 map 中 key 是唯一的，所以只会返回 1
cout << studentGrade2.count("zhangsan") << endl; // 1

操作

// insert
studentGrade2.insert(pair<string, int>("lili", 91));
cout << studentGrade2.at("lili") << endl; // 91
    
// erase - 通过 key 值删除
studentGrade2.erase("lili"); // lili 被移除
    
// clear - 清空 map
studentGrade2.clear();

set

  1. 头文件：<set>
  2. 常用操作
分类 小类 操作 返回值 原地操作
修改 insert 插入一个容器元素 √
修改 erase 删除一个容器元素 √
修改 clear 清除所有容器元素，size 变为 0 √

pair

  1. 头文件：<utility>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化 默认构造函数初始化
初始化 构造函数初始化
初始化 初始化列表
初始化 make_pair
访问 first，second 获取 pair 的第一个和第二个元素值 元素值

初始化

// 默认构造函数初始化
std::pair<int, double> p1; 

// 构造函数初始化
std::pair<int, double> p2(1, 2.0); 

// 初始化列表
std::pair<int, double> p3{1, 2.0}; 

// make_pair
auto p4 = std::make_pair(1, 2.0);

访问

cout << p3.first << endl;  // 1
cout << p3.second << endl; // 2

tuple

  1. 头文件：<tuple>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化 make_tuple 初始化
初始化 构造函数初始化
初始化 初始化列表
访问 get<idx>(tupleName) 获取 idx 位置上的 tuple 值 元素值

初始化

// make_tuple 初始化
auto myTuple = std::make_tuple(10, 3.14, 'a'); 

// 构造函数初始化
std::tuple<int, double, char> myTuple(10, 3.14, 'a'); 

// 初始化列表初始化
std::tuple<int, double, char> myTuple{10, 3.14, 'a'}; 

// tie 初始化
int a = 10;
double b = 3.14;
char c = 'a';
std::tuple<int, double, char> myTuple = std::tie(a, b, c);

访问

// 访问 tuple 的元素，0，1，2 是索引下标
std::get<0>(myTuple); // 10
std::get<1>(myTuple); // 3.14
std::get<2>(myTuple); // a

string

  1. 头文件：<string>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化 字面量初始化
初始化 构造函数初始化
初始化 列表初始化
容量 size 返回字符串长度 字符串长度
容量 length 返回字符串长度，等同于 size 字符串长度
容量 capacity 返回分配的大小 字符串容量
容量 empty 判断是否为空字符串 若为空返回 true，否则返回 false
容量 [] 返回字符串下标所对应的字符，无边界检查 字符
容量 at 返回字符串下标所对应的字符，有边界检查 字符
容量 back 返回最后一个字符 字符值
容量 front 返回第一个字符 字符
修改 += 追加字符（串） 字符串 √
修改 append 追加字符（串） 字符串 √
修改 push_back 追加字符 √
修改 pop_back 弹出最后一个字符 √
修改 insert 通过迭代器，在指定位置插入字符（串） 字符串 √
修改 erase 移除 string 中的字符（串） 字符串 √
修改 clear 清空字符串 字符串 √
修改 replace 替换字符（串） 字符串 √
特殊操作 swap 交换两个 string 容器的内容，两个容器的大小可以不同 √
特殊操作 c_str 获取 c 风格字符串 新字符串 ×
特殊操作 find 在字符串中查找字符（串） 第一次匹配的下标
特殊操作 find_first_of 查找子串中任意字符第一次在父串中出现的下标 第一次匹配的下标
特殊操作 find_last_of 查找子串中任意字符最后一次在父串中出现的下标 最后一次匹配的下标
特殊操作 find_first_not_of 查找父串中不属于子串的任意字符第一次出现的下标 满足条件的下标
特殊操作 find_last_not_of
特殊操作 substr 截取子串 截取的子串 ×
特殊操作 compare 比较字符串大小 相等则返回 ==0；!=0，表示字符串不相等；<0 表示 str1 的第一个不相同字符小于 str2 的第一个不相同字符，或 str1 短于 str2；>0 反之
特殊操作 npos 静态常量，字符串长度最大值，用于 find 操作中，没有找到子串时的比较

初始化

    // 字面量初始化
    string str1 = "Literal Initialization"; // 后续以 str1 和 str2 为例
    // 构造函数初始化
    string str2("Constructor initialization");
    // 列表初始化
    string str3{"List Initialization"};
    // 列表初始化
    string str4 = {"List Initialization"};

容量

	// size
    cout << str1.size() << endl; // 22，返回字节数
    // length 等效于 size
    cout << str1.length() << endl; // 22，返回字节数
    //  capacity 字符串的实际容量，该值 >= size 和 length
    cout << str1.capacity() << endl; // 22，返回字节数
    // empty
    cout << str1.empty() << endl; // false 表示非空，true 表示空

访问

	// []
    cout << str1[0] << endl;      // L
    // at
    cout << str1.at(0) << endl;   // L
    // front
    cout << str1.front() << endl; // L
    // back
    cout << str1.back() << endl;  // n

修改

// +=
cout << (str1 += " str1") << endl; // Literal Initialization str1

// append - 追加单个字符
cout << str1.append("L") << endl; // Literal InitializationL
// append - 追加字符串
cout << str1.append(str2) << endl; // Literal InitializationConstructor initialization
// append - 追加字符串 - 0 表示 str2 起始地址，11 表示追加的个数
cout << str1.append(str2, 0, 11) << endl; // Literal InitializationConstructor
// append - 追加字符串 - 使用迭代器
cout << str1.append(str2.begin(), str2.begin() + 11) << endl; // Literal InitializationConstructor

// 追加单个字符
str1.push_back('L');  // 错误写法：str1.push_back('L')
cout << str1 << endl; // Literal InitializationL

// 修改 - 弹出末尾字符
str1.pop_back();      // 弹出末尾的字符
cout << str1 << endl; // Literal Initializatio，n 被弹出

// insert - 指定位置插入一个字符
cout << str1.insert(8, "_") << endl;   // Literal _Initialization
// insert - 指定位置插入字符串
cout << str1.insert(str1.length(), str2) << endl;   // Literal InitializationConstructor initialization
// insert - 指定位置插入子串
// str1.length()：要插入的位置
// str2：被插入的字符串
// 0：被插入字符串的子串起始位置
// 2：从起始位置截取的长度
cout << str1.insert(str1.length(), str2, 0, 2) << endl; // Literal InitializationCo

// 删除某个位置的元素
str.erase();     // 删除全部元素，执行后 size 为 0
str.erase(2);    // 从下标为 2 的元素开始删除到结尾（包含下标 2）
str.erase(2, 1); // 删除下标为 2 位置的元素，这里的 1 表示删除的字符个数

// replace - 从 str1 第 0 位起，长度为 7 的子串被 str2 替换
cout << str1.replace(0, 7, str2) << endl; // Constructor Initialization Initialization
// replace - 从 str1 第 0 位起，长度为 7 的子串被 str2 第 0 位起，长度为 7 的子串替换
cout << str1.replace(0, 7, str2, 0, 11) << endl; // Constructor Initialization
// 支持迭代器方式

// 交换两个字符串
str1.swap(str2);
cout << str1 << " | " << str2 << endl; // onstructor Initialization | Literal Initialization

特殊操作

// c_str
const char* cString = str.c_str();
std::cout << cString << std::endl; // 输出: Hello, World!

// find - 查找子串
cout << str1.find("Initialization") << endl; // 8。**返回第一次匹配的下标**
// find - 查找子串，从指定位置（str1 的第 8 位）开始
cout << str1.find("Initialization", 8) << endl; // 8
// find - 查找子串，从指定位置（str1 的第 0 位）开始，长度为 7
cout << str1.find("Literal", 0, 7) << endl; // 0

// find_first_of - 查找子串中任意字符第一次在 str1 中出现的位置
cout << str1.find_first_of("Initialization") << endl; // 1。因为 Initialization 中 i 字符最开始出现在 Literal 的第 1 位中

// find_last_of - 查找子串中任意字符最后一次在 str1 中出现的位置    
cout << str1.find_last_of("Initialization") << endl; // 21。因为 Initialization 中 n 字符最后出现在 str1 的最后一位中

// find_first_not_of - 查找 str1 中不属于子串的任意字符第一次出现的下标
cout << str1.find_first_not_of("Literal") << endl; // 7。下标 7 是空格，子串中没有空格字符

// substr - 截取子串
cout << str1.substr(0, 7) << endl; // Literal
cout << str1.substr(0) << endl;    // Literal Initialization，若没有第二个参数，则表示截取一直到末尾

// compare - 比较 str1 和 str2 是否相同
cout << str1.compare(str2) << endl; // !=0，表示字符串不相等；<0 表示 str1 的第一个不相同字符小于 str2 的第一个不相同字符，或 str1 短于 str2；>0 反之
// compare - 将 Initialization 和 str1 从第 8 位开始，长度为 14 的子串比较
cout << str1.compare(8, 14, "Initialization") << endl; // 0
// compare - 比较 str1 从第 8 位开始，长度为 14 的子串和 str2 从第 12 位起，长度为 14 的子串
cout << str1.compare(8, 14, str2, 12, 14); // 0

// string::npos：静态常量，字符串长度最大值，用于 find 操作中，没有找到子串时的比较
size_t found = str.find(toFind);
if (found == std::string::npos) std::cout << "'" << toFind << "' not found in the string." << std::endl;

array

  1. 头文件：<array>
  2. 常用操作
分类 小类 操作 返回值 原地操作
初始化
访问 [] 返回字符串下标所对应的字符，无边界检查 元素值
访问 at 返回字符串下标所对应的字符，有边界检查 元素值
访问 front 返回第一个字符 元素值
访问 back 返回最后一个字符 元素值
容量 empty 判断容器是否为空 若为空返回 true，否则返回 false
容量 size 返回容器长度 长度值
操作 fill 用值填充容器 √
操作 swap 交换容器之间的内容 √

初始化并赋值

	array<int, 5> arr1 = {1,2,3,4,5};

访问

    // [] - 下标访问，无边界限制
    cout << arr1[0] << endl; // 1
    cout << arr1[5] << endl; // 可以访问越界值，危险

	// at - 下标访问，有边界限制
    cout << arr1.at(0) << endl; // 1
    cout << arr1.at(5) << endl; // 抛出异常

    // front - 访问数组第一个元素
    cout << arr1.front() << endl; // 1

    // back - 访问数组最后一个元素
    cout << arr1.back() << endl; // 5

容量

    // empty - 判断容器是否为空
    cout << arr1.empty() << endl; // 0，即 false，也就是不为空。反之为 true

    // size - 返回容器的大小
    cout << arr1.size() << endl; // 5

操作

    // fill - 填充所有元素
    arr1.fill(100); // 100 100 100 100 100。所有元素被 100 填充

    // swap - 交换两个容器 - 要求 array 大小相同，这一点和 vector 不同
    // arr1 6 7 8 0 0
    // arr2 1 2 3 4 5
    arr1.swap(arr2);

list

  1. 描述：双向链表，支持快速插入和删除，但访问速度较慢
  2. 常用操作
    1. 初始化
    2. 访问
      1. front
      2. back
    3. 容量
      1. empty
      2. size
    4. 修改
      5. insert
      6. push_back
      7. pop_back
      8. push_front
      9. pop_front
      10. swap
      11. erase
      12. clear
    5. 操作
      1. merge
      2. splice
      3. remove
      4. unique
      5. sort

常用算法函数

排序

快速排序

  1. 头文件：<algorithm>
  2. 注意点：不能使用 sort 对 map 或 set 进行排序，因为 map 和 set 本身就是有序的，当你向 map 或 set 中插入一个元素，map 或 set 会进行全量自排序
    vector<int> vec = {3, 1, 2, 9, 5};

    sort(vec.begin(), vec.end());

    for( auto v : vec){
        cout << v << " "; // 1 2 3 5 9
    }
    cout << endl;

    sort(vec.begin(), vec.end(), greater()); // 降序排列
    for( auto v : vec){
        cout << v << " "; //  9 5 3 2 1 
    }
    cout << endl;

数组翻转

  1. 头文件：<algorithm>
    vector<int> vec = {3, 1, 2, 9, 5};

    reverse(vec.begin(), vec.end());

    for( auto v : vec){
        cout << v << " "; // 5 9 2 1 3 
    }
    cout << endl;

    int arr[] = {3, 1, 2, 9, 5};
    reverse(begin(arr), end(arr)); // 这种写法针对 c 型数组这种没有迭代器的数据结构
    for( auto v : vec){
        cout << v << " "; // 5 9 2 1 3 
    }
    cout << endl;

绝对值

  1. c 风格
    1. cmath 头文件中的 abs：取整数绝对值函数
    2. cmath 头文件中的 fabs：取浮点数绝对值函数
  2. c++ 11 风格：cmath 头文件中的 std::abs 取任意数值类型绝对值函数
  3. 示例
// abs
#include <iostream>
#include <cmath> // 包含 abs() 函数

int main() {
    int num = -5;
    int absoluteValue = abs(num); // 计算绝对值
    std::cout << "绝对值: " << absoluteValue << std::endl; // 输出: 绝对值: 5
    return 0;
}
// fabs
#include <iostream>
#include <cmath> // 包含 fabs() 函数

int main() {
    double num = -3.14;
    double absoluteValue = fabs(num); // 计算绝对值
    std::cout << "绝对值: " << absoluteValue << std::endl; // 输出: 绝对值: 3.14
    return 0;
}

// std::abs
#include <iostream>
#include <cmath>

int main() {
    int intNum = -10;
    float floatNum = -2.5f;
    double doubleNum = -7.89;

    std::cout << "int 绝对值: " << std::abs(intNum) << std::endl;      // 10
    std::cout << "float 绝对值: " << std::abs(floatNum) << std::endl;  // 2.5
    std::cout << "double 绝对值: " << std::abs(doubleNum) << std::endl; // 7.89

    return 0;
}

最值

std::max 和 std::min

  1. 描述：比较两个数的大小
  2. 返回值：最值
  3. 头文件：<algorithm>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a = 10;
    int b = 20;
    cout << max(a, b) << endl; // 20
    cout << min(a, b) << endl; // 10
    cout << max(3.14, 3.15) << endl; // 3.15
    cout << max('a', 'z') << endl;   // z

    return 0;
}

min_element，max_element 和 minmax_element

  1. 描述：返回一个序列中的最值
  2. 返回值：指向最值的迭代器
  3. 头文件：<algorithm>
// 在顺序容器中取最值
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec{1,2,3,4,5,6,7};

    cout << *(max_element(vec.begin(), vec.end())) << endl; // 7。最大值
    cout << *(min_element(vec.begin(), vec.end())) << endl; // 1。最小值

	// minmax_element 第一个元素（first）为最小值，第二个元素（second）为最大值
    cout << *(minmax_element(vec.begin(), vec.end())).first << endl; // 1
    cout << *(minmax_element(vec.begin(), vec.end())).second << endl;// 7

    return 0;
}

// 在关联容器中取最值，以 map 为例
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    map<int, string> mapTest = {{1, "grade 1"}, {2, "grade 2"}, {3, "grade 3"}};

    auto it = max_element(mapTest.begin(), mapTest.end()); // 默认比较 key

    cout << it->first << endl; // 3

    return 0;
}

求和

  1. 头文件：<numeric>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main()
{
    vector<int> nums = {1,2,3,4,5,6,7,8,9};
    // 0 表示初始化 sum 的值
    int sum = accumulate(nums.begin(), nums.end(), 0); // 45
    cout << sum << endl;
}

查找

  1. 头文件：<algorithm>
  2. 举例来说，假设有数据结构图 vector<tuple<int, int, int>> tempVar，此时如果我们想从 tempVar 找到符合要求的元素应该怎么做呢
#include <algorithm>
#include <tuple>
#include <vector>

using TupleType = std::tuple<char, int, int>;

// 查找完全匹配的元组
auto findTuple(const std::vector<TupleType>& vec, const TupleType& target) {
    return std::find(vec.begin(), vec.end(), target);
}

// 使用示例
int main() {
    std::vector<TupleType> vec = {
        {'a', 1, 10},
        {'b', 2, 20},
        {'c', 3, 30}
    };
    
    TupleType target = {'b', 2, 20};
    auto it = findTuple(vec, target);
    
    if (it != vec.end()) {
        // 找到元素
    } else {
        // 未找到
    }
}
  1. 查找自定义数据类型：需要重载自定义数据类型的 ==

假设自定义数据类型为 Person

#include <iostream>
#include <vector>
#include <algorithm> // for std::find
#include <string>

struct Person {
    std::string name;
    int age;

    // 重载 == 运算符，用于比较两个 Person 是否相等
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

将 Person 作为 vector 的参数

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    Person target = {"Bob", 25};

    // 使用 std::find 查找目标元素
    auto it = std::find(people.begin(), people.end(), target);

    if (it != people.end()) {
        std::cout << "Found: " << it->name << ", " << it->age << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

二分查找

  1. 头文件：<algorithm>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {1,2,3,4,5,6,7,8,9};
    auto pos1 = lower_bound(vec.begin(), vec.end(), 2);
    auto pos2 = upper_bound(vec.begin(), vec.end(), 2);
    auto flag = binary_search(vec.begin(), vec.end(), 2);
    cout << "first >= 2 position " << *pos1 << endl;     // 2
    cout << "first > 2 position " << *pos2 << endl;      // 3
    cout << "is there equal 2 number " << flag << endl;  // 1
}
  1. 若要求小于等于和小于，则使用 greater<Type>() 这个仿函数来处理
// 示例如下
// 返回 nums 中第一个小于或等于 target 元素位置的迭代器
lower_bound(nums.begin(), nums.end(), target, greater<int>());

// 返回 nums 中第一个小于 target 元素位置的迭代器
upper_bound(nums.begin(), nums.end(), target, greater<int>());

去重

  1. 描述：去除数列中重复的函数，但并非真正的去重，而是将重复的元素往后放，如果要实现真正的去重，就需要辅助使用 earse 来擦除
int main(){
    vector<int> vec = {1,1,2,3,3,4,4,5};
    auto pos = unique(vec.begin(), vec.end()); // pos 为第一个被移至末尾的重复项的迭代器
    
    for(int v : vec) cout << v << ' '; // 1 2 3 4 5 4 4 5
    cout << endl;
    
    vec.erase(pos, vec.end());
    
    for(int v : vec) cout << v << ' '; // 1 2 3 4 5 
    cout << endl;
    
    return 0;
}

【注】类似的还有 remove 和 earse 组合使用

lower_bound，upper_bound 和 binary_search

  1. 描述：以上三个算法底层都采用二分查找实现，所以需要数列是有序的
  2. lower_bound：查找当前有序数列中，大于等于 target 的值的位置
  3. upper_bound：查找当前有序数列中，大于 target 的值的位置
  4. binary_search：查找当前有序数列中，是否存在 target，若存在则返回 1，否则返回 0
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec = {1,2,3,4,5,6,7,8,9};
    auto pos1 = lower_bound(vec.begin(), vec.end(), 2);
    auto pos2 = upper_bound(vec.begin(), vec.end(), 2);
    auto flag = binary_search(vec.begin(), vec.end(), 2);
    cout << "first >= 2 position " << *pos1 << endl;     // 2
    cout << "first > 2 position " << *pos2 << endl;      // 3
    cout << "is there equal 2 number " << flag << endl;  // 1
}
  1. 若要求小于等于和小于，则使用 greater<Type>() 这个仿函数来处理
// 示例如下
// 返回 nums 中第一个小于或等于 target 元素位置的迭代器
lower_bound(nums.begin(), nums.end(), target, greater<int>());

// 返回 nums 中第一个小于 target 元素位置的迭代器
upper_bound(nums.begin(), nums.end(), target, greater<int>());

字符串相关

数字字符转数字

  1. 描述：字符数字转为数值类型。之所以这么操作有效，是因为是用的数字字符的 ascii 码相减，而其他数字字符的 ascii 和 ‘0’ 的 ascii 差值正好为其他数字字符对应的整型数字
int main() {
    char c = '5';
    int num = '5' - '0';
    cout << num << endl; // 5

    return 0;
}

【注】数字字符无法使用下文中的 stoi 等函数进行转换，因为 stoi 等函数的参数要求是字符串类型

字符串转数字（含进制转换）

  1. 描述：字符串数字转换为数值类型
  2. 头文件：<string>
  3. 函数分类
    1. stoi：转换为 int 类型
    2. stol：转换为 long int 类型
    3. stoll：转换为 long long int 类型
    4. stof：转换为 float 类型
    5. stod：转换为 double 类型
    6. …
  4. 返回值：数值
#include <iostream>
#include <string>

using namespace std;

int main() {
    string strNum  = "12345";					// 期望转换为 int
    string strNum2 = "123456789";				// 期望转换为 long int
    string strNum3 = "3.1415";					// 期望转换为 float
    string strHex  = "40F1";            		// 期望转换为 16 进制，对应 10 进制 16625
    string strBin  = "100000011110001"; 		// 期望转换为 2 进制，对应 10 进制 16625
    string strMix  = "123abc";					// 混合
    string strMix2  = "abc123abc";				// 混合

    cout << stoi(strNum) << endl;  				// 12345
    cout << stol(strNum2) << endl; 				// 123456789
    cout << stof(strNum3) << endl; 				// 3.1415
    cout << stoi(strHex, nullptr, 16)  << endl; // 16625
    cout << stoi(strBin, nullptr, 2)  << endl;  // 16625
    cout << stoi(strMix) << endl;  				// 123。仅转换 abc 前的数字字符
    // cout << stoi(strMix2) << endl; 			// 抛出异常

    return 0;
}

数字转字符串

  1. 描述：数值转为字符串
  2. 头文件：<string>
  3. 函数：to_string
  4. 返回值：字符串
#include <iostream>
#include <string>

using namespace std;

int main() {
    int numToString = 12345;
    float numToString2 = 3.1415;

    cout << to_string(numToString) << endl;  // "12345"
    cout << to_string(numToString2) << endl; // "3.141500"

    return 0;
}

大小写转换

  1. 头文件：<cctyep>
  2. islower：判断字符是否是小写，若是则返回 true
  3. isupper：判断字符是否是大写，若是则返回 true
  4. tolower：将大写字符转换为小写，需要接收返回值
  5. toupper：将小写字符转换为大写，需要接收返回值
	#include <cctyep>
	char c = 'a';
    char c1 = 'A';
    cout << "is lower: " << islower(c) << endl;  // 是小写，返回非零值
    cout << "is lower: " << islower(c1) << endl; // 否则返回 0

    // 小写转大写
    // 大写转小写用 tolower()
    cout << "is lower: " << islower(toupper(c)) << endl;  // 0

转换字符串中英文字符大小写

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
  string str{"abcdefG"};
  for (int i = 0; i < str.size(); i++) {
    if (islower(str[i])) str[i] = toupper(str[i]);
  }

  cout << str << endl; // ABCDEFG
}

使用 ascii 码值来进行大小写转换。其中 A ~ Z 对应 ascii 码 65 ~ 90，a ~ z 对应 ascii 码 97 ~ 122

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
  string str{"abcdefG"};
  for (int i = 0; i < str.size(); i++) {
    if (str[i] >= 97 && str[i] <= 122) str[i] = str[i] - 32;
  }

  cout << str << endl; // ABCDEFG
}

字符串分割

  1. 描述：结合 getline 和 sstream 流来实现 c++ 字符串分割
// 字符串中仅含空格，直接用 ssteram 流分割
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string str = "abc 123 张三-李四";
    stringstream ss(str);
    vector<string> vecString;
    string tempStr;

    while(ss >> tempStr) {
        vecString.push_back(tempStr);
    }

    for (auto& v : vecString) {
        cout << v << endl;
    }

    return 0;
}

输出
abc
123
张三-李四

// 字符串中通过 , 分割字符，使用 getline + sstream
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string str = "abc,123,张三-李四";
    stringstream ss(str);
    vector<string> vecString;
    string tempStr;

    while(getline(ss, tempStr, ',')) {
        vecString.push_back(tempStr);
    }

    for (auto& v : vecString) {
        cout << v << endl;
    }

    return 0;
}

输出
abc
123
张三-李四

acm 输入输出

输入

  1. 输入一个字符
// 输入一个字符
// 示例：键盘输入数字 5 后回车，即可把 5 存入变量 a 中
int a;
cin >> a
  1. 输入固定数量一行字符
// 输入固定数量一行字符
// 示例：键盘输入 5 2 3，然后按 ctrl+z 后，再按回车
int a, b, c;
cin >> a >> b >> c;
  1. 输入固定大量一行或任意数量一行
// 输入固定大量一行或任意数量一行
// 示例：键盘输入 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
#include <iostream>
#include <vector>
#include <sstream>

int main() {
    std::string line;
    std::getline(std::cin, line); // 读取整行输入

    std::vector<int> numbers;
    std::istringstream iss(line); // 将字符串转换为输入流
    int num;

    while (iss >> num) { // 从输入流中读取数字
        numbers.push_back(num); // 将数字存入 vector
    }
    
    return 0;
}
# leetcode # c++ # 数据结构
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

cover

KingbaseES数据库：医疗信创潮涌沅江，国产化信创打造医疗新质生产力

avatar DAMO开发者矩阵
cover

告别迁移焦虑：金仓KDMS V4带你轻松搞定数据库国产化替代

avatar DAMO开发者矩阵
cover

KingbaseES数据库在常德二院全栈国产化信创中产生新质生产力,医疗信创的部署如何实现，如何操作？

avatar DAMO开发者矩阵