Добавление символа char в начало строки приводит к превышению лимита памяти - PullRequest
Новая
       40

Добавление символа char в начало строки приводит к превышению лимита памяти

0 голосов
/ 20 марта 2020

При выполнении задачи кодирования, скажем, у меня есть string s из length 50000

Я создаю другую строку на основе некоторых ограничений.

Ниже код дает мне результат . 

string res = "";

for(int i = 0; i < s.length(); i++)
{
    if(/* some constraint satisfied */)
    {
        res += s[i];
    }
}

Ниже кода выдается Memory Limit Exceeded на Online Judge. 

string res = "";

for(int i = s.length() - 1; i >= 0; i--)
{
    if(/* some constraint satisfied */)
    {
        res = s[i] + res;
    }
}
  1. Создает ли он новую строку каждый раз во втором случае?

  2. Если да, то как я могу избежать этого при повторении в обратном направлении.

  3. Нужно ли резервировать память в самом начале?

  4. Если да, какой размер должен быть?

Любая помощь будет высоко оценена.

1 Ответ

0 голосов
/ 20 марта 2020

Вторая версия очень неэффективна, поскольку вставка символа в начале длинной строки многократно означает, что все символы должны быть сдвинуты на одно место. Более того, res += s[i] может использовать свободную емкость в буфере res (строки увеличивают свой размер при превышении их емкости, так что повторная вставка в конце не требует перераспределения памяти каждый раз), тогда как res = s[i] + res всегда выделяет новую строку и переместите строку в res.

Вместо того, чтобы выкатывать свой собственный l oop и делать много ошибок (неправильный тип индекса, использование неоптимального оператора приращения / уменьшения, ошибка переноса ), используйте std::copy_if (определено в заголовке <algorithm>) вместе с std::back_inserter (определено в заголовке <iterator> ): 

std::string result;
std::copy_if(source.begin(), source.end(), std::back_inserter(result),
             [](char c) {
                 return /* constraint */;
             });

Вы также можете использовать reserve, если вы знаете приблизительное количество символов, которые заранее удовлетворяют критерию.

...