Когда вы работаете со строками, нередко возникают задачи склеить много строк или просто надобавлять их в конец. Также нередко вы знаете заранее размер финальной строки. И никогда по перформансу невыгодно добавлять строки по одной, в итоге будет достаточно много реаллокаций.

К сожалению, сейчас в С++ нет максимально быстрого способа поджойнить строки, чтобы не платить оверхеда. И по-моему сейчас нет ни в одном языке библиотечной поддержки так делать:

Одни скажут, что можно сделать reserve и сделать append, но тогда append будет каждый раз проверять на то, нужно ли расширять буффер, будет добавлять нулевой байтик в конец, потому что строки в С++ заканчиваются нулевым байтом и будут обновлять размер:

std::string GeneratePattern(const std::string& pattern, size_t count) {
   std::string ret;
   ret.reserve(pattern.size() * count);
   for (size_t i = 0; i < count; i++) {
     // SUB-OPTIMAL:
     // * Writes 'count' nulls
     // * Updates size and checks for potential resize 'count' times
     ret.append(pattern);
   }
   return ret;
}

Другие скажут, что можно сделать resize и потом memcpy, но, к сожалению, resize должен как-то проинициализировать память, поэтому будет лишний memset:

std::string GeneratePattern(const std::string& pattern, size_t count) {
   std::string ret;
   const auto step = pattern.size();
   // SUB-OPTIMAL: We memset step*count bytes
   // only to overwrite them.
   ret.resize(step * count);
   for (size_t i = 0; i < count; i++) {
     // GOOD: No bookkeeping
     memcpy(ret.data() + i * step, pattern.data(), step);
   }
   return ret;
}

В итоге стандартные библиотеки имеют незадокументированную функцию __resize_default_init, которая просто аллоцирует сырые неинициализированные байты, в которые можно копировать. Abseil это использует для Join строк, а вот в Яндексе делается reserve и добавляется appendом. Тут винить некого, так просто получилось, что интерфейс "выделить сырую память и проинициализировать тем, чем надо" сложно выражется через обычные примитивы строк.

В C++ на этой неделе, надеюсь, примут в C++23 resize_default_init, который исправляет эту проблему. Синтаксис получается функциональный немного, вызывается callback, который должен заполнять байты выделенной строки, чтобы ни в какой момент времени не оставлять строку неинициализированной, возвращаемое значение отвечает за столько байт, сколько останется в строке в итоге.

ret.resize_default_init(step * count, [&](char* buf, size_t n) {
     for (size_t i = 0; i < count; i++) {
       // GOOD: No bookkeeping
       memcpy(buf + i * step, pattern.data(), step);
     }
     return step * count; // must be <=n, in that case ==n.
 });

[1] P1072 пропозал для стандарта
[2] Abseil resize uninitialized
[3] Abseil join
[4] Yandex join
[5] __resize_default_init в LLVM

Иногда так бывает, что асимптотика решения задачи зависит от количества делителей числа во входе. Когда я только начинал заниматься спортивным программированием, я несколько раз слышал такое утверждение: «количество делителей числа n — это примерно кубический корень из n». И с самого начала я относился к этому факту с подозрением: неужели у чисел может быть так много делителей?

На самом деле, это, конечно, не так, но оценка в кубический корень дает нужный порядок величин для грубых оценок на числах, с которыми мы имеем дело в реальной жизни (отличие не больше, чем в 4 раза при n ≤ 10^15, и не больше, чем в 10 раз при n ≤ 10^18). Давайте разберемся, сколько все таки на самом деле делителей у чисел, и как этим пользоваться, а также придумаем новую более точную оценку.

https://telegra.ph/Ocenka-na-kolichestvo-delitelej-chisla-09-10