C++中是否存在类似Python ''.join()的O(n)时间复杂度字符串拼接方法？

当然有啦！就像Python里的''.join()能以*O(n)的高效复杂度拼接字符串列表一样，C++里也有不少靠谱的方案，能避开直接用+=拼接可能带来的O(n²)*时间开销——毕竟每次+=要是遇到字符串容量不够，就得重新分配内存、拷贝旧数据，次数多了效率肯定拉胯。

下面是几种常用的高效实现方式：

• 提前预留空间 + 逐次追加
  这是最直接的优化思路：先算出所有待拼接字符串的总长度，用std::string::reserve()一次性分配足够的内存，之后再用append()或者+=逐个追加内容。这样全程只会触发一次内存分配，整体时间复杂度稳定在O(n)。

  代码示例：

  #include <string>
  #include <vector>
  
  std::string join(const std::vector<std::string>& strs) {
      std::string result;
      // 计算所有字符串的总长度
      size_t total_len = 0;
      for (const auto& s : strs) {
          total_len += s.size();
      }
      // 一次性预留足够内存
      result.reserve(total_len);
      // 逐个追加字符串
      for (const auto& s : strs) {
          result += s;
          // 也可以用 result.append(s); 效果一致
      }
      return result;
  }
  

• 使用std::stringstream
  如果你需要混合拼接不同类型的数据（比如字符串和数字），std::stringstream会是个很方便的选择。它内部会自动管理缓冲区，增长策略也比较高效，单纯拼接字符串列表时，性能和上面的方法差不多，但代码更简洁：

  代码示例：

  #include <string>
  #include <vector>
  #include <sstream>
  
  std::string join(const std::vector<std::string>& strs) {
      std::stringstream ss;
      for (const auto& s : strs) {
          ss << s;
      }
      return ss.str();
  }
  

• C++20及以上：用范围库的std::views::join
  C++20引入的范围库（Ranges）带来了更简洁的写法：std::views::join可以把字符串列表“扁平化”成一个连续的字符范围，直接用这个范围构造std::string即可，底层同样是先分配足够内存再一次性拷贝，效率拉满：

  代码示例：

  #include <string>
  #include <vector>
  #include <ranges>
  
  std::string join(const std::vector<std::string>& strs) {
      return std::string(strs | std::views::join);
  }
  

最后再提一句：直接用+=循环拼接之所以会出现*O(n²)*的复杂度，是因为每次容量不足时都会触发内存重分配和旧数据拷贝。比如拼接n个长度为k的字符串，最坏情况下拷贝的总数据量是k + 2k + ... + (n-1)k，这就导致了平方级的时间开销。而上面的方法都通过预分配内存或者高效的缓冲区管理，避免了这种频繁拷贝的问题。

内容的提问来源于stack exchange，提问作者Bjorn Lom