C 字符串是以 '\0' 结尾的一串字符,长度不保存在任何地方。strlen 要从头数到尾,把 strlen(s) 写进循环条件,循环就整体退化成 O(n²)。strcpy、strcat、strcmp 这些函数与数据是分离的,空间也由调用者自己管:

#include <string.h>
 
int main(void)
{
    char buf[6] = "hello";
    strcpy(buf, "hello world");   /* 需要 12 字节,目标只有 6 字节 */
    return 0;
}

越界写不一定当场崩,可能改写相邻变量,也可能在很久之后才出问题。std::string 把这些职责收进对象:长度、容量、指向字符缓冲的指针都在对象里,修改时由类自己扩容。使用时包含 <string>,类型名在 std 命名空间。

auto 与范围 for:先把遍历写短

课件在讲接口前补了两个 C++11 语法。auto 在 C 语言里原本是“自动存储期”的存储类说明符,C++11 改成了类型推导:声明变量时由初始值决定类型。

#include <iostream>
#include <map>
#include <string>
 
int main()
{
    int a = 10;
    auto b = a;        /* int */
    auto c = 'a';      /* char */
    int x = 10;
 
    auto y = &x;       /* int* */
    auto* z = &x;      /* int*,和上一行等价 */
    auto& m = x;       /* int&,引用必须自己写 & */
 
    /* auto e;                编译错误:auto 变量必须有初始值 */
    /* auto cc = 3, dd = 4.0; 编译错误:同一行里的 auto 必须推导成同一类型 */
    /* auto arr[] = {1, 2};   编译错误:数组元素不能用 auto */
    /* void f(auto v);        编译错误:auto 不能做形参 */
 
    std::map<std::string, std::string> dict = {{"apple", "苹果"}, {"orange", "橙子"}};
    for (auto it = dict.begin(); it != dict.end(); ++it)
        std::cout << it->first << ':' << it->second << '\n';
    return 0;
}

auto 可以写在返回值位置,但类型从实现里推出来,调用者读签名时看不到真实类型,公开接口不建议这么写。auto 声明指针时 auto 与 auto* 没有区别,声明引用时必须写 &——推导会丢掉引用,auto m = x; 是一份拷贝。

范围 for 进一步省掉迭代器的样板代码:

#include <iostream>
#include <string>
 
int main()
{
    int array[] = {1, 2, 3, 4, 5};
 
    for (auto& e : array)
        e *= 2;
    for (auto e : array)
        std::cout << e << ' ';
    std::cout << '\n';
 
    std::string s("hello world");
    for (auto ch : s)
        std::cout << ch;
    std::cout << '\n';
    return 0;
}

冒号左边是变量,右边是被遍历的范围。要改元素就写 auto&,只读就写 const auto&,写 auto 拿到的是副本。范围 for 对数组和容器都成立,底层展开成 begin() / end() 迭代器加 != 判断,所以遍历期间不能 push_back 或 erase,那会让正在用的迭代器失效。

构造与容量:对象记着自己的长度

常用构造函数四个:

函数作用
string()构造空串
string(const char* s)用 C 字符串构造
string(size_t n, char c)n 个字符 c
string(const string& s)拷贝构造

容量相关的接口七个:

接口含义
size()有效字符个数
length()与 size() 等价,两个名字底层同一实现
capacity()当前分配的字符缓冲能放多少个字符
empty()是否为空串
clear()清空有效字符,不释放空间
reserve(n)预留至少能放 n 个字符的空间
resize(n) / resize(n, c)把有效字符个数改成 n

四条容易记混的规则:

  • size() 和 length() 是同一个东西,引入 size() 是为了和别的容器接口统一。
  • clear() 只把长度归零,capacity() 不变,之后再追加不用重新分配。
  • resize 变长时,多出来的位置用 '\0' 填充;resize(n, c) 用 c 填充。这些填充字符算在 size() 里,打印时看不出来。
  • resize 减少长度不改变容量;reserve 的参数小于当前容量时不会缩容,C++20 起明确规定这种情况什么也不做。
#include <iostream>
#include <string>
 
int main()
{
    std::string s("hello bit");
 
    std::cout << "size=" << s.size() << " capacity=" << s.capacity() << '\n';
 
    s.reserve(64);                     /* 只改容量 */
    std::cout << "size=" << s.size() << " capacity=" << s.capacity() << '\n';
 
    s.resize(20, '#');                 /* 长度变 20,多出来的用 # 填 */
    std::cout << "size=" << s.size() << " capacity=" << s.capacity() << '\n';
 
    s.clear();                         /* 长度归零,容量不变 */
    std::cout << "size=" << s.size() << " capacity=" << s.capacity() << '\n';
    return 0;
}

第一行打印出的容量因实现而异:短字符串通常放在对象内部的小缓冲里(小字符串优化,SSO),容量可能是 15 或 22,超过阈值才上堆。能确定的是三条关系:reserve 之后 size 不变;resize 之后 size 等于参数;clear 之后容量不变。

预留空间是为循环服务的。往一个空字符串里追加十万次,不 reserve 就会反复扩容、反复搬字符;先 reserve(100000),整个追加过程只申请一次。reserve 只保证空间,不创建元素——reserve(100) 之后 s[50] 仍然是越界访问。

下标、迭代器、find 与 substr:边界写在接口上

operator[] 不检查边界,超出 size() 是未定义行为;at() 会检查,越界抛 std::out_of_range。下标来自用户输入或配置时用 at,自己控制的循环里用 [] 少一层判断。

#include <iostream>
#include <string>
 
int main()
{
    std::string s("hello world");
 
    std::cout << s[0] << ' ' << s.at(1) << '\n';
 
    std::size_t pos = s.find('o');
    if (pos != std::string::npos)
        std::cout << "first o at " << pos << '\n';
 
    std::cout << s.substr(6) << '\n';       /* world */
    std::cout << s.substr(6, 2) << '\n';    /* wo */
 
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        std::cout << *it;
    std::cout << '\n';
    return 0;
}

s[s.size()] 是合法的,C++11 起 operator[] 在 pos == size() 时返回结尾那个 '\0' 的引用;读它没问题,把它改成别的值才是未定义行为。

find 找不到时返回 npos。它的类型是 size_type,在 std::string 里就是无符号的 size_t,npos 定义为 size_type(-1),也就是这个无符号类型的最大值,没有任何负数含义。比较只写 pos == std::string::npos;把结果塞进 int 再和 -1 比,字长一变就会出错。

rfind 从后往前找,substr(pos, n) 从 pos 开始截 n 个字符。边界规则不对称:pos 大于 size() 抛 out_of_range,n 超过剩余长度则安静截断,不会报错。

迭代器方面,begin() / end() 是正向,rbegin() / rend() 是反向。课件表格里 rbegin + rend 那一行是从 begin + end 直接复制过来的,写着“end 获取最后一个字符下一个位置的迭代器”,那是正向的说法。反向迭代器的起点在尾部:rbegin() 指向最后一个字符,rend() 指向第一个字符前一位,++ 是往回走。const 对象上 begin() 返回 const_iterator,只能读不能改。

修改接口里最常用的是 push_back、append 和 +=。append 一次能追加多个字符,+= 字符和字符串都能接,两者都是原地追加,只在容量不足时扩容。operator+ 不一样:每次返回一个新对象,两个操作数各拷一遍,结果再申请一块空间,拼五段就是五次分配。能改原对象时用 += 或 append,不要在循环里用 operator+。

c_str() 返回内部缓冲的地址,不是拷贝。任何可能触发扩容的修改之后,之前存下的 const char* 就悬空了,要在用的时候现取。读一整行用 getline(cin, line);cin >> line 遇到空格就停,剩下的内容留在缓冲区里。

非成员函数还有输入输出和比较。operator<<、operator>> 直接读写整串,>> 读到空白为止;<、==、!= 这些关系运算符按字典序逐字符比较,直接得到布尔结果,C 的 strcmp 返回的是正负零,调用处还得再判断一次。

对象布局:28 字节、4 字节与今天的 SSO

课件按 32 位平台给了两套结构。VS 那套是 28 字节:一个联合体 _Bx,短串时用里面 16 字节的字符数组 _Buf,长串时换成指针 _Ptr;后面跟两个 size_t,分别记长度和容量;再加一个指针做别的事,合计 16 + 4 + 4 + 4。

调试器里展开的 VS string:_Bx 是联合体,短串走 _Buf 那条 16 字节缓冲,长串走 _Ptr;下面 _Mysize 是有效长度,_Myres 是容量。注意这是 32 位平台的字段宽度

g++ 那套课件写的是“总共 4 个字节,内部只有一个指针,指向一块包含长度、容量、引用计数的堆空间”,也就是写时拷贝(copy-on-write)的结构。这段描述对应的是 GCC 5 之前的 libstdc++。

从 GCC 5.1 起,libstdc++ 启用了新的库 ABI,std::string 被重新实现成短串内联、长串上堆的 SSO 结构,不再写时拷贝,符号也搬进了 std::__cxx11。原因在 C++11 的规定:c_str() 返回的指针在未修改时必须一直有效,operator[] 返回的是引用,非 const 操作后旧迭代器的失效规则也被收紧,共享缓冲加引用计数很难同时满足这些约束。今天在 64 位 libstdc++ 上 sizeof(std::string) 是 32,短串容量 15;libc++ 是 24 字节、容量 22;64 位 MSVC 也是 32 字节。数字随实现和版本变,要确认就在自己机器上打一次:

#include <iostream>
#include <string>
 
int main()
{
    std::string s("hello");
    std::cout << "sizeof=" << sizeof(s)
              << " capacity=" << s.capacity()
              << " size=" << s.size() << '\n';
    return 0;
}

新老 ABI 混用会直接体现为链接错误:一边用 _GLIBCXX_USE_CXX11_ABI=0 编译的库,另一边用默认值编译的程序,互相传 std::string 时会找不到 std::__cxx11::basic_string 的符号。遇到这种报错,先查对方的 ABI 宏,别怀疑自己的代码。

五道 OJ 里反复出现的接口

课件用五道题串起了查找、截取、迭代器、+= 的用法。第一道是只反转字母,非字母留在原位:

#include <string>
#include <utility>
 
class Solution
{
public:
    bool isLetter(char ch)
    {
        return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
    }
 
    std::string reverseOnlyLetters(std::string s)
    {
        if (s.empty())
            return s;
 
        int begin = 0;
        int end = static_cast<int>(s.size()) - 1;
        while (begin < end)
        {
            while (begin < end && !isLetter(s[begin]))
                ++begin;
            while (begin < end && !isLetter(s[end]))
                --end;
            std::swap(s[begin], s[end]);
            ++begin;
            --end;
        }
        return s;
    }
};

第二道找第一个只出现一次的字符,用 256 个计数桶:

#include <string>
 
int firstUniqChar(const std::string& s)
{
    int count[256] = {0};
 
    for (char ch : s)
        ++count[static_cast<unsigned char>(ch)];
 
    for (int i = 0; i < static_cast<int>(s.size()); ++i)
        if (count[static_cast<unsigned char>(s[i])] == 1)
            return i;
    return -1;
}

下标必须转成 unsigned char。char 在多数平台上是有符号的,遇到字节大于 127 的字符,s[i] 是负数,count[s[i]] 就成了负下标,属于越界访问。

第三道求最后一个单词的长度,用 getline 读整行再做 rfind:

#include <iostream>
#include <string>
 
int main()
{
    std::string line;
    while (std::getline(std::cin, line))
    {
        std::size_t pos = line.rfind(' ');
        if (pos == std::string::npos)
            std::cout << line.size() << '\n';
        else
            std::cout << line.size() - pos - 1 << '\n';
    }
    return 0;
}

课件写的是 line.size() - pos - 1,省略了判断。没有空格时 rfind 返回 npos,也就是 SIZE_MAX,size() - SIZE_MAX - 1 靠无符号回绕恰好等于 size(),结果碰巧正确。能跑通,但不该依赖回绕,把没有空格的情况单独写出来更清楚。

第四道回文判断,先把小写转成大写,再用双指针跳过非字母数字:

#include <string>
 
bool isLetterOrNumber(char ch)
{
    return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
 
bool isPalindrome(std::string s)
{
    for (auto& ch : s)
        if (ch >= 'a' && ch <= 'z')
            ch -= 32;
 
    int begin = 0;
    int end = static_cast<int>(s.size()) - 1;
    while (begin < end)
    {
        while (begin < end && !isLetterOrNumber(s[begin]))
            ++begin;
        while (begin < end && !isLetterOrNumber(s[end]))
            --end;
        if (s[begin] != s[end])
            return false;
        ++begin;
        --end;
    }
    return true;
}

第五道字符串相加,从后往前逐位加,结果先尾插再整体反转:

#include <algorithm>
#include <string>
 
std::string addStrings(std::string num1, std::string num2)
{
    int end1 = static_cast<int>(num1.size()) - 1;
    int end2 = static_cast<int>(num2.size()) - 1;
    int next = 0;
    std::string ret;
 
    while (end1 >= 0 || end2 >= 0)
    {
        int value1 = end1 >= 0 ? num1[end1--] - '0' : 0;
        int value2 = end2 >= 0 ? num2[end2--] - '0' : 0;
        int sum = value1 + value2 + next;
 
        next = sum > 9 ? 1 : 0;
        if (sum > 9)
            sum -= 10;
        ret += static_cast<char>(sum + '0');
    }
    if (next == 1)
        ret += '1';
 
    std::reverse(ret.begin(), ret.end());
    return ret;
}

用 += 而不是 insert(ret.begin(), sum + '0'):后者每次都要把已有字符整体后移,n 位加法就退化成 O(n²)。先尾插再反转,整体是 O(n)。

课件后面还留了翻转字符串 II(区间翻转)、翻转字符串 III(翻转单词)、字符串相乘,套路都是双指针配合 reverse、substr。

模拟实现:浅拷贝、深拷贝、写时拷贝

课件先给了一个只有构造和析构的版本:

#include <cassert>
#include <cstring>
 
class String
{
public:
    String(const char* str = "")
    {
        assert(str != nullptr);
        _str = new char[std::strlen(str) + 1];
        std::strcpy(_str, str);
    }
 
    ~String() { delete[] _str; }
 
private:
    char* _str;
};
 
void TestString()
{
    String s1("hello bit!!!");
    String s2(s1);      /* 编译器生成的拷贝构造,只把指针复制过去 */
}

s2 构造时走的是编译器隐式生成的拷贝构造,行为是逐成员复制。成员只有一个 char*,复制之后 s1._str 和 s2._str 数值相同,两个对象都认为这块堆内存归自己。

浅拷贝的结果:s1 和 s2 的成员指针指向同一块字符缓冲。局部对象先析构 s2,它把那块空间 delete[] 掉;s1 之后析构时再释放同一地址,指针已经悬空

s2 先析构,delete[] 归还空间;s1 再析构,对同一个地址再 delete[] 一次,这是堆管理器能检测到的那类错误。这种复制方式叫浅拷贝(shallow copy):只复制对象里的值,不复制值指向的资源。

深拷贝(deep copy)是每个对象各自持有一份独立资源。传统写法把拷贝构造、赋值运算符、析构函数、构造函数四件一起给出:

#include <cstring>
 
class String
{
public:
    String(const char* str = "")
    {
        _str = new char[std::strlen(str) + 1];
        std::strcpy(_str, str);
    }
 
    String(const String& other)
        : _str(new char[std::strlen(other._str) + 1])
    {
        std::strcpy(_str, other._str);
    }
 
    String& operator=(const String& other)
    {
        if (this != &other)
        {
            char* tmp = new char[std::strlen(other._str) + 1];
            std::strcpy(tmp, other._str);
            delete[] _str;
            _str = tmp;
        }
        return *this;
    }
 
    ~String() { delete[] _str; }
 
private:
    char* _str;
};

赋值里两个顺序不能反:先申请并拷贝新的,再释放旧的。反过来先 delete[],一旦 new 抛 bad_alloc,对象就停在“旧数据没了、新数据没来”的状态,析构也救不回来。自赋值判断同样不能省,a = a 时不检查,先删掉的就是自己,后面 strlen(other._str) 读的是刚释放的内存。

深拷贝:拷贝构造为 s2 单独申请一块同样大的空间,再把字符逐个复制过去。两个对象的指针值不同,各自析构各自的空间,不会重复释放

现代写法把顺序和分支交给语言机制:

#include <cstring>
#include <utility>
 
class String
{
public:
    String(const char* str = "")
    {
        _str = new char[std::strlen(str) + 1];
        std::strcpy(_str, str);
    }
 
    String(const String& other) : _str(nullptr)
    {
        String tmp(other._str);
        std::swap(_str, tmp._str);
    }
 
    String& operator=(String other)
    {
        std::swap(_str, other._str);
        return *this;
    }
 
    ~String() { delete[] _str; }
 
private:
    char* _str;
};

赋值的形参是值传递,实参进来时已经构造好一份独立拷贝,函数体只交换两个指针;形参在函数结束时析构,旧资源跟着它一起走。自赋值会先拷贝一份再交换,碰不到自己那块内存;拷贝发生在进入函数体之前,失败时 this 原封不动。多付一次拷贝,换掉所有顺序判断和分支,这就是 copy-and-swap。

写时拷贝(copy-on-write)走的是另一条路:拷贝时只共享缓冲并把引用计数加一,有人要写时才真正复制一份。构造时计数置 1,每次拷贝加 1,析构时减 1,减到 0 才释放。

课件用这组表情包解释写时拷贝的“拖延”:先不动手,等真要写的时候才各抄一份。引用计数就是判断“还有没有别人在用”的依据

它的麻烦在于每个非 const 的访问都要先检查引用计数:operator[] 返回引用,若此时计数大于 1,必须先把缓冲复制出来,否则 s[0] = 'x' 会改到所有共享者;多线程下计数还要原子操作。C++11 之后主流实现放弃了这套方案,std::string 回到每个对象独立管理缓冲的 SSO 结构。

还有一处课件里的写法需要注意:构造里遇到空指针用 assert(false); return;,NDEBUG 定义后 assert 被整段去掉,return 会让 _str 没有被赋值,析构时 delete[] 一个未初始化的指针。要用断言拦住非法参数,就得保证 release 版本也不放过,或者干脆在构造里抛异常。