この実装は高速である必要があります。
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;
}
3 つの単体テストすべてに合格します。
GNU libstdc++ を使用する場合、libstdc++ はグローバルな「空の文字列」変数を使用するため、宣言と初期化を行う行retは非常に高速です。したがって、これは単にポインタのコピーです。およびの const バージョンに解決されるため、beginおよびendの呼び出しsも高速です。したがって、の内部表現は「リーク」しません。libstdc++ では、ポインタ型でランダム アクセス イテレータである is があります。したがって、入力範囲の長さを取得するために呼び出す場合、それはポインタ差分演算です。また、結果は. 最後に、操作により、戻り値に十分なメモリが使用できることが保証されます。beginendbegin() constend() constsstd::string::const_iteratorconst char*std::string::append<const char*>(const char*, const char*)std::distancestd::string::append<const char*>(const char*, const char*)memmovereserve
編集: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 で 4 つのバリアントをテストしました。
バリアント 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 は 2 番目です (バリアント 4 より 5% 遅い)
- バリアント 1 は 3 番目です (バリアント 3 より 2% 遅い)
- バリアント 2 は 4 番目です (バリアント 1 より 0.2% 遅い)
VC++ 16.00.30319.01 の結果は次のとおりです。
- バリアント 1 が最速
- バリアント 2 が 2 位 (バリアント 1 より 3% 遅い)
- バリアント 4 は 3 番目です (バリアント 2 より 4% 遅い)
- バリアント 3 は 4 番目です (バリアント 4 より 17% 遅い)
当然のことながら、最速のバリアントはコンパイラによって異なります。ただし、どのコンパイラが使用されるかはわかりませんが、C++ の使い慣れたスタイルであり、g++ を使用すると最速であり、VC++ を使用するとバリアント 1 または 2 よりもそれほど遅くないため、私のバリアントが最適であると思います。
VC++ の結果から興味深いことの 1 つは、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;
}
sの開始イテレータと終了イテレータが保存されることを除いて、バリアント 4 と同じです。
バリアント 5 をテストしたところ、VC++ を使用すると、実際にはバリアント 2 (データ文字列のバリアント) よりも優れています。
- バリアント 1 が最速
- バリアント 5 は 2 番目です (バリアント 1 より 1.6% 遅い)
- バリアント 2 は 3 番目です (バリアント 5 より 1.4% 遅い)
- バリアント 4 は 3 番目です (バリアント 2 より 4% 遅い)
- バリアント 3 は 4 番目です (バリアント 4 より 17% 遅い)