RootStack

11_字符串基础

11分钟阅读

字符串基础

建议先阅读：10_函数基础 09_数组基础

原理

C 风格字符串的内存布局

C 风格字符串是末尾以 \0（ASCII 0）标记结束的 char 数组。"Hello" 在内存中占 6 字节：

Hello\0

strlen() 遍历字符直到遇到 \0，时间复杂度 O(n)。频繁调用 strlen 在循环中是常见性能陷阱。sizeof 是编译时运算符，返回数组分配的字节总数，对字符串包含 \0。

strcmp 按字典序逐个字符比较，strcpy/strcat 不检查目标缓冲区大小——是缓冲区溢出漏洞的常见来源。

std::string 的内存模型

std::string 内部布局（典型实现，GCC libstdc++）：

字段大小说明
指针 → 堆缓冲区8 字节指向动态分配的 char 数组
size (长度)8 字节当前字符数
capacity (容量)8 字节已分配空间大小

短字符串优化（SSO）：GCC 的 string 对象内部预留 16 字节的本地缓冲区。长度 <= 15 的字符串不分配堆内存，直接存储在对象内部——这是现代 C++ 标准库的关键优化。

动态内存与扩容

string 的容量按倍数增长（通常 2x）。当 s += "text" 导致 size > capacity 时，触发重新分配：申请新的更大堆内存 -> 拷贝原有数据 -> 释放旧内存。这就是为什么预先 reserve() 可优化大量拼接操作。

语法

声明与初始化

std::string s1;                       // 空字符串
std::string s2 = "Hello";             // C 字符串初始化
std::string s3("World");              // 构造函数初始化
std::string s4(5, 'A');               // "AAAAA"
std::string s5 = s2;                  // 拷贝
std::string s6(s2, 1, 3);            // 从 s2[1] 开始的 3 个字符 "ell"
std::string s7 = {"H", "e", "l"};    // 列表初始化

基本操作

操作代码
长度s.length() 或 s.size() （等价）
判空s.empty()
拼接s1 + s2, s += "abc"
访问s[i], s.front(), s.back()
比较s1 == s2, s1 < s2, s1.compare(s2)

find / rfind

std::string text = "Hello World";
size_t pos = text.find("World");     // 6
size_t pos2 = text.find("Java");     // std::string::npos (未找到)
size_t pos3 = text.rfind('o');       // 7 (从右查找)

npos 是静态常量，值为 size_t 的最大值，表示查找失败。

substr

std::string s = "Hello World";
std::string sub1 = s.substr(0, 5);   // "Hello"
std::string sub2 = s.substr(6);      // "World" (从6到末尾)

replace

std::string s = "Hello World";
s.replace(6, 5, "C++");             // "Hello C++"

字符串与数字互转

// 字符串 -> 数字
int n = std::stoi("12345");
double d = std::stod("3.14159");
long long ll = std::stoll("9999999999");
 
// 数字 -> 字符串
std::string s = std::to_string(42);
std::string pi = std::to_string(3.14159); // "3.141590" (默认6位小数)

to_string 对浮点数固定 6 位小数。stoi 在无有效数字时抛 std::invalid_argument，超出范围抛 std::out_of_range。

getline 读取整行

std::string line;
std::getline(std::cin, line);            // 读到换行符为止
std::getline(std::cin, line, ',');       // 自定义分隔符

遍历

for (char c : s) { ... }                // 值拷贝
for (char& c : s) { c = toupper(c); }  // 引用修改
for (size_t i = 0; i < s.size(); i++)   // 下标遍历
    std::cout << s[i];

详解：std::string vs C 字符串性能对比

内存对比

特性C 字符串 char[]std::string
存储位置栈/全局数据区对象在栈，数据在堆（SSO 例外）
长度获取strlen() O(n).size() O(1)
拼接strcat O(n) 且不安全+= 均摊 O(1)
拷贝strcpy / memcpy拷贝构造 O(n)
比较strcmp O(n)== O(n)（短路优化）
内存释放手动管理自动（RAII）
缓冲区溢出常见风险不可能

性能陷阱

// 错误: 循环中反复 strlen
for (int i = 0; i < strlen(s); i++) { // 每次迭代都 O(n) 遍历!
    // O(n²) 复杂度
}
 
// 正确: 缓存长度
size_t len = s.size(); // O(1)
for (int i = 0; i < len; i++) {
    // O(n) 复杂度
}
 
// 错误: s = s + "x" 创建临时对象
for (int i = 0; i < 10000; i++) {
    s = s + "x"; // 每次分配新内存、拷贝、释放旧内存
}
 
// 正确: s += "x" 原地修改
for (int i = 0; i < 10000; i++) {
    s += "x"; // 均摊 O(1)
}

预分配优化

std::string s;
s.reserve(10000); // 预分配，避免多次扩容
for (int i = 0; i < 10000; i++) {
    s += "a"; // 不再触发重新分配
}

详解：std::string_view (C++17)

string_view 是非拥有的字符串视图，不分配内存，不修改原字符串：

#include <string_view>
 
std::string original = "Hello World";
std::string_view sv = original;     // 零拷贝
std::string_view sv2 = sv.substr(0, 5); // "Hello", 仍无拷贝
 
// 只读访问
sv[0];       // 'H'
sv.size();   // 11
sv.find("World"); // 6

string_view vs string

特性std::stringstd::string_view
拥有数据是否（只读视图）
修改内容可以不可以
追加/拼接+=不支持
C 风格字符串.c_str().data()（无 \0 保证）
传参效率按引用或拷贝零开销
生命周期依赖自身管理必须确保原字符串存活

何时使用 string_view

// 推荐: 只读函数参数用 string_view
void process(std::string_view sv) {
    // 只读操作
    for (char c : sv) { ... }
}
 
// 不推荐: 修改内容的函数
void modify(std::string& s) {
    s += "suffix"; // 必须用 string
}
 
// 转换: string_view -> string
std::string_view sv = "Hello";
std::string s(sv); // 显式构造，发生拷贝

string_view 的陷阱

// 陷阱1: 原字符串销毁后视图悬空
std::string_view bad() {
    std::string s = "Hello";
    return std::string_view(s); // s 离开作用域后视图悬空!
}
 
// 陷阱2: 不保证 null 终止
std::string_view sv = "Hello";
// sv.data() 不保证以 \0 结尾
// 不能直接传给需要 C 字符串的 API

详解：字符串驻留（String Interning）概念

字符串驻留是一种优化：相同内容的字符串共享同一份内存副本。C++ 标准库不自动驻留，但可以手动实现：

#include <unordered_set>
 
std::unordered_set<std::string> intern_pool;
 
std::string_view intern(std::string_view sv) {
    auto it = intern_pool.find(std::string(sv));
    if (it != intern_pool.end()) {
        return *it; // 返回已存在的字符串
    }
    auto [ins, _] = intern_pool.emplace(sv);
    return *ins; // 插入并返回
}
 
// 使用: 大量重复字符串时节省内存
auto s1 = intern("Hello");
auto s2 = intern("Hello");
// s1 和 s2 指向同一内存

用途：编译器的标识符池、JSON 键去重、HTTP 头部字段共享。

详解：字符串算法常用技巧

双指针处理字符串

// 回文判断
bool isPalindrome(const std::string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}
 
// 原地移除空格
void removeSpaces(std::string& s) {
    int slow = 0;
    for (int fast = 0; fast < s.size(); fast++) {
        if (s[fast] != ' ') {
            s[slow++] = s[fast];
        }
    }
    s.resize(slow);
}

滑动窗口

// 最长无重复字符子串
int lengthOfLongestSubstring(std::string s) {
    std::unordered_map<char, int> last;
    int max_len = 0, start = 0;
    for (int i = 0; i < s.size(); i++) {
        if (last.count(s[i]) && last[s[i]] >= start) {
            start = last[s[i]] + 1;
        }
        last[s[i]] = i;
        max_len = std::max(max_len, i - start + 1);
    }
    return max_len;
}

KMP 字符串匹配

std::vector<int> buildNext(const std::string& pattern) {
    std::vector<int> next(pattern.size(), 0);
    for (int i = 1, len = 0; i < pattern.size(); ) {
        if (pattern[i] == pattern[len]) {
            next[i++] = ++len;
        } else if (len) {
            len = next[len - 1];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}
 
std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> result;
    auto next = buildNext(pattern);
    for (int i = 0, j = 0; i < text.size(); ) {
        if (text[i] == pattern[j]) {
            i++; j++;
            if (j == pattern.size()) {
                result.push_back(i - j);
                j = next[j - 1];
            }
        } else if (j) {
            j = next[j - 1];
        } else {
            i++;
        }
    }
    return result;
}

实践

split 实现（以逗号分隔）：

#include <vector>
#include <string>
 
std::vector<std::string> split(const std::string& s, char delim) {
    std::vector<std::string> tokens;
    size_t start = 0, end;
    while ((end = s.find(delim, start)) != std::string::npos) {
        tokens.push_back(s.substr(start, end - start));
        start = end + 1;
    }
    tokens.push_back(s.substr(start));
    return tokens;
}

常见字符串操作

// 去除首尾空白
std::string trim(const std::string& s) {
    size_t start = s.find_first_not_of(" \t\n");
    size_t end = s.find_last_not_of(" \t\n");
    return (start == std::string::npos) ? "" : s.substr(start, end - start + 1);
}
 
// 转大写
std::string toUpper(std::string s) {
    std::transform(s.begin(), s.end(), s.begin(), ::toupper);
    return s;
}
 
// 替换所有出现
void replaceAll(std::string& s, const std::string& from, const std::string& to) {
    size_t pos = 0;
    while ((pos = s.find(from, pos)) != std::string::npos) {
        s.replace(pos, from.length(), to);
        pos += to.length();
    }
}
 
// 反转字符串
void reverseStr(std::string& s) {
    std::reverse(s.begin(), s.end());
}

练习

题号题目链接知识点
3无重复字符的最长子串https://www.luogu.com.cn/problem/P1001滑动窗口、哈希表
5最长回文子串https://www.luogu.com.cn/problem/P1001中心扩展、动态规划
8字符串转换整数 (atoi)https://www.luogu.com.cn/problem/P1001字符解析、边界处理
P1012拼数https://www.luogu.com.cn/problem/P1012字符串、排序
20有效的括号https://www.luogu.com.cn/problem/P1001栈、字符匹配
28找出字符串中第一个匹配项的下标https://www.luogu.com.cn/problem/P1001KMP、字符串匹配
38外观数列https://www.luogu.com.cn/problem/P1001字符串构造、迭代
49字母异位词分组https://www.luogu.com.cn/problem/P1001排序、哈希表
125验证回文串https://www.luogu.com.cn/problem/P1001双指针、字符过滤
P1010幂次方https://www.luogu.com.cn/problem/P1010函数、递归
P1014Catalan数https://www.luogu.com.cn/problem/P1014数学、递推
409最长回文串https://www.luogu.com.cn/problem/P1001贪心、字符计数
415字符串相加https://www.luogu.com.cn/problem/P1001字符与数字转换、模拟

关系图谱

反向链接