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;
}

我的更改摘要:

• 更改接口以获取返回字符串作为参考(假设RVO和rvalues尚不可用)

• 删除了通过substr构造的临时字符串

• 将输入字符串作为const引用传递,以便绕过输入的临时实例化

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

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

• 在字符串s的大小小于n的情况下放置一个检查,对于失败返回false.

假设只允许本机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;
}

它通过了所有三个单元测试.

使用GNU libstdc ++时,声明和初始化的行ret非常快,因为libstdc ++使用全局"空字符串"变量.因此,它只是一个指针副本.拨打begin和end上s还快,因为它们将解析到的常量版本begin和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操作确保有足够的内存可用于返回值.

编辑: 对于好奇,这里是retMinGW 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%)

Answer 2

如果不需要保留原始字符串的内容，则可以将最后 n 个字符复制到[n+1, 2n]原始字符串的位置并在 处截断2n。您必须首先小心地扩展字符串，并且如果字符串短于 ，则在写入之前要小心不要覆盖任何字符2n。

这将使构造字符串的操作数量减半，并且无需创建新字符串。所以理论上它的速度要快 2 到 4 倍。当然，你刚刚破坏了原始字符串，你必须询问面试官是否可以接受。