面试题：C++ 字符串函数高级难度题

Question

假设有一个自定义的字符串类 `MyString`，其中包含一个 `char*` 类型的成员变量来存储字符串。请实现一个 `append` 成员函数，功能类似 `std::string` 的 `append` 方法，在处理字符串连接时需要考虑内存管理以及不同类型（如 `const char*`、`MyString` 对象）作为参数的情况，并分析可能出现的性能问题及优化方式。

Answer 1

1. 实现 MyString 类及 append 函数

#include <iostream>
#include <cstring>

class MyString {
private:
    char* str;
    size_t length;

public:
    // 构造函数
    MyString(const char* s = nullptr) {
        if (s == nullptr) {
            length = 0;
            str = new char[1];
            str[0] = '\0';
        } else {
            length = std::strlen(s);
            str = new char[length + 1];
            std::strcpy(str, s);
        }
    }

    // 析构函数
    ~MyString() {
        delete[] str;
    }

    // 拷贝构造函数
    MyString(const MyString& other) {
        length = other.length;
        str = new char[length + 1];
        std::strcpy(str, other.str);
    }

    // 赋值运算符重载
    MyString& operator=(const MyString& other) {
        if (this != &other) {
            delete[] str;
            length = other.length;
            str = new char[length + 1];
            std::strcpy(str, other.str);
        }
        return *this;
    }

    // append 函数，接受 const char* 作为参数
    MyString& append(const char* s) {
        size_t newLength = length + std::strlen(s);
        char* newStr = new char[newLength + 1];
        std::strcpy(newStr, str);
        std::strcat(newStr, s);
        delete[] str;
        str = newStr;
        length = newLength;
        return *this;
    }

    // append 函数，接受 MyString 对象作为参数
    MyString& append(const MyString& other) {
        return append(other.str);
    }

    // 输出函数
    void print() const {
        std::cout << str << std::endl;
    }
};

2. 性能问题分析

• 频繁内存分配和释放：每次调用 append 函数时，都会重新分配内存并释放旧内存，这会导致频繁的系统调用，增加时间开销。例如，多次调用 append 连接短字符串时，这种开销会比较明显。
• 数据拷贝开销：在新内存中拷贝原字符串和要追加的字符串也会消耗时间，特别是对于长字符串。

3. 优化方式

• 预分配足够内存：可以预先估计最终字符串的长度，一次性分配足够的内存，减少内存分配和释放的次数。例如，可以在类中增加一个 reserve 函数，用户可以提前调用该函数分配足够内存。

void reserve(size_t newCapacity) {
    if (newCapacity > length) {
        char* newStr = new char[newCapacity + 1];
        std::strcpy(newStr, str);
        delete[] str;
        str = newStr;
    }
}

• 使用更高效的字符串拼接算法：例如，使用 std::string 内部的优化算法，或者采用 std::vector<char> 来管理字符串，利用其动态增长特性减少内存重新分配的次数。

// 示例使用 std::vector<char> 优化
class MyStringOptimized {
private:
    std::vector<char> data;

public:
    MyStringOptimized(const char* s = nullptr) {
        if (s) {
            data.assign(s, s + std::strlen(s));
            data.push_back('\0');
        } else {
            data.push_back('\0');
        }
    }

    MyStringOptimized& append(const char* s) {
        size_t oldSize = data.size() - 1;
        size_t appendSize = std::strlen(s);
        data.resize(oldSize + appendSize + 1);
        std::strcpy(&data[oldSize], s);
        data.back() = '\0';
        return *this;
    }

    MyStringOptimized& append(const MyStringOptimized& other) {
        return append(other.data.data());
    }

    void print() const {
        std::cout << data.data() << std::endl;
    }
};

这种方式利用 std::vector<char> 的动态增长机制，减少了内存重新分配的次数，提高了性能。