Неявно квадратичный алгоритм

[_winnie]

vector v;
for (int i = 0; i < 1000*1000; ++i) {
v.reserve(v.size() + 10);
v.push_back(i);
}

Если удалить строчку с reserve, то отрабатывает за долю секунды, с reserve - зависает на 5 минут.

Comments

[strangeraven]

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

[antonz]

Ну такое писать это ж совсем факап. Так что пример достаточно академический.

[_winnie]

Это минимальный пример. Типичный пример из "промышленного кода", сплошь и рядом в любой большой кодобазе -

class Data {
std::vector data;

void AddMoreData(char *p, size_t n) {
data.reserve(data.size() + n);
for (size_t i = 0; i < n; ++i) {
if (p[i] != 'x') {
data.push_back(p[i]);
}
}
}
};
..............

Data data;
for (каждая строка LINE из файла) {
data.AddMoreData(LINE.c_str(), LINE.size());
}

[antonz]

Да, такое неявное использование может быть много где. Хотя опытный разработчик класса Data предусмотрит дополнительное резервирование отдельным методом, а вызывающий зарезервирует хотя бы под размер файла (тут конечно хорошо если его можно получить, хехе).

P.S. Я ж надеюсь правильно помню, что холостой reserve() достаточно дешевый и не вызывает реаллокейтов?

[aamonster]

Правильно, я пролистал доку.
Но, если я правильно понял, он имеет право резервировать и больше, чем ему сказали, так что в другой реализации вектора проблем может и не оказаться.
Интереснее, что push_back гарантирует константное амортизированное время - я привык на такое не закладываться и сам удваивать размер массива при необходимости.

[sergegers1]

Как правило, реализация удваивает capacity, когда заканчивается место.

[_winnie]

В случае resize - да, reserve - нет. Чем и коварен.

[_winnie]

Про удвоение - некоторые библиотеки выбирает не удвоение, а умножение на 1.5, так как 1.5 чуть меньше чем золотое сечение, и позволяет переиспользовать освобожденную память ( https://crntaylor.wordpress.com/2011/07/15/optimal-memory-reallocation-and-the-golden-ratio/ )

[sergegers1]

Это да. Читал когда-то.

[sergegers1]

Ну вот по дефолту он и удваивает. Я ни разу не вызывал reserve(), и есть очень мало случаев, когда это могло бы понадобиться.

[aruslan]

Грустный код. Вижу такое второй раз - вроде бы zeux такую же подставу показывал в роблокоде.
Мой вывод - не надо говорить людям, что есть reserve, они от этого плохо спят, пишут всякое стыдное, пухнут и не дохнут.