麦地

Back

1. 核心概念与存储模型#

1.1 基本定义#

#include <string>
std::string s;
cpp

竞赛常用写法:

#include <bits/stdc++.h>
using namespace std;

string s;
cpp

string 实际上是:

std::basic_string<char>
cpp

核心特征:

  1. 保存一串 char,长度可以动态变化。
  2. 支持下标随机访问,s[i] 为 O(1)。
  3. 从 C++11 起,普通 string 的字符连续存储。
  4. 自动记录长度,size() 不需要像 strlen() 一样重新扫描。
  5. 提供 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' 就停止
cpp

1.3 c_str() 与 data()#

const char *p = s.c_str();
printf("%s\n", s.c_str());
cpp

注意:

  1. c_str() 返回的指针由 string 管理,不要手动 delete/free。
  2. C 风格函数通常遇到第一个 '\0' 就停止,不能正确处理内嵌空字符。
  3. 字符串扩容、修改或销毁后,旧指针可能失效,应重新调用 c_str()。
  4. 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::string
cpp

3. 输入输出#

3.1 cin >> s:读取一个非空白单词#

string s;
cin >> s;
cpp
  • 自动跳过前导空白。
  • 遇到空格、制表符、换行就停止。
  • 输入 hello world 时,只读入 hello。

循环读取单词直到 EOF:

string s;
while (cin >> s) {
    // 处理 s
}
cpp

3.2 getline:读取整行#

string s;
getline(cin, s);
cpp
  • 保留空格。
  • 丢弃行末换行符。
  • 空行会读成空字符串。
  • 可指定分隔符:getline(cin, s, ','),但分隔符不会保留在结果中。

循环读取每一行:

string line;
while (getline(cin, line)) {
    // 处理一整行
}
cpp

3.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();
cpp

3.5 输出与加速#

cout << s << '\n';
ios::sync_with_stdio(false);
cin.tie(nullptr);
cpp

cout << s 按 string 保存的完整长度输出,不依赖 C 字符串终止符。大规模输出优先 '\n',不要频繁使用会刷新缓冲区的 endl。


4. 字符访问与遍历#

4.1 下标访问#

s[i] = 'A';
char c = s[i];
cpp
  • s[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];
}
cpp

4.3 范围 for#

只读:

for (char c : s) {
    cout << c;
}
cpp

修改:

for (char &c : s) {
    if (c >= 'a' && c <= 'z') c = c - 'a' + 'A';
}
cpp

for (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;
}
cpp

string 的迭代器支持随机访问,但算法竞赛中大多直接下标遍历,更简洁。


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();  // 请求缩容,不保证执行
cpp

clear() 后 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;
cpp

6.3 字符串字面量不能直接相加#

// auto s = "abc" + "def"; // 错误:两个都是 const char 数组/指针语义
string s = string("abc") + "def"; // 正确
cpp

6.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');
cpp

7.2 删除#

s.erase(pos);        // 删除 pos 到末尾
s.erase(pos, len);   // 删除 [pos, pos+len),超出末尾的部分自动截断
s.clear();           // 全部删除
cpp

删除一个字符:

s.erase(s.begin() + i);
// 或 s.erase(i, 1);
cpp

7.3 替换#

s.replace(pos, len, "abc"); // 删除原区间,再放入 "abc"
cpp

7.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

规则:

  1. 返回一个新的 string,会发生字符复制,复杂度通常为 O(len)。
  2. pos > s.size() 会抛出 std::out_of_range。
  3. pos == s.size() 返回空串。
  4. len 超过剩余长度时自动截取到末尾。
  5. 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');
cpp

rfind(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

比较规则是按字符序列进行字典序比较:

  1. 从前往后找到第一对不同的字符,字符编码较小者对应字符串较小。
  2. 若公共前缀完全相同,较短字符串较小。
  3. 比较区分大小写。
"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);
cpp

to_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 浮点数

注意:

  1. 无有效数字时抛出 std::invalid_argument。
  2. 超出目标类型范围时抛出 std::out_of_range。
  3. 会接受允许的前导空白和符号。
  4. 默认可以只解析合法前缀,例如 stoi("123abc") 返回 123。

要求整串都被消费时:

size_t used = 0;
long long x = stoll(s, &used);
if (used != s.size()) {
    // 后面还有未解析字符
}
cpp

11.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),适合大量切片和只读传参。

危险点:

  1. 不拥有内存,原字符串销毁后 view 悬空。
  2. 原字符串扩容或修改导致存储变化后,view 可能失效。
  3. view.data() 不保证以 '\0' 结尾,不能直接当 C 字符串使用。
  4. 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;
}
cpp

15.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);
}
cpp

15.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;
}
cpp

C++20 可直接使用:

s.starts_with(p);
s.ends_with(p);
cpp

15.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

原则:

  1. 任何可能改变存储的操作后,重新获取 c_str()、data()、迭代器和引用。
  2. 不要长期保存指向临时 string 内部的指针或 view。
  3. substr 返回独立新 string,而 string_view::substr 仍依赖原字符存储。

临时对象导致的悬空:

// const char *p = (a + b).c_str(); // 临时 string 销毁后 p 悬空
// string_view v = string("abc");  // 临时对象销毁后 v 悬空
cpp

17. 高频错误与避坑清单#

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) {}
cpp

17.2 空串调用 front/back/pop_back#

if (!s.empty()) {
    cout << s.back();
    s.pop_back();
}
cpp

17.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);      // 正确
cpp

17.10 将字节数误认为 Unicode 字符数#

std::string 的元素是 char,size() 统计的是 char 单元数:

  • ASCII 文本中通常一个字符一个字节。
  • UTF-8 中文通常占多个字节。
  • s[i]、substr 可能切断一个 UTF-8 编码字符。

算法竞赛大多默认 ASCII 或按字节处理;真正需要 Unicode 字符级处理时,需要明确编码并使用相应解码方法或库。


18. 一页速记#

最终必须牢牢记住:

  1. cin >> s 读单词,getline 读整行,两者混用要处理换行。
  2. size() 为 O(1),有效字符下标为 [0,size())。
  3. substr 会复制,string_view::substr 只创建视图。
  4. find 失败返回 string::npos,使用前必须判断。
  5. 中间插入删除为 O(n),循环反复执行可能退化为 O(n^2)。
  6. 扩容或修改后,旧迭代器、指针、引用和 view 可能失效。
  7. 只读传参优先 const string&,避免无意义深拷贝。
  8. string 可以包含内嵌 '\0',不能总用 strlen 代替 size。
  9. 字符分类函数使用前先转 unsigned char。
  10. string::size() 统计字节型 char 单元,不等于 Unicode 字符数。
Comment seems to stuck. Try to refresh?✨