Реализация std :: string и шаблоны выражений
Кажется, что std :: string — потому что он не использует шаблоны выражений — имеет сложность O (n ^ 2) вместо, возможно, сложности O (n) для некоторых операций, таких как конкатенация. То же самое с классом std :: stringstream, когда вам нужно вставить много элементов.
Я хотел бы понять это, по крайней мере, если бы кто-то мог иметь хорошие ссылки по этому вопросу, это было бы здорово.
Решение
Объединение нескольких строк вместе имеет разные сложности в C ++ в зависимости от того, как это делается. Я считаю, что ситуация, о которой вы думаете, такова:
string result = string("Hello, ") + username + "! " +
"Welcome to " + software_product + ".";
который объединяет 6 строк. Первая строка копируется 5 раз, вторая — 4 раза и т. Д. Как Леонид Вольницкий отмечает в своем ответе точную оценку этого Θ (NM), где M — число операций конкатенации, а N — общая длина конкатенируемых строк. Мы также можем назвать это O (N ^ 2), когда M <= N. Обратите внимание, что не гарантируется, что M <= N, потому что вы можете увеличить M, не увеличивая N, пытаясь объединить пустую строку.
Шаблоны выражений могут помочь ускорить этот вариант использования, хотя это может вызвать проблемы с auto а также decltype вывод типов в C ++ 11, а также вывод типов в C ++ 98. Все это выведет тип
auto result = string("Hello, ") + username + "! " +
"Welcome to " + software_product + ".";
быть лениво оцененным типом строкового шаблона, который использовался для создания магии шаблона выражения. Другие причины, почему шаблоны выражений не являются отличной идеей, включают Леонид Вольницкийответ об этом замедлении времени компиляции. Вероятно, это также увеличит размер вашего скомпилированного двоичного файла.
Вместо этого есть другие решения в C ++, которые можно использовать для конкатенации Θ (N):
string result = "Hello, ";
result += username;
result += "! ";
result += "Welcome to ";
result += software_product;
result += ".";
В этой версии строка модифицируется на месте, и в то время как данные, которые уже были скопированы в result иногда необходимо восстановить, строки C ++ обычно реализуются как динамические массивы которые выделяют новое пространство экспоненциально, так что вставка каждого нового символа занимает амортизированное постоянное время, что приводит к общему поведению Θ (N) для повторной конкатенации.
Ниже приведен способ сделать то же самое, почти в одной строке. Он использует тот же принцип внутри, но также поддерживает преобразование нестроковых типов в строки, используя << перегрузка.
stringstream result;
result << "Hello, " << username << "! " << "Welcome to " << software_product
<< ".";
// do something with result.str()
Наконец, стандартная библиотека C ++ не включает это, но можно определить следующую функцию с некоторой магией потока строк внутри нее. Реализация оставлена в качестве упражнения для читателя.
template <typename... Items>
std::string concat(std::string const& a, std::string const& b, Items&&... args)
Вы можете позвонить concat для повторного объединения в одну строку за O (N) время:
string result = concat("Hello, ", username, "! ", "Welcome to ",
software_product, ".");
Предположительно, все они являются лучшими решениями, чем путаница с выводом типа путем создания типа шаблона выражения.
Другие решения
Если у нас есть общая длина строки выражения N, а также M операции конкатенации, то сложность должна быть O(NM),
Определенно возможно ускорить его с помощью шаблонов выражений. Это не было сделано, вероятно, из-за их сложности. Скорость компиляции тоже будет медленнее — для этого потребуются M-рекурсивные типы.
Мне трудно поверить, что конкатенация O(n^2), но здесь идет некоторый ответ, связанный с вашим вопросом:
Стандарт C ++ не определяет детали реализации, а только
определяет требования к сложности в некоторых случаях. Единственная сложность
требования к операциям std :: string: size (), max_size (),
operator [], swap (), c_str () и data () имеют постоянное время.
Сложность чего-либо еще зависит от выбора, сделанного кем бы то ни было
реализовал библиотеку, которую вы используете.
Смотрите ссылку: C ++ строка :: найти сложность
Как это может быть O (N ^ 2)? Конкатенация строк:
- перераспределение при необходимости (постоянное амортизированное время);
- поиск конца первой строки (постоянное время, так как они считаются строкой);
- копия символа из второй строки (O (N)).
Я не понимаю, как шаблоны могут иметь к этому какое-то отношение.
detector