1. C++ string类基础概念与初始化
在算法竞赛和日常C++开发中，string类是最常用的字符串处理工具之一。相较于传统的C风格字符数组，string提供了更安全、更便捷的操作方式。我们先从最基础的创建和初始化开始讲起。
1.1 string类的头文件与基本特性
使用string类首先需要包含<string>头文件。这个头文件定义了string类及其相关操作。值得注意的是，<string>与C语言的<string.h>是不同的头文件，前者是C++的string类，后者是C风格的字符串处理函数。
cpp复制#include <string>
string类有几个重要特性：
- 自动管理内存：无需手动分配和释放内存
- 动态大小：可以根据内容自动调整存储空间
- 丰富的成员函数：提供了各种字符串操作功能
- 安全性：相比字符数组更不容易出现缓冲区溢出等问题
1.2 字符串的多种初始化方式
string对象有多种初始化方式，每种方式在不同场景下各有优势：
cpp复制// 空字符串
string s1;
// 用字符串字面量初始化
string s2 = "hello world";
// 构造函数初始化
string s3("hello world");
// 用另一个string对象初始化
string s4 = s2;
// 用部分字符初始化
string s5(s2, 0, 5); // 从s2的第0个字符开始，取5个字符
// 用重复字符初始化
string s6(10, 'a'); // 10个'a'组成的字符串
在算法竞赛中，最常用的是前三种初始化方式。特别是空字符串初始化后通过输入填充的方式，在解决需要处理多组输入的题目时非常实用。
注意：虽然string可以直接用=赋值，但在性能敏感的场景（如循环中大量赋值）建议使用assign()成员函数，它提供了更多选项且有时更高效。
1.3 string与C风格字符串的区别
虽然string可以像C风格字符串一样使用，但两者有本质区别：
-
内存管理：
- C风格字符串需要手动管理内存
- string自动管理内存，减少内存泄漏风险
-
安全性：
- C风格字符串容易发生缓冲区溢出
- string会自动调整大小，防止溢出
-
操作便捷性：
- C风格字符串需要strcpy等函数操作
- string支持直接赋值、比较等操作
-
性能：
- C风格字符串在某些操作上可能更快
- string在频繁修改时可能涉及内存重分配
在算法竞赛中，除非题目特别要求，否则建议优先使用string，它能减少很多低级错误，让选手更专注于算法本身。
2. string的输入输出操作
2.1 基本输入输出方法
2.1.1 使用cin进行输入
最基础的输入方式是使用cin，但这种方式有一个明显的限制：
cpp复制string s;
cin >> s; // 遇到空格、制表符、换行符会停止读取
这种输入方式在遇到空白字符时会停止读取，因此不适合需要读取整行内容的场景。在算法竞赛中，很多题目需要读取包含空格的字符串，这时就需要更强大的输入方法。
2.1.2 使用getline读取整行
getline函数是读取整行文本的利器，它有两种形式：
- 默认以换行符结束：
cpp复制string line;
getline(cin, line); // 读取直到遇到换行符
- 自定义结束符：
cpp复制string part;
getline(cin, part, ';'); // 读取直到遇到分号
在算法竞赛中，第一种形式更为常用，特别是在处理需要读取多行输入的题目时。
实用技巧：在混合使用cin和getline时，要注意cin可能会在缓冲区留下换行符，导致随后的getline立即返回空字符串。解决方法是在cin后使用cin.ignore()清除缓冲区。
2.2 输入性能优化
在算法竞赛中，输入输出的效率有时会成为瓶颈。对于大规模数据输入，可以考虑以下优化方法：
- 关闭同步：
cpp复制ios::sync_with_stdio(false);
cin.tie(nullptr);
这可以显著提高C++流的IO速度，但代价是不能与C标准IO函数混用。
- 预先分配空间：
cpp复制string s;
s.reserve(1000000); // 预先分配足够空间，避免频繁重分配
- 批量读取：
对于极大输入，可以考虑一次性读取整个输入：
cpp复制string input;
input.assign(istreambuf_iterator<char>(cin),
istreambuf_iterator<char>());
2.3 字符串的输出
string对象的输出非常简单：
cpp复制string s = "Hello";
cout << s << endl;
在算法竞赛中，输出通常不需要特别优化，但要注意：
- 避免频繁使用endl，它会导致缓冲区刷新，可以用'\n'代替
- 对于大量输出，可以考虑先构建完整字符串再一次性输出
3. string的常用操作与成员函数
3.1 访问字符串内容
string提供了多种访问字符的方式：
- 使用[]运算符：
cpp复制char c = s[0]; // 不检查越界
- 使用at()成员函数：
cpp复制char c = s.at(0); // 会检查越界，越界时抛出异常
- 使用迭代器：
cpp复制for(auto it = s.begin(); it != s.end(); ++it) {
char c = *it;
}
在算法竞赛中，[]运算符最为常用，因为它简洁且效率高。但要注意它不进行边界检查，使用时需确保索引有效。
3.2 获取字符串信息
- 获取长度：
cpp复制int len = s.size(); // 或 s.length()
- 检查是否为空：
cpp复制if(s.empty()) { ... }
- 获取容量：
cpp复制int cap = s.capacity();
在算法竞赛中，size()是最常用的函数之一，很多题目需要根据字符串长度进行不同处理。
3.3 字符串修改操作
3.3.1 追加内容
cpp复制s += " world"; // 追加字符串
s.push_back('!'); // 追加单个字符
s.append(" hello"); // 追加字符串
3.3.2 插入和删除
cpp复制s.insert(5, "inserted"); // 在位置5插入
s.erase(5, 3); // 从位置5开始删除3个字符
s.clear(); // 清空字符串
3.3.3 替换内容
cpp复制s.replace(6, 5, "there"); // 从位置6开始替换5个字符
在算法竞赛中，这些操作常用于字符串变换类题目。需要注意的是，频繁的插入和删除操作可能导致性能问题，特别是在循环中使用时。
3.4 字符串查找与比较
3.4.1 查找子串
cpp复制size_t pos = s.find("world"); // 返回首次出现的位置
pos = s.rfind("world"); // 从后向前查找
pos = s.find_first_of("aeiou"); // 查找任意匹配字符
pos = s.find_last_not_of(" \t\n"); // 查找最后一个不匹配字符
3.4.2 字符串比较
cpp复制if(s1 == s2) { ... } // 内容相等比较
if(s1.compare(s2) == 0) { ... } // 同样比较内容
if(s1.compare(0, 5, s2, 0, 5) == 0) { ... } // 比较部分内容
在算法竞赛中，find()系列函数非常实用，特别是在处理字符串匹配、模式识别类题目时。
4. string在算法竞赛中的高级应用
4.1 字符串与数值转换
算法竞赛中经常需要在字符串和数值之间转换：
cpp复制// 字符串转数值
int i = stoi("42");
double d = stod("3.14");
// 数值转字符串
string s1 = to_string(123);
string s2 = to_string(3.14159);
注意：stoi等函数会忽略前导空白符，遇到非数字字符停止转换。如果转换失败会抛出异常，在竞赛中可以使用try-catch处理，但更常见的做法是确保输入格式正确。
4.2 字符串分割
标准库没有直接提供字符串分割功能，但可以结合find和substr实现：
cpp复制vector<string> split(const string &s, char delim) {
vector<string> tokens;
size_t start = 0, end = 0;
while((end = s.find(delim, start)) != string::npos) {
tokens.push_back(s.substr(start, end - start));
start = end + 1;
}
tokens.push_back(s.substr(start));
return tokens;
}
这个函数在解析输入数据时非常有用，特别是在处理以空格或逗号分隔的输入时。
4.3 字符串匹配算法
虽然string的find()函数已经足够应付多数情况，但在某些高性能要求的场景下，了解专门的字符串匹配算法很有帮助：
- KMP算法：处理有重复模式的字符串匹配
- Boyer-Moore算法：适合长模式串的快速匹配
- Rabin-Karp算法：基于哈希的匹配方法
在算法竞赛中，这些算法偶尔会出现在专门的字符串处理题目中，值得掌握其基本原理。
4.4 性能优化技巧
- 预分配空间：
cpp复制string s;
s.reserve(1000); // 预先分配足够空间
- 避免不必要的拷贝：
cpp复制void process(const string &s); // 使用引用避免拷贝
- 使用移动语义：
cpp复制string process() {
string result;
// ... 处理result
return result; // 编译器通常会优化为移动操作
}
- 谨慎使用+=：
在循环中使用+=拼接字符串可能导致多次重分配，更好的方式是先计算总长度，预分配空间后再拼接。
5. 常见问题与解决方案
5.1 内存相关问题
-
问题：string对象占用内存过大
- 解决方案：使用shrink_to_fit()释放多余内存
cpp复制s.shrink_to_fit(); -
问题：频繁修改导致内存重分配
- 解决方案：预先调用reserve()分配足够空间
5.2 性能瓶颈
-
问题：大量字符串拼接操作缓慢
- 解决方案：使用ostringstream代替多次拼接
cpp复制ostringstream oss; oss << "part1" << "part2" << "part3"; string result = oss.str(); -
问题：频繁的子串操作
- 解决方案：考虑使用string_view(C++17)避免拷贝
5.3 编码问题
-
问题：处理多字节字符(如UTF-8)时长度计算错误
- 解决方案：使用专门的库如ICU，或确保题目输入为ASCII
-
问题：大小写转换不完整
- 解决方案：使用locale-aware转换或第三方库
cpp复制#include <algorithm> #include <locale> string s = "Hello"; locale loc; transform(s.begin(), s.end(), s.begin(), [&loc](char c){ return toupper(c, loc); });
5.4 算法竞赛中的特殊技巧
- 快速清空字符串：
cpp复制s.clear();
s.shrink_to_fit(); // 如果需要释放内存
- 快速交换内容：
cpp复制string s1, s2;
s1.swap(s2); // 高效交换内容
- 使用字符串作为缓冲区：
cpp复制string buffer;
buffer.resize(1024);
cin.read(&buffer[0], buffer.size()); // 直接读取到string中
- 快速判断回文：
cpp复制bool is_palindrome = equal(s.begin(), s.begin() + s.size()/2, s.rbegin());
在算法竞赛中，掌握这些技巧可以节省宝贵的时间，特别是在时间限制严格的比赛中。