1. 核心概念与存储模型#
1.1 基本定义#
#include <string>
std::string s;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
string s;cppstring 实际上是:
std::basic_string<char>cpp核心特征:
- 保存一串
char,长度可以动态变化。 - 支持下标随机访问,
s[i]为O(1)。 - 从 C++11 起,普通
string的字符连续存储。 - 自动记录长度,
size()不需要像strlen()一样重新扫描。 - 提供
c_str(),可转换为以'\0'结尾的 C 风格字符串指针。
1.2 size、length 与 capacity#
cout << s.size(); // 字符个数
cout << s.length(); // 与 size() 完全相同
cout << s.capacity(); // 当前已分配容量
cout << s.empty(); // 是否为空cpp- 有效字符下标为
[0, size())。 size()不计算末尾用于 C 接口的终止符'\0'。capacity()也不把额外终止符计入字符容量。string可以保存内嵌的'\0',因此size()与strlen(s.c_str())不一定相等。
string s("a\0b", 3);
cout << s.size() << endl; // 3
cout << strlen(s.c_str()) << endl; // 1:遇到第一个 '\0' 就停止cpp1.3 c_str() 与 data()#
const char *p = s.c_str();
printf("%s\n", s.c_str());cpp注意:
c_str()返回的指针由string管理,不要手动delete/free。- C 风格函数通常遇到第一个
'\0'就停止,不能正确处理内嵌空字符。 - 字符串扩容、修改或销毁后,旧指针可能失效,应重新调用
c_str()。 - C++17 起非 const
data()可返回可修改字符的指针,但仍不能越界写入或破坏终止符。
1.4 小字符串优化 SSO#
很多实现会采用 SSO(Small String Optimization):短字符串直接存在 string 对象内部,避免动态内存分配。SSO 的容量阈值和行为由实现决定,标准不保证,竞赛代码不要依赖具体阈值。
2. 创建与初始化#
string a; // 空字符串
string b = "abc"; // 由字符串字面量构造
string c("abc"); // 同上
string d(5, 'x'); // "xxxxx"
string e(b); // 拷贝
string f(b, 1, 2); // 从下标 1 开始复制最多 2 个字符,得到 "bc"
string g(b.begin(), b.end()); // 由迭代器区间构造
string h = d + b; // "xxxxxabc"cpp重复字符:
string line(80, '-');
string zeros(n, '0');cpp原始字符串字面量,适合包含大量反斜杠或换行的文本:
string path = R"(C:\new_folder\test)";cpp字符串字面量后缀:
using namespace std::string_literals;
string s = "abc"s; // C++14,明确构造 std::stringcpp3. 输入输出#
3.1 cin >> s:读取一个非空白单词#
string s;
cin >> s;cpp- 自动跳过前导空白。
- 遇到空格、制表符、换行就停止。
- 输入
hello world时,只读入hello。
循环读取单词直到 EOF:
string s;
while (cin >> s) {
// 处理 s
}cpp3.2 getline:读取整行#
string s;
getline(cin, s);cpp- 保留空格。
- 丢弃行末换行符。
- 空行会读成空字符串。
- 可指定分隔符:
getline(cin, s, ','),但分隔符不会保留在结果中。
循环读取每一行:
string line;
while (getline(cin, line)) {
// 处理一整行
}cpp3.3 cin >> 后接 getline 的高频问题#
int n;
cin >> n;
// getline(cin, s); // 可能直接读到 n 后面的换行,得到空字符串cpp处理方法:
int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
string s;
getline(cin, s);cpp如果知道下一行就是要读取的内容,也可先用一个临时 getline 吃掉行尾,但 ignore 的意图更明确。
3.4 行末可能的 \r#
某些跨平台测试数据使用 CRLF 行尾,getline 去掉 '\n' 后可能留下 '\r'。必要时:
if (!s.empty() && s.back() == '\r') s.pop_back();cpp3.5 输出与加速#
cout << s << '\n';
ios::sync_with_stdio(false);
cin.tie(nullptr);cppcout << s 按 string 保存的完整长度输出,不依赖 C 字符串终止符。大规模输出优先 '\n',不要频繁使用会刷新缓冲区的 endl。
4. 字符访问与遍历#
4.1 下标访问#
s[i] = 'A';
char c = s[i];cpps[i]不检查越界,越界是未定义行为。s.at(i)检查越界,越界抛出std::out_of_range。- 首尾字符:
char a = s.front();
char b = s.back();cpp空字符串上调用 front()、back() 是未定义行为。
4.2 下标遍历#
for (int i = 0; i < (int)s.size(); ++i) {
cout << s[i];
}cpp反向遍历:
for (int i = (int)s.size() - 1; i >= 0; --i) {
cout << s[i];
}cpp4.3 范围 for#
只读:
for (char c : s) {
cout << c;
}cpp修改:
for (char &c : s) {
if (c >= 'a' && c <= 'z') c = c - 'a' + 'A';
}cppfor (char c : s) 中修改 c 只修改副本,不影响原字符串。
4.4 迭代器#
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it;
}
for (auto it = s.rbegin(); it != s.rend(); ++it) {
cout << *it;
}cppstring 的迭代器支持随机访问,但算法竞赛中大多直接下标遍历,更简洁。
5. 长度、容量与大小调整#
5.1 reserve#
string s;
s.reserve(1000000);cpp只预留容量,不改变 size()。适合已知答案长度、需要大量拼接时减少扩容。
5.2 resize#
s.resize(n); // 扩大时新增 '\0' 字符
s.resize(n, '0'); // 扩大时新增 '0'cpp- 扩大:新增字符。
- 缩小:删除尾部字符。
- 改变长度后,新长度内的字符可以通过下标访问。
5.3 clear 与 shrink_to_fit#
s.clear(); // 变为空串,容量通常保留
s.shrink_to_fit(); // 请求缩容,不保证执行cppclear() 后 size()==0,但不代表释放了全部内存。
6. 拼接与尾部修改#
6.1 += 与 append#
string s = "abc";
s += 'd'; // "abcd"
s += "ef"; // "abcdef"
s += string("gh");
s.append("ijk");
s.append(3, 'x'); // 追加 "xxx"cpp已知最终结果规模时:
string ans;
ans.reserve(n);
for (int i = 0; i < n; ++i) ans += 'a';cpp尾部追加单个字符通常为均摊 O(1),但扩容时会搬移原字符。
6.2 operator+#
string a = "hello";
string b = "world";
string c = a + " " + b;
string d = 'X' + a; // 有相应重载
string e = a + '!';cpp+ 会生成新字符串,需要复制相关字符。循环中构造大型结果时通常优先复用一个对象并 +=,避免反复创建完整副本。
// 通常推荐
string ans;
for (...) ans += piece;
// 谨慎使用:可能反复分配并复制
// ans = ans + piece;cpp6.3 字符串字面量不能直接相加#
// auto s = "abc" + "def"; // 错误:两个都是 const char 数组/指针语义
string s = string("abc") + "def"; // 正确cpp6.4 单字符栈式操作#
s.push_back('a');
char c = s.back();
s.pop_back();cpp空字符串上调用 pop_back() 是未定义行为。括号匹配、表达式模拟等场景常把 string 当作字符栈。
7. 插入、删除、替换与交换#
7.1 插入#
s.insert(0, "abc"); // 在下标 0 前插入
s.insert(2, 3, 'x'); // 在下标 2 前插入 3 个 'x'
s.insert(s.begin(), 'A');cpp7.2 删除#
s.erase(pos); // 删除 pos 到末尾
s.erase(pos, len); // 删除 [pos, pos+len),超出末尾的部分自动截断
s.clear(); // 全部删除cpp删除一个字符:
s.erase(s.begin() + i);
// 或 s.erase(i, 1);cpp7.3 替换#
s.replace(pos, len, "abc"); // 删除原区间,再放入 "abc"cpp7.4 交换#
a.swap(b);cpp通常为 O(1),不会逐字符复制。
7.5 复杂度提醒#
string 是连续字符序列,中间插入、删除和替换通常需要移动后方字符,单次可能为 O(n)。循环中反复在中间操作,总复杂度可能达到 O(n^2)。
8. 子串:substr#
string t = s.substr(pos); // 从 pos 到末尾
string u = s.substr(pos, len); // 从 pos 开始,最多 len 个字符cpp规则:
- 返回一个新的 string,会发生字符复制,复杂度通常为
O(len)。 pos > s.size()会抛出std::out_of_range。pos == s.size()返回空串。len超过剩余长度时自动截取到末尾。string::npos常作为 len,表示直到末尾。
string s = "abcdef";
cout << s.substr(2, 3); // "cde"
cout << s.substr(4); // "ef"cpp在循环中大量 substr 会产生复制成本;若只读子串,C++17 优先考虑 string_view。
9. 查找:find 家族#
9.1 正向查找#
size_t p = s.find("abc"); // 从下标 0 开始
size_t q = s.find("abc", pos); // 从 pos 开始
size_t r = s.find('a'); // 查找字符cpp返回值:
- 找到:返回匹配起始下标。
- 找不到:返回
string::npos。
if (s.find("abc") == string::npos) {
// 不存在
}cpp不要依赖 npos 的具体数值;始终用 == string::npos 判断。
查找全部出现位置:
for (size_t p = s.find(t); p != string::npos; p = s.find(t, p + 1)) {
cout << p << '\n';
}cpp此写法从 p+1 继续,因此能找到重叠匹配。例如 s="aaaa"、t="aa" 会得到 0、1、2。
9.2 反向查找#
size_t p = s.rfind("abc");
size_t q = s.rfind('a');cpprfind(str, pos) 查找起始位置不超过 pos 的最后一次匹配。
9.3 字符集合查找#
s.find_first_of("aeiou"); // 第一个属于集合的字符
s.find_last_of("aeiou"); // 最后一个属于集合的字符
s.find_first_not_of(" \t"); // 第一个不属于集合的字符
s.find_last_not_of(" \t");cpp第二个参数可以指定起始位置,例如 s.find_first_of("0123456789", pos)。
9.4 复杂度与字符串匹配#
find 的接口不等于 KMP,不要默认它提供严格线性时间保证。竞赛中若需要在最坏情况下高效查找大量模式,应显式使用 KMP、Z 函数、字符串哈希等算法。
10. 字符串比较与字典序#
a == b;
a != b;
a < b;
a <= b;
a > b;
a >= b;cpp比较规则是按字符序列进行字典序比较:
- 从前往后找到第一对不同的字符,字符编码较小者对应字符串较小。
- 若公共前缀完全相同,较短字符串较小。
- 比较区分大小写。
"abc" < "abd" // 第三字符不同
"abc" < "abcd" // 前者是后者的前缀
"Apple" < "apple" // 按常见 ASCII 编码成立,但不能把它当作忽略大小写比较cpp更细粒度的接口:
int x = a.compare(b);
int y = a.compare(pos, len, b);cpp返回值为负、零、正,分别表示小于、等于、大于。竞赛通常直接使用关系运算符。
自定义排序:
sort(words.begin(), words.end(), [](const string &a, const string &b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
});cpp该比较器先按长度,再按字典序,满足严格弱序,可用于 sort。
11. string 与数值转换#
11.1 数值转字符串#
int x = 123;
long long y = 1234567890123LL;
string a = to_string(x);
string b = to_string(y);cppto_string 不适合需要严格格式、指定浮点精度等场景;此时可用 snprintf、ostringstream 或格式化输出工具。
11.2 字符串转数值#
int x = stoi(s);
long long y = stoll(s);
double d = stod(s);cpp常用函数:
| 函数 | 目标类型 |
|---|---|
stoi |
int |
stol |
long |
stoll |
long long |
stoul / stoull |
无符号整数 |
stof / stod / stold |
浮点数 |
注意:
- 无有效数字时抛出
std::invalid_argument。 - 超出目标类型范围时抛出
std::out_of_range。 - 会接受允许的前导空白和符号。
- 默认可以只解析合法前缀,例如
stoi("123abc")返回 123。
要求整串都被消费时:
size_t used = 0;
long long x = stoll(s, &used);
if (used != s.size()) {
// 后面还有未解析字符
}cpp11.3 C++17 from_chars:严格、快速的整数解析#
#include <charconv>
long long x;
auto [ptr, ec] = from_chars(s.data(), s.data() + s.size(), x);
if (ec != errc() || ptr != s.data() + s.size()) {
// 格式错误、越界,或存在未消费字符
}cpp特点:不抛异常、不自动跳过空白、不分配内存,适合严格解析和高性能场景。竞赛环境需支持 C++17 的 <charconv>。
12. 与 <algorithm>、字符函数配合#
12.1 排序、反转、统计#
sort(s.begin(), s.end()); // 按字符编码排序
reverse(s.begin(), s.end()); // 反转
int c = count(s.begin(), s.end(), 'a');cpp排序字符可改变原串顺序;需要保留原串时先复制。
12.2 去重#
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());cpp与 vector 一样,unique 只处理相邻重复元素,必须配合 erase 才真正缩短字符串。
12.3 大小写转换#
只处理 ASCII 时,竞赛中手写规则最明确:
for (char &c : s) {
if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';
}cpp使用 <cctype>:
char lower = (char)tolower((unsigned char)c);
bool digit = isdigit((unsigned char)c);
bool alpha = isalpha((unsigned char)c);
bool space = isspace((unsigned char)c);cpp必须先转为 unsigned char:若 char 为 signed 且值为负,直接把负值传给这些函数会产生未定义行为(EOF 除外)。tolower 等函数返回 int,存回字符时再转为 char。
12.4 字符数字与字母编号#
int digit = c - '0'; // 前提是 c 确实在 '0' 到 '9'
int id = c - 'a'; // 前提是 c 确实在 'a' 到 'z'cpp不要对任意字符直接做减法后当成合法数字或数组下标。
13. 拷贝、移动、传参与 string_view#
13.1 深拷贝#
string a = "abc";
string b = a;
b[0] = 'X'; // a 仍为 "abc"cpp复制长字符串通常为 O(n)。
13.2 函数传参#
void readOnly(const string &s) {} // 只读,不复制
void modify(string &s) {} // 修改调用者的字符串
void ownCopy(string s) {} // 需要独立副本或接管右值cpp默认只读传参使用 const string&,不要按值复制大字符串。
13.3 string_view:只读视图,不拥有字符#
#include <string_view>
void printPrefix(string_view s) {
cout << s.substr(0, 3) << '\n';
}
string_view getPart(const string &s, int l, int len) {
return string_view(s).substr(l, len); // 不复制字符
}cpp优点:表示只读字符串或子串,substr 为 O(1),适合大量切片和只读传参。
危险点:
- 不拥有内存,原字符串销毁后 view 悬空。
- 原字符串扩容或修改导致存储变化后,view 可能失效。
view.data()不保证以'\0'结尾,不能直接当 C 字符串使用。- view 的
size()是视图长度,不是原字符串总长度。
只读函数若同时接受 string、字面量和子串,可考虑 string_view;若需要长期保存内容,应使用 string。
14. 常用操作复杂度#
设当前长度为 n,追加或结果长度为 m:
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
s[i]、at(i) |
O(1) |
随机访问 |
size()、length()、empty() |
O(1) |
长度已保存 |
front()、back() |
O(1) |
空串禁止 |
push_back()、尾部 += char |
均摊 O(1) |
扩容时可能搬移 |
| 拼接长度为 m 的内容 | 通常 O(m),另有扩容成本 |
需复制新增字符 |
中间 insert / erase / replace |
通常 O(n) |
移动后方字符 |
substr(pos, len) |
O(len) |
创建新 string 并复制 |
string_view::substr |
O(1) |
只创建视图 |
| 拷贝 string | O(n) |
深拷贝 |
| 比较两个字符串 | 最坏 O(min(n,m)) |
可能提前结束 |
find |
不应默认严格线性 | 模式匹配需保证复杂度时用专门算法 |
clear() |
通常视为清空操作 | 容量通常保留 |
swap |
通常 O(1) |
交换内部表示 |
sort 字符 |
O(n log n) |
改变字符顺序 |
实际性能还受动态分配、缓存、SSO 和字符串实现影响。
15. 竞赛常用模板#
15.1 统计字符频次#
仅小写字母:
vector<int> cnt(26, 0);
for (char c : s) ++cnt[c - 'a'];cpp任意字节值:
vector<int> cnt(256, 0);
for (unsigned char c : s) ++cnt[c];cpp使用 unsigned char 可避免负下标。
15.2 判断回文#
bool isPalindrome(const string &s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l] != s[r]) return false;
++l;
--r;
}
return true;
}cpp时间 O(n),额外空间 O(1),不需要构造反转副本。
15.3 线性删除满足条件的字符#
反复 erase 可能达到 O(n^2),可使用读写双指针:
int w = 0;
for (char c : s) {
if (c != ' ') s[w++] = c;
}
s.resize(w);cpp时间 O(n),额外空间 O(1)。最后才改变长度,循环中没有发生结构性修改。
15.4 按单个分隔符切分,并保留空字段#
vector<string> split(const string &s, char delim) {
vector<string> parts;
size_t start = 0;
while (true) {
size_t p = s.find(delim, start);
if (p == string::npos) {
parts.push_back(s.substr(start));
break;
}
parts.push_back(s.substr(start, p - start));
start = p + 1;
}
return parts;
}cpp例如 "a,,b," 会得到 "a"、""、"b"、""。空字符串会得到一个空字段。若不需要保留空字段,可在加入结果前增加判断。
15.5 按空白切分单词#
#include <sstream>
istringstream in(line);
string word;
while (in >> word) {
// 每个由空白分隔的单词
}cpp写法方便,但严格高性能场景中通常比手写扫描或使用高效输入方式慢。
15.6 拼接字符串数组#
string join(const vector<string> &a, char delim) {
string ans;
for (int i = 0; i < (int)a.size(); ++i) {
if (i) ans += delim;
ans += a[i];
}
return ans;
}cpp15.7 去除首尾空白#
string trim(const string &s) {
int l = 0, r = s.size();
while (l < r && isspace((unsigned char)s[l])) ++l;
while (r > l && isspace((unsigned char)s[r - 1])) --r;
return s.substr(l, r - l);
}cpp15.8 判断前缀与后缀#
C++17:
bool startsWith(const string &s, const string &p) {
return s.size() >= p.size() && s.compare(0, p.size(), p) == 0;
}
bool endsWith(const string &s, const string &p) {
return s.size() >= p.size()
&& s.compare(s.size() - p.size(), p.size(), p) == 0;
}cppC++20 可直接使用:
s.starts_with(p);
s.ends_with(p);cpp15.9 用 string 作字符栈:括号匹配思路#
string st;
for (char c : s) {
if (c == '(') st.push_back(c);
else if (c == ')') {
if (st.empty()) return false;
st.pop_back();
}
}
return st.empty();cpp此模板只处理一种括号;多种括号还需检查栈顶类型是否匹配。
16. 迭代器、指针与引用失效#
string 的动态存储与 vector 类似,扩容会搬移字符。
危险示例:
string s = "abc";
const char *p = s.c_str();
char &c = s[0];
auto it = s.begin();
s += "a very long suffix"; // 可能扩容
// printf("%s", p); // 危险:旧指针可能失效
// cout << c; // 危险:旧引用可能失效
// cout << *it; // 危险:旧迭代器可能失效cpp原则:
- 任何可能改变存储的操作后,重新获取
c_str()、data()、迭代器和引用。 - 不要长期保存指向临时 string 内部的指针或 view。
substr返回独立新 string,而string_view::substr仍依赖原字符存储。
临时对象导致的悬空:
// const char *p = (a + b).c_str(); // 临时 string 销毁后 p 悬空
// string_view v = string("abc"); // 临时对象销毁后 v 悬空cpp17. 高频错误与避坑清单#
17.1 size() 无符号下溢#
string s;
// for (int i = 0; i < s.size() - 1; ++i) {} // 空串时危险cpp推荐:
int n = s.size();
for (int i = 0; i + 1 < n; ++i) {}cpp17.2 空串调用 front/back/pop_back#
if (!s.empty()) {
cout << s.back();
s.pop_back();
}cpp17.3 substr 起点越界#
pos > size() 会抛异常;len 太大则会自动截断,两者规则不同。
17.4 忘记检查 find 的返回值#
size_t p = s.find(t);
if (p == string::npos) {
// 必须处理未找到
}cpp不要把未找到位置直接传给 substr、erase 或作为正常下标使用。
17.5 误以为 find 找不到就返回 -1#
string::npos 是无符号类型,虽然常由 -1 转换定义而来,但应始终与 string::npos 比较,不要把它当普通有符号 -1 做算术。
17.6 大量 substr 或字符串复制导致性能下降#
void f(string s); // 可能复制
string t = s.substr(l, len); // 复制 len 个字符cpp只读传参使用 const string& 或 string_view,只读切片优先考虑 string_view。
17.7 循环中反复中间删除#
单次 erase 为 O(n),反复执行可能为 O(n^2)。能双指针重写时优先线性处理。
17.8 错误使用 C 字符串函数#
strlen每次为O(n),而s.size()为O(1)。strlen、strcmp等遇'\0'停止,不能处理内嵌空字符。- 需要字符串功能时优先 string 自己的接口,不要混用两套长度语义。
17.9 字符分类函数未转换 unsigned char#
// isdigit(c); // c 为负时有风险
isdigit((unsigned char)c); // 正确cpp17.10 将字节数误认为 Unicode 字符数#
std::string 的元素是 char,size() 统计的是 char 单元数:
- ASCII 文本中通常一个字符一个字节。
- UTF-8 中文通常占多个字节。
s[i]、substr可能切断一个 UTF-8 编码字符。
算法竞赛大多默认 ASCII 或按字节处理;真正需要 Unicode 字符级处理时,需要明确编码并使用相应解码方法或库。
18. 一页速记#
string s; // 空串
string t = "abc"; // 字面量构造
string u(n, '0'); // n 个 '0'
string v(s, pos, len); // 复制子串
cin >> s; // 读一个单词
getline(cin, s); // 读一整行
cout << s << '\n';
s.size(); s.length(); // 字符数,O(1)
s.empty(); s.capacity();
s[i]; s.at(i); // 下标访问 / 检查访问
s.front(); s.back(); // 空串禁止
s.c_str(); s.data(); // C 字符串 / 字符存储
s += 'a'; s += "abc"; // 尾部拼接
s.append("abc");
s.push_back('a'); s.pop_back(); // 字符栈,空串禁止 pop
s.insert(pos, "abc");
s.erase(pos, len);
s.replace(pos, len, "abc");
s.clear(); // 清空,容量通常保留
s.reserve(n); // 只预留容量
s.resize(n, '0'); // 改变长度
string sub = s.substr(pos, len); // 新 string,O(len)
size_t p = s.find("abc", pos);
if (p == string::npos) {} // 未找到
s.rfind('a');
s.find_first_of("aeiou");
s.find_first_not_of(" \t");
a == b; a < b; // 字典序,区分大小写
a.compare(b);
sort(s.begin(), s.end());
reverse(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
string num = to_string(x);
long long x = stoll(s);
for (int i = 0; i < (int)s.size(); ++i) {}
for (char c : s) {} // 只读副本
for (char &c : s) {} // 修改字符cpp最终必须牢牢记住:
cin >> s读单词,getline读整行,两者混用要处理换行。size()为O(1),有效字符下标为[0,size())。substr会复制,string_view::substr只创建视图。find失败返回string::npos,使用前必须判断。- 中间插入删除为
O(n),循环反复执行可能退化为O(n^2)。 - 扩容或修改后,旧迭代器、指针、引用和 view 可能失效。
- 只读传参优先
const string&,避免无意义深拷贝。 string可以包含内嵌'\0',不能总用strlen代替size。- 字符分类函数使用前先转
unsigned char。 string::size()统计字节型char单元,不等于 Unicode 字符数。