02_C++ 算法篇
本文最后更新于 2025-01-17，学习久了要注意休息哟
第一章 STL介绍
1.1 STL 介绍
在使用 C 语言学习数据结构时，我们常常面临一个问题：每当需要处理不同类型的数据时，就不得不重新编写一遍数据结构的算法。这导致我们做了许多表面上不同，但实际上重复的工作。
C++ 提出的 面向对象 和 泛型编程 思想正是为了解决这一问题的——这也是我们接下来学习 STL 的核心目的。
1.2 STL 概念
STL（Standard Template Library，标准模板库）是 C++ 中的一组用于处理数据的通用模板类和函数库。它提供了一套丰富的模板集合，旨在提升代码的复用性和可维护性。
STL 的编程思想主要包括 泛型编程 和 面向对象编程，帮助我们实现对不同数据类型的通用操作需求，增强代码的可读性和灵活性。
1.3 核心部分
STL 由三大核心部分构成：算法（Algorithms）、容器（Containers） 和 迭代器（Iterators）。这三部分相互协作，使数据的存储和处理更高效、灵活。
容器： 容器用于存储数据。STL 提供了多种常用数据结构，如数组、链表、树、栈、队列、集合和映射表。容器分为以下两类：
- 序列式容器： 按顺序存储元素，例如
vector和list。 - 关联式容器： 基于树结构，不保证元素的顺序，例如
map和set。
算法： 算法是解决问题的步骤，包括一系列逻辑和数学操作。STL 提供的算法主要分为两类：
- 质变算法： 改变数据内容，如复制、替换和删除。
- 非质变算法： 不改变数据内容，如查找、计数和遍历。
迭代器： 迭代器提供了访问容器中元素的方式，类似于指针。它是连接容器和算法的桥梁，支持遍历容器元素的功能。
1.4 主要组件
除了上述三大核心部分，STL 还包含以下六大组件：容器、算法、迭代器、仿函数、适配器 和 空间配置器。以下是它们的简要说明：
- 容器（Containers）： 用于存储和组织数据的模板类，例如
vector、list和map。 - 算法（Algorithms）： 各种操作数据的函数模板，例如排序、查找和复制。
- 迭代器（Iterators）： 类似指针的对象，用于遍历容器中的元素。
- 仿函数（Functors）： 像函数一样调用的对象，用于自定义算法行为。
- 适配器（Adapters）： 用于改变容器或迭代器接口的组件，例如
stack、queue和reverse_iterator。 - 空间配置器（Allocators）： 负责内存的分配和管理，为容器提供底层的内存支持。
第二章 STL容器
2.1 strlen容器
string是C++风格的字符串，而string本质上是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。
string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责。
2.1.1 构造函数
API介绍
string(); // 创建一个空的字符串，例如: string str;
string(const char* s); // 使用C风格字符串 s 初始化
string(const string& str); // 使用另一个 string 对象 str 初始化
string(int n, char c); // 使用 n 个字符 c 初始化
示例程序
#include <iostream>
#include <string>
int main() {
// 1. 使用默认构造函数创建空字符串
std::string str1;
std::cout << "str1: \"" << str1 << "\"" << std::endl;
// 2. 使用 C 风格字符串初始化
const char* s = "Hello, World!";
std::string str2(s);
std::cout << "str2: \"" << str2 << "\"" << std::endl;
// 3. 使用另一个 string 对象初始化
std::string str3(str2);
std::cout << "str3: \"" << str3 << "\"" << std::endl;
// 4. 使用 n 个字符 c 初始化
std::string str4(5, '*');
std::cout << "str4: \"" << str4 << "\"" << std::endl;
return 0;
}
2.1.2 赋值函数
API介绍
string& operator=(const char* s); // char* 类型字符串赋值给当前字符串
string& operator=(const string &s); // 把字符串 s 赋给当前字符串
string& operator=(char c); // 单个字符赋值给当前字符串
string& assign(const char *s); // 把 C 风格字符串 s 赋给当前字符串
string& assign(const char *s, int n); // 把 C 风格字符串 s 的前 n 个字符赋给当前字符串
string& assign(const string &s); // 把字符串 s 赋给当前字符串
string& assign(int n, char c); // 用 n 个字符 c 赋值给当前字符串
示例程序
#include <iostream>
#include <string>
int main() {
std::string str;
// 使用 char* 类型字符串赋值
str = "Hello, World!";
std::cout << "str = \"Hello, World!\": " << str << std::endl;
// 使用另一个 string 对象赋值
std::string anotherStr = "C++ Programming";
str = anotherStr;
std::cout << "str = anotherStr: " << str << std::endl;
// 使用字符赋值
str = 'A';
std::cout << "str = 'A': " << str << std::endl;
// 使用 assign() 方法赋值 - 整个 C 风格字符串
str.assign("Welcome to C++");
std::cout << "str.assign(\"Welcome to C++\"): " << str << std::endl;
// 使用 assign() 方法赋值 - C 风格字符串的前 n 个字符
str.assign("Good Morning", 4); // 只取前 4 个字符
std::cout << "str.assign(\"Good Morning\", 4): " << str << std::endl;
// 使用 assign() 方法赋值 - 另一个 string 对象
str.assign(anotherStr);
std::cout << "str.assign(anotherStr): " << str << std::endl;
// 使用 assign() 方法赋值 - 用 n 个字符 c
str.assign(5, '*');
std::cout << "str.assign(5, '*'): " << str << std::endl;
return 0;
}
2.1.3 插入和删除
API介绍
// 插入
string& insert(size_t pos, const string& str); // 在 pos 位置插入字符串 str
string& insert(size_t pos, const char* s); // 在 pos 位置插入 C 风格字符串 s
string& insert(size_t pos, const char* s, size_t n); // 在 pos 位置插入 C 风格字符串 s 的前 n 个字符
string& insert(size_t pos, size_t n, char c); // 在 pos 位置插入 n 个字符 c
// 删除
string& erase(size_t pos = 0, size_t len = npos); // 从 pos 位置开始删除 len 个字符（默认为到末尾）
示例程序
#include <iostream>
#include <string>
int main() {
std::string str = "Hello, World!";
// 在指定位置插入字符串
str.insert(7, "beautiful ");
std::cout << "在位置 7 插入字符串后: " << str << std::endl;
// 在指定位置插入 C 风格字符串
str.insert(0, "Say: ");
std::cout << "在位置 0 插入 C 风格字符串后: " << str << std::endl;
// 在指定位置插入 C 风格字符串的前 n 个字符
str.insert(4, "Hello, Universe", 5); // 只插入 "Hello" 的前 5 个字符
std::cout << "在位置 4 插入前 5 个字符后: " << str << std::endl;
// 在指定位置插入多个字符
str.insert(10, 3, '*'); // 插入 3 个 '*'
std::cout << "在位置 10 插入 3 个 '*' 后: " << str << std::endl;
// 从指定位置删除字符
str.erase(10, 3); // 删除从位置 10 开始的 3 个字符
std::cout << "删除位置 10 开始的 3 个字符后: " << str << std::endl;
// 从指定位置开始删除到字符串末尾
str.erase(4);
std::cout << "从位置 4 开始删除到末尾后: " << str << std::endl;
return 0;
}
2.1.4 字符串拼接
实现在字符串末尾拼接字符串
API介绍
string& operator+=(const char* str); // 重载 += 操作符，将 C 风格字符串 str 拼接到当前字符串末尾
string& operator+=(const char c); // 重载 += 操作符，将字符 c 拼接到当前字符串末尾
string& operator+=(const string& str); // 重载 += 操作符，将 string 对象 str 拼接到当前字符串末尾
string& append(const char *s); // 将 C 风格字符串 s 拼接到当前字符串末尾
string& append(const char *s, int n); // 将 C 风格字符串 s 的前 n 个字符拼接到当前字符串末尾
string& append(const string &s); // 同 operator+=(const string& str)，拼接整个字符串 s
string& append(const string &s, int pos, int n); // 从字符串 s 的 pos 位置开始，拼接 n 个字符到当前字符串末尾
示例程序
#include <iostream>
#include <string>
int main() {
std::string str = "Hello";
// 使用 += 操作符拼接 C 风格字符串
str += ", ";
std::cout << "str += \", \": " << str << std::endl;
// 使用 += 操作符拼接字符
str += 'W';
std::cout << "str += 'W': " << str << std::endl;
// 使用 += 操作符拼接 string 对象
std::string suffix = "orld!";
str += suffix;
std::cout << "str += suffix: " << str << std::endl;
// 使用 append() 方法拼接 C 风格字符串
str.append(" Welcome");
std::cout << "str.append(\" Welcome\"): " << str << std::endl;
// 使用 append() 方法拼接 C 风格字符串的前 n 个字符
str.append(" to C++ programming", 3); // 只拼接前 3 个字符
std::cout << "str.append(\" to C++ programming\", 3): " << str << std::endl;
// 使用 append() 方法拼接 string 对象
str.append(suffix);
std::cout << "str.append(suffix): " << str << std::endl;
// 使用 append() 方法拼接 string 对象中的部分字符
str.append(suffix, 1, 3); // 从 suffix 中第 1 个字符开始，拼接 3 个字符
std::cout << "str.append(suffix, 1, 3): " << str << std::endl;
return 0;
}
2.1.5 查找和替换
API 介绍
int find(const string& str, int pos = 0) const; // 查找字符串 str 第一次出现的位置，从 pos 开始查找
int find(const char* s, int pos = 0) const; // 查找 C 风格字符串 s 第一次出现的位置，从 pos 开始查找
int find(const char* s, int pos, int n) const; // 从 pos 开始查找 s 的前 n 个字符第一次出现的位置
int find(const char c, int pos = 0) const; // 查找字符 c 第一次出现的位置，从 pos 开始查找
int rfind(const string& str, int pos = npos) const; // 查找字符串 str 最后一次出现的位置，从 pos 开始查找
int rfind(const char* s, int pos = npos) const; // 查找 C 风格字符串 s 最后一次出现的位置，从 pos 开始查找
int rfind(const char* s, int pos, int n) const; // 从 pos 开始查找 s 的前 n 个字符最后一次出现的位置
int rfind(const char c, int pos = 0) const; // 查找字符 c 最后一次出现的位置，从 pos 开始查找
string& replace(int pos, int n, const string& str); // 将从 pos 开始的 n 个字符替换为字符串 str
string& replace(int pos, int n, const char* s); // 将从 pos 开始的 n 个字符替换为 C 风格字符串 s
示例程序
#include <iostream>
#include <string>
int main() {
// 初始化字符串
std::string str = "Hello, World! Welcome to C++ World!";
std::cout << "原始字符串: " << str << std::endl;
// 使用 find 查找子字符串首次出现的位置
int pos1 = str.find("World");
std::cout << "第一次出现 'World' 的位置: " << pos1 << std::endl;
// 从指定位置开始查找子字符串首次出现的位置
int pos2 = str.find("World", pos1 + 1);
std::cout << "第二次出现 'World' 的位置: " << pos2 << std::endl;
// 查找 C 风格字符串首次出现的位置
int pos3 = str.find("Welcome");
std::cout << "'Welcome' 第一次出现的位置: " << pos3 << std::endl;
// 查找单个字符首次出现的位置
int pos4 = str.find('C');
std::cout << "字符 'C' 第一次出现的位置: " << pos4 << std::endl;
// 使用 rfind 从末尾查找子字符串最后一次出现的位置
int rpos1 = str.rfind("World");
std::cout << "'World' 最后一次出现的位置: " << rpos1 << std::endl;
// 从指定位置开始，查找 C 风格字符串的前 3 个字符的最后一次出现位置
int rpos2 = str.rfind("Wel", pos3);
std::cout << "'Wel' 最后一次出现的位置: " << rpos2 << std::endl;
// 使用 replace 替换指定位置的部分字符串
str.replace(pos1, 5, "Universe"); // 将第一个 "World" 替换为 "Universe"
std::cout << "替换第一个 'World' 为 'Universe' 后的字符串: " << str << std::endl;
// 使用 replace 替换指定位置的部分字符为 C 风格字符串
str.replace(rpos1, 5, "Planet"); // 将最后一个 "World" 替换为 "Planet"
std::cout << "替换最后一个 'World' 为 'Planet' 后的字符串: " << str << std::endl;
return 0;
}
2.1.6 字符串比较
比较方式：
字符串比较是按字符的ASCII码进行对比
- = 返回 0
>返回 1- < 返回 -1
API介绍
int compare(const string &s) const; // 与字符串 s 比较
int compare(const char *s) const; // 与 C 风格字符串 s 比较
示例程序
#include <iostream>
#include <string>
int main() {
// 定义两个字符串
std::string str1 = "Hello";
std::string str2 = "World";
std::string str3 = "Hello";
// 使用 compare 比较两个 string 对象
int result1 = str1.compare(str2);
if (result1 == 0) {
std::cout << "str1 等于 str2" << std::endl;
} else if (result1 > 0) {
std::cout << "str1 大于 str2" << std::endl;
} else {
std::cout << "str1 小于 str2" << std::endl;
}
// 比较两个相同的字符串
int result2 = str1.compare(str3);
if (result2 == 0) {
std::cout << "str1 等于 str3" << std::endl;
} else if (result2 > 0) {
std::cout << "str1 大于 str3" << std::endl;
} else {
std::cout << "str1 小于 str3" << std::endl;
}
// 使用 compare 比较 string 和 C 风格字符串
int result3 = str1.compare("Hello");
if (result3 == 0) {
std::cout << "str1 等于 \"Hello\"" << std::endl;
} else if (result3 > 0) {
std::cout << "str1 大于 \"Hello\"" << std::endl;
} else {
std::cout << "str1 小于 \"Hello\"" << std::endl;
}
return 0;
}
2.1.7 字符串转数值
API介绍
int std::stoi(const std::string& str, std::size_t* pos = 0, int base = 10); // 将字符串转换为 int
long std::stol(const std::string& str, std::size_t* pos = 0, int base = 10); // 将字符串转换为 long
long long std::stoll(const std::string& str, std::size_t* pos = 0, int base = 10); // 将字符串转换为 long long
float std::stof(const std::string& str, std::size_t* pos = 0); // 将字符串转换为 float
double std::stod(const std::string& str, std::size_t* pos = 0); // 将字符串转换为 double
long double std::stold(const std::string& str, std::size_t* pos = 0); // 将字符串转换为 long double
示例程序
#include <iostream>
#include <string>
int main() {
std::string intStr = "42";
std::string floatStr = "3.14";
std::string longStr = "123456789";
std::string doubleStr = "2.71828";
// 将字符串转换为 int
int intValue = std::stoi(intStr);
std::cout << "字符串 \"" << intStr << "\" 转换为 int: " << intValue << std::endl;
// 将字符串转换为 float
float floatValue = std::stof(floatStr);
std::cout << "字符串 \"" << floatStr << "\" 转换为 float: " << floatValue << std::endl;
// 将字符串转换为 long
long longValue = std::stol(longStr);
std::cout << "字符串 \"" << longStr << "\" 转换为 long: " << longValue << std::endl;
// 将字符串转换为 double
double doubleValue = std::stod(doubleStr);
std::cout << "字符串 \"" << doubleStr << "\" 转换为 double: " << doubleValue << std::endl;
return 0;
}
2.1.8 字符串存取
API介绍
char& operator[](std::size_t pos); // 获取指定位置的字符（支持修改）
const char& operator[](std::size_t pos) const; // 获取指定位置的字符（只读）
char& at(std::size_t pos); // 获取指定位置的字符，带边界检查（支持修改）
const char& at(std::size_t pos) const; // 获取指定位置的字符，带边界检查（只读）
char& front(); // 获取字符串的第一个字符（支持修改）
const char& front() const; // 获取字符串的第一个字符（只读）
char& back(); // 获取字符串的最后一个字符（支持修改）
const char& back() const; // 获取字符串的最后一个字符（只读）
示例程序
#include <iostream>
#include <string>
int main() {
std::string str = "Hello, World!";
// 使用 operator[] 访问字符
std::cout << "str[0]: " << str[0] << std::endl; // 输出第一个字符
str[0] = 'h'; // 修改第一个字符
std::cout << "修改后 str: " << str << std::endl;
// 使用 at() 方法访问字符，带边界检查
std::cout << "str.at(1): " << str.at(1) << std::endl;
str.at(1) = 'E'; // 修改第二个字符
std::cout << "修改后 str: " << str << std::endl;
// 使用 front() 获取第一个字符
std::cout << "str.front(): " << str.front() << std::endl;
str.front() = 'H'; // 修改第一个字符
std::cout << "修改后 str: " << str << std::endl;
// 使用 back() 获取最后一个字符
std::cout << "str.back(): " << str.back() << std::endl;
str.back() = '?'; // 修改最后一个字符
std::cout << "修改后 str: " << str << std::endl;
return 0;
}
2.1.9 查子串
API 介绍
std::string substr(std::size_t pos = 0, std::size_t len = npos) const; // 从指定位置 pos 开始，提取长度为 len 的子串
示例程序
#include <iostream>
#include <string>
int main() {
std::string str = "Hello, World! Welcome to C++ programming.";
// 提取从位置 7 开始，长度为 5 的子串
std::string sub1 = str.substr(7, 5);
std::cout << "从位置 7 开始的子串（长度 5）: " << sub1 << std::endl;
// 提取从位置 13 开始，直到字符串末尾的子串
std::string sub2 = str.substr(13);
std::cout << "从位置 13 开始到末尾的子串: " << sub2 << std::endl;
// 提取整个字符串的子串
std::string sub3 = str.substr();
std::cout << "整个字符串的子串: " << sub3 << std::endl;
return 0;
}
2.2 vector容器-单端数组
vector 不是静态数组 是动态的
功能：
vector是一种与 数组非常相似 的数据结构，通常称为 单端数组，因为数据在末端进行插入和删除操作。
vector 与普通数组的区别：
- 普通数组是固定大小的静态空间，而
vector则可以根据需求 动态扩展，自动调整大小。
动态扩展机制：
vector的动态扩展并不是在原空间后续接新空间，而是会找到更大的连续内存空间，将原有数据 拷贝到新空间，并释放掉旧空间。
2.1.1 构造函数
- 默认构造、指定大小构造、拷贝构造、移动构造
1、API介绍
vector()： 默认构造函数，创建空的 vector。
vector(size_type count)： 创建指定大小的 vector。
vector(size_type count, const T &value)： 创建指定大小并填充指定值的 vector。
vector(const vector &other)： 拷贝构造函数。
vector(vector &&other) noexcept： 移动构造函数。
2、示例程序
普通类型构造
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 默认构造，创建一个空的 vector 容器
vector<int> vec1;
cout << "vec1 的大小为: " << vec1.size() << endl;
// 指定大小构造，创建一个包含 5 个元素，值为 10 的 vector
vector<int> vec2(5, 10);
cout << "vec2 的大小为: " << vec2.size() << "，第一个元素为: " << vec2[0] << endl;
// 拷贝构造，将 vec2 的内容复制到 vec3
vector<int> vec3(vec2);
cout << "vec3 的大小为: " << vec3.size() << "，第一个元素为: " << vec3[0] << endl;
// 移动构造，将 vec3 的内容移动到 vec4，vec3 被清空
vector<int> vec4(move(vec3));
cout << "vec4 的大小为: " << vec4.size() << "，第一个元素为: " << vec4[0] << endl;
return 0;
}
自定义类型构造
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
// 构造函数，创建一个 Person 对象
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
// 拷贝构造函数，创建 Person 对象的副本
Person(const Person &p) : name(p.name), age(p.age) {
cout << "拷贝 Person: " << name << endl;
}
// 移动构造函数，转移资源，提高效率
Person(Person &&p) noexcept : name(move(p.name)), age(p.age) {
cout << "移动 Person: " << name << endl;
}
};
int main(int argc, char const *argv[])
{
// 默认构造，创建一个空的 vector<Person> 容器
vector<Person> vec1;
// 指定大小构造，创建一个包含 3 个 "John" 对象的 vector
vector<Person> vec2(3, Person("John", 30));
cout << "vec2 的大小为: " << vec2.size() << endl;
// 拷贝构造，将 vec2 的内容复制到 vec3
vector<Person> vec3(vec2);
cout << "vec3 的大小为: " << vec3.size() << endl;
// 移动构造，将 vec3 的内容移动到 vec4，vec3 被清空
vector<Person> vec4(move(vec3));
cout << "vec4 的大小为: " << vec4.size() << endl;
return 0;
}
3、总结
- 默认构造：创建空容器。
- 指定大小构造：创建包含指定数量元素的容器，可指定初始值。
- 拷贝构造：创建容器的副本。
- 移动构造：转移资源，提高效率。
4、注意事项
- 拷贝构造调用元素的拷贝构造函数。
- 移动构造后，原容器不再拥有数据，提高内存利用效率。
2.1.2 赋值操作
- 赋值运算符、重新分配与赋值
1、API介绍
operator=： 赋值运算符，将一个 vector 的内容复制或移动到另一个 vector。
assign(size_type count, const T &value)： 重新分配并填充指定数量的元素，所有元素都为相同的值。
assign(InputIterator first, InputIterator last)：用指定范围的元素重新分配 vector 的内容。
2、示例程序
普通类型赋值
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 创建一个包含 5 个元素，值为 10 的 vector
vector<int> vec1(5, 10);
cout << "vec1 的大小为: " << vec1.size() << "，第一个元素为: " << vec1[0] << endl;
// 赋值运算符，将 vec1 赋值给 vec2
vector<int> vec2 = vec1;
cout << "vec2 的大小为: " << vec2.size() << "，第一个元素为: " << vec2[0] << endl;
// 重新分配并赋值，用三个值为 20 的元素填充 vec1
vec1.assign(3, 20);
cout << "重新分配后，vec1 的大小为: " << vec1.size() << "，第一个元素为: " << vec1[0] << endl;
return 0;
}
自定义类型赋值
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
// 拷贝赋值运算符
Person &operator=(const Person &p) {
if (this != &p) {
name = p.name;
age = p.age;
cout << "拷贝赋值 Person: " << name << endl;
}
return *this;
}
};
int main(int argc, char const *argv[])
{
// 创建一个包含两个 "John" 对象的 vector
vector<Person> vec1(2, Person("John", 30));
// 使用赋值运算符将 vec1 赋值给 vec2
vector<Person> vec2 = vec1;
cout << "vec2 的大小为: " << vec2.size() << endl;
// 重新分配并赋值，使用新内容替换 vec1 中的元素
vec1.assign(3, Person("Jane", 25));
cout << "重新分配后，vec1 的大小为: " << vec1.size() << endl;
return 0;
}
3、总结
- 赋值运算符：将一个容器的内容复制或移动到另一个容器。
- 重新分配并赋值：改变容器的大小并用指定值填充。
4、注意事项
- 使用
assign时，会清空原有内容并重新分配空间。 - 如果赋值的对象有自定义赋值运算符（如
operator=），则会调用该运算符。
2.1.3 元素访问
- at、operator[]、front、back、data
1、API介绍
at(size_type pos) ：返回指定位置的元素，有越界检查。
operator[] ：返回指定位置的元素，没有越界检查。
front() ：返回第一个元素。
back() ：返回最后一个元素。
data() ：返回指向容器数据的指针。
2、示例程序
普通类型元素访问
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 创建并初始化一个 vector
vector<int> vec = {10, 20, 30, 40, 50};
// 使用 at() 访问元素（带越界检查）
cout << "使用 at() 访问第二个元素: " << vec.at(1) << endl;
// 使用 operator[] 访问元素（不带越界检查）
cout << "使用 operator[] 访问第三个元素: " << vec[2] << endl;
// 访问第一个元素
cout << "第一个元素: " << vec.front() << endl;
// 访问最后一个元素
cout << "最后一个元素: " << vec.back() << endl;
// 获取数据指针
int* data_ptr = vec.data();
cout << "data() 返回的第一个元素: " << *data_ptr << endl;
return 0;
}
自定义类型元素访问
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 创建并初始化一个包含 Person 对象的 vector
vector<Person> vec = {Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)};
// 使用 at() 访问元素并调用 display() 方法
cout << "使用 at() 访问第二个元素: ";
vec.at(1).display();
// 使用 operator[] 访问元素
cout << "使用 operator[] 访问第三个元素: ";
vec[2].display();
// 访问第一个元素
cout << "第一个元素: ";
vec.front().display();
// 访问最后一个元素
cout << "最后一个元素: ";
vec.back().display();
// 获取数据指针并调用第一个元素的 display() 方法
Person* data_ptr = vec.data();
cout << "data() 返回的第一个元素: ";
data_ptr->display();
return 0;
}
3、总结
- at()：带有越界检查，安全性更高，适合需要检测范围的访问。
- operator[]：不进行越界检查，性能较高。
- front()/back()：快速访问首尾元素。
- data()：获取容器底层的数组指针，便于与其他低层数据接口交互。
4、注意事项
- 使用
at()时，如果访问越界，会抛出异常。 operator[]不会进行边界检查，可能导致未定义行为。
2.1.4 迭代器
1、API介绍
begin() ：返回指向容器第一个元素的迭代器。
end() ：返回指向容器末尾之后位置的迭代器。
rbegin() ：返回指向容器最后一个元素的逆向迭代器。
rend() ：返回指向容器第一个元素之前位置的逆向迭代器。
cbegin() ：返回指向容器第一个元素的常量迭代器。
cend() ：返回指向容器末尾之后位置的常量迭代器。
crbegin() ：返回指向容器最后一个元素的常量逆向迭代器。
crend() ：返回指向容器第一个元素之前位置的常量逆向迭代器。
2、示例程序
普通类型迭代器示例
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 创建并初始化一个 vector
vector<int> vec = {10, 20, 30, 40, 50};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历: ";
for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历: ";
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历: ";
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
自定义类型迭代器示例
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 创建并初始化一个包含 Person 对象的 vector
vector<Person> vec = {Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历:" << endl;
for (auto it = vec.begin(); it != vec.end(); ++it) {
it->display();
}
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历:" << endl;
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
it->display();
}
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历:" << endl;
for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
it->display();
}
return 0;
}
3、总结
- begin()/end()：适用于正向遍历。
- rbegin()/rend()：适用于逆向遍历。
- cbegin()/cend() 和 crbegin()/crend()：适用于常量遍历，保证元素不可修改。
4、注意事项
- 常量迭代器（
cbegin等）用于确保在遍历过程中不修改容器内容，适合只读操作。 - 逆向迭代器适合需要反向访问元素的情况，比如从尾到头处理数据。
2.1.5 容量管理
- empty、size、max_size、capacity、reserve、shrink_to_fit
1、API介绍
empty() ：检查容器是否为空，若为空返回 true，否则返回 false。
size() ：返回容器当前的元素数量。
max_size() ：返回容器可容纳的最大元素数量 (系统允许)。
capacity() ：返回容器当前分配的存储空间大小（即容量）。
reserve(size) ：预留存储空间，至少能容纳指定数量的元素。
shrink_to_fit() ：收缩容器的容量，释放未使用的内存。
2、示例程序
容量管理示例
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 vector
vector<int> vec;
// 检查容器是否为空
cout << "容器是否为空: " << (vec.empty() ? "是" : "否") << endl;
// 添加元素并查看容量
vec.push_back(1);
cout << "添加元素后，size: " << vec.size() << "，capacity: " << vec.capacity() << endl;
// 预留容量
vec.reserve(10);
cout << "预留容量后，size: " << vec.size() << "，capacity: " << vec.capacity() << endl;
// 添加更多元素
vec.push_back(2);
vec.push_back(3);
cout << "添加更多元素后，size: " << vec.size() << "，capacity: " << vec.capacity() << endl;
// 收缩容量
vec.shrink_to_fit();
cout << "收缩容量后，size: " << vec.size() << "，capacity: " << vec.capacity() << endl;
return 0;
}
3、总结
- empty()：用于检查容器是否为空。
- size() 和 capacity()：分别获取当前元素数量和存储空间容量。
- reserve()：预先分配内存空间，减少扩容开销。
- shrink_to_fit()：释放未使用的内存，优化空间利用。
4、注意事项
reserve()只是预留空间，不会影响size()，但会改变capacity()。shrink_to_fit()是建议性请求，具体实现上可能不一定会减少容量。
2.1.6 修改操作
- clear、insert、erase、push_back、pop_back、resize、swap
1、API介绍
clear() ：清空容器中的所有元素。
insert(iterator pos, value) ：在指定位置插入一个元素。
insert(iterator pos, count, value)：在指定位置插入多个相同值的元素。
erase(iterator pos) ：删除指定位置的元素。
erase(iterator first, last) ：删除指定范围内的元素。
push_back(value) ：在容器尾部添加一个元素。
pop_back() ：移除容器尾部的元素。
resize(count) ：调整容器大小，默认填充值为默认构造的值。
resize(count, value) ：调整容器大小，填充指定的值。
swap(other) ：交换两个容器的内容。
advance(InputIterator& it, Distance n);
：将迭代器 it 移动 n 个位置 用于和 insert 结合使用。
2、示例程序
修改操作示例
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 vector
vector<int> vec = {1, 2, 3, 4, 5};
// 在指定位置插入一个元素
vec.insert(vec.begin() + 1, 10);
cout << "在第 2 个位置插入 10 后: ";
for (int v : vec) cout << v << " ";
cout << endl;
// 删除指定位置的元素
vec.erase(vec.begin() + 2);
cout << "删除第 3 个位置的元素后: ";
for (int v : vec) cout << v << " ";
cout << endl;
// 添加元素到末尾
vec.push_back(6);
cout << "在末尾添加元素 6 后: ";
for (int v : vec) cout << v << " ";
cout << endl;
// 删除末尾元素
vec.pop_back();
cout << "删除末尾元素后: ";
for (int v : vec) cout << v << " ";
cout << endl;
// 调整大小
vec.resize(7, 0);
cout << "调整大小为 7，并填充 0 后: ";
for (int v : vec) cout << v << " ";
cout << endl;
// 交换两个 vector
vector<int> vec2 = {100, 200, 300};
vec.swap(vec2);
cout << "交换后，vec 内容为: ";
for (int v : vec) cout << v << " ";
cout << endl;
cout << "交换后，vec2 内容为: ";
for (int v : vec2) cout << v << " ";
cout << endl;
return 0;
}
3、总结
- clear()：清空容器，释放所有元素。
- insert() 和 erase()：在指定位置插入或删除元素。
- push_back() 和 pop_back()：添加或移除尾部元素。
- resize()：调整容器大小，可以指定默认填充值。
- swap()：交换两个容器的内容，不涉及数据拷贝。
4、注意事项
clear()只清空元素，不释放已分配的内存。insert()和erase()会使指向容器元素的迭代器失效。resize()增大时新元素被默认构造或赋指定值；缩小时会删除多余元素。
2.1.7 比较操作
- operator==、operator!=、operator<、operator<=、operator>、operator>=
1、API介绍
operator== ：判断两个容器是否相等（元素数量和内容均相同时返回 true）。
operator!= ：判断两个容器是否不相等（若元素数量或内容不同则返回 true）。
operator< ：按字典顺序判断当前容器是否小于另一个容器。
operator<= ：按字典顺序判断当前容器是否小于或等于另一个容器。
operator> ：按字典顺序判断当前容器是否大于另一个容器。
operator>= ：按字典顺序判断当前容器是否大于或等于另一个容器。
2、示例程序
比较操作示例
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化两个 vector
vector<int> vec1 = {1, 2, 3};
vector<int> vec2 = {1, 2, 3};
vector<int> vec3 = {1, 2, 4};
// 相等比较
cout << "vec1 和 vec2 是否相等: " << (vec1 == vec2 ? "是" : "否") << endl;
// 不等比较
cout << "vec1 和 vec3 是否不等: " << (vec1 != vec3 ? "是" : "否") << endl;
// 小于比较
cout << "vec1 是否小于 vec3: " << (vec1 < vec3 ? "是" : "否") << endl;
// 大于比较
cout << "vec3 是否大于 vec2: " << (vec3 > vec2 ? "是" : "否") << endl;
// 小于等于比较
cout << "vec1 是否小于等于 vec2: " << (vec1 <= vec2 ? "是" : "否") << endl;
// 大于等于比较
cout << "vec3 是否大于等于 vec1: " << (vec3 >= vec1 ? "是" : "否") << endl;
return 0;
}
3、总结
- operator== 和 operator!=：用于判断容器是否相等或不等。
- operator<、operator<=、operator>、operator>=：按字典顺序比较容器，用于排序或范围判断。
4、注意事项
- 容器的比较是逐元素的字典顺序比较，因此只要某个位置的元素不同，就能确定大小关系。
- 比较操作符要求两个容器的类型相同，且存储的元素类型支持相应的比较操作。
2.3 deque容器-双端数组
2.3.1 构造函数
- 默认构造、指定大小构造、拷贝构造、移动构造
1、API介绍
deque() ：默认构造函数，创建空的 deque。
deque(size_type count) ：创建包含 count 个默认构造元素的 deque。
deque(size_type count, const T &value) ：创建包含 count 个值为 value 的元素。
deque(const deque &other) ：拷贝构造函数，创建其他 deque 的副本。
deque(deque &&other) noexcept ：移动构造函数，将另一个 deque 的内容移动到当前 deque。
2、示例程序
普通类型构造
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 默认构造
deque<int> dq1;
cout << "dq1 的大小为: " << dq1.size() << endl;
// 指定大小构造
deque<int> dq2(5); // 包含 5 个默认值的元素
cout << "dq2 的大小为: " << dq2.size() << ", dq2[0]: " << dq2[0] << endl;
// 指定大小和值构造
deque<int> dq3(5, 10); // 包含 5 个值为 10 的元素
cout << "dq3 的大小为: " << dq3.size() << ", dq3[0]: " << dq3[0] << endl;
// 拷贝构造
deque<int> dq4(dq3);
cout << "dq4 的大小为: " << dq4.size() << ", dq4[0]: " << dq4[0] << endl;
// 移动构造
deque<int> dq5(move(dq4));
cout << "dq5 的大小为: " << dq5.size() << ", dq5[0]: " << dq5[0] << endl;
return 0;
}
自定义类型构造
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
// 构造函数
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
// 拷贝构造函数
Person(const Person &p) : name(p.name), age(p.age) {
cout << "拷贝 Person: " << name << endl;
}
// 移动构造函数
Person(Person &&p) noexcept : name(move(p.name)), age(p.age) {
cout << "移动 Person: " << name << endl;
}
};
int main(int argc, char const *argv[])
{
// 默认构造
deque<Person> dq1;
// 指定大小和值构造
deque<Person> dq2(2, Person("John", 30));
cout << "dq2 的大小为: " << dq2.size() << endl;
// 拷贝构造
deque<Person> dq3(dq2);
cout << "dq3 的大小为: " << dq3.size() << endl;
// 移动构造
deque<Person> dq4(move(dq3));
cout << "dq4 的大小为: " << dq4.size() << endl;
return 0;
}
3、总结
- 默认构造：创建空容器，适合之后逐步插入元素。
- 指定大小构造：创建包含指定数量元素的容器，元素可以有指定初始值。
- 拷贝构造：创建容器的副本。
- 移动构造：转移资源，提高效率。
4、注意事项
- 拷贝构造会调用元素的拷贝构造函数，适合复制数据。
- 移动构造后，原容器将不再持有数据，可有效节省内存并提升效率。
2.3.2 赋值操作
- 赋值运算符、重新分配与赋值
1、API介绍
operator= ：赋值运算符，将一个 deque 的内容复制或移动到另一个 deque。
assign(size_type count, const T &value) ：重新分配并填充指定数量的元素，所有元素都为相同的值。
assign(InputIterator first, InputIterator last) ：用指定范围的元素重新分配 deque 的内容。
2、示例程序
普通类型赋值
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 deque
deque<int> dq1 = {1, 2, 3, 4, 5};
cout << "dq1 初始内容: ";
for (int v : dq1) cout << v << " ";
cout << endl;
// 赋值运算符，将 dq1 的内容赋值给 dq2
deque<int> dq2 = dq1;
cout << "dq2 复制自 dq1 的内容: ";
for (int v : dq2) cout << v << " ";
cout << endl;
// 重新分配并赋值，用三个值为 10 的元素填充 dq1
dq1.assign(3, 10);
cout << "dq1 重新分配后的内容: ";
for (int v : dq1) cout << v << " ";
cout << endl;
return 0;
}
自定义类型赋值
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
Person(const Person &p) : name(p.name), age(p.age) {
cout << "拷贝 Person: " << name << endl;
}
};
int main(int argc, char const *argv[])
{
// 初始化一个包含 Person 对象的 deque
deque<Person> dq1 = {Person("Alice", 25), Person("Bob", 30)};
cout << "dq1 初始内容:" << endl;
for (const auto &p : dq1) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
// 使用赋值运算符将 dq1 赋值给 dq2
deque<Person> dq2 = dq1;
cout << "dq2 复制自 dq1 的内容:" << endl;
for (const auto &p : dq2) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
// 重新分配并赋值，使用新内容替换 dq1 中的元素
dq1.assign(2, Person("Charlie", 35));
cout << "dq1 重新分配后的内容:" << endl;
for (const auto &p : dq1) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
return 0;
}
3、总结
- 赋值运算符：将一个容器的内容复制或移动到另一个容器。
- 重新分配并赋值：清空原内容，并用指定数量的元素重新填充容器。
4、注意事项
assign会清空原内容并重新分配内存空间。- 自定义类型的元素使用赋值运算符时会调用其拷贝构造函数或移动构造函数。
2.3.3 元素访问
- at、operator[]、front、back
1、API介绍
at(size_type pos) ：返回指定位置的元素，有越界检查。
operator[] ：返回指定位置的元素，没有越界检查。
front() ：返回第一个元素。
back() ：返回最后一个元素。
2、示例程序
普通类型元素访问
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 deque
deque<int> dq = {10, 20, 30, 40, 50};
// 使用 at() 访问元素（带越界检查）
cout << "使用 at() 访问第二个元素: " << dq.at(1) << endl;
// 使用 operator[] 访问元素（不带越界检查）
cout << "使用 operator[] 访问第三个元素: " << dq[2] << endl;
// 访问第一个元素
cout << "第一个元素: " << dq.front() << endl;
// 访问最后一个元素
cout << "最后一个元素: " << dq.back() << endl;
return 0;
}
自定义类型元素访问
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 初始化一个包含 Person 对象的 deque
deque<Person> dq = {Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)};
// 使用 at() 访问元素并调用 display() 方法
cout << "使用 at() 访问第二个元素: ";
dq.at(1).display();
// 使用 operator[] 访问元素
cout << "使用 operator[] 访问第三个元素: ";
dq[2].display();
// 访问第一个元素
cout << "第一个元素: ";
dq.front().display();
// 访问最后一个元素
cout << "最后一个元素: ";
dq.back().display();
return 0;
}
3、总结
- at()：带有越界检查，安全性更高，适合需要检测范围的访问。
- operator[]：不进行越界检查，性能较高。
- front() 和 back()：分别返回首尾元素，适合快速访问第一个和最后一个元素。
4、注意事项
- 使用
at()访问超出范围的元素会抛出异常，适合需要越界检测的情况。 operator[]不进行边界检查，如果访问越界可能会导致未定义行为。
2.3.4 迭代器
- begin、end、rbegin、rend、cbegin、cend、crbegin、crend
1、API介绍
begin() ：返回指向容器第一个元素的迭代器。
end() ：返回指向容器末尾之后位置的迭代器。
rbegin() ：返回指向容器最后一个元素的逆向迭代器。
rend() ：返回指向容器第一个元素之前位置的逆向迭代器。
cbegin() ：返回指向容器第一个元素的常量迭代器。
cend() ：返回指向容器末尾之后位置的常量迭代器。
crbegin() ：返回指向容器最后一个元素的常量逆向迭代器。
crend() ：返回指向容器第一个元素之前位置的常量逆向迭代器。
2、示例程序
普通类型迭代器示例
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 deque
deque<int> dq = {10, 20, 30, 40, 50};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历: ";
for (auto it = dq.begin(); it != dq.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历: ";
for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历: ";
for (auto it = dq.cbegin(); it != dq.cend(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
自定义类型迭代器示例
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 初始化一个包含 Person 对象的 deque
deque<Person> dq = {Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历:" << endl;
for (auto it = dq.begin(); it != dq.end(); ++it) {
it->display();
}
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历:" << endl;
for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
it->display();
}
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历:" << endl;
for (auto it = dq.cbegin(); it != dq.cend(); ++it) {
it->display();
}
return 0;
}
3、总结
- begin() 和 end()：用于正向遍历，适合对容器中的元素进行逐个访问。
- rbegin() 和 rend()：用于逆向遍历，适合从尾到头访问元素。
- cbegin()/cend() 和 crbegin()/crend()：用于常量遍历，确保元素在遍历过程中不可修改。
4、注意事项
- 常量迭代器（如
cbegin）用于保证遍历时不修改容器内容，适合只读操作。 - 逆向迭代器适合需要反向访问的场景，尤其是需要从尾部进行处理的情况。
2.3.5 容量管理
- empty、size、max_size、shrink_to_fit
1、API介绍
empty() ：检查容器是否为空，若为空返回 true，否则返回 false。
size() ：返回容器当前的元素数量。
max_size() ：返回容器能够容纳的最大元素数量。
shrink_to_fit() ：请求收缩容器的容量以适应当前大小，释放未使用的内存。
2、示例程序
容量管理示例
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 deque 并检查是否为空
deque<int> dq;
cout << "容器是否为空: " << (dq.empty() ? "是" : "否") << endl;
// 向容器添加元素
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);
// 查看容器的大小
cout << "添加元素后，size: " << dq.size() << endl;
// 查看容器的最大容量
cout << "容器的最大容量为: " << dq.max_size() << endl;
// 收缩容量以适应当前大小
dq.shrink_to_fit();
cout << "收缩容量后，size: " << dq.size() << endl;
return 0;
}
3、总结
- empty()：用于检查容器是否为空，常用于在操作前判断容器状态。
- size()：返回当前的元素数量，用于获取容器的实时大小。
- max_size()：返回容器理论上能够容纳的最大元素数量，但实际受内存限制。
- shrink_to_fit()：请求释放未使用的内存，提高内存使用效率。
4、注意事项
shrink_to_fit()是建议性的操作，不保证所有实现都会实际收缩容量。- 使用
empty()检查容器状态可以避免在空容器上执行不安全的操作。
2.3.6 修改操作
- clear、insert、erase、push_back、push_front、pop_back、pop_front、resize、swap
1、API介绍
clear() ：清空容器中的所有元素。
insert(iterator pos, value) ：在指定位置插入一个元素。
insert(iterator pos, count, value)：在指定位置插入多个相同值的元素。
erase(iterator pos) ：删除指定位置的元素。
erase(iterator first, last) ：删除指定范围内的元素。
push_back(value) ：在容器尾部添加一个元素。
push_front(value) ：在容器头部添加一个元素。
pop_back() ：移除容器尾部的元素。
pop_front() ：移除容器头部的元素。
resize(count) ：调整容器大小，默认填充值为默认构造的值。
resize(count, value) ：调整容器大小，并填充指定的值。
swap(deque &other) ：交换两个容器的内容。
2、示例程序
普通类型修改操作示例
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 deque
deque<int> dq = {1, 2, 3, 4, 5};
// 插入元素
dq.insert(dq.begin() + 1, 10);
cout << "在第 2 个位置插入 10 后: ";
for (int v : dq) cout << v << " ";
cout << endl;
// 删除指定位置的元素
dq.erase(dq.begin() + 2);
cout << "删除第 3 个位置的元素后: ";
for (int v : dq) cout << v << " ";
cout << endl;
// 添加元素到末尾和头部
dq.push_back(6);
dq.push_front(0);
cout << "在末尾添加 6，在头部添加 0 后: ";
for (int v : dq) cout << v << " ";
cout << endl;
// 删除末尾和头部元素
dq.pop_back();
dq.pop_front();
cout << "删除头尾元素后: ";
for (int v : dq) cout << v << " ";
cout << endl;
// 调整大小
dq.resize(7, 99);
cout << "调整大小为 7，并填充 99 后: ";
for (int v : dq) cout << v << " ";
cout << endl;
// 交换两个 deque
deque<int> dq2 = {100, 200, 300};
dq.swap(dq2);
cout << "交换后，dq 的内容为: ";
for (int v : dq) cout << v << " ";
cout << endl;
cout << "交换后，dq2 的内容为: ";
for (int v : dq2) cout << v << " ";
cout << endl;
return 0;
}
自定义类型修改操作示例
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 初始化 deque
deque<Person> dq;
dq.push_back(Person("Alice", 25));
dq.push_front(Person("Bob", 30));
cout << "初始队列内容:" << endl;
for (const auto &p : dq) {
p.display();
}
// 在指定位置插入元素
dq.insert(dq.begin() + 1, Person("Charlie", 28));
cout << "插入 'Charlie' 后的内容:" << endl;
for (const auto &p : dq) {
p.display();
}
// 删除第一个元素
dq.pop_front();
cout << "删除头部元素后内容:" << endl;
for (const auto &p : dq) {
p.display();
}
// 调整大小
dq.resize(4, Person("Dave", 40));
cout << "调整大小为 4 并填充 'Dave' 后内容:" << endl;
for (const auto &p : dq) {
p.display();
}
// 交换两个 deque
deque<Person> dq2 = {Person("Eve", 35)};
dq.swap(dq2);
cout << "交换后 dq 的内容:" << endl;
for (const auto &p : dq) {
p.display();
}
cout << "交换后 dq2 的内容:" << endl;
for (const auto &p : dq2) {
p.display();
}
return 0;
}
3、总结
- clear()：清空容器，释放所有元素。
- insert() 和 erase()：在指定位置插入或删除元素，可以单个或批量操作。
- push_back() 和 push_front()：分别在容器的尾部和头部添加元素。
- pop_back() 和 pop_front()：移除容器的尾部和头部元素。
- resize()：调整容器大小，可以指定填充值。
- swap()：交换两个容器的内容，不涉及数据拷贝。
4、注意事项
clear()只清空元素，不释放已分配的内存。insert()和erase()操作会使指向容器元素的迭代器失效。resize()增大时，新元素会被默认构造或赋指定值；缩小时会删除多余元素。
2.3.7 比较操作
operator==、operator!=、operator<、operator<=、operator>、operator>=
1、API介绍
operator== ：判断两个 deque 是否相等（元素数量和内容均相同时返回 true）。
operator!= ：判断两个 deque 是否不相等（若元素数量或内容不同则返回 true）。
operator< ：按字典顺序判断当前 deque 是否小于另一个 deque。
operator<= ：按字典顺序判断当前 deque 是否小于或等于另一个 deque。
operator> ：按字典顺序判断当前 deque 是否大于另一个 deque。
operator>= ：按字典顺序判断当前 deque 是否大于或等于另一个 deque。
2、示例程序
普通类型比较示例
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化两个 deque
deque<int> dq1 = {1, 2, 3};
deque<int> dq2 = {1, 2, 3};
deque<int> dq3 = {1, 2, 4};
// 相等比较
cout << "dq1 和 dq2 是否相等: " << (dq1 == dq2 ? "是" : "否") << endl;
// 不等比较
cout << "dq1 和 dq3 是否不等: " << (dq1 != dq3 ? "是" : "否") << endl;
// 小于比较
cout << "dq1 是否小于 dq3: " << (dq1 < dq3 ? "是" : "否") << endl;
// 大于比较
cout << "dq3 是否大于 dq2: " << (dq3 > dq2 ? "是" : "否") << endl;
// 小于等于比较
cout << "dq1 是否小于等于 dq2: " << (dq1 <= dq2 ? "是" : "否") << endl;
// 大于等于比较
cout << "dq3 是否大于等于 dq1: " << (dq3 >= dq1 ? "是" : "否") << endl;
return 0;
}
自定义类型比较示例
要使用自定义类型进行比较，需要在类中重载比较运算符。以下是示例代码：
#include <iostream>
#include <deque>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载比较运算符（按年龄和姓名比较）
bool operator==(const Person &other) const {
return age == other.age && name == other.name;
}
bool operator!=(const Person &other) const {
return !(*this == other);
}
bool operator<(const Person &other) const {
return age < other.age || (age == other.age && name < other.name);
}
bool operator<=(const Person &other) const {
return *this < other || *this == other;
}
bool operator>(const Person &other) const {
return !(*this <= other);
}
bool operator>=(const Person &other) const {
return !(*this < other);
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main(int argc, char const *argv[])
{
// 初始化两个 deque，包含 Person 对象
deque<Person> dq1 = {Person("Alice", 25), Person("Bob", 30)};
deque<Person> dq2 = {Person("Alice", 25), Person("Bob", 30)};
deque<Person> dq3 = {Person("Alice", 25), Person("Charlie", 35)};
// 相等比较
cout << "dq1 和 dq2 是否相等: " << (dq1 == dq2 ? "是" : "否") << endl;
// 不等比较
cout << "dq1 和 dq3 是否不等: " << (dq1 != dq3 ? "是" : "否") << endl;
// 小于比较
cout << "dq1 是否小于 dq3: " << (dq1 < dq3 ? "是" : "否") << endl;
// 大于比较
cout << "dq3 是否大于 dq2: " << (dq3 > dq2 ? "是" : "否") << endl;
// 小于等于比较
cout << "dq1 是否小于等于 dq2: " << (dq1 <= dq2 ? "是" : "否") << endl;
// 大于等于比较
cout << "dq3 是否大于等于 dq1: " << (dq3 >= dq1 ? "是" : "否") << endl;
return 0;
}
3、总结
- operator== 和 operator!=：用于判断两个容器是否相等或不等。
- operator<、operator<=、operator>、operator>=：按字典顺序比较两个容器，适用于排序或范围判断。
4、注意事项
- 比较操作是逐元素进行的字典顺序比较，因此当容器内容在某个位置不同，就可确定大小关系。
- 自定义类型的对象需要重载比较运算符，确保可以按指定规则进行比较操作。
2.4 list容器-链表
2.4.1 构造函数与析构函数
- 默认构造、指定大小构造、拷贝构造、移动构造
1、API介绍
list() ：默认构造函数，创建空的 list。
list(size_type count) ：创建包含 count 个默认构造元素的 list。
list(size_type count, const T &value) ：创建包含 count 个值为 value 的元素的 list。
list(const list &other) ：拷贝构造函数，创建其他 list 的副本。
list(list &&other) noexcept ：移动构造函数，将其他 list 的内容移动到当前 list。
2、示例程序
普通类型构造
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char const *argv[])
{
// 默认构造，创建一个空的 list
list<int> lst1;
cout << "lst1 的大小为: " << lst1.size() << endl;
// 指定大小构造，创建一个包含 5 个默认值的 list
list<int> lst2(5);
cout << "lst2 的大小为: " << lst2.size() << ", lst2 的第一个元素为: " << lst2.front() << endl;
// 指定大小和值构造，创建一个包含 5 个值为 10 的 list
list<int> lst3(5, 10);
cout << "lst3 的大小为: " << lst3.size() << ", lst3 的第一个元素为: " << lst3.front() << endl;
// 拷贝构造，将 lst3 的内容复制到 lst4
list<int> lst4(lst3);
cout << "lst4 的大小为: " << lst4.size() << ", lst4 的第一个元素为: " << lst4.front() << endl;
// 移动构造，将 lst4 的内容移动到 lst5，lst4 被清空
list<int> lst5(move(lst4));
cout << "lst5 的大小为: " << lst5.size() << ", lst5 的第一个元素为: " << lst5.front() << endl;
cout << "移动后，lst4 的大小为: " << lst4.size() << endl;
return 0;
}
自定义类型构造
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
// 构造函数
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
// 拷贝构造函数
Person(const Person &p) : name(p.name), age(p.age) {
cout << "拷贝 Person: " << name << endl;
}
// 移动构造函数
Person(Person &&p) noexcept : name(move(p.name)), age(p.age) {
cout << "移动 Person: " << name << endl;
}
};
int main(int argc, char const *argv[])
{
// 默认构造，创建一个空的 list<Person>
list<Person> lst1;
// 指定大小和值构造，创建包含 2 个 "John" 的 list
list<Person> lst2(2, Person("John", 30));
cout << "lst2 的大小为: " << lst2.size() << endl;
// 拷贝构造，将 lst2 的内容复制到 lst3
list<Person> lst3(lst2);
cout << "lst3 的大小为: " << lst3.size() << endl;
// 移动构造，将 lst3 的内容移动到 lst4，lst3 被清空
list<Person> lst4(move(lst3));
cout << "lst4 的大小为: " << lst4.size() << endl;
cout << "移动后，lst3 的大小为: " << lst3.size() << endl;
return 0;
}
3、总结
- 默认构造：创建空容器，适合之后逐步插入元素。
- 指定大小构造：创建包含指定数量元素的容器，元素可以有指定初始值。
- 拷贝构造：创建容器的副本。
- 移动构造：转移资源，提高效率。
4、注意事项
- 拷贝构造会调用元素的拷贝构造函数，适合复制数据。
- 移动构造后，原容器将不再持有数据，可有效节省内存并提升效率。
2.4.2 赋值操作
- 赋值运算符、重新分配与赋值
1、API介绍
operator= ：赋值运算符，将一个 list 的内容复制或移动到另一个 list。
assign(size_type count, const T &value) ：重新分配并填充指定数量的元素，所有元素都为相同的值。
assign(InputIterator first, InputIterator last) ：用指定范围的元素重新分配 list 的内容。
2、示例程序
普通类型赋值
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char const *argv[])
{
// 初始化一个 list
list<int> lst1 = {1, 2, 3, 4, 5};
cout << "lst1 初始内容: ";
for (int v : lst1) cout << v << " ";
cout << endl;
// 赋值运算符，将 lst1 的内容赋值给 lst2
list<int> lst2 = lst1;
cout << "lst2 复制自 lst1 的内容: ";
for (int v : lst2) cout << v << " ";
cout << endl;
// 重新分配并赋值，用三个值为 10 的元素填充 lst1
lst1.assign(3, 10);
cout << "lst1 重新分配后的内容: ";
for (int v : lst1) cout << v << " ";
cout << endl;
// 使用范围赋值，将 lst1 的内容赋值给 lst3
list<int> lst3;
lst3.assign(lst2.begin(), lst2.end());
cout << "lst3 使用范围赋值自 lst2 的内容: ";
for (int v : lst3) cout << v << " ";
cout << endl;
return 0;
}
自定义类型赋值
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
// 拷贝赋值运算符
Person& operator=(const Person &p) {
if (this != &p) {
name = p.name;
age = p.age;
cout << "拷贝赋值 Person: " << name << endl;
}
return *this;
}
};
int main(int argc, char const *argv[])
{
// 初始化一个包含 Person 对象的 list
list<Person> lst1 = {Person("Alice", 25), Person("Bob", 30)};
cout << "lst1 初始内容:" << endl;
for (const auto &p : lst1) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
// 使用赋值运算符将 lst1 赋值给 lst2
list<Person> lst2 = lst1;
cout << "lst2 复制自 lst1 的内容:" << endl;
for (const auto &p : lst2) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
// 重新分配并赋值，使用新内容替换 lst1 中的元素
lst1.assign(2, Person("Charlie", 35));
cout << "lst1 重新分配后的内容:" << endl;
for (const auto &p : lst1) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
// 使用范围赋值，将 lst1 的内容赋值给 lst3
list<Person> lst3;
lst3.assign(lst2.begin(), lst2.end());
cout << "lst3 使用范围赋值自 lst2 的内容:" << endl;
for (const auto &p : lst3) {
cout << "姓名: " << p.name << "，年龄: " << p.age << endl;
}
return 0;
}
3、总结
- 赋值运算符：将一个容器的内容复制或移动到另一个容器。
- 重新分配并赋值：清空原有内容，并用指定数量的元素重新填充容器。
- 范围赋值：使用另一个容器的部分或全部元素重新赋值当前容器。
4、注意事项
assign会清空原内容并重新分配内存空间。- 自定义类型的元素使用赋值运算符时，会调用其拷贝赋值运算符或移动赋值运算符。
- 当使用范围赋值时，确保迭代器的范围有效，避免未定义行为。
2.4.3 元素访问
- front、back
1、API介绍
front() ：返回容器中第一个元素的引用。
back() ：返回容器中最后一个元素的引用。
2、示例程序
示例1：普通类型的首尾元素访问
#include <iostream>
#include <list>
using namespace std;
int main() {
// 初始化一个包含整数的 list
list<int> numbers = {10, 20, 30, 40, 50};
// 访问第一个元素
cout << "第一个元素: " << numbers.front() << endl;
// 访问最后一个元素
cout << "最后一个元素: " << numbers.back() << endl;
// 修改首尾元素
numbers.front() = 5;
numbers.back() = 60;
cout << "修改后的第一个元素: " << numbers.front() << endl;
cout << "修改后的最后一个元素: " << numbers.back() << endl;
return 0;
}
示例2：自定义类型的首尾元素访问
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
// 初始化一个包含 Person 对象的 list
list<Person> people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)};
// 访问第一个元素
cout << "第一个元素: ";
people.front().display();
// 访问最后一个元素
cout << "最后一个元素: ";
people.back().display();
// 修改首尾元素
people.front() = Person("Alex", 28);
people.back() = Person("Chloe", 40);
cout << "修改后的第一个元素: ";
people.front().display();
cout << "修改后的最后一个元素: ";
people.back().display();
return 0;
}
3、总结
front()和back()分别用于访问容器中的第一个和最后一个元素，操作简便。- 由于它们返回的是元素的引用，可以直接对元素进行修改。
4、注意事项
- 在访问
list的front()或back()之前，应确保容器非空，以避免未定义行为。
2.4.4 迭代器
- begin、end、rbegin、rend、cbegin、cend、crbegin、crend
1、API介绍
begin() ：返回指向容器第一个元素的迭代器。
end() ：返回指向容器末尾之后位置的迭代器。
rbegin() ：返回指向容器最后一个元素的逆向迭代器。
rend() ：返回指向容器第一个元素之前位置的逆向迭代器。
cbegin() ：返回指向容器第一个元素的常量迭代器。
cend() ：返回指向容器末尾之后位置的常量迭代器。
crbegin() ：返回指向容器最后一个元素的常量逆向迭代器。
crend() ：返回指向容器第一个元素之前位置的常量逆向迭代器。
2、示例程序
示例1：普通类型的迭代器操作
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> numbers = {10, 20, 30, 40, 50};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历: ";
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历: ";
for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历: ";
for (auto cit = numbers.cbegin(); cit != numbers.cend(); ++cit) {
cout << *cit << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的迭代器操作
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
list<Person> people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历:" << endl;
for (auto it = people.begin(); it != people.end(); ++it) {
it->display();
}
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历:" << endl;
for (auto rit = people.rbegin(); rit != people.rend(); ++rit) {
rit->display();
}
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历:" << endl;
for (auto cit = people.cbegin(); cit != people.cend(); ++cit) {
cit->display();
}
return 0;
}
3、总结
- begin()/end() 用于正向遍历，适合对容器中的元素逐个访问。
- rbegin()/rend() 用于逆向遍历，适合从尾到头访问元素。
- cbegin()/cend() 和 crbegin()/crend() 用于常量遍历，保证元素不可修改。
4、注意事项
- 常量迭代器（如
cbegin）可确保遍历时不修改容器内容，适合只读操作。 - 逆向迭代器适合从尾部向头部遍历的情况，在操作时可以提高代码的灵活性。
2.4.5 容量管理
- empty、size、max_size、resize
1、API介绍
empty() ：检查容器是否为空，若为空返回 true，否则返回 false。
size() ：返回容器当前的元素数量。
max_size() ：返回容器最大支持的元素数量。
resize(count) ：调整容器大小，若新大小大于当前大小，则以默认值填充新增元素。
resize(count, value) ：调整容器大小，若新大小大于当前大小，则用指定的值填充新增元素。
2、示例程序
示例1：普通类型的容量管理
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> numbers = {10, 20, 30};
// 检查是否为空
cout << "容器是否为空: " << (numbers.empty() ? "是" : "否") << endl;
// 查看当前大小
cout << "容器大小: " << numbers.size() << endl;
// 调整大小并查看新内容
numbers.resize(5, 100); // 扩展大小到 5，并用 100 填充新元素
cout << "调整大小后的内容: ";
for (int n : numbers) {
cout << n << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的容量管理
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n = "Unknown", int a = 0) : name(n), age(a) {
cout << "创建 Person: " << name << ", 年龄: " << age << endl;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
list<Person> people = {Person("Alice", 30), Person("Bob", 25)};
// 检查是否为空
cout << "容器是否为空: " << (people.empty() ? "是" : "否") << endl;
// 查看当前大小
cout << "容器大小: " << people.size() << endl;
// 调整大小
people.resize(4, Person("Charlie", 35)); // 扩展大小到 4，并用新的 Person 对象填充
cout << "调整大小后的内容:" << endl;
for (const auto& person : people) {
person.display();
}
return 0;
}
3、总结
- empty()：用于检查容器是否为空，常用于在操作前确认容器状态。
- size()：返回当前元素数量，适合获取实时大小。
- max_size()：提供容器的理论最大容量，受内存限制。
- resize()：调整容器大小，可以指定新元素的填充值，便于灵活扩展或缩小容器。
4、注意事项
resize扩大容器时，新元素会以默认构造的值或指定的值填充；缩小时会删除多余的元素。- 使用
empty()检查容器状态，可避免在空容器上执行不安全操作。
2.4.6 修改操作
- clear、insert、erase、push_back、push_front、pop_back、pop_front、resize、swap
1、API介绍
clear() ：清空容器中的所有元素。
insert(iterator pos, value) ：在指定位置插入一个元素。
insert(iterator pos, count, value)：在指定位置插入多个相同值的元素。
erase(iterator pos) ：删除指定位置的元素。
erase(iterator first, last) ：删除指定范围内的元素。
push_back(value) ：在容器尾部添加一个元素。
push_front(value) ：在容器头部添加一个元素。
pop_back() ：移除容器尾部的元素。
pop_front() ：移除容器头部的元素。
resize(count) ：调整容器大小，默认填充值为默认构造的值。
resize(count, value) ：调整容器大小，并填充指定的值。
swap(list &other) ：交换两个容器的内容。
advance(InputIterator& it, Distance n);
：将迭代器 it 移动 n 个位置 用于和 insert 结合使用。
2、示例程序
示例1：普通类型的修改操作
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> numbers = {10, 20, 30};
// 在头部和尾部插入元素
numbers.push_front(5);
numbers.push_back(40);
cout << "添加头尾元素后的内容: ";
for (int n : numbers) cout << n << " ";
cout << endl;
// 删除头部和尾部元素
numbers.pop_front();
numbers.pop_back();
cout << "删除头尾元素后的内容: ";
for (int n : numbers) cout << n << " ";
cout << endl;
// 在指定位置插入多个元素
auto it = numbers.begin();
advance(it, 1);
numbers.insert(it, 2, 15);
cout << "插入多个元素后的内容: ";
for (int n : numbers) cout << n << " ";
cout << endl;
// 删除指定范围内的元素
it = numbers.begin();
auto it_end = numbers.end();
advance(it_end, -1);
numbers.erase(it, it_end);
cout << "删除范围内元素后的内容: ";
for (int n : numbers) cout << n << " ";
cout << endl;
// 清空容器
numbers.clear();
cout << "清空容器后的大小: " << numbers.size() << endl;
return 0;
}
示例2：自定义类型的修改操作
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
list<Person> people = {Person("Alice", 30), Person("Bob", 25)};
// 在头部和尾部添加元素
people.push_front(Person("Zara", 22));
people.push_back(Person("Chris", 35));
cout << "添加头尾元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 删除头部和尾部元素
people.pop_front();
people.pop_back();
cout << "删除头尾元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 在指定位置插入元素
auto it = people.begin();
advance(it, 1);
people.insert(it, Person("Eve", 28));
cout << "在指定位置插入元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 删除指定范围内的元素
it = people.begin();
auto it_end = people.end();
advance(it, 1);
advance(it_end, -1);
people.erase(it, it_end);
cout << "删除范围内元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 交换两个 list
list<Person> other_people = {Person("Tom", 40), Person("Jerry", 35)};
people.swap(other_people);
cout << "交换后 people 的内容:" << endl;
for (const auto& person : people) person.display();
return 0;
}
3、总结
push_front()和push_back()用于在容器的头部和尾部添加元素。pop_front()和pop_back()用于移除头部和尾部元素。insert()和erase()可以在指定位置或范围内插入或删除元素。resize()可以调整容器大小，增加时用默认值或指定值填充，减少时删除多余元素。clear()可以清空容器内容，swap()可以交换两个list的内容。
4、注意事项
insert()和erase()操作会使指向容器元素的迭代器失效，操作后应重新获取迭代器。clear()只清空元素，不释放容器的内存。swap()不涉及数据拷贝，只交换内部指针，因此效率高。
2.4.7 比较操作
operator==、operator!=、operator<、operator<=、operator>、operator>=
1、API介绍
operator== ：判断两个 list 是否相等（元素数量和内容均相同时返回 true）。
operator!= ：判断两个 list 是否不相等（若元素数量或内容不同则返回 true）。
operator< ：按字典顺序判断当前 list 是否小于另一个 list。
operator<= ：按字典顺序判断当前 list 是否小于或等于另一个 list。
operator> ：按字典顺序判断当前 list 是否大于另一个 list。
operator>= ：按字典顺序判断当前 list 是否大于或等于另一个 list。
2、示例程序
示例1：普通类型的比较操作
#include <iostream>
#include <list>
using namespace std;
int main() {
// 初始化两个整数类型的 list
list<int> list1 = {1, 2, 3};
list<int> list2 = {1, 2, 3};
list<int> list3 = {1, 2, 4};
// 相等比较
cout << "list1 和 list2 是否相等: " << (list1 == list2 ? "是" : "否") << endl;
// 不等比较
cout << "list1 和 list3 是否不等: " << (list1 != list3 ? "是" : "否") << endl;
// 小于比较
cout << "list1 是否小于 list3: " << (list1 < list3 ? "是" : "否") << endl;
// 大于比较
cout << "list3 是否大于 list2: " << (list3 > list2 ? "是" : "否") << endl;
return 0;
}
示例2：自定义类型的比较操作
自定义类型的对象在使用 list 比较时，需要重载相应的比较运算符，确保能够按特定规则进行比较。
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载相等运算符
bool operator==(const Person& other) const {
return (name == other.name && age == other.age);
}
// 重载小于运算符，用于字典顺序比较
bool operator<(const Person& other) const {
return (age < other.age) || (age == other.age && name < other.name);
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
list<Person> people1 = {Person("Alice", 30), Person("Bob", 25)};
list<Person> people2 = {Person("Alice", 30), Person("Bob", 25)};
list<Person> people3 = {Person("Alice", 30), Person("Charlie", 35)};
// 相等比较
cout << "people1 和 people2 是否相等: " << (people1 == people2 ? "是" : "否") << endl;
// 不等比较
cout << "people1 和 people3 是否不等: " << (people1 != people3 ? "是" : "否") << endl;
// 小于比较
cout << "people1 是否小于 people3: " << (people1 < people3 ? "是" : "否") << endl;
return 0;
}
3、总结
- operator== 和 operator!= 用于判断两个容器的内容是否完全相同或不同。
- operator<、operator<=、operator>、operator>= 按字典顺序逐元素比较，常用于排序和范围判断。
4、注意事项
- 自定义类型需要重载相应的比较运算符，确保比较操作按预期进行。
- 比较操作会逐个比较
list容器中的元素，一旦某个位置的元素不同，就会确定大小关系。
2.5 stack容器-栈
2.5.1 基本概念
栈
2.5.2 API介绍
1、构造函数与析构函数
stack() ：默认构造函数，创建空的 stack。
stack(const stack &other) ：拷贝构造函数，用其他 stack 初始化当前 stack。
stack(stack &&other) ：移动构造函数，将另一个 stack 的内容移动到当前 stack。
2、赋值操作
operator= ：赋值运算符，将一个 stack 的内容赋值给另一个 stack。
3、元素访问
top() ：返回栈顶元素的引用。
4、容量
empty() ：检查 stack 是否为空，若为空返回 true，否则返回 false。
size() ：返回 stack 中元素的数量。
5、修改操作
push(const T& value) ：将元素压入栈顶。 入栈
pop() ：移除栈顶元素。 出栈
emplace(args...) ：在栈顶位置直接构造元素，避免额外拷贝。
swap(stack &other) ：交换两个 stack 的内容。
2.5.3 示例程序
普通类型
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> numbers;
// 使用 push 将元素压入栈顶
numbers.push(10);
numbers.push(20);
numbers.push(30);
// 获取栈顶元素
cout << "栈顶元素: " << numbers.top() << endl;
// 移除栈顶元素
numbers.pop();
cout << "移除栈顶元素后，新的栈顶元素: " << numbers.top() << endl;
// 查看栈的大小
cout << "栈的大小: " << numbers.size() << endl;
return 0;
}
自定义类型
#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
stack<Person> people;
// 使用 emplace 在栈顶直接构造元素
people.emplace("Alice", 30);
people.emplace("Bob", 25);
// 获取栈顶元素
cout << "栈顶元素: ";
people.top().display();
// 移除栈顶元素
people.pop();
cout << "移除栈顶元素后，新的栈顶元素: ";
people.top().display();
// 查看栈的大小
cout << "栈的大小: " << people.size() << endl;
return 0;
}
2.5.4 总结
- top() 返回栈顶元素，可以直接访问或修改栈顶元素。
- push() 和 pop() 负责在栈顶添加和删除元素。
- empty() 和 size() 提供对栈状态的查询，检查是否为空以及当前元素数量。
- emplace() 可直接在栈顶位置构造元素，避免额外拷贝。
2.5.5 注意事项
stack仅支持在栈顶操作元素，不能随机访问其他位置。top()应在empty()检查之后使用，避免对空栈操作导致未定义行为。
2.6 queue容器-队列
2.6.1 基本概念
队列
2.6.2 API介绍
1、构造函数与析构函数
queue(); // 默认构造函数，创建一个空的队列。
queue(const queue& other); // 拷贝构造函数，用 other 初始化新的队列。
queue(queue&& other); // 移动构造函数，移动 other 的内容到新的队列。
2、赋值操作
queue& operator=(const queue& other); // 拷贝赋值，将 other 的内容复制到当前队列。
queue& operator=(queue&& other); // 移动赋值，将 other 的内容移动到当前队列。
3、元素访问
reference front(); // 返回队列头部元素的引用。
const_reference front() const; // 返回队列头部元素的常量引用。
reference back(); // 返回队列尾部元素的引用。
const_reference back() const; // 返回队列尾部元素的常量引用。
4、容量管理
bool empty() const; // 检查队列是否为空，若为空返回 true。
size_type size() const; // 返回队列中元素的数量。
5、修改操作
void push(const value_type& value); // 将元素拷贝到队列尾部。
void push(value_type&& value); // 将元素移动到队列尾部。
template <class... Args>
void emplace(Args&&... args); // 原位构造元素到队列尾部。
void pop(); // 移除队列头部的元素。
void swap(queue& other); // 交换两个队列的内容。
2.6.3 示例程序
普通类型
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 创建一个整数类型的队列
queue<int> q;
// 插入元素
q.push(10);
q.push(20);
q.push(30);
// 输出队列头部和尾部元素
cout << "队列头部元素: " << q.front() << endl;
cout << "队列尾部元素: " << q.back() << endl;
// 移除头部元素
q.pop();
cout << "移除一个元素后，队列头部元素: " << q.front() << endl;
// 输出队列的大小
cout << "队列的大小: " << q.size() << endl;
// 检查队列是否为空
cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl;
return 0;
}
自定义类型
#include <iostream>
#include <queue>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {
cout << "创建 Person: " << name << endl;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
// 创建一个 Person 类型的队列
queue<Person> q;
// 插入元素
q.push(Person("Alice", 30));
q.push(Person("Bob", 25));
// 输出队列头部和尾部元素
cout << "队列头部元素: ";
q.front().display();
cout << "队列尾部元素: ";
q.back().display();
// 移除头部元素
q.pop();
cout << "移除一个元素后，队列头部元素: ";
q.front().display();
// 输出队列的大小
cout << "队列的大小: " << q.size() << endl;
// 检查队列是否为空
cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl;
return 0;
}
2.7 set / multiset 容器
简介：
- 所有元素都会在插入时自动被排序
本质：
- set/multiset属于关联式容器，底层结构是用二叉树实现。
set和multiset区别：
- set不允许容器中有重复的元素
- multiset允许容器中有重复的元素
2.7.1 构造函数
- 默认构造、指定范围构造、拷贝构造、移动构造
1、API介绍
// 默认构造函数，创建一个空的 set
set();
// 迭代器范围构造函数，使用 [first, last) 范围内的元素构造 set
template <class InputIterator>
set(InputIterator first, InputIterator last);
// 拷贝构造函数，创建一个与给定 set 相同的副本
set(const set& other);
// 移动构造函数，从给定的 set 移动元素到新创建的 set
set(set&& other) noexcept;
2、示例程序
示例1：普通类型的构造
#include <iostream>
#include <set>
using namespace std;
int main() {
// 默认构造，创建一个空的 set
set<int> s1;
cout << "s1 的大小为: " << s1.size() << endl;
// 使用迭代器范围构造
int arr[] = {3, 1, 4, 1, 5};
set<int> s2(arr, arr + 5);
cout << "s2 的大小为: " << s2.size() << endl;
cout << "s2 的元素: ";
for (int val : s2) {
cout << val << " ";
}
cout << endl;
// 拷贝构造
set<int> s3(s2);
cout << "s3 的大小为: " << s3.size() << endl;
// 移动构造
set<int> s4(move(s3));
cout << "s4 的大小为: " << s4.size() << endl;
cout << "移动后，s3 的大小为: " << s3.size() << endl;
return 0;
}
示例2：自定义类型的构造
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载小于运算符，用于 set 的排序
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
// 默认构造，创建一个空的 set
set<Person> people1;
cout << "people1 的大小为: " << people1.size() << endl;
// 使用迭代器范围构造
Person arr[] = {Person("Alice", 30), Person("Bob", 25)};
set<Person> people2(arr, arr + 2);
cout << "people2 的大小为: " << people2.size() << endl;
cout << "people2 的元素:" << endl;
for (const auto& person : people2) {
person.display();
}
// 拷贝构造
set<Person> people3(people2);
cout << "people3 的大小为: " << people3.size() << endl;
// 移动构造
set<Person> people4(move(people3));
cout << "people4 的大小为: " << people4.size() << endl;
cout << "移动后，people3 的大小为: " << people3.size() << endl;
return 0;
}
3、总结
- 默认构造：创建一个空的
set，适合在后续逐步插入元素。 - 迭代器范围构造：使用已有元素范围初始化
set，会自动去重并按照排序规则排列。 - 拷贝构造：创建一个
set的副本，元素完全相同。 - 移动构造：将另一个
set的内容移动到新创建的set中，原来的set将被清空，提高效率。
4、注意事项
- 使用自定义类型时，必须重载
<运算符，以便set能正确地排序元素。 - 移动构造后，原
set将被清空，不能再访问其内容。 - 由于
set会自动去重，相同的元素只会保留一个。
2.7.2 赋值操作
- 赋值运算符、
swap、insert、emplace
1、API介绍
set& operator=(const set& other); // 拷贝赋值，将 other 的内容复制到当前 set。
set& operator=(set&& other); // 移动赋值，将 other 的内容移动到当前 set。
void swap(set& other); // 交换两个 set 的内容。
pair<iterator, bool> insert(const value_type& value); // 插入一个元素，返回迭代器和插入是否成功。
iterator insert(iterator hint, const value_type& value); // 使用提示位置插入一个元素。
template <class InputIterator>
void insert(InputIterator first, InputIterator last); // 插入 [first, last) 范围内的元素。
template<class... Args>
pair<iterator, bool> emplace(Args&&... args); // 原位构造并插入元素到 set。
template<class... Args>
iterator emplace_hint(iterator hint, Args&&... args); // 使用提示位置原位构造并插入元素到 set。
2、示例程序
示例1：普通类型的赋值操作
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s1 = {1, 2, 3};
set<int> s2;
// 拷贝赋值
s2 = s1;
cout << "s2 的内容（拷贝赋值）: ";
for (int val : s2) cout << val << " ";
cout << endl;
// 移动赋值
set<int> s3;
s3 = move(s1);
cout << "s3 的内容（移动赋值）: ";
for (int val : s3) cout << val << " ";
cout << endl;
// 交换内容
s2.swap(s3);
cout << "交换后，s2 的内容: ";
for (int val : s2) cout << val << " ";
cout << endl;
// 插入元素
auto result = s2.insert(4);
cout << "插入 4 是否成功: " << (result.second ? "是" : "否") << endl;
// 插入范围
int arr[] = {5, 6, 7};
s2.insert(arr, arr + 3);
cout << "插入范围后的 s2 内容: ";
for (int val : s2) cout << val << " ";
cout << endl;
return 0;
}
示例2：自定义类型的赋值操作
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载小于运算符
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people1 = {Person("Alice", 30), Person("Bob", 25)};
set<Person> people2;
// 拷贝赋值
people2 = people1;
cout << "people2 的内容（拷贝赋值）:" << endl;
for (const auto& person : people2) person.display();
// 移动赋值
set<Person> people3;
people3 = move(people1);
cout << "people3 的内容（移动赋值）:" << endl;
for (const auto& person : people3) person.display();
// 交换内容
people2.swap(people3);
cout << "交换后，people2 的内容:" << endl;
for (const auto& person : people2) person.display();
// 原位插入
people2.emplace("Charlie", 35);
cout << "插入 'Charlie' 后的 people2 内容:" << endl;
for (const auto& person : people2) person.display();
return 0;
}
3、总结
operator=：支持拷贝赋值和移动赋值，将一个set的内容赋给另一个set。swap()：交换两个set的内容，不涉及数据拷贝，效率高。insert()：插入元素或范围，如果元素已存在则不会插入，返回是否插入成功。emplace()：原位构造并插入新元素，避免不必要的拷贝或移动，效率更高。
4、注意事项
- 自定义类型的
set需要重载<运算符以支持排序。 - 使用
move后，被移动的set会被清空，不再持有数据。 insert保证元素的唯一性，重复插入的元素会被忽略。
2.7.3 迭代器
- begin、end、rbegin、rend、cbegin、cend、crbegin、crend
1、API介绍
begin() ：返回指向第一个元素的迭代器。
end() ：返回指向最后一个元素之后位置的迭代器。
rbegin() ：返回指向最后一个元素的逆向迭代器。
rend() ：返回指向第一个元素之前位置的逆向迭代器。
cbegin() ：返回指向第一个元素的常量迭代器。
cend() ：返回指向最后一个元素之后位置的常量迭代器。
crbegin() ：返回指向最后一个元素的常量逆向迭代器。
crend() ：返回指向第一个元素之前位置的常量逆向迭代器。
2、示例程序
示例1：普通类型的迭代器操作
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30, 40, 50};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历: ";
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历: ";
for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历: ";
for (auto cit = numbers.cbegin(); cit != numbers.cend(); ++cit) {
cout << *cit << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的迭代器操作
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载小于运算符，用于 set 的排序
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历:" << endl;
for (auto it = people.begin(); it != people.end(); ++it) {
it->display();
}
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历:" << endl;
for (auto rit = people.rbegin(); rit != people.rend(); ++rit) {
rit->display();
}
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历:" << endl;
for (auto cit = people.cbegin(); cit != people.cend(); ++cit) {
cit->display();
}
return 0;
}
3、总结
- begin()/end()：用于正向遍历
set容器中的元素。 - rbegin()/rend()：用于逆向遍历
set容器，从尾部向头部访问元素。 - cbegin()/cend() 和 crbegin()/crend()：用于常量遍历，确保元素在遍历中不被修改。
4、注意事项
- 由于
set是有序容器，遍历时元素会按照升序排列。 - 常量迭代器
cbegin、cend、crbegin和crend可以确保元素不可修改，适合只读操作。
2.7.4 容量管理
- empty、size、max_size
1、API介绍
bool empty() const; // 检查 set 是否为空，若为空返回 true。
size_type size() const; // 返回 set 中元素的数量。
size_type max_size() const; // 返回 set 容器支持的最大元素数量。
2、示例程序
示例1：普通类型的容量管理
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30};
// 检查是否为空
cout << "set 是否为空: " << (numbers.empty() ? "是" : "否") << endl;
// 获取当前大小
cout << "set 的大小: " << numbers.size() << endl;
// 获取最大容量
cout << "set 的最大容量: " << numbers.max_size() << endl;
return 0;
}
示例2：自定义类型的容量管理
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people = {Person("Alice", 30), Person("Bob", 25)};
// 检查是否为空
cout << "people 是否为空: " << (people.empty() ? "是" : "否") << endl;
// 获取当前大小
cout << "people 的大小: " << people.size() << endl;
// 获取最大容量
cout << "people 的最大容量: " << people.max_size() << endl;
return 0;
}
3、总结
- empty()：用于检查容器是否为空，常用于在操作前确认容器状态。
- size()：返回当前元素数量，适合获取实时大小。
- max_size()：提供容器的理论最大容量，受系统内存限制。
4、注意事项
size()和empty()在操作容器前是非常有用的检查，特别是在要访问元素时。max_size()返回的值通常是理论上的最大值，实际可用大小受系统内存影响。
2.7.5 修改操作
- clear、insert、erase、emplace、swap
1、API介绍
void clear(); // 清空 set 中的所有元素。
pair<iterator, bool> insert(const value_type& value); // 插入元素，返回迭代器和是否插入成功。
iterator insert(iterator hint, const value_type& value); // 使用提示位置插入元素。
template<class InputIterator>
void insert(InputIterator first, InputIterator last); // 插入范围 [first, last) 内的元素。
void erase(iterator pos); // 删除指定位置的元素。
size_type erase(const key_type& key); // 删除等于 key 的元素，返回删除的数量。
void erase(iterator first, iterator last); // 删除 [first, last) 范围内的元素。
void swap(set& other); // 交换两个 set 的内容。
template<class... Args>
pair<iterator, bool> emplace(Args&&... args); // 原位构造并插入元素到 set。
template<class... Args>
iterator emplace_hint(iterator hint, Args&&... args); // 使用提示位置原位构造并插入元素。
2、示例程序
示例1：普通类型的修改操作
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30};
// 插入元素
auto result = numbers.insert(40);
cout << "插入 40 是否成功: " << (result.second ? "是" : "否") << endl;
// 插入范围
int arr[] = {50, 60, 70};
numbers.insert(arr, arr + 3);
cout << "插入范围后的内容: ";
for (int val : numbers) cout << val << " ";
cout << endl;
// 删除元素
numbers.erase(20);
cout << "删除元素 20 后的内容: ";
for (int val : numbers) cout << val << " ";
cout << endl;
// 使用 emplace 原位构造并插入元素
numbers.emplace(15);
cout << "使用 emplace 插入 15 后的内容: ";
for (int val : numbers) cout << val << " ";
cout << endl;
// 清空 set
numbers.clear();
cout << "清空后，set 的大小: " << numbers.size() << endl;
return 0;
}
示例2：自定义类型的修改操作
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people;
// 插入元素
people.insert(Person("Alice", 30));
people.insert(Person("Bob", 25));
// 使用 emplace 原位构造并插入元素
people.emplace("Charlie", 35);
cout << "插入元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 删除元素
auto it = people.begin();
people.erase(it);
cout << "删除第一个元素后的内容:" << endl;
for (const auto& person : people) person.display();
// 交换两个 set
set<Person> other_people = {Person("Tom", 40), Person("Jerry", 45)};
people.swap(other_people);
cout << "交换后 people 的内容:" << endl;
for (const auto& person : people) person.display();
return 0;
}
3、总结
clear()：清空容器内容，使set变为空。insert()：插入单个元素或范围内的元素，若元素已存在则不会插入。erase()：删除指定位置的元素、指定值的元素或指定范围内的元素。emplace()：原位构造并插入元素，避免额外的拷贝或移动，提高性能。swap()：交换两个set的内容，操作高效。
4、注意事项
insert()操作会根据set的排序规则自动放置元素位置，不会插入重复元素。emplace()提供了更高的性能，适合构造元素的同时插入set。erase()操作会使指向已删除元素的迭代器失效，操作后应重新获取迭代器。
2.7.6 查找操作
- find、count、lower_bound、upper_bound、equal_range
1、API介绍
iterator find(const key_type& key); // 查找 key，若找到则返回指向该元素的迭代器，否则返回 end()。
size_type count(const key_type& key) const; // 返回等于 key 的元素数量（对于 set，结果要么是 0，要么是 1）。
iterator lower_bound(const key_type& key); // 返回第一个不小于 key 的元素的迭代器。
iterator upper_bound(const key_type& key); // 返回第一个大于 key 的元素的迭代器。
pair<iterator, iterator> equal_range(const key_type& key); // 返回等于 key 的元素范围（[lower_bound, upper_bound)）。
2、示例程序
示例1：普通类型的查找操作
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30, 40, 50};
// 查找元素
int key = 30;
auto it = numbers.find(key);
cout << "查找元素 " << key << ": " << (it != numbers.end() ? "找到" : "未找到") << endl;
// 统计元素个数
cout << "元素 30 的个数: " << numbers.count(30) << endl;
cout << "元素 100 的个数: " << numbers.count(100) << endl;
// 获取 lower_bound
auto lb = numbers.lower_bound(25);
cout << "lower_bound(25): " << (lb != numbers.end() ? to_string(*lb) : "未找到") << endl;
// 获取 upper_bound
auto ub = numbers.upper_bound(30);
cout << "upper_bound(30): " << (ub != numbers.end() ? to_string(*ub) : "未找到") << endl;
// 获取 equal_range
auto range = numbers.equal_range(40);
cout << "equal_range(40): ";
for (auto it = range.first; it != range.second; ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的查找操作
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)};
// 查找元素
Person key("Bob", 25);
auto it = people.find(key);
cout << "查找元素 Bob (25 岁): " << (it != people.end() ? "找到" : "未找到") << endl;
// 统计元素个数
Person target("Charlie", 35);
cout << "元素 Charlie (35 岁) 的个数: " << people.count(target) << endl;
// 获取 lower_bound
Person p1("Unknown", 28);
auto lb = people.lower_bound(p1);
cout << "lower_bound(28 岁): ";
if (lb != people.end()) {
lb->display();
} else {
cout << "未找到" << endl;
}
// 获取 upper_bound
Person p2("Unknown", 30);
auto ub = people.upper_bound(p2);
cout << "upper_bound(30 岁): ";
if (ub != people.end()) {
ub->display();
} else {
cout << "未找到" << endl;
}
return 0;
}
3、总结
- find()：用于查找指定元素，返回指向该元素的迭代器或
end()。 - count()：统计元素出现次数，对于
set，结果要么是 0，要么是 1。 - lower_bound()：返回第一个不小于指定元素的迭代器。
- upper_bound()：返回第一个大于指定元素的迭代器。
- equal_range()：返回等于指定元素的范围，便于同时获取
lower_bound和upper_bound。
4、注意事项
- 对于自定义类型，使用查找功能时，需要重载
<运算符以支持排序。 equal_range()返回一个范围，适合查找所有等于给定元素的元素（尽管set不允许重复元素）。
2.7.7 观察器
- key_comp、value_comp
1、API介绍
key_compare key_comp() const; // 返回用于比较键的比较对象。
value_compare value_comp() const; // 返回用于比较值的比较对象（对于 set，键和值相同）。
2、示例程序
示例1：普通类型的观察器
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30, 40, 50};
// 使用 key_comp() 获取比较对象
auto comp = numbers.key_comp();
int highest = *numbers.rbegin();
cout << "使用 key_comp() 比较元素: ";
for (int n : numbers) {
if (comp(n, highest)) {
cout << n << " ";
}
}
cout << endl;
return 0;
}
示例2：自定义类型的观察器
#include <iostream>
#include <set>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
set<Person> people = {Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35)};
// 使用 key_comp() 获取比较对象
auto comp = people.key_comp();
Person highest = *people.rbegin();
cout << "使用 key_comp() 比较元素:" << endl;
for (const auto& person : people) {
if (comp(person, highest)) {
person.display();
}
}
return 0;
}
3、总结
- key_comp()：返回一个比较对象，用于确定元素的顺序。它可以用于检查两个元素的相对顺序。
- value_comp()：对于
set，键和值相同，因此value_comp与key_comp等价。
4、注意事项
key_comp和value_comp通常用于自定义比较条件的容器中，以确保元素的排序符合自定义类型的规则。- 观察器函数通常用于特定的比较需求，而不是直接用于数据访问。
2.7.8 比较操作
operator==、operator!=、operator<、operator<=、operator>、operator>=
2.8 map / multimap 容器
高性能 std::map 是一种关联容器，内部采用平衡二叉树（如红黑树）实现，存储键值对（key-value）。map 自动根据键对元素进行排序，键的类型必须支持比较操作。
简介：
- map中所有元素都是pair
- pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
- 所有元素都会根据元素的键值自动排序
本质：
- map/multimap属于关联式容器，底层结构是用二叉树实现。
优点：
- 可以根据key值快速找到value值
map和multimap区别：
- map不允许容器中有重复key值元素
- multimap允许容器中有重复key值元素
2.8.1 构造函数与析构函数
- 默认构造、拷贝构造、移动构造、范围构造
1、API介绍
// 默认构造函数，创建一个空的 map
map();
// 迭代器范围构造函数，使用 [first, last) 范围内的元素构造 map
template <class InputIterator>
map(InputIterator first, InputIterator last);
// 拷贝构造函数，创建一个与给定 map 相同的副本
map(const map& other);
// 移动构造函数，从给定的 map 移动元素到新创建的 map
map(map&& other) noexcept;
2、示例程序
示例1：普通类型的构造
#include <iostream>
#include <map>
using namespace std;
int main() {
// 默认构造，创建一个空的 map
map<int, string> map1;
cout << "map1 的大小为: " << map1.size() << endl;
// 使用迭代器范围构造
map<int, string> temp = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> map2(temp.begin(), temp.end());
cout << "map2 的大小为: " << map2.size() << endl;
// 拷贝构造
map<int, string> map3(map2);
cout << "map3 的大小为: " << map3.size() << endl;
// 移动构造
map<int, string> map4(move(map3));
cout << "map4 的大小为: " << map4.size() << endl;
cout << "移动后，map3 的大小为: " << map3.size() << endl;
return 0;
}
示例2：自定义类型的构造
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
// 重载小于运算符，用于 map 的键排序
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
// 默认构造，创建一个空的 map
map<Person, string> people1;
cout << "people1 的大小为: " << people1.size() << endl;
// 使用迭代器范围构造
map<Person, string> temp = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
map<Person, string> people2(temp.begin(), temp.end());
cout << "people2 的大小为: " << people2.size() << endl;
// 拷贝构造
map<Person, string> people3(people2);
cout << "people3 的大小为: " << people3.size() << endl;
// 移动构造
map<Person, string> people4(move(people3));
cout << "people4 的大小为: " << people4.size() << endl;
cout << "移动后，people3 的大小为: " << people3.size() << endl;
return 0;
}
3、总结
- 默认构造：创建一个空的
map，适合在后续插入元素。 - 迭代器范围构造：用已有元素范围初始化
map，可以将其他容器或已有的map初始化为新map。 - 拷贝构造：创建一个
map的副本，所有元素完全相同。 - 移动构造：将另一个
map的内容移动到新创建的map中，避免不必要的拷贝，提升性能。
4、注意事项
- 自定义类型作为
map的键时，必须重载<运算符，以支持键的排序。 - 移动构造后，被移动的
map将被清空，不能再访问其内容。 - 迭代器范围构造可避免逐个插入，提高初始化效率。
2.8.2 赋值操作
- 赋值运算符、
swap交换
1、API介绍
map& operator=(const map& other); // 拷贝赋值，将 other 的内容复制到当前 map。
map& operator=(map&& other); // 移动赋值，将 other 的内容移动到当前 map。
void swap(map& other); // 交换两个 map 的内容。
2、示例程序
示例1：普通类型的赋值操作
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> map1 = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> map2;
// 拷贝赋值
map2 = map1;
cout << "map2 的内容（拷贝赋值）:" << endl;
for (const auto& pair : map2) {
cout << pair.first << ": " << pair.second << endl;
}
// 移动赋值
map<int, string> map3;
map3 = move(map1);
cout << "map3 的内容（移动赋值）:" << endl;
for (const auto& pair : map3) {
cout << pair.first << ": " << pair.second << endl;
}
cout << "移动后，map1 的大小: " << map1.size() << endl;
// 交换内容
map2.swap(map3);
cout << "交换后，map2 的内容:" << endl;
for (const auto& pair : map2) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
示例2：自定义类型的赋值操作
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
map<Person, string> people1 = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
map<Person, string> people2;
// 拷贝赋值
people2 = people1;
cout << "people2 的内容（拷贝赋值）:" << endl;
for (const auto& entry : people2) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
// 移动赋值
map<Person, string> people3;
people3 = move(people1);
cout << "people3 的内容（移动赋值）:" << endl;
for (const auto& entry : people3) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
cout << "移动后，people1 的大小: " << people1.size() << endl;
// 交换内容
people2.swap(people3);
cout << "交换后，people2 的内容:" << endl;
for (const auto& entry : people2) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
return 0;
}
3、总结
operator=：支持拷贝赋值和移动赋值，将一个map的内容赋给另一个map，操作完成后目标map拥有相同的内容。swap()：交换两个map的内容，不涉及数据拷贝，因此交换操作的效率很高。
4、注意事项
- 使用移动赋值后，被移动的
map将被清空，大小变为 0。 swap仅交换指向内容的内部指针，适合在需要高效交换内容的场景中使用。
2.8.3 元素访问
operator[]、at
1、API介绍
mapped_type& operator[](const key_type& key); // 使用键访问元素，若键不存在则创建并插入一个新元素。
mapped_type& operator[](key_type&& key); // 使用移动语义的键访问元素，若键不存在则创建并插入一个新元素。
mapped_type& at(const key_type& key); // 使用键访问元素，若键不存在则抛出 out_of_range 异常。
const mapped_type& at(const key_type& key) const; // 常量版本的 at，用于 const map。
2、示例程序
示例1：普通类型的元素访问
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> map1;
// 使用 operator[] 添加和访问元素
map1[1] = "one";
map1[2] = "two";
cout << "map1[1]: " << map1[1] << endl;
cout << "map1[2]: " << map1[2] << endl;
// 使用 at() 访问元素
try {
cout << "map1.at(1): " << map1.at(1) << endl;
cout << "map1.at(3): " << map1.at(3) << endl; // 不存在的键
} catch (const out_of_range& e) {
cout << "异常: " << e.what() << endl;
}
return 0;
}
示例2：自定义类型的元素访问
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
map<Person, string> people;
// 使用 operator[] 添加和访问元素
people[Person("Alice", 30)] = "Engineer";
people[Person("Bob", 25)] = "Doctor";
cout << "people[Person(\"Alice\", 30)]: " << people[Person("Alice", 30)] << endl;
cout << "people[Person(\"Bob\", 25)]: " << people[Person("Bob", 25)] << endl;
// 使用 at() 访问元素
try {
cout << "people.at(Person(\"Alice\", 30)): " << people.at(Person("Alice", 30)) << endl;
cout << "people.at(Person(\"Charlie\", 35)): " << people.at(Person("Charlie", 35)) << endl; // 不存在的键
} catch (const out_of_range& e) {
cout << "异常: " << e.what() << endl;
}
return 0;
}
3、总结
operator[]：通过键访问元素，若键不存在则创建一个新元素，适合需要同时访问和修改元素的场景。at()：安全访问元素，若键不存在则抛出out_of_range异常，适合在需要确保键存在的情况下使用。
4、注意事项
operator[]在键不存在时会自动插入新元素，注意避免无意间增大map。at()会抛出异常，因此在使用at前应确保键存在，以避免运行时错误。
2.8.4 迭代器
begin、end、rbegin、rend、cbegin、cend、crbegin、crend
1、API介绍
iterator begin(); // 返回指向第一个元素的迭代器。
iterator end(); // 返回指向最后一个元素之后位置的迭代器。
reverse_iterator rbegin(); // 返回指向最后一个元素的逆向迭代器。
reverse_iterator rend(); // 返回指向第一个元素之前位置的逆向迭代器。
const_iterator cbegin() const; // 返回指向第一个元素的常量迭代器。
const_iterator cend() const; // 返回指向最后一个元素之后位置的常量迭代器。
const_reverse_iterator crbegin() const; // 返回指向最后一个元素的常量逆向迭代器。
const_reverse_iterator crend() const; // 返回指向第一个元素之前位置的常量逆向迭代器。
2、示例程序
示例1：普通类型的迭代器操作
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> numbers = {{1, "one"}, {2, "two"}, {3, "three"}};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历: ";
for (auto it = numbers.begin(); it != numbers.end(); ++it) {
cout << it->first << ": " << it->second << " ";
}
cout << endl;
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历: ";
for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
cout << rit->first << ": " << rit->second << " ";
}
cout << endl;
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历: ";
for (auto cit = numbers.cbegin(); cit != numbers.cend(); ++cit) {
cout << cit->first << ": " << cit->second << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的迭代器操作
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age;
}
};
int main() {
map<Person, string> people = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
// 使用 begin() 和 end() 进行正向遍历
cout << "正向遍历:" << endl;
for (auto it = people.begin(); it != people.end(); ++it) {
it->first.display();
cout << " - 职业: " << it->second << endl;
}
// 使用 rbegin() 和 rend() 进行反向遍历
cout << "反向遍历:" << endl;
for (auto rit = people.rbegin(); rit != people.rend(); ++rit) {
rit->first.display();
cout << " - 职业: " << rit->second << endl;
}
// 使用 cbegin() 和 cend() 进行常量正向遍历
cout << "常量正向遍历:" << endl;
for (auto cit = people.cbegin(); cit != people.cend(); ++cit) {
cit->first.display();
cout << " - 职业: " << cit->second << endl;
}
return 0;
}
3、总结
- begin() / end()：用于正向遍历
map容器的元素。 - rbegin() / rend()：用于逆向遍历
map容器，从尾部向头部访问元素。 - cbegin() / cend() 和 crbegin() / crend()：用于常量遍历，保证元素不可修改，适合只读操作。
4、注意事项
- 迭代器允许对
map容器进行顺序遍历，map会自动按键的升序排列元素。 - 常量迭代器
cbegin、cend、crbegin和crend用于防止对元素的修改，适合只读访问。
2.8.5 容量管理
empty、size、max_size
1、API介绍
bool empty() const; // 检查 map 是否为空，若为空返回 true。
size_type size() const; // 返回 map 中元素的数量。
size_type max_size() const; // 返回 map 容器能容纳的最大元素数量。
2、示例程序
示例1：普通类型的容量管理
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> numbers = {{1, "one"}, {2, "two"}, {3, "three"}};
// 检查是否为空
cout << "map 是否为空: " << (numbers.empty() ? "是" : "否") << endl;
// 获取当前大小
cout << "map 的大小: " << numbers.size() << endl;
// 获取最大容量
cout << "map 的最大容量: " << numbers.max_size() << endl;
return 0;
}
示例2：自定义类型的容量管理
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
map<Person, string> people = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
// 检查是否为空
cout << "people 是否为空: " << (people.empty() ? "是" : "否") << endl;
// 获取当前大小
cout << "people 的大小: " << people.size() << endl;
// 获取最大容量
cout << "people 的最大容量: " << people.max_size() << endl;
return 0;
}
3、总结
- empty()：用于检查容器是否为空，返回
true表示无元素，适合在操作前确认容器状态。 - size()：返回当前元素数量，适合获取容器的实际大小。
- max_size()：返回
map的理论最大容量，用于了解容器的潜在存储能力。
4、注意事项
size()和empty()在操作容器前是非常有用的检查，特别是在要访问元素时。max_size()的返回值通常是理论最大值，实际可用大小受系统内存和资源限制。
2.8.6 修改器
insert、emplace、erase、clear、swap
1、API介绍
pair<iterator, bool> insert(const value_type& value); // 插入键值对，返回迭代器和是否插入成功。
iterator insert(iterator hint, const value_type& value); // 在 hint 位置插入键值对，提高插入效率。
template<class InputIterator>
void insert(InputIterator first, InputIterator last); // 插入 [first, last) 范围内的键值对。
template<class... Args>
pair<iterator, bool> emplace(Args&&... args); // 原位构造并插入新元素，避免额外拷贝。
template<class... Args>
iterator emplace_hint(iterator hint, Args&&... args); // 使用提示位置原位构造并插入新元素。
iterator erase(iterator pos); // 删除指定位置的元素，返回下一个元素的迭代器。
size_type erase(const key_type& key); // 删除指定键的元素，返回删除的数量。
iterator erase(iterator first, iterator last); // 删除 [first, last) 范围内的元素。
void clear(); // 清空 map 中的所有元素。
void swap(map& other); // 交换两个 map 的内容。
2、示例程序
示例1：普通类型的修改操作
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> numbers;
// 使用 insert 插入元素
numbers.insert({1, "one"});
numbers.insert({2, "two"});
// 使用 emplace 原位插入元素
numbers.emplace(3, "three");
// 使用 hint 插入元素
auto it = numbers.begin();
numbers.insert(it, {0, "zero"});
// 显示 map 内容
cout << "map 内容: ";
for (const auto& pair : numbers) {
cout << pair.first << ": " << pair.second << " ";
}
cout << endl;
// 删除元素
numbers.erase(2);
cout << "删除键 2 后的内容: ";
for (const auto& pair : numbers) {
cout << pair.first << ": " << pair.second << " ";
}
cout << endl;
// 清空 map
numbers.clear();
cout << "清空后的 map 大小: " << numbers.size() << endl;
return 0;
}
示例2：自定义类型的修改操作
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age << endl;
}
};
int main() {
map<Person, string> people;
// 使用 insert 插入元素
people.insert({Person("Alice", 30), "Engineer"});
people.insert({Person("Bob", 25), "Doctor"});
// 使用 emplace 原位插入元素
people.emplace(Person("Charlie", 35), "Teacher");
// 显示 map 内容
cout << "people 内容:" << endl;
for (const auto& entry : people) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
// 删除元素
auto it = people.begin();
people.erase(it);
cout << "删除第一个元素后的内容:" << endl;
for (const auto& entry : people) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
// 交换两个 map
map<Person, string> other_people = {{Person("David", 40), "Manager"}};
people.swap(other_people);
cout << "交换后 people 的内容:" << endl;
for (const auto& entry : people) {
entry.first.display();
cout << "职业: " << entry.second << endl;
}
return 0;
}
3、总结
- insert()：用于插入单个键值对或范围内的键值对，适合需要条件性插入的场景。
- emplace()：原位构造并插入元素，避免不必要的拷贝或移动操作，提高效率。
- erase()：删除指定元素或范围内的元素，返回更新后的迭代器。
- clear()：清空整个
map，将其大小变为 0。 - swap()：交换两个
map的内容，不涉及数据拷贝，效率高。
4、注意事项
- insert() 和 emplace() 都可以添加新元素，但 emplace() 直接构造元素，避免了临时对象创建。
- 使用 erase() 时，指向已删除元素的迭代器将失效，需重新获取迭代器。
- swap() 操作高效，因为仅交换内部指针，数据未被拷贝。
2.8.7 查找操作
find、count、lower_bound、upper_bound、equal_range
1、API介绍
iterator find(const key_type& key); // 查找 key，若找到则返回指向该元素的迭代器，否则返回 end()。
size_type count(const key_type& key) const; // 返回等于 key 的元素数量，对于 map，结果要么是 0 要么是 1。
iterator lower_bound(const key_type& key); // 返回第一个不小于 key 的元素的迭代器。
iterator upper_bound(const key_type& key); // 返回第一个大于 key 的元素的迭代器。
pair<iterator, iterator> equal_range(const key_type& key); // 返回等于 key 的元素范围（[lower_bound, upper_bound)）。
2、示例程序
示例1：普通类型的查找操作
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> numbers = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};
// 查找元素
int key = 3;
auto it = numbers.find(key);
cout << "查找键 " << key << ": " << (it != numbers.end() ? it->second : "未找到") << endl;
// 统计元素个数
cout << "键 3 的个数: " << numbers.count(3) << endl;
cout << "键 5 的个数: " << numbers.count(5) << endl;
// 获取 lower_bound
auto lb = numbers.lower_bound(2);
cout << "lower_bound(2): " << (lb != numbers.end() ? lb->second : "未找到") << endl;
// 获取 upper_bound
auto ub = numbers.upper_bound(3);
cout << "upper_bound(3): " << (ub != numbers.end() ? ub->second : "未找到") << endl;
// 获取 equal_range
auto range = numbers.equal_range(3);
cout << "equal_range(3): ";
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
cout << endl;
return 0;
}
示例2：自定义类型的查找操作
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age;
}
};
int main() {
map<Person, string> people = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}, {Person("Charlie", 35), "Teacher"}};
// 查找元素
Person key("Bob", 25);
auto it = people.find(key);
cout << "查找元素 Bob (25 岁): " << (it != people.end() ? it->second : "未找到") << endl;
// 统计元素个数
cout << "键 Bob (25 岁) 的个数: " << people.count(key) << endl;
// 获取 lower_bound
Person p1("Unknown", 28);
auto lb = people.lower_bound(p1);
cout << "lower_bound(28 岁): ";
if (lb != people.end()) {
lb->first.display();
cout << " - 职业: " << lb->second << endl;
} else {
cout << "未找到" << endl;
}
// 获取 upper_bound
Person p2("Unknown", 30);
auto ub = people.upper_bound(p2);
cout << "upper_bound(30 岁): ";
if (ub != people.end()) {
ub->first.display();
cout << " - 职业: " << ub->second << endl;
} else {
cout << "未找到" << endl;
}
return 0;
}
3、总结
- find()：用于查找指定键的元素，返回指向该元素的迭代器或
end()。 - count()：统计键出现的次数，对于
map，结果要么是 0 要么是 1。 - lower_bound()：返回第一个不小于指定键的元素的迭代器。
- upper_bound()：返回第一个大于指定键的元素的迭代器。
- equal_range()：返回一个范围，包含等于指定键的元素，便于同时获取
lower_bound和upper_bound。
4、注意事项
- 自定义类型作为
map的键时，需重载<运算符以支持排序，从而确保可以进行查找操作。 equal_range()返回的范围包含所有等于给定键的元素，尽管map不允许重复键。
2.8.8 观察器
key_comp、value_comp
1、API介绍
key_compare key_comp() const; // 返回用于比较键的比较对象。
value_compare value_comp() const; // 返回用于比较键值对的比较对象（只比较键）。
2、示例程序
示例1：普通类型的观察器
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> numbers = {{1, "one"}, {2, "two"}, {3, "three"}};
// 使用 key_comp() 获取比较对象
auto comp = numbers.key_comp();
int highest = numbers.rbegin()->first;
cout << "使用 key_comp() 比较的元素: ";
for (const auto& pair : numbers) {
if (comp(pair.first, highest)) {
cout << pair.first << ": " << pair.second << " ";
}
}
cout << endl;
// 使用 value_comp() 获取比较对象
auto val_comp = numbers.value_comp();
cout << "使用 value_comp() 比较的元素: ";
for (const auto& pair : numbers) {
if (val_comp(pair, *numbers.rbegin())) {
cout << pair.first << ": " << pair.second << " ";
}
}
cout << endl;
return 0;
}
示例2：自定义类型的观察器
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age;
}
};
int main() {
map<Person, string> people = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}, {Person("Charlie", 35), "Teacher"}};
// 使用 key_comp() 获取比较对象
auto comp = people.key_comp();
Person highest = people.rbegin()->first;
cout << "使用 key_comp() 比较的元素:" << endl;
for (const auto& entry : people) {
if (comp(entry.first, highest)) {
entry.first.display();
cout << " - 职业: " << entry.second << endl;
}
}
// 使用 value_comp() 获取比较对象
auto val_comp = people.value_comp();
cout << "使用 value_comp() 比较的元素:" << endl;
for (const auto& entry : people) {
if (val_comp(entry, *people.rbegin())) {
entry.first.display();
cout << " - 职业: " << entry.second << endl;
}
}
return 0;
}
3、总结
- key_comp()：返回一个比较对象，用于比较键的相对顺序。它可以检查一个键是否小于另一个键。
- value_comp()：返回一个比较对象，用于比较键值对的顺序。实际上只比较键，但在需要完整键值对的情况下使用。
4、注意事项
key_comp和value_comp在自定义类型中需要键类型实现<运算符，以确保正确排序。- 观察器函数通常用于检查顺序而非直接数据访问。
2.8.9 比较操作
operator==、operator!=、operator<、operator<=、operator>、operator>=
1、API介绍
bool operator==(const map& lhs, const map& rhs); // 判断两个 map 是否相等（键值对数量和内容均相同）。
bool operator!=(const map& lhs, const map& rhs); // 判断两个 map 是否不相等。
bool operator<(const map& lhs, const map& rhs); // 按字典顺序判断 lhs 是否小于 rhs。
bool operator<=(const map& lhs, const map& rhs); // 按字典顺序判断 lhs 是否小于或等于 rhs。
bool operator>(const map& lhs, const map& rhs); // 按字典顺序判断 lhs 是否大于 rhs。
bool operator>=(const map& lhs, const map& rhs); // 按字典顺序判断 lhs 是否大于或等于 rhs。
2、示例程序
示例1：普通类型的比较操作
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> map1 = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> map2 = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> map3 = {{1, "one"}, {2, "two"}, {4, "four"}};
// 相等比较
cout << "map1 和 map2 是否相等: " << (map1 == map2 ? "是" : "否") << endl;
// 不等比较
cout << "map1 和 map3 是否不等: " << (map1 != map3 ? "是" : "否") << endl;
// 小于比较
cout << "map1 是否小于 map3: " << (map1 < map3 ? "是" : "否") << endl;
// 大于比较
cout << "map3 是否大于 map2: " << (map3 > map2 ? "是" : "否") << endl;
return 0;
}
示例2：自定义类型的比较操作
在 map 中使用自定义类型作为键时，需为键类型定义比较运算符（如 <），以支持顺序比较。
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person {
public:
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
bool operator<(const Person& other) const {
return age < other.age;
}
void display() const {
cout << "姓名: " << name << "，年龄: " << age;
}
};
int main() {
map<Person, string> people1 = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
map<Person, string> people2 = {{Person("Alice", 30), "Engineer"}, {Person("Bob", 25), "Doctor"}};
map<Person, string> people3 = {{Person("Alice", 30), "Engineer"}, {Person("Charlie", 35), "Teacher"}};
// 相等比较
cout << "people1 和 people2 是否相等: " << (people1 == people2 ? "是" : "否") << endl;
// 不等比较
cout << "people1 和 people3 是否不等: " << (people1 != people3 ? "是" : "否") << endl;
// 小于比较
cout << "people1 是否小于 people3: " << (people1 < people3 ? "是" : "否") << endl;
return 0;
}
3、总结
- operator== 和 operator!=：判断两个
map是否相等，要求键值对的数量和内容相同。 - operator<, operator<=, operator>, operator>=：逐键值对进行字典顺序比较，确定两个
map的相对顺序。
4、注意事项
- 使用自定义类型作为
map的键时，需重载<运算符，以支持字典顺序比较。 - 比较操作按键值对的顺序逐项进行，遇到第一个不同的元素时即确定两个
map的相对顺序。
第四章 函数对象
4.1 函数对象
4.1.1 函数对象概念
1、概念介绍
- 函数对象（Function Object），也称为仿函数（Functor），是一个重载了函数调用运算符
operator()的类。 - 通过重载
operator()，对象可以像函数一样被调用。
2、函数对象的本质
- 函数对象本质上是一个类的实例，而不是一个普通函数。
- 它可以拥有成员变量和成员函数，能够维护自己的状态。
4.1.2 函数对象的使用
1、特点
- 像函数一样调用：函数对象可以像普通函数一样接受参数并返回值。
- 维护状态：函数对象可以有自己的成员变量，用于记录状态信息。
- 作为参数传递：函数对象可以作为参数传递给其他函数。
2、示例程序
示例1：基本函数对象的使用
#include <iostream>
using namespace std;
// 定义一个加法函数对象
class Add {
public:
int operator()(int a, int b) {
return a + b;
}
};
int main() {
Add add;
int result = add(10, 20); // 像函数一样调用
cout << "结果是：" << result << endl;
return 0;
}
示例2：函数对象的状态
#include <iostream>
#include <string>
using namespace std;
// 定义一个打印函数对象，记录调用次数
class Printer {
public:
Printer() : count(0) {}
void operator()(const string& message) {
cout << message << endl;
count++; // 记录调用次数
}
int getCount() const {
return count;
}
private:
int count;
};
int main() {
Printer printer;
printer("你好，世界");
printer("欢迎学习 C++");
cout << "打印函数被调用了 " << printer.getCount() << " 次" << endl;
return 0;
}
示例3：函数对象作为参数
#include <iostream>
using namespace std;
// 定义一个乘法函数对象
class Multiply {
public:
int operator()(int a, int b) {
return a * b;
}
};
// 接受函数对象作为参数的函数
void compute(Multiply& func, int x, int y) {
int result = func(x, y);
cout << "计算结果是：" << result << endl;
}
int main() {
Multiply multiply;
compute(multiply, 5, 6);
return 0;
}
3、总结
- 函数对象通过重载
operator()，使对象可以像函数一样被调用。 - 函数对象可以维护内部状态，提供比普通函数更灵活的功能。
- 可以将函数对象作为参数传递，实现更高程度的代码复用。
4、注意事项
- 函数对象是类的实例，使用时要注意其状态的维护，尤其在多线程环境下。
- 在使用函数对象作为参数时，建议以引用方式传递，避免不必要的拷贝。
4.2 谓词
4.2.1 概念
1、什么是谓词
- **谓词（Predicate）**是一个返回布尔值的函数或函数对象，用于判断某个条件是否成立。
- 在 C++ 中，谓词常用于标准模板库（STL）中的算法，对元素进行筛选、比较等操作。
2、谓词的分类
- 一元谓词：接受一个参数的谓词函数或函数对象。
- 二元谓词：接受两个参数的谓词函数或函数对象。
4.2.2 一元谓词
1、概念介绍
- 一元谓词是指接受一个参数并返回布尔值的函数或函数对象。
- 常用于 STL 算法，如
find_if、count_if、remove_if等，对容器中的元素进行条件判断。
2、示例程序
示例1：使用函数判断奇数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义一个函数，判断是否为奇数
bool isOdd(int n) {
return n % 2 != 0;
}
int main() {
vector<int> numbers = {1, 2, 3, 4, 5, 6};
// 使用 find_if 查找第一个奇数 find_if 按条件查找
auto it = find_if(numbers.begin(), numbers.end(), isOdd);
if (it != numbers.end()) {
cout << "找到奇数：" << *it << endl;
} else {
cout << "未找到奇数" << endl;
}
return 0;
}
示例2：使用函数对象判断负数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义一个函数对象，判断是否为负数
class IsNegative {
public:
bool operator()(int n) const {
return n < 0;
}
};
int main() {
vector<int> numbers = {3, -1, 4, -5, 9};
// 使用 count_if 统计负数的个数
int count = count_if(numbers.begin(), numbers.end(), IsNegative());
cout << "负数的个数：" << count << endl;
return 0;
}
3、总结
- 一元谓词用于判断单个元素是否满足某个条件。
- 可以使用普通函数或函数对象来实现一元谓词，函数对象可以维护状态，更加灵活。
4、注意事项
- 在使用 STL 算法时，谓词应对元素进行只读操作，避免修改容器内容。
- 谓词应满足纯函数特性，即相同输入产生相同输出，没有副作用。
4.2.3 二元谓词
1、概念介绍
- 二元谓词是指接受两个参数并返回布尔值的函数或函数对象。
- 常用于需要比较两个元素的 STL 算法，如
sort、unique、merge等。
2、示例程序
示例1：自定义排序规则
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义一个函数对象，按绝对值大小排序
class AbsLess {
public:
bool operator()(int a, int b) const {
return abs(a) < abs(b);
}
};
int main() {
vector<int> numbers = {3, -1, 4, -5, 9};
// 使用自定义的二元谓词进行排序
sort(numbers.begin(), numbers.end(), AbsLess());
cout << "按绝对值排序结果：";
for (int n : numbers) {
cout << n << " ";
}
cout << endl;
return 0;
}
示例2：比较字符串长度
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// 定义一个函数对象，比较字符串长度
class CompareLength {
public:
bool operator()(const string &a, const string &b) const {
return a.length() < b.length();
}
};
int main() {
vector<string> words = {"apple", "banana", "pear", "grape"};
// 使用自定义的二元谓词进行排序
sort(words.begin(), words.end(), CompareLength());
cout << "按长度排序结果：";
for (const auto &word : words) {
cout << word << " ";
}
cout << endl;
return 0;
}
3、总结
- 二元谓词用于比较两个元素，确定其相对关系，如排序、合并等操作。
- 自定义二元谓词可以改变算法的默认行为，实现特殊的比较规则。
4、注意事项
- 二元谓词应满足严格弱序（Strict Weak Ordering）的要求，确保算法的正确性。
- 定义二元谓词时，应注意比较操作的对称性和传递性，避免出现不一致的比较结果。
4.3 内建函数对象
4.3.1 内建函数对象的意义
1、概念
- 内建函数对象是指 C++ 标准模板库（STL）中预定义的一些函数对象，也称为仿函数。
- 这些函数对象通过重载
operator()，使对象可以像函数一样被调用。
2、分类
- 算术仿函数：用于执行基本的算术运算。
- 关系仿函数：用于比较两个值之间的关系。
- 逻辑仿函数：用于执行逻辑运算。
3、用法
- 内建函数对象的用法与普通函数类似，但它们可以作为模板参数传递，增强了算法的灵活性。
- 使用内建函数对象需要包含头文件
#include <functional>。
4.3.2 算术仿函数
1、功能描述
- 算术仿函数用于执行基本的算术运算，包括加法、减法、乘法、除法、取模和取反。
- 除了
negate是一元运算（接受一个参数），其他都是二元运算（接受两个参数）。
2、仿函数原型
template<class T> T plus<T> // 加法仿函数
template<class T> T minus<T> // 减法仿函数
template<class T> T multiplies<T> // 乘法仿函数
template<class T> T divides<T> // 除法仿函数
template<class T> T modulus<T> // 取模仿函数
template<class T> T negate<T> // 取反仿函数
3、示例程序
#include <iostream>
#include <functional>
int main() {
// 使用 negate 仿函数进行取反操作
std::negate<int> negateFunc;
int num = 10;
std::cout << "原始值: " << num << "，取反后: " << negateFunc(num) << std::endl;
// 使用 plus 仿函数进行加法运算
std::plus<int> plusFunc;
int a = 5, b = 15;
std::cout << a << " + " << b << " = " << plusFunc(a, b) << std::endl;
// 使用 multiplies 仿函数进行乘法运算
std::multiplies<int> multipliesFunc;
int x = 3, y = 7;
std::cout << x << " * " << y << " = " << multipliesFunc(x, y) << std::endl;
return 0;
}
运行结果：
原始值: 10，取反后: -10
5 + 15 = 20
3 * 7 = 21
4、总结
- 算术仿函数提供了对基本运算符的封装，可以在算法中灵活使用。
- 在使用内建函数对象时，记得包含头文件
#include <functional>。
4.3.3 关系仿函数
1、功能描述
- 关系仿函数用于比较两个值之间的关系，如大小、等于、不等等。
- 常用于排序、搜索等需要比较元素的算法中。
2、仿函数原型
template<class T> bool equal_to<T> // 等于
template<class T> bool not_equal_to<T> // 不等于
template<class T> bool greater<T> // 大于
template<class T> bool less<T> // 小于
template<class T> bool greater_equal<T> // 大于等于
template<class T> bool less_equal<T> // 小于等于
3、示例程序
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
int main() {
// 定义一个整数向量
std::vector<int> numbers = {10, 20, 30, 40, 50};
// 使用 greater 仿函数进行降序排序
std::sort(numbers.begin(), numbers.end(), std::greater<int>());
std::cout << "降序排序结果: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用 less 仿函数进行升序排序
std::sort(numbers.begin(), numbers.end(), std::less<int>());
std::cout << "升序排序结果: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
// 使用 equal_to 仿函数查找值为30的元素
auto it = std::find_if(numbers.begin(), numbers.end(), std::bind(std::equal_to<int>(), std::placeholders::_1, 30));
if (it != numbers.end()) {
std::cout << "找到元素: " << *it << std::endl;
} else {
std::cout << "未找到元素 30" << std::endl;
}
return 0;
}
运行结果：
降序排序结果: 50 40 30 20 10
升序排序结果: 10 20 30 40 50
找到元素: 30
4、总结
- 关系仿函数可以方便地改变算法的默认比较行为，如在
sort中指定排序规则。 - 常用的关系仿函数是
greater和less，分别用于降序和升序排序。
4.3.4 逻辑仿函数
1、功能描述
- 逻辑仿函数用于执行逻辑运算，如逻辑与、逻辑或、逻辑非。
- 常用于布尔类型数据的处理，或结合算法对条件进行判断。
2、仿函数原型
template<class T> bool logical_and<T> // 逻辑与
template<class T> bool logical_or<T> // 逻辑或
template<class T> bool logical_not<T> // 逻辑非
3、示例程序
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
int main() {
// 定义一个布尔向量
std::vector<bool> flags = {true, false, true, false};
std::cout << "原始值: ";
for (bool flag : flags) {
std::cout << std::boolalpha << flag << " ";
}
std::cout << std::endl;
// 使用 logical_not 仿函数进行逻辑取反
std::vector<bool> result(flags.size());
std::transform(flags.begin(), flags.end(), result.begin(), std::logical_not<bool>());
std::cout << "取反后: ";
for (bool flag : result) {
std::cout << std::boolalpha << flag << " ";
}
std::cout << std::endl;
// 使用 logical_and 仿函数进行逻辑与运算
std::vector<bool> otherFlags = {false, false, true, true};
std::vector<bool> andResult(flags.size());
std::transform(flags.begin(), flags.end(), otherFlags.begin(), andResult.begin(), std::logical_and<bool>());
std::cout << "逻辑与运算结果: ";
for (bool flag : andResult) {
std::cout << std::boolalpha << flag << " ";
}
std::cout << std::endl;
return 0;
}
运行结果：
原始值: true false true false
取反后: false true false true
逻辑与运算结果: false false true false
4、总结
- 逻辑仿函数在处理布尔类型数据时非常有用，尤其是需要对序列中的元素进行批量逻辑运算时。
- 常与算法如
std::transform结合使用，实现对容器元素的批量操作。
总的来说，内建函数对象为 STL 算法提供了强大的功能扩展，利用它们可以更灵活地定制算法的行为。在编写代码时，善用这些仿函数可以提高代码的可读性和效率。
第五章 STL算法
5.1 遍历算法
5.1.1 for_each 遍历
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn);
参数
first： 遍历区间的起始位置，指向容器中开始的位置。
last： 遍历区间的结束位置，指向容器最后一个元素的下一个位置（不包含）。
fn： 可调用对象（如函数指针、lambda 表达式或函数对象），应用于区间内每个元素。
返回值
返回传入的函数对象 `fn`，用于可能的结果获取或状态更新。
2、示例程序
普通类型
// 普通类型遍历
#include <iostream>
#include <vector>
#include <algorithm>
// 定义一个函数用于打印整数值
void print(int value) {
std::cout << value << " ";
}
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 for_each 遍历并打印每个元素
std::for_each(numbers.begin(), numbers.end(), print);
return 0;
}
自定义类型
// 自定义类型遍历
#include <iostream>
#include <vector>
#include <algorithm>
// 定义一个表示人的类
class Person {
public:
// 构造函数初始化姓名和年龄
Person(std::string name, int age) : name(name), age(age) {}
// 打印人的信息
void print() const {
std::cout << "Name: " << name << ", Age: " << age << std::endl;
}
private:
std::string name;
int age;
};
// 函数对象，用于调用 Person 的 print 方法
void printPerson(const Person& person) {
person.print();
}
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 使用 for_each 遍历并打印每个人的信息
std::for_each(people.begin(), people.end(), printPerson);
return 0;
}
5.1.2 transform 搬运
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
参数
first：转换区间的起始位置，指向容器中第一个元素的位置。
last：转换区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
result：输出区间的起始位置，用于存储转换后的元素。
op：一元操作函数或函数对象，它应用于每个输入元素并返回转换后的结果。
返回值
返回指向输出区间的迭代器，表示最后一个被写入元素的下一个位置。
2、示例程序
普通类型转换
// 普通类型转换
#include <iostream>
#include <vector>
#include <algorithm>
// 定义一个函数，将整数值加倍
int doubleValue(int value) {
return value * 2;
}
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 定义一个用于存储结果的向量，大小与 numbers 相同
std::vector<int> results(numbers.size());
// 使用 transform 将 numbers 中的每个元素加倍，并存储到 results 中
std::transform(numbers.begin(), numbers.end(), results.begin(), doubleValue);
// 输出转换后的结果
for (int value : results) {
std::cout << value << " ";
}
return 0;
}
自定义类型转换
// 自定义类型转换
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
// 定义一个表示人的类
class Person {
public:
Person(std::string name, int age) : name(name), age(age) {}
// 获取年龄
int getAge() const {
return age;
}
private:
std::string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 定义一个用于存储年龄的向量，大小与 people 相同
std::vector<int> ages(people.size());
// 使用 transform 提取每个人的年龄，并存储到 ages 中
std::transform(people.begin(), people.end(), ages.begin(),
[](const Person& person) { return person.getAge(); });
// 输出转换后的年龄
for (int age : ages) {
std::cout << age << " ";
}
return 0;
}
5.2 查找算法
按照您的格式，内容如下：
5.2.1 find 查找
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);
参数
first：查找区间的起始位置，指向容器中第一个元素的位置。
last：查找区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
value：要查找的元素值。
返回值
返回一个迭代器，指向第一个等于 `value` 的元素；如果未找到该元素，则返回 `end`。
2、示例程序
普通类型查找
// 普通类型查找
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
int target = 3;
// 使用 find 查找目标元素
auto it = std::find(numbers.begin(), numbers.end(), target);
// 判断是否找到目标元素
if (it != numbers.end()) {
std::cout << "找到 " << target << "，位置 " << (it - numbers.begin()) << std::endl;
} else {
std::cout << target << " 没找到" << std::endl;
}
return 0;
}
自定义类型查找
// 自定义类型查找
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
Person(std::string name, int age) : name(name), age(age) {}
// 重载 == 运算符用于比较两个 Person 对象
bool operator==(const Person& other) const {
return this->name == other.name && this->age == other.age;
}
std::string getName() const { return name; }
int getAge() const { return age; }
private:
std::string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 定义要查找的目标对象
Person target("王五", 35);
// 使用 find 查找目标 Person 对象
auto it = std::find(people.begin(), people.end(), target);
// 判断是否找到目标对象
if (it != people.end()) {
std::cout << "姓名:" << it->getName() << " 年龄:" << it->getAge() << std::endl;
} else {
std::cout << "没找到" << std::endl;
}
return 0;
}
5.2.2 find_if查找
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
参数
first：查找区间的起始位置，指向容器中第一个元素的位置。
last：查找区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
pred：一元谓词函数或函数对象，对区间内的每个元素应用此条件，返回 true 时即为找到目标。
返回值
返回一个迭代器，指向第一个满足 `pred` 条件的元素；如果未找到则返回 `last`。
2、示例程序
普通类型查找
// 普通类型查找
#include <iostream>
#include <vector>
#include <algorithm>
// 定义一个条件函数，判断元素是否大于 3
bool isGreaterThanThree(int value) {
return value > 3;
}
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 find_if 查找第一个大于 3 的元素
auto it = std::find_if(numbers.begin(), numbers.end(), isGreaterThanThree);
// 判断是否找到目标元素
if (it != numbers.end()) {
std::cout << "找到大于 3 的元素：" << *it << std::endl;
} else {
std::cout << "没有找到大于 3 的元素" << std::endl;
}
return 0;
}
自定义类型查找
// 自定义类型查找
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
Person(std::string name, int age) : name(name), age(age) {}
std::string getName() const { return name; }
int getAge() const { return age; }
private:
std::string name;
int age;
};
// 条件函数，用于查找年龄大于 30 的 Person 对象
bool isOlderThan30(const Person& person) {
return person.getAge() > 30;
}
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 使用 find_if 查找第一个年龄大于 30 的人
auto it = std::find_if(people.begin(), people.end(), isOlderThan30);
// 判断是否找到目标对象
if (it != people.end()) {
std::cout << "找到年龄大于 30 的人：" << it->getName() << "，年龄 " << it->getAge() << std::endl;
} else {
std::cout << "没有找到年龄大于 30 的人" << std::endl;
}
return 0;
}
5.2.3 adjacent_find
用于查找相邻重复的元素
1、函数原型
头文件
#include <algorithm>
函数原型
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
参数
first：查找区间的起始位置，指向容器中第一个元素的位置。
last：查找区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
pred：二元谓词函数，用于判断相邻元素是否满足自定义条件。如果省略该参数，则默认判断相邻元素是否相等。
返回值
返回一个迭代器，指向第一个满足条件的相邻元素的第一个位置；如果未找到则返回 `last`。
2、示例程序
查找相邻相等的元素
// 查找相邻相等的元素
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 定义一个整数向量，其中包含相邻重复的元素
std::vector<int> numbers = {1, 2, 3, 3, 4, 5};
// 使用 adjacent_find 查找相邻相等的元素
auto it = std::adjacent_find(numbers.begin(), numbers.end());
// 判断是否找到相邻相等的元素
if (it != numbers.end()) {
std::cout << "找到相邻相等的元素：" << *it << std::endl;
} else {
std::cout << "没有找到相邻相等的元素" << std::endl;
}
return 0;
}
查找满足自定义条件的相邻元素
// 查找满足自定义条件的相邻元素
#include <iostream>
#include <vector>
#include <algorithm>
// 自定义条件函数，判断相邻元素是否连续递增
bool isConsecutive(int a, int b) {
return b == a + 1;
}
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 5, 6, 7};
// 使用 adjacent_find 查找连续递增的相邻元素
auto it = std::adjacent_find(numbers.begin(), numbers.end(), isConsecutive);
// 判断是否找到符合条件的相邻元素
if (it != numbers.end()) {
std::cout << "找到连续递增的相邻元素：" << *it << " 和 " << *(it + 1) << std::endl;
} else {
std::cout << "没有找到连续递增的相邻元素" << std::endl;
}
return 0;
}
5.2.4 binary_search 二分查找
查找指定元素是否存在
注意: 在 无序的容器中不可用
1、函数原型
头文件
#include <algorithm>
函数原型
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
参数
first：查找区间的起始位置，指向容器中第一个元素的位置。
last：查找区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
value：要查找的目标值。
comp：二元比较函数，用于自定义比较规则（可选）。
返回值
如果找到 `value` 返回 `true`；否则返回 `false`。
注意：`binary_search` 只能用于有序区间，如果区间未排序，结果不可靠。
2、示例程序
普通类型查找
// 普通类型二分查找
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 定义一个已排序的整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
int target = 3;
// 使用 binary_search 查找目标元素是否存在
bool found = std::binary_search(numbers.begin(), numbers.end(), target);
// 输出查找结果
if (found) {
std::cout << "找到元素 " << target << std::endl;
} else {
std::cout << "没有找到元素 " << target << std::endl;
}
return 0;
}
自定义比较规则的查找
// 自定义比较规则的二分查找
#include <iostream>
#include <vector>
#include <algorithm>
struct Person {
std::string name;
int age;
Person(std::string name, int age) : name(name), age(age) {}
};
// 自定义比较规则，按年龄查找
bool compareByAge(const Person& a, const Person& b) {
return a.age < b.age;
}
int main() {
// 定义一个已按年龄排序的 Person 向量
std::vector<Person> people = {
{"张三", 25},
{"李四", 30},
{"王五", 35}
};
Person target("", 30); // 要查找年龄为 30 的对象
// 使用 binary_search 查找是否存在年龄为 30 的 Person 对象
bool found = std::binary_search(people.begin(), people.end(), target, compareByAge);
// 输出查找结果
if (found) {
std::cout << "找到年龄为 " << target.age << " 的人" << std::endl;
} else {
std::cout << "没有找到年龄为 " << target.age << " 的人" << std::endl;
}
return 0;
}
5.2.5 count 计数
统计元素出现次数
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class T>
typename std::iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);
参数
first：计数区间的起始位置，指向容器中第一个元素的位置。
last：计数区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
value：要计数的元素值。
返回值
返回值为 `value` 在指定区间内出现的次数。
2、示例程序
普通类型计数
// 普通类型计数
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
int target = 2;
// 使用 count 计数目标元素的出现次数
int count = std::count(numbers.begin(), numbers.end(), target);
// 输出计数结果
std::cout << "元素 " << target << " 出现了 " << count << " 次" << std::endl;
return 0;
}
自定义类型计数
// 自定义类型计数
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
Person(std::string name, int age) : name(name), age(age) {}
// 获取年龄
int getAge() const { return age; }
// 重载 == 运算符用于比较两个 Person 对象
bool operator==(const Person& other) const {
return this->age == other.age;
}
private:
std::string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 30},
{"赵六", 35},
{"钱七", 30}
};
Person target("", 30); // 要计数的目标对象
// 使用 count 计数年龄为 30 的 Person 对象的出现次数
int count = std::count(people.begin(), people.end(), target);
// 输出计数结果
std::cout << "年龄为 " << target.getAge() << " 的人出现了 " << count << " 次" << std::endl;
return 0;
}
5.2.6 count_if 条件计数
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class UnaryPredicate>
typename std::iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, UnaryPredicate pred);
参数
first：计数区间的起始位置，指向容器中第一个元素的位置。
last：计数区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
pred：一元谓词函数或函数对象，对区间内的每个元素应用此条件，返回 true 时计入计数。
返回值
返回满足 `pred` 条件的元素个数。
2、示例程序
普通类型条件计数
// 普通类型条件计数
#include <iostream>
#include <vector>
#include <algorithm>
// 条件函数，判断元素是否大于 3
bool isGreaterThanThree(int value) {
return value > 3;
}
int main() {
// 定义一个整数向量
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 count_if 统计大于 3 的元素数量
int count = std::count_if(numbers.begin(), numbers.end(), isGreaterThanThree);
// 输出计数结果
std::cout << "大于 3 的元素数量为 " << count << std::endl;
return 0;
}
自定义类型条件计数
// 自定义类型条件计数
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
Person(std::string name, int age) : name(name), age(age) {}
// 获取年龄
int getAge() const { return age; }
private:
std::string name;
int age;
};
// 条件函数，用于统计年龄大于 30 的 Person 对象
bool isOlderThan30(const Person& person) {
return person.getAge() > 30;
}
int main() {
// 定义一个 Person 类型的向量
std::vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35},
{"赵六", 40},
{"钱七", 28}
};
// 使用 count_if 统计年龄大于 30 的人数量
int count = std::count_if(people.begin(), people.end(), isOlderThan30);
// 输出计数结果
std::cout << "年龄大于 30 的人数量为 " << count << std::endl;
return 0;
}
5.3 排序算法
5.3.1 sort 排序
1、函数原型
头文件
#include <algorithm>
函数原型
template <class RandomAccessIterator>
void std::sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void std::sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
参数
first：排序区间的起始位置，指向容器中第一个元素的位置。
last：排序区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
comp：二元比较函数，用于自定义排序规则（可选）。如果省略，则使用默认的 `<` 操作符进行升序排序。
返回值
无返回值，`sort` 函数会直接对指定区间内的元素进行排序。
2、示例程序
普通类型排序（升序和降序）
// 普通类型排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {5, 2, 4, 1, 3};
// 默认升序排序
sort(nums.begin(), nums.end());
cout << "升序排序结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
// 自定义降序排序
sort(nums.begin(), nums.end(), greater<int>());
cout << "降序排序结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型排序
// 自定义类型排序
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
// 按年龄升序排序
bool byAge(const Person& a, const Person& b) {
return a.getAge() < b.getAge();
}
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35},
{"赵六", 20}
};
// 按年龄升序排序
sort(people.begin(), people.end(), byAge);
// 输出排序结果
cout << "按年龄升序排序结果：" << endl;
for (const auto& p : people) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.3.2 random_shuffle 随机打乱
1、函数原型
头文件
#include <algorithm>
函数原型
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& rng);
参数
first：打乱区间的起始位置，指向容器中第一个元素的位置。
last：打乱区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
rng：随机数生成器函数（可选），用于自定义随机顺序。
返回值
无返回值，`random_shuffle` 函数会直接对指定区间内的元素进行随机打乱。
注意：从 C++17 开始，`random_shuffle` 被标记为已废弃，推荐使用 `std::shuffle` 替代。
2、示例程序
普通类型随机打乱
// 普通类型随机打乱
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 4, 5};
// 设置随机数种子
// srand(static_cast<unsigned int>(time(0)));
srand(Time(NULL));
// 使用 random_shuffle 随机打乱元素顺序
random_shuffle(nums.begin(), nums.end());
// 输出打乱后的结果
cout << "打乱后的结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型随机打乱
// 自定义类型随机打乱
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctime>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35},
{"赵六", 20}
};
// 设置随机数种子
// srand(static_cast<unsigned int>(time(0)));
srand((unsigned int)time(NULL));
// 使用 random_shuffle 随机打乱元素顺序
random_shuffle(people.begin(), people.end());
// 输出打乱后的结果
cout << "打乱后的结果：" << endl;
for (const auto& p : people) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
注意：从 C++17 开始，random_shuffle 已被废弃，建议使用 std::shuffle 代替，它更加灵活且安全。
5.3.3 merge 合并排序
两个容器元素合并，并存储到另一容器中
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
参数
first1：第一个已排序区间的起始位置。
last1：第一个已排序区间的结束位置。
first2：第二个已排序区间的起始位置。
last2：第二个已排序区间的结束位置。
result：输出区间的起始位置，用于存储合并后的结果。
comp：二元比较函数，用于自定义排序规则（可选）。如果省略，则使用默认的 `<` 操作符。
返回值
返回一个迭代器，指向合并结果的区间末尾。
注意：`merge` 函数要求两个输入区间都是已排序的，否则结果不保证正确。
2、示例程序
普通类型合并
// 普通类型合并
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义两个已排序的整数向量
vector<int> nums1 = {1, 3, 5, 7};
vector<int> nums2 = {2, 4, 6, 8};
// 定义一个结果向量，大小为两个向量之和
vector<int> result(nums1.size() + nums2.size());
// 使用 merge 合并两个已排序的向量
merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
// 输出合并后的结果
cout << "合并后的结果：";
for (int n : result) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型合并
// 自定义类型合并
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
// 自定义比较规则，按年龄升序排序
bool byAge(const Person& a, const Person& b) {
return a.getAge() < b.getAge();
}
int main() {
// 定义两个已排序的 Person 向量
vector<Person> group1 = {
{"张三", 25},
{"李四", 30}
};
vector<Person> group2 = {
{"王五", 20},
{"赵六", 35}
};
// 定义一个结果向量，大小为两个向量之和
vector<Person> result(group1.size() + group2.size());
// 使用 merge 按年龄合并两个已排序的向量
merge(group1.begin(), group1.end(), group2.begin(), group2.end(), result.begin(), byAge);
// 输出合并后的结果
cout << "按年龄合并后的结果：" << endl;
for (const auto& p : result) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.3.4 reverse 反转
1、函数原型
头文件
#include <algorithm>
函数原型
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
参数
first：反转区间的起始位置，指向容器中第一个元素的位置。
last：反转区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
返回值
无返回值，`reverse` 函数会直接对指定区间内的元素进行原地反转。
2、示例程序
普通类型反转
// 普通类型反转
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 4, 5};
// 使用 reverse 反转向量
reverse(nums.begin(), nums.end());
// 输出反转后的结果
cout << "反转后的结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型反转
// 自定义类型反转
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35},
{"赵六", 20}
};
// 使用 reverse 反转向量
reverse(people.begin(), people.end());
// 输出反转后的结果
cout << "反转后的结果：" << endl;
for (const auto& p : people) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.4 拷贝和替代算法
5.4.1 copy 复制
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
参数
first：复制区间的起始位置，指向容器中第一个元素的位置。
last：复制区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
result：目标区间的起始位置，用于存储复制的结果。
返回值
返回指向目标区间末尾的迭代器。
注意：目标区间的大小必须足够容纳复制的元素，否则会导致未定义行为。
2、示例程序
普通类型复制
// 普通类型复制
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义一个源整数向量
vector<int> src = {1, 2, 3, 4, 5};
// 定义一个目标向量，大小与源向量相同
vector<int> dest(src.size());
// 使用 copy 复制元素
copy(src.begin(), src.end(), dest.begin());
// 输出复制后的结果
cout << "复制后的结果：";
for (int n : dest) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型复制
// 自定义类型复制
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
int main() {
// 定义一个源 Person 类型的向量
vector<Person> src = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 定义一个目标向量，大小与源向量相同
vector<Person> dest(src.size());
// 使用 copy 复制元素
copy(src.begin(), src.end(), dest.begin());
// 输出复制后的结果
cout << "复制后的结果：" << endl;
for (const auto& p : dest) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.4.2 replace 替换
将容器内指定范围的旧元素修改为新元素
1、函数原型
头文件
#include <algorithm>
函数原型
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
参数
first：替换区间的起始位置，指向容器中第一个元素的位置。
last：替换区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
old_value：要被替换的目标值。
new_value：用于替换的值。
返回值
无返回值，`replace` 函数会直接对指定区间内的元素进行替换操作。
2、示例程序
普通类型替换
// 普通类型替换
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
// 使用 replace 将所有值为 2 的元素替换为 9
replace(nums.begin(), nums.end(), 2, 9);
// 输出替换后的结果
cout << "替换后的结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型替换
// 自定义类型替换
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
// 重载 == 运算符用于判断两个 Person 对象是否相等
bool operator==(const Person& other) const {
return this->age == other.age; // 仅根据年龄判断相等
}
private:
string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 30},
{"赵六", 35}
};
// 使用 replace 将所有年龄为 30 的 Person 替换为新的 Person 对象
replace(people.begin(), people.end(), Person("", 30), Person("新名字", 20));
// 输出替换后的结果
cout << "替换后的结果：" << endl;
for (const auto& p : people) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.4.3 replace_if 条件替换
1、函数原型
头文件
#include <algorithm>
函数原型
template <class ForwardIterator, class UnaryPredicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, UnaryPredicate pred, const T& new_value);
参数
first：替换区间的起始位置，指向容器中第一个元素的位置。
last：替换区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
pred：一元谓词函数或函数对象，对区间内的每个元素应用此条件，返回 true 时将该元素替换。
new_value：用于替换满足条件的元素的新值。
返回值
无返回值，`replace_if` 函数会直接对指定区间内满足条件的元素进行替换操作。
2、示例程序
普通类型条件替换
// 普通类型条件替换
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 条件函数，判断元素是否大于 3
bool isGreaterThanThree(int value) {
return value > 3;
}
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 4, 5};
// 使用 replace_if 将所有大于 3 的元素替换为 0
replace_if(nums.begin(), nums.end(), isGreaterThanThree, 0);
// 输出替换后的结果
cout << "替换后的结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型条件替换
// 自定义类型条件替换
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
private:
string name;
int age;
};
// 条件函数，用于判断是否年龄大于 30
bool isOlderThan30(const Person& person) {
return person.getAge() > 30;
}
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35},
{"赵六", 40}
};
// 使用 replace_if 将年龄大于 30 的 Person 替换为新对象
replace_if(people.begin(), people.end(), isOlderThan30, Person("新名字", 20));
// 输出替换后的结果
cout << "替换后的结果：" << endl;
for (const auto& p : people) {
cout << "名字: " << p.getName() << ", 年龄: " << p.getAge() << endl;
}
return 0;
}
5.4.4 swap 交换
1、函数原型
头文件
#include <algorithm>
函数原型
template <class T>
void swap(T& a, T& b);
参数
a：第一个交换的对象。
b：第二个交换的对象。
返回值
无返回值，`swap` 函数会直接交换 `a` 和 `b` 的值。
说明
`swap` 是一种简单的交换操作，用于交换两个相同类型的变量内容。
2、示例程序
普通类型交换
// 普通类型交换
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a = 10;
int b = 20;
// 使用 swap 交换 a 和 b 的值
swap(a, b);
// 输出交换后的结果
cout << "交换后的 a: " << a << ", b: " << b << endl;
return 0;
}
自定义类型交换
// 自定义类型交换
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
void print() const {
cout << "名字: " << name << ", 年龄: " << age << endl;
}
private:
string name;
int age;
};
int main() {
// 定义两个 Person 对象
Person person1("张三", 30);
Person person2("李四", 25);
// 输出交换前的结果
cout << "交换前：" << endl;
person1.print();
person2.print();
// 使用 swap 交换两个 Person 对象
swap(person1, person2);
// 输出交换后的结果
cout << "交换后：" << endl;
person1.print();
person2.print();
return 0;
}
5.5 算数生成算法
5.5.1 accumulate 累加
1、函数原型
头文件
#include <numeric>
函数原型
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation op);
参数
first：累加区间的起始位置，指向容器中第一个元素的位置。
last：累加区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
init：累加的初始值。
op：二元操作函数，用于指定累加的方式（可选）。若省略，则默认为加法操作。
返回值
返回累加的最终结果。
2、示例程序
普通类型累加
// 普通类型累加
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 4, 5};
// 使用 accumulate 计算所有元素的和，初始值为 0
int sum = accumulate(nums.begin(), nums.end(), 0);
// 输出累加结果
cout << "所有元素的和为：" << sum << endl;
return 0;
}
自定义累加操作（乘积）
// 自定义累加操作
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
// 定义一个整数向量
vector<int> nums = {1, 2, 3, 4, 5};
// 使用 accumulate 计算所有元素的乘积，初始值为 1
int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());
// 输出累加（乘积）结果
cout << "所有元素的乘积为：" << product << endl;
return 0;
}
自定义类型累加
// 自定义类型累加
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
int getAge() const { return age; }
private:
string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量
vector<Person> people = {
{"张三", 30},
{"李四", 25},
{"王五", 35}
};
// 使用 accumulate 计算所有人的年龄总和，初始值为 0
int total_age = accumulate(people.begin(), people.end(), 0,
[](int sum, const Person& person) {
return sum + person.getAge();
});
// 输出累加（年龄总和）结果
cout << "所有人的年龄总和为：" << total_age << endl;
return 0;
}
5.5.2 fill 填充
1、函数原型
头文件
#include <algorithm>
函数原型
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
参数
first：填充区间的起始位置，指向容器中第一个元素的位置。
last：填充区间的结束位置，指向容器中最后一个元素的下一个位置（不包含该位置）。
value：用于填充的值，将被赋值给区间内的每个元素。
返回值
无返回值，`fill` 函数会直接对指定区间内的元素进行填充操作。
2、示例程序
普通类型填充
// 普通类型填充
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义一个整数向量并分配大小
vector<int> nums(5);
// 使用 fill 将所有元素填充为 9
fill(nums.begin(), nums.end(), 9);
// 输出填充后的结果
cout << "填充后的结果：";
for (int n : nums) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型填充
// 自定义类型填充
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name = "未知", int age = 0) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
void print() const {
cout << "名字: " << name << ", 年龄: " << age << endl;
}
private:
string name;
int age;
};
int main() {
// 定义一个 Person 类型的向量并分配大小
vector<Person> people(3);
// 使用 fill 将所有元素填充为指定的 Person 对象
fill(people.begin(), people.end(), Person("张三", 30));
// 输出填充后的结果
cout << "填充后的结果：" << endl;
for (const auto& p : people) {
p.print();
}
return 0;
}
5.6 常用集合算法
5.6.1 set_intersection 集合交集
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
参数
first1、last1：第一个已排序区间的起始和结束位置。
first2、last2：第二个已排序区间的起始和结束位置。
result：输出区间的起始位置，用于存储交集结果。
comp：二元比较函数，用于自定义排序规则（可选）。如果省略，则使用默认的 `<` 操作符。
返回值
返回一个迭代器，指向交集结果的区间末尾。
注意：`set_intersection` 要求两个输入区间都是已排序的，否则结果不保证正确。
2、示例程序
普通类型集合交集
// 普通类型集合交集
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义两个已排序的整数向量
vector<int> nums1 = {1, 2, 3, 4, 5};
vector<int> nums2 = {3, 4, 5, 6, 7};
// 定义一个结果向量，用于存储交集结果
vector<int> result(min(nums1.size(), nums2.size()));
// 使用 set_intersection 计算交集
auto it = set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
// 调整结果向量的大小以适应实际交集元素数量
result.resize(it - result.begin());
// 输出交集结果
cout << "交集结果：";
for (int n : result) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型集合交集
// 自定义类型集合交集
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
// 重载 < 运算符，用于 set_intersection 按年龄排序
bool operator<(const Person& other) const {
return age < other.age;
}
void print() const {
cout << "名字: " << name << ", 年龄: " << age << endl;
}
private:
string name;
int age;
};
int main() {
// 定义两个已排序的 Person 类型向量
vector<Person> group1 = {
{"张三", 25},
{"李四", 30},
{"王五", 35}
};
vector<Person> group2 = {
{"赵六", 30},
{"钱七", 35},
{"孙八", 40}
};
// 定义一个结果向量，用于存储交集结果
vector<Person> result(min(group1.size(), group2.size()));
// 使用 set_intersection 计算交集
auto it = set_intersection(group1.begin(), group1.end(), group2.begin(), group2.end(), result.begin());
// 调整结果向量的大小以适应实际交集元素数量
result.resize(it - result.begin());
// 输出交集结果
cout << "交集结果：" << endl;
for (const auto& p : result) {
p.print();
}
return 0;
}
5.6.2 set_union 集合并集
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
参数
first1、last1：第一个已排序区间的起始和结束位置。
first2、last2：第二个已排序区间的起始和结束位置。
result：输出区间的起始位置，用于存储并集结果。
comp：二元比较函数，用于自定义排序规则（可选）。如果省略，则使用默认的 `<` 操作符。
返回值
返回一个迭代器，指向并集结果的区间末尾。
注意：`set_union` 要求两个输入区间都是已排序的，否则结果不保证正确。
2、示例程序
普通类型集合并集
// 普通类型集合并集
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义两个已排序的整数向量
vector<int> nums1 = {1, 2, 3, 4, 5};
vector<int> nums2 = {4, 5, 6, 7, 8};
// 定义一个结果向量，大小为两个向量之和，用于存储并集结果
vector<int> result(nums1.size() + nums2.size());
// 使用 set_union 计算并集
auto it = set_union(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
// 调整结果向量的大小以适应实际并集元素数量
result.resize(it - result.begin());
// 输出并集结果
cout << "并集结果：";
for (int n : result) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型集合并集
// 自定义类型集合并集
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
// 重载 < 运算符，用于 set_union 按年龄排序
bool operator<(const Person& other) const {
return age < other.age;
}
void print() const {
cout << "名字: " << name << ", 年龄: " << age << endl;
}
private:
string name;
int age;
};
int main() {
// 定义两个已排序的 Person 类型向量
vector<Person> group1 = {
{"张三", 25},
{"李四", 30},
{"王五", 35}
};
vector<Person> group2 = {
{"赵六", 30},
{"钱七", 35},
{"孙八", 40}
};
// 定义一个结果向量，大小为两个向量之和，用于存储并集结果
vector<Person> result(group1.size() + group2.size());
// 使用 set_union 计算并集
auto it = set_union(group1.begin(), group1.end(), group2.begin(), group2.end(), result.begin());
// 调整结果向量的大小以适应实际并集元素数量
result.resize(it - result.begin());
// 输出并集结果
cout << "并集结果：" << endl;
for (const auto& p : result) {
p.print();
}
return 0;
}
5.6.3 set_difference 集合差集
1、函数原型
头文件
#include <algorithm>
函数原型
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
参数
first1、last1：第一个已排序区间的起始和结束位置。
first2、last2：第二个已排序区间的起始和结束位置。
result：输出区间的起始位置，用于存储差集结果。
comp：二元比较函数，用于自定义排序规则（可选）。如果省略，则使用默认的 `<` 操作符。
返回值
返回一个迭代器，指向差集结果的区间末尾。
注意：`set_difference` 要求两个输入区间都是已排序的，否则结果不保证正确。
2、示例程序
普通类型集合差集
// 普通类型集合差集
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 定义两个已排序的整数向量
vector<int> nums1 = {1, 2, 3, 4, 5};
vector<int> nums2 = {4, 5, 6, 7, 8};
// 定义一个结果向量，用于存储差集结果
vector<int> result(nums1.size());
// 使用 set_difference 计算差集 (nums1 - nums2)
auto it = set_difference(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
// 调整结果向量的大小以适应实际差集元素数量
result.resize(it - result.begin());
// 输出差集结果
cout << "差集结果 (nums1 - nums2)：";
for (int n : result) {
cout << n << " ";
}
cout << endl;
return 0;
}
自定义类型集合差集
// 自定义类型集合差集
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age) : name(name), age(age) {}
string getName() const { return name; }
int getAge() const { return age; }
// 重载 < 运算符，用于 set_difference 按年龄排序
bool operator<(const Person& other) const {
return age < other.age;
}
void print() const {
cout << "名字: " << name << ", 年龄: " << age << endl;
}
private:
string name;
int age;
};
int main() {
// 定义两个已排序的 Person 类型向量
vector<Person> group1 = {
{"张三", 25},
{"李四", 30},
{"王五", 35}
};
vector<Person> group2 = {
{"赵六", 30},
{"钱七", 35},
{"孙八", 40}
};
// 定义一个结果向量，用于存储差集结果
vector<Person> result(group1.size());
// 使用 set_difference 计算差集 (group1 - group2)
auto it = set_difference(group1.begin(), group1.end(), group2.begin(), group2.end(), result.begin());
// 调整结果向量的大小以适应实际差集元素数量
result.resize(it - result.begin());
// 输出差集结果
cout << "差集结果 (group1 - group2)：" << endl;
for (const auto& p : result) {
p.print();
}
return 0;
}
第六章 C++练习项目
管理系统 + <网络>
参考
智能家居管理系统 UDP 协议
增加用户
删除用户
用户登陆
增加设备 ： 为系统加入设备
删除设备 ： 让设备离线 不能控制
修改设备状态 ： 给设备发信息 <开灯 关灯>
查找设备 ： 给设备发信息 设备端 <发出提示音>
控制状态： 灯 <开灯> <关灯> 空调<制冷> ...
查看状态： 冰箱<正常> <这个莴笋搜了> <这个土豆丝酸了> 在线 离线
选用vector容器 或者 list 容器
- 感谢你赐予我前进的力量
-
微信 
支付宝
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 小道士
