手写 std::string

实现限定 char 的动态字符串与小字符串优化，理解结尾零字节、容量标记和移动语义的细节。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

一、学习目标

始终维护 NUL 结尾
实现 SSO 与堆模式切换
区分 size、capacity 和 strlen

二、前置条件

完成 vector 篇，理解 union、对象表示和 Rule of Five。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

三、问题与设计选择

对象内保留 23 字节小缓冲；短文本不分配，长文本保存指针、大小和容量。所有修改操作在提交前预留结尾 \0。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

四、内存布局与核心不变量

data()[size()] 始终为 \0；SSO 与 heap 模式互斥，heap 模式的容量不包含结尾零字节。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

五、核心实现

void append(std::string_view text) {
    if (text.empty()) return;
    const auto old = size_;
    ensure_capacity(old + text.size());
    std::memmove(data_mut() + old, text.data(), text.size());
    size_ += text.size();
    data_mut()[size_] = '\0';
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

class string {
    static constexpr std::size_t small_capacity = 23;
    char* data_;
    std::size_t size_{};
    std::size_t capacity_{small_capacity};
    alignas(char*) char small_[small_capacity + 1]{};

    bool is_small() const noexcept { return data_ == small_; }

    void copy_from(const string& other) {
        if (other.size_ <= small_capacity) {
            data_ = small_;
            capacity_ = small_capacity;
        } else {
            data_ = new char[other.size_ + 1];
            capacity_ = other.size_;
        }
        size_ = other.size_;
        std::memcpy(data_, other.data_, size_ + 1);
    }

    bool overlaps(std::string_view view) const noexcept {
        return !view.empty() && view.data() >= data_ && view.data() < data_ + size_;
    }

public:
    string() noexcept : data_(small_) { small_[0] = '\0'; }
    string(std::string_view text) : string() {
        ensure_capacity(text.size());
        std::memcpy(data_, text.data(), text.size());
        size_ = text.size();
        data_[size_] = '\0';
    }
    string(const char* text) : string(std::string_view(text)) {}
    string(const string& other) { copy_from(other); }
    string(string&& other) noexcept : string() {
        if (other.is_small()) {
            size_ = other.size_;
            std::memcpy(small_, other.small_, size_ + 1);
        } else {
            data_ = std::exchange(other.data_, other.small_);
            size_ = std::exchange(other.size_, 0);
            capacity_ = std::exchange(other.capacity_, small_capacity);
            other.small_[0] = '\0';
        }
    }
    string& operator=(const string& other) {
        if (this == &other) return *this;
        string copy(other);
        return *this = std::move(copy);
    }
    string& operator=(string&& other) noexcept {
        if (this == &other) return *this;
        if (!is_small()) delete[] data_;
        data_ = small_;
        size_ = 0;
        capacity_ = small_capacity;
        small_[0] = '\0';
        if (other.is_small()) {
            size_ = other.size_;
            std::memcpy(small_, other.small_, size_ + 1);
            other.size_ = 0;
            other.small_[0] = '\0';
        } else {
            data_ = std::exchange(other.data_, other.small_);
            size_ = std::exchange(other.size_, 0);
            capacity_ = std::exchange(other.capacity_, small_capacity);
            other.small_[0] = '\0';
        }
        return *this;
    }
    ~string() {
        if (!is_small()) delete[] data_;
    }

    const char* data() const noexcept { return data_; }
    char* data() noexcept { return data_; }
    const char* c_str() const noexcept { return data_; }
    std::size_t size() const noexcept { return size_; }
    std::size_t capacity() const noexcept { return capacity_; }
    bool empty() const noexcept { return size_ == 0; }
    bool uses_sso() const noexcept { return is_small(); }
    char& operator[](std::size_t index) noexcept { return data_[index]; }
    const char& operator[](std::size_t index) const noexcept { return data_[index]; }
    auto begin() noexcept { return data_; }
    auto begin() const noexcept { return data_; }
    auto end() noexcept { return data_ + size_; }
    auto end() const noexcept { return data_ + size_; }

    void ensure_capacity(std::size_t requested) {
        if (requested <= capacity_) return;
        std::size_t next = std::max(requested, capacity_ * 2);
        char* fresh = new char[next + 1];
        std::memcpy(fresh, data_, size_ + 1);
        if (!is_small()) delete[] data_;
        data_ = fresh;
        capacity_ = next;
    }

    void append(std::string_view text) {
        if (text.empty()) return;
        std::string owned;
        if (overlaps(text)) {
            owned.assign(text);
            text = owned;
        }
        ensure_capacity(size_ + text.size());
        std::memmove(data_ + size_, text.data(), text.size());
        size_ += text.size();
        data_[size_] = '\0';
    }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

七、使用示例与输出

预期输出或状态：

短字符串保持在对象内部；追加到超过 23 字节后切换到堆模式，内容和 NUL 结尾不变。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

八、复杂度与失效规则

操作	复杂度	说明
data/c_str/size	O(1)	返回连续存储
append	摊还 O(m)	必要时扩容
find	O(nm)	教学版朴素搜索
substr	O(m)	创建新字符串

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

九、异常安全与资源管理

获取资源后立即交给 RAII 对象或明确记录已构造数量。
用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
只有在所有后续步骤不会失败时才修改不可回滚的链接。
析构、释放和关闭路径不得抛异常。
并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

十、常见错误

1. 容量没有为 `\0` 留空间

容量没有为 \0 留空间会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 从自身子串 append 时使用 memcpy

从自身子串 append 时使用 memcpy会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 移动 SSO 字符串时只搬指针

移动 SSO 字符串时只搬指针会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

SSO 为什么会影响 ABI？
string_view 如何产生悬空引用？
size() 为什么不必调用 strlen？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

十二、练习与自测

实现 erase 与 insert
为自追加编写测试
比较不同 SSO 容量对 sizeof 的影响

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

十三、官方资料与延伸阅读

上一篇：手写 std::vector ｜下一篇：手写 std::forward_list