Вопрос о производительности контейнера C ++

Question

Что может иметь лучшую производительность, вектор stl или динамический массив, который просто realloc'd каждый раз, когда я хочу что-то добавить к нему?

Было бы быстрее использовать vectors :: iterator, чем цикл forна массиве?

И если бы кто-то мог объяснить, почему, это было бы здорово.

Answer 1

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

источник: Исходное изображение от Jameson Williams

Однажды вам, возможно, потребуется интенсивная оптимизация и использование динамического массива, но это должно быть редкостью .... однажды вам также понадобятся коллекции, которые являются многопоточными безопасными ... и так далее ... но в целом стандартнымконтейнеры - это путь.

Answer 2

Что могло бы иметь лучшую производительность, вектор stl или динамический массив, который просто realloc'd каждый раз, когда я хочу что-то добавить к нему?

Векторы Stl имеют вставку в амортизированное постоянное время (поскольку перераспределение выполняется не все время, а резервирование происходит с коэффициентом 1,5 (минимум)).

Поэтому, согласно вашему описанию, векторы будут значительно быстрее, чем перераспределение все время

Будет ли использование vectors :: iterator быстрее, чем использование цикла for в массиве?

В общем случае: точно так же.Однако некоторые реализации STL генерируют проверки в режиме отладки, которые могут значительно замедлить использование контейнерных итераторов.

(обратите внимание, что большинство реализаций реализуют итераторы вектора / строки как typedef для value_type*)

Иесли бы кто-то мог объяснить почему, это было бы здорово.

Answer 3

Что могло бы иметь лучшую производительность, вектор stl или динамический массив, который просто realloc'd каждый раз, когда я хочу что-то добавить к нему?

stl vector должен быть победителем в этом случае, потому что он не перераспределяет каждый раз [вектор гарантирует O(1) амортизированное время вставки]. Однако, это может быть похоже, если ваша реализация malloc оптимизирована для такого использования.

Будет ли использование vectors :: iterator быстрее, чем использование цикла for в массиве?

Они должны быть одинаковыми, особенно потому, что vector :: iterator обычно представляет собой просто указатели на массив или его тонкие обертки.

Answer 4

Разницы в скорости нет, но vector намного безопаснее.Это потому, что функции будут просто встроены вашим компилятором, но vector несет большое количество гарантий и проверок границ (если вы запрашиваете это), которые вы не увидите при использовании ваших собственных необработанных массивов.