Nvidia C++ 高性能字符串：短串缓冲区、所有权与复制语义

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练类保留 128 字节内联数组、长度和可空堆指针：长度 <128 时连同终止符放内联；长度 ≥128 时堆分配 length+1。题目代码示意有笔误，本文按可编译接口重写。
• 构造参数是指针和明确长度；空指针仅允许长度为零。可以按长度保存内嵌 NUL 字节，但作为 C 字符串使用时会在 NUL 处截断。
• 示例实现构造、深拷贝、移动、析构、compare 和 swap；cat/substr 的 API 与异常约定题目未明确，不声称本文实现了它们。

解题路线

1. 先定不变量：pointer_ 非空时它独占可释放的堆块，内容长度为 length_，末尾有 `\0`；否则 buffer_ 保存内容与终止符。构造时先检查 null 与 length+1 溢出，再分配、按精确长度 memcpy、补终止符。
2. 堆指针引入所有权：只写构造函数而使用默认复制会让两对象共享同一块内存，析构时 double free。实现析构、深拷贝和移动；拷贝赋值用先构造副本再 swap，分配失败时原对象不变。
3. compare 只比较两串共同长度的字节，前缀相同后再比较长度。这样含内嵌 NUL 时也保持按长度语义；与使用 strcmp 的 C 字符串比较不同。
4. 评估性能时分别测短串/长串分布、构造、比较和拼接，并检查分配次数、缓存命中与编译器优化。不能仅凭短串在缓存中或把 char 当整数拷贝就断言固定倍数加速。

手动走一遍

长度 127 时，127 个字节加 `\0` 恰占满 128 字节 buffer；长度 128 时需分配 129 字节。复制后一方销毁，另一方仍持有独立内容；移动长串时转移指针并将源对象重置为空。比较 `abc` 和 `abcd`：共同前缀相同，短串较小。

C++ 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <new>
#include <stdexcept>

// Training implementation: 127 bytes plus '\0' fit in the inline buffer.
class SmallString {
public:
    static constexpr std::size_t buffer_size = 128;

    SmallString(const char* data, std::size_t length) : length_(length) {
        if (data == nullptr && length != 0) throw std::invalid_argument("null data");
        if (length >= buffer_size) {
            if (length == static_cast<std::size_t>(-1)) throw std::length_error("too long");
            pointer_ = static_cast<char*>(std::malloc(length + 1));
            if (pointer_ == nullptr) throw std::bad_alloc();
            std::memcpy(pointer_, data, length);
            pointer_[length] = '\0';
        } else {
            if (length != 0) std::memcpy(buffer_, data, length);
            buffer_[length] = '\0';
        }
    }

    SmallString(const SmallString& other) : SmallString(other.data(), other.length_) {}

    SmallString& operator=(const SmallString& other) {
        if (this != &other) {
            SmallString copy(other);
            swap(copy);
        }
        return *this;
    }

    SmallString(SmallString&& other) noexcept : length_(other.length_), pointer_(other.pointer_) {
        std::memcpy(buffer_, other.buffer_, buffer_size);
        other.length_ = 0;
        other.pointer_ = nullptr;
        other.buffer_[0] = '\0';
    }

    SmallString& operator=(SmallString&& other) noexcept {
        if (this != &other) {
            std::free(pointer_);
            std::memcpy(buffer_, other.buffer_, buffer_size);
            length_ = other.length_;
            pointer_ = other.pointer_;
            other.length_ = 0;
            other.pointer_ = nullptr;
            other.buffer_[0] = '\0';
        }
        return *this;
    }

    ~SmallString() { std::free(pointer_); }

    const char* data() const noexcept { return pointer_ ? pointer_ : buffer_; }
    std::size_t size() const noexcept { return length_; }

    int compare(const SmallString& other) const noexcept {
        const std::size_t common = std::min(length_, other.length_);
        const int prefix = std::memcmp(data(), other.data(), common);
        if (prefix != 0) return prefix;
        return length_ < other.length_ ? -1 : (length_ > other.length_ ? 1 : 0);
    }

    void swap(SmallString& other) noexcept {
        if (this == &other) return;
        for (std::size_t i = 0; i < buffer_size; ++i) std::swap(buffer_[i], other.buffer_[i]);
        std::swap(length_, other.length_);
        std::swap(pointer_, other.pointer_);
    }

private:
    char buffer_[buffer_size]{};
    std::size_t length_ = 0;
    char* pointer_ = nullptr;
};

复杂度

长度 L 的构造和深拷贝时间 O(L)，长串额外堆空间 O(L)、短串无单独堆分配；移动长串在理论上可只转移指针，但此示例为保持统一对象不变量还复制固定 128 字节，故相对 L 为 O(1)。compare 最坏 O(min(L₁,L₂))。对象尺寸与对齐取决于 ABI，不能从字段字节数直接推断。

易错点与追问

容易失分的边界

• 把 `strncpy` 与 `memcpy` 说成完全等价：前者遇源 NUL 后可能补零，后者精确复制指定字节数；这里有显式长度，所以用 memcpy 再自己写终止符。
• 只写长串 malloc 而不写析构和复制语义，会泄漏或双重释放；只补析构仍不够。
• 把 `len=128` 错放进 128 字节 buf，终止符越界。
• 把短串快归因于唯一的 CPU 缓存原因；实际结果还受长度、分配、分支和数据分布影响。
• 以 union 复用 buf 与指针时忽略活跃成员、对齐和状态位；这个优化必须重新证明对象不变量。

继续深挖

• 若要求更小的对象，比较 union/带标记表示与 std::string 的实现思路，并实测 sizeof、分配与吞吐。
• 若增加 concat/substr，先定义容量与异常语义、内嵌 NUL 和返回所有权，再检查相同对象参与操作时的别名问题。
• 若面试官问对象大小，按实际编译器的 sizeof、alignof 与字段偏移解释 padding；不同平台不能套用固定答案。