C++字符串面试题

Question

我最近参加了一次 C++ 技术面试，在那里我得到了一些简单的字符串操作代码，该代码旨在获取一个字符串并返回一个由第一个和最后一个 n 个字符组成的字符串，然后继续为了更正任何错误并使功能尽可能高效，我想出了下面的解决方案，但是面试官声称有一个更快更优化的方法:

原码:

std::string first_last_n(int n, std::string s)
{
   std::string first_n = s.substr(0,n);
   std::string last_n = s.substr(s.size()-n-1,n);
   return first_n + last_n;
}

我的代码:

bool first_last_n(const std::size_t& n, const std::string& s, std::string& r)
{
   if (s.size() < n)
      return false;
   r.reserve(2 * n);
   r.resize(0);
   r.append(s.data(),s.data() + n);
   r.append(s.data() + (s.size() - n), s.data() + s.size());
   return true;
}

我的更改总结:

• 更改了接口(interface)以将返回字符串作为引用(假设 RVO 和右值尚不可用)

• 移除了正在通过 substr 构造的临时字符串

• 将输入字符串作为常量引用传递，以绕过输入的临时实例化

• 修复了 last_n 字符串中的 off-by-1 错误

• 将每个角色的触地次数减少到一次或两次(在重叠场景的情况下)

• 在字符串 s 的大小小于 n 的情况下进行检查，失败返回 false。

假设只允许使用 native C++，是否有其他方法可以更有效或最佳地完成上述操作？

注1:原始输入字符串实例不可修改。

注意2:所有解决方案必须通过以下测试用例，否则无效。

void test()
{
   {
      std::string s = "0123456789";
      std::string r = first_last_n(10,s);
      assert(r == "01234567890123456789");
   }

   {
      std::string s = "0123456789ABC0123456789";
      std::string r = first_last_n(10,s);
      assert(r == "01234567890123456789");
   }

   {
      std::string s = "1234321";
      std::string r = first_last_n(5,s);
      assert(r == "1234334321");
   }

}

Answer 1

这个实现应该很快:

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
    n = std::min(n, s.size());
    std::string ret;
    ret.reserve(2*n);
    ret.append(s.begin(), s.begin() + n);
    ret.append(s.end() - n, s.end());
    return ret;
}

它 passes all three unit tests .

使用 GNU libstdc++ 时，声明和初始化 ret 的行非常快，因为 libstdc++ 使用全局“空字符串”变量。因此，它只是一个指针拷贝。调用 begin和 end在 s也很快，因为它们将解析为 begin 的 const 版本和 end , begin() const和 end() const ，所以s的内部表示没有“泄露”。使用 libstdc++，std::string::const_iterator是 const char* ，这是一个指针类型和随机访问迭代器。因此，当 std::string::append<const char*>(const char*, const char*)来电 std::distance 获取输入范围的长度，是指针差分运算。另外，std::string::append<const char*>(const char*, const char*)结果类似于 memmove .最后，reserve操作确保有足够的内存可用于返回值。

编辑: 出于好奇，这里是 ret 的初始化在 MinGW g++ 4.5.0 的汇编输出中:

    movl    $__ZNSs4_Rep20_S_empty_rep_storageE+12, (%ebx)

它只是将指针复制到全局“空表示”。

EDIT2: 好的。我现在已经使用 g++ 4.5.0 和 Visual C++ 16.00.30319.01 测试了四个变体:

变体 1(“c_str 变体”):

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
   std::string::size_type s_size = s.size();
   n = std::min(n, s_size);
   std::string ret;
   ret.reserve(2*n);
   const char *s_cStr = s.c_str(), *s_cStr_end = s_cStr + s_size;
   ret.append(s_cStr, s_cStr + n);
   ret.append(s_cStr_end - n, s_cStr_end);
   return ret;
}

变体 2(“数据字符串”变体):

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
   std::string::size_type s_size = s.size();
   n = std::min(n, s_size);
   std::string ret;
   ret.reserve(2*n);
   const char *s_data = s.data(), *s_data_end = s_data + s_size;
   ret.append(s_data, s_data + n);
   ret.append(s_data_end - n, s_data_end);
   return ret;
}

变体 3:

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
   std::string::size_type s_size = s.size();
   n = std::min(n, s_size);
   std::string ret(s);
   std::string::size_type d = s_size - n;
   return ret.replace(n, d, s, d, n);
}

变体 4(我的原始代码):

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
   n = std::min(n, s.size());
   std::string ret;
   ret.reserve(2*n);
   ret.append(s.begin(), s.begin() + n);
   ret.append(s.end() - n, s.end());
   return ret;
}

g++ 4.5.0 的结果是:

• 变体 4 是最快的
• 变体 3 次之(比变体 4 慢 5%)
• 变体 1 排在第三位(比变体 3 慢 2%)
• 变体 2 排在第四位(比变体 1 慢 0.2%)

VC++ 16.00.30319.01 的结果是:

• 变体 1 是最快的
• 变体 2 次之(比变体 1 慢 3%)
• 变体 4 排在第三位(比变体 2 慢 4%)
• 变体 3 排在第四位(比变体 4 慢 17%)

不出所料，最快的变体取决于编译器。但是，不知道会使用哪个编译器，我认为我的变体是最好的，因为它是熟悉的 C++ 风格，使用 g++ 时速度最快，使用 VC++ 时也不比变体 1 或 2 慢多少。

VC++ 结果中有趣的一点是，使用 c_str而不是 data是比较快的。也许这就是为什么你的面试官说有比你的实现更快的方法。

EDIT3:

其实我只是想到了另一种变体:

变体 5:

inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
   n = std::min(n, s.size());
   std::string ret;
   ret.reserve(2*n);
   std::string::const_iterator s_begin = s.begin(), s_end = s.end();
   ret.append(s_begin, s_begin + n);
   ret.append(s_end - n, s_end);
   return ret;
}

它和变体 4 一样，只是 s 的开始和结束迭代器不同。已保存。

当测试变体 5 时，它实际上在使用 VC++ 时击败了变体 2(数据字符串变体):

• 变体 1 是最快的
• 变体 5 次之(比变体 1 慢 1.6%)
• 变体 2 排在第三位(比变体 5 慢 1.4%)
• 变体 4 排在第三位(比变体 2 慢 4%)
• 变体 3 排在第四位(比变体 4 慢 17%)