Эта реализация должна быть быстрой:
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 обеспечивает наличие достаточного объема памяти для возвращаемого значения.
EDIT:
Для любопытных вот инициализация 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 - второй (на 5% медленнее, чем вариант 4)
- Вариант 1 третий (на 2% медленнее, чем вариант 3)
- Вариант 2 четвертый (на 0,2% медленнее, чем вариант 1)
Результаты для VC ++ 16.00.30319.01:
- Вариант 1 самый быстрый
- Вариант 2 - второй (на 3% медленнее, чем вариант 1)
- Вариант 4 третий (на 4% медленнее, чем вариант 2)
- Вариант 3 - четвертый (на 17% медленнее, чем вариант 4)
Неудивительно, что самый быстрый вариант зависит от компилятора. Однако, не зная, какой компилятор будет использоваться, я думаю, что мой вариант лучше, потому что это знакомый стиль C ++, он самый быстрый при использовании g ++, и он не намного медленнее, чем варианты 1 или 2 при использовании VC ++.
Из результатов 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, он на самом деле превосходит вариант 2 (вариант строки данных) при использовании VC ++:
- Вариант 1 самый быстрый
- Вариант 5 - второй (на 1,6% медленнее, чем вариант 1)
- Вариант 2 третий (на 1,4% медленнее, чем вариант 5)
- Вариант 4 - третий (на 4% медленнее, чем вариант 2)
- Вариант 3 - четвертый (на 17% медленнее, чем вариант 4)