面试题：C++字符串常量拼接与性能优化

Question

假设你有一系列字符串常量需要拼接成一个长字符串，在性能优先的场景下，使用`ostringstream`和`string`的`append`方法进行拼接，哪种方式更优？请通过代码示例说明原因，并分析拼接过程中的时间复杂度和空间复杂度。

Answer 1

在性能优先的场景下，ostringstream通常更优。

代码示例

#include <iostream>
#include <sstream>
#include <string>
#include <chrono>

// 使用append方法
std::string appendMethod() {
    std::string result;
    std::string str1 = "Hello";
    std::string str2 = ", ";
    std::string str3 = "world!";
    result.append(str1);
    result.append(str2);
    result.append(str3);
    return result;
}

// 使用ostringstream
std::string ostringstreamMethod() {
    std::ostringstream oss;
    std::string str1 = "Hello";
    std::string str2 = ", ";
    std::string str3 = "world!";
    oss << str1 << str2 << str3;
    return oss.str();
}

原因分析

1. 内存分配策略：
   • string的append方法：每次调用append时，如果当前string的容量不足以容纳新的内容，就会重新分配内存，导致数据复制。多次append可能会引发多次内存分配和数据复制，这在性能上开销较大。
   • ostringstream：ostringstream内部维护一个缓冲区，它会在缓冲区满时一次性分配更大的内存空间，而不是每次添加新内容都重新分配。这样减少了内存分配的次数，从而提高性能。

时间复杂度分析

1. string的append方法：假设每次append时都需要重新分配内存，每次重新分配内存和复制数据的时间复杂度为$O(n)$，如果有$k$次append操作，每次append的字符串长度为$n_i$，总的时间复杂度为$O(\sum_{i = 1}^{k} i \cdot n_i)$，平均情况下接近$O(n^2)$，其中$n = \sum_{i = 1}^{k} n_i$。
2. ostringstream：ostringstream内部缓冲区增长策略相对高效，假设缓冲区每次增长$m$个字符，总共拼接$n$个字符，那么最多需要增长$\lceil \frac{n}{m} \rceil$次，每次增长复制数据的时间复杂度为$O(n)$，总的时间复杂度接近$O(n)$。

空间复杂度分析

1. string的append方法：空间复杂度为$O(n)$，$n$为最终拼接后字符串的长度，因为需要存储最终的字符串。但是由于可能多次重新分配内存，实际占用空间可能会大于$n$。
2. ostringstream：空间复杂度同样为$O(n)$，$n$为最终拼接后字符串的长度，虽然内部缓冲区可能会分配比实际需要大一些的空间，但总体也是线性的空间复杂度。

综上所述，在性能优先的场景下，ostringstream在时间复杂度上更优，因此是更好的选择。