Сравнение эффективности str.erase () в C ++

Question

Предположим, строка содержит много ведущих пробельных символов.Моя задача - удалить эти символы.

Я думаю об этом:

while(1) {
    if(str[i] == ' ')
        str.erase(str.begin()+i);
    else
        break;
}

Будет ли это O (1) за операцию или больше, чем O (n)?Я читал во многих блогах, что мы не должны стирать один элемент, потому что вся строка может быть скопирована в другое место для поддержания непрерывного выделения памяти.

Тогда как насчет этого вида стирания:

while(1) {
    if(str[i] == ' '){
        cnt++;
        break; 
    }
}
str.erase(0, cnt);

Какой из них лучше?

Answer 1

Первый пример довольно неэффективен. erase перемещает все элементы за точку стирания вниз, чтобы заполнить пространство, которое создает erase; этот код заканчивает тем, что копирует все более поздние элементы строки один раз для каждого начального пробела . Второй пример не выполняет то, о чем спрашивает вопрос, потому что оператор break рано выходит из цикла. Но подход во втором намного лучше. В общем, если вы звоните erase более одного раза, вы, вероятно, ошиблись. Гораздо лучше найти первого персонажа, которого вы хотите сохранить, и , а затем удалите все символы перед ним. Итак:

std::string::size_type pos = str.find_first_not_of(' ');
if (pos != std::string::npos)
    str.erase(0, pos);

Answer 2

Поскольку вы хотите удалить только начальные пробелы, лучше всего будет выполнить алгоритм, подобный двоичному поиску, чтобы найти первый не-пробел в O (log (N)). Это, я считаю, может быть сделано с умным использованием std::upper_bound. Затем удалите диапазон [0, result) из строки.