Используя массивы или std :: vectors в C ++, какова разница в производительности?

208

В нашем курсе C ++ они предлагают больше не использовать массивы C ++ в новых проектах. Насколько я знаю, сам Stroustroup предлагает не использовать массивы. Но есть ли существенные различия в производительности?

tunnuz
источник
2
Почему вы думаете, что есть разрыв в производительности.
Мартин Йорк,
99
Потому что обычно с лучшей функциональностью приходит худшая производительность.
Tunnuz
19
Я согласен с преждевременной оптимизацией, но выбор лучшего способа хранения имеет смысл. Часто в реальном мире необходимо отправить код и разработать следующий продукт, а этап оптимизации никогда не происходит.
Муравей
132
Я хотел бы, чтобы люди перестали кричать "преждевременная оптимизация!" всякий раз, когда кто-то задает простой вопрос, связанный с производительностью! ответьте на вопрос и не просто предположительно предположите, что люди делают что-то преждевременно.
d7samurai
4
@ d7samaurai: согласен, я еще не видел, чтобы кто-нибудь попробовал использоватьint main(int argc, const std::vector<string>& argv)
Марк К Коуэн

Ответы:

189

Использование массивов C ++ с newСледует избегать использования массивов (то есть динамических массивов). Есть проблема, вы должны следить за размером, и вам нужно удалить их вручную и сделать все виды домашнего хозяйства.

Использование массивов в стеке также не рекомендуется, поскольку у вас нет проверки диапазона, и передача массива потеряет любую информацию о его размере (преобразование массива в указатель). Вы должны использовать boost::arrayв этом случае, который оборачивает массив C ++ в небольшой класс и обеспечиваетsize функцию и итераторы для его перебора.

Теперь std :: vector против собственных массивов C ++ (взятых из Интернета):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Примечание. Если вы размещаете массивы вместе с newобъектами, не относящимися к классу (например, обычные int), или классами без определенного пользователем конструктора, и не хотите, чтобы ваши элементы инициализировались изначально, использование newмассивов -allocated может иметь преимущества в производительности, поскольку std::vectorинициализация всех элементов выполняется значения по умолчанию (например, 0 для int) при построении (кредиты @bernie за напоминание).

Йоханнес Шауб - Литб
источник
77
Кто изобрел этот чертов синтаксис AT & T? Только если бы я знал ... :)
Mehrdad Afshari
4
Это не так для компилятора Visual C ++. Но для GCC это так.
до
5
Суть моего ответа в том, что вектор не должен быть медленнее, чем соответствующие операции с указателями. Конечно, это может быть (легко достичь, включив также режим отладки) :)
Йоханнес Шауб - litb
18
+1 для «Индексация вектора - это то же самое, что и индексация указателя». и для других выводов.
Наваз
3
@ Piotr99 Я не собираюсь спорить с вами, но когда вы изучаете ассемблер после изучения языков более высокого уровня, синтаксис Intel имеет гораздо больше смысла, чем некоторые задом наперед, с префиксами (цифры), с суффиксами (инструкции) и неясными (доступ к памяти ) природа синтаксиса AT & T.
Коул Джонсон
73

Преамбула для микрооптимизаторов

Помните:

«Программисты тратят огромное количество времени на размышления или беспокойство по поводу скорости некритических частей своих программ, и эти попытки повышения эффективности на самом деле оказывают сильное негативное влияние при рассмотрении вопросов отладки и обслуживания. Мы должны забыть о небольшой эффективности, скажем о 97% времени: преждевременная оптимизация - корень всего зла. Однако мы не должны упускать наши возможности в эти критические 3% ».

(Благодаря метаморфозам за полную цитату)

Не используйте массив C вместо вектора (или чего-либо еще) только потому, что вы считаете, что он быстрее, так как предполагается, что он более низкого уровня. Ты был бы неправ.

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

Тем не менее, мы можем вернуться к первоначальному вопросу.

Статический / Динамический Массив?

Классы массива C ++ ведут себя лучше, чем низкоуровневый массив C, потому что они много знают о себе и могут отвечать на вопросы, а массивы C не могут. Они умеют убирать за собой. И что еще более важно, они обычно пишутся с использованием шаблонов и / или встраивания, что означает, что то, что кажется для большого количества кода в отладке, разрешается в виде небольшого или нулевого кода, созданного в сборке релиза, что означает отсутствие различий с их встроенной менее безопасной конкуренцией.

В целом, это падает на две категории:

Динамические массивы

Использование указателя на массив malloc-ed / new-ed будет в лучшем случае таким же быстрым, как версия std :: vector, и намного менее безопасным (см. Сообщение от litb). ).

Так что используйте std :: vector.

Статические массивы

Использование статического массива будет в лучшем случае:

  • так же быстро, как std :: array версия
  • и намного менее безопасно.

Так что используйте std :: array .

Неинициализированная память

Иногда использование vectorбуфера вместо необработанного буфера влечет за собой видимые затраты, потому что vectorон инициализирует буфер при построении, в то время как код, который он заменяет, этого не сделал, как заметил Берни в своем ответе. .

Если это так, то вы можете справиться с этим, используя unique_ptrвместо vectorили или, если случай не является исключительным в вашей кодовой строке, на самом деле написать класс, buffer_ownerкоторый будет владеть этой памятью, и дать вам простой и безопасный доступ к ней, в том числе бонусы, такие как изменение размера (использование realloc?) или все, что вам нужно.

paercebal
источник
1
Спасибо за обращение и к статическим массивам - std :: vector бесполезен, если вам не разрешено динамически распределять память по соображениям производительности.
Том
10
Когда вы говорите «Использование статического массива будет в лучшем случае столь же быстрым, как версия boost :: array», это показывает, насколько вы предвзяты. Это должно быть наоборот, Boost: массив может быть в лучшем случае быстрым, как статические массивы.
до
3
@toto: Это недоразумение: вы должны прочитать его как «Использование статического массива будет в лучшем случае ((так же быстро, как версия boost :: array) && (намного менее безопасно))». Я отредактирую пост, чтобы уточнить это. Кстати, спасибо за сомнение в пользу.
paercebal
1
что насчет std :: array?
Пол
4
Всегда показывайте полную цитату. «Программисты тратят огромное количество времени на размышления или беспокойство по поводу скорости некритических частей своих программ, и эти попытки повышения эффективности на самом деле оказывают сильное негативное влияние при рассмотрении вопросов отладки и обслуживания. Мы должны забыть о небольшой эффективности, скажем о 97% времени: преждевременная оптимизация - корень всего зла. Но мы не должны упускать наши возможности в эти критические 3% ». Иначе это становится бессмысленным звуковым прикусом.
метаморфоза
32

Векторы - это массивы под капотом. Производительность такая же.

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

Когда вектор заполняется, он меняет свой размер, что может означать новое выделение массива, за которым следуют n конструкторов копирования, за которыми следуют около n вызовов деструктора, а затем удаление массива.

Если ваша конструкция / деструктор дорогая, вам лучше сделать вектор правильного размера для начала.

Есть простой способ продемонстрировать это. Создайте простой класс, который показывает, когда он создается / уничтожается / копируется / назначается. Создайте вектор этих вещей и начните помещать их в конец вектора. Когда вектор заполнится, произойдет каскад активности при изменении размера вектора. Затем попробуйте снова с вектором, размер которого соответствует ожидаемому количеству элементов. Вы увидите разницу.

EvilTeach
источник
4
Подвеска: производительность имеет такой же большой O. std :: vector выполняет небольшую бухгалтерию, что, вероятно, потребует небольшого количества времени. OTOH, вы заканчиваете тем, что делали большую часть той же самой бухгалтерии, катая свои собственные динамические массивы.
dmckee --- котенок экс-модератора
Да, я понимаю. Суть его вопроса заключалась в том, каковы различия в производительности ..... Я попытался решить эту проблему.
EvilTeach
Std :: vector Gcc действительно увеличивает емкость один за другим, если вы вызываете push_back.
Bjhend
3
@bjhend Тогда std::vectorстандарты GCC не соответствуют стандартам? Я полагаю, что стандарт требует, чтобы vector::push_backамортизировалась постоянная сложность, и увеличение емкости на 1 для каждого push_backбудет равно n ^ 2 сложности после учета перераспределения. - предполагая , какое - то экспоненциальный рост мощности на push_backи insert, неспособность reserveприведет к не более постоянному повышению коэффициента в копиях вектора контента. Коэффициент экспоненциального вектора роста 1,5 будет означать ~ 3 раза больше копий, если вы не смогли reserve().
Якк - Адам Невраумонт
3
@bjhend вы не правы. Стандарт запрещает экспоненциальный рост: в п. 23.2.3 параграфа 16 говорится: «В таблице 101 перечислены операции, которые предоставляются для некоторых типов контейнеров последовательностей, но не для других. Реализация должна предоставлять эти операции для всех типов контейнеров, показанных в столбце« контейнер », и должен выполнять их так, чтобы принимать амортизированное постоянное время ". (таблица 101 - та, в которой есть push_back). Теперь, пожалуйста, прекратите распространять FUD. Никакая основная реализация не нарушает это требование. Стандартная библиотека C ++ от Microsoft увеличивается в 1,5 раза, а GCC - в 2 раза.
Р. Мартиньо Фернандес
27

Чтобы ответить на что-то, Мердад сказал:

Однако могут быть случаи, когда вам все еще нужны массивы. При взаимодействии с кодом низкого уровня (т. Е. Сборкой) или старыми библиотеками, которым требуются массивы, вы не сможете использовать векторы.

Совсем не правда. Векторы хорошо разлагаются на массивы / указатели, если вы используете:

vector<double> vector;
vector.push_back(42);

double *array = &(*vector.begin());

// pass the array to whatever low-level code you have

Это работает для всех основных реализаций STL. В следующем стандарте он будет работать (хотя сегодня он работает нормально).

Фрэнк Крюгер
источник
1
Нынешний стандарт не говорит ничего подобного. Это подразумевается, и это реализовано как непрерывное хранение. Но стандарт просто говорит, что это контейнер произвольного доступа (с использованием итераторов). Следующий стандарт будет явным.
Фрэнк Крюгер
1
& * v.begin () просто применяет оператор & к результату разыменования итератора. Разыменование может вернуть ЛЮБОЙ тип. Использование оператора address-of может снова вернуть ЛЮБОЙ тип. Стандарт не определяет это как указатель на непрерывную область памяти.
Фрэнк Крюгер
15
Оригинальный текст стандарта 1998 года действительно не требовал этого, но в 2003 году было добавление, в котором говорится об этом, поэтому он действительно охватывается стандартом. herbutter.wordpress.com/2008/04/07/…
Неманья Трифунович
2
C ++ 03 явно говорит, что &v[n] == &v[0] + nдопустимо, если оно nнаходится в пределах диапазона размеров. Абзац, содержащий это утверждение, не изменился с C ++ 11.
12:30
2
почему бы просто не использовать std :: vector :: data ()?
Пол
15

У вас еще меньше причин использовать простые массивы в C ++ 11.

В природе существует 3 вида массивов, от самых быстрых до самых медленных, в зависимости от имеющихся у них функций (конечно, качество реализации может сделать вещи действительно быстрыми даже для случая 3 в списке):

  1. Статический размер известен во время компиляции. ---std::array<T, N>
  2. Динамический с размером, известным во время выполнения и никогда не изменяемым. Типичная оптимизация здесь заключается в том, что если массив может быть размещен в стеке напрямую. - Недоступно . Может быть, dynarrayв C ++ TS после C ++ 14. В C есть VLA
  3. Динамический и изменяемый размер во время выполнения. ---std::vector<T>

Для 1. простых статических массивов с фиксированным числом элементов используйте std::array<T, N>в C ++ 11.

За 2. массивов фиксированного размера, указанных во время выполнения, но это не изменит их размера, есть обсуждение в C ++ 14, но оно было перенесено в техническую спецификацию и наконец сделано из C ++ 14.

Для 3. std::vector<T> обычно будет спрашивать память в куче . Это может повлиять на производительность, хотя вы можете использовать это std::vector<T, MyAlloc<T>>для улучшения ситуации с помощью специального распределителя. Преимущество по сравнению с тем T mytype[] = new MyType[n];, что вы можете изменить его размер и не указывать на указатель, как это делают обычные массивы.

Используйте упомянутые стандартные типы библиотек, чтобы избежать попадания массивов в указатели . Вы сэкономите время отладки, а производительность будет точно такой же, как и у простых массивов, если вы используете тот же набор функций.

Герман Диаго
источник
2
std :: dynarray. После рассмотрения комментариев национальных органов к n3690 этот компонент библиотеки был исключен из рабочего документа C ++ 14 в отдельную техническую спецификацию. Этот контейнер не является частью проекта C ++ 14 с n3797. от en.cppreference.com/w/cpp/container/dynarray
Мохамед Эль-Накиб
1
очень хороший ответ. Кратко и резюмируя, но больше деталей, чем любой.
Мохаммед эль-Накиб
6

Иди с STL. Там нет потери производительности. Алгоритмы очень эффективны и хорошо справляются с деталями, о которых большинство из нас не думает.

Джон Д. Кук
источник
6

О вкладе Дули .

Вывод состоит в том, что массивы целых чисел быстрее, чем векторы целых чисел (в моем примере 5 раз). Однако массивы и векторы имеют одинаковую скорость для более сложных / не выровненных данных.

lalebarde
источник
5

STL - сильно оптимизированная библиотека. Фактически даже предлагается использовать STL в играх, где может потребоваться высокая производительность. Массивы слишком подвержены ошибкам, чтобы их можно было использовать в повседневных задачах. Современные компиляторы также очень умны и могут действительно создавать отличный код с помощью STL. Если вы знаете, что делаете, STL обычно может обеспечить необходимую производительность. Например, путем инициализации векторов до необходимого размера (если вы знаете с самого начала), вы в основном можете достичь производительности массива. Однако могут быть случаи, когда вам все еще нужны массивы. При взаимодействии с кодом низкого уровня (т. Е. Сборкой) или старыми библиотеками, которым требуются массивы, вы не сможете использовать векторы.

Мехрдад Афшари
источник
4
учитывая, что вектор является смежным, все еще довольно легко взаимодействовать с библиотеками, которые требуют массивов.
Грег Роджерс
Да, но если вы хотите поработать с внутренними элементами вектора, использование вектора будет меньшим преимуществом. Кстати, ключевое слово было «возможно, нет».
Мехрдад Афшари
3
я знаю только один случай, когда векторы нельзя использовать: если размер равен 0. тогда & a [0] или & * a.begin () не будут работать. C ++ 1x исправит это с помощью функции a.data (), которая возвращает внутренний буфер с элементами
Johannes Schaub - litb
Конкретный сценарий, о котором я думал, когда писал, был основанным на стеке массивом.
Мехрдад Афшари
1
Интерфейсный вектор или любой смежный контейнер с C: vec.data()для данных и vec.size()для размера. Это так просто.
Герман Диаго
3

Если вы компилируете программное обеспечение в режиме отладки, многие компиляторы не будут включать функции доступа к вектору. Это сделает реализацию вектора stl намного медленнее в условиях, когда производительность является проблемой. Это также облегчит отладку кода, поскольку в отладчике видно, сколько памяти было выделено.

В оптимизированном режиме я бы ожидал, что вектор stl приблизится к эффективности массива. Это потому, что многие из векторных методов теперь встроены.


источник
Это важно упомянуть. Профилирование отладки STL очень, очень медленно. И это одна из причин, почему люди думают, что STL работает медленно.
Эрик Аронесты
3

Определенно, это влияет на производительность при использовании std::vectorмассива raw, когда вы хотите неинициализированный буфер (например, для использования в качестве места назначения memcpy()). An std::vectorинициализирует все свои элементы, используя конструктор по умолчанию. Необработанный массив не будет.

Спецификация c ++ для std:vectorконструктора, принимающего countаргумент (это третья форма), гласит:

`Создает новый контейнер из множества источников данных, необязательно используя предоставленный пользователем распределитель alloc.

3) Создает контейнер с количеством вставленных по умолчанию экземпляров T. Копии не создаются.

сложность

2-3) Линейный по количеству

Необработанный массив не несет затрат на инициализацию.

Смотрите также Как я могу избежать std :: vector <> для инициализации всех его элементов?

Bernie
источник
2

Разница в производительности между ними очень сильно зависит от реализации - если вы сравните плохо реализованный std :: vector с оптимальной реализацией массива, массив победит, но перевернет его, и вектор победит ...

Пока вы сравниваете яблоки с яблоками (либо массив, и вектор имеют фиксированное количество элементов, либо оба динамически изменяются в размерах), я думаю, что разница в производительности незначительна, если вы придерживаетесь практики кодирования STL. Не забывайте, что использование стандартных контейнеров C ++ также позволяет вам использовать предварительно свернутые алгоритмы, которые являются частью стандартной библиотеки C ++, и большинство из них, вероятно, будут более эффективными, чем обычная реализация того же алгоритма, который вы создали сами ,

Тем не менее, ИМХО, вектор выигрывает в сценарии отладки с отладочным STL, так как большинство реализаций STL с надлежащим режимом отладки могут по крайней мере выделить / скрыть типичные ошибки, допущенные людьми при работе со стандартными контейнерами.

Да, и не забывайте, что массив и вектор совместно используют одну и ту же структуру памяти, поэтому вы можете использовать векторы для передачи данных в устаревший код C или C ++, который ожидает базовые массивы. Имейте в виду, что большинство ставок в этом сценарии отменены, и вы снова имеете дело с сырой памятью.

Тимо Гойш
источник
1
Я думаю, что для удовлетворения требований к производительности (O (1) поиска и вставки), у вас почти есть реализовать std :: vector <> с использованием динамических массивов. Конечно, это очевидный способ сделать это.
dmckee --- котенок экс-модератора
Не только требования к производительности, но и требование, чтобы хранилище было непрерывным. Плохая векторная реализация создаст слишком много уровней косвенности между массивом и API. Хорошая векторная реализация позволит использовать встроенный код, SIMD для циклов и т. Д.
Макс Либберт,
Плохая векторная реализация, как описано, не будет соответствовать стандарту. Если вы хотите косвенность, std::dequeможет быть использован.
Phil1970
1

Если вам не нужно динамически регулировать размер, у вас есть накладные расходы памяти на сохранение емкости (один указатель / size_t). Вот и все.

Грег Роджерс
источник
1

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

Я удивлен, что никто еще не упомянул об этом - не беспокойтесь о производительности, пока она не станет проблемой, а затем оцените ее.

Марк Рэнсом
источник
1

Я бы сказал, что главное - не производительность, а безопасность. Вы можете сделать много ошибок с массивами (например, рассмотрите возможность изменения размера), когда вектор избавит вас от большой боли.

Габриэль Изенберг
источник
1

Векторы используют чуть больше памяти, чем массивы, поскольку они содержат размер массива. Они также увеличивают размер жесткого диска программ и, вероятно, объем памяти программ. Эти увеличения незначительны, но могут иметь значение, если вы работаете со встроенной системой. Хотя большинство мест, где эти различия имеют значение, это места, где вы бы использовали C, а не C ++.

Брайан
источник
2
Если это имеет значение, то вы, очевидно, не используете массивы динамического размера, и поэтому ваши массивы не должны изменять размер. (Если бы они сделали, вы бы как-то сохранили размер). Следовательно, вы могли бы также использовать boost :: array, если я не ошибаюсь - и что заставляет вас говорить, что для этого нужно где-то «хранить размер»?
Арафангион
1

Следующий простой тест:

C ++ Array vs Vector Объяснение теста производительности

противоречит выводам из «Сравнения ассемблерного кода, сгенерированного для базовых операций индексации, разыменования и приращения векторов и массивов / указателей».

Должна быть разница между массивами и векторами. Тест говорит так ... просто попробуйте, код есть ...

Hamed100101
источник
1

Иногда массивы действительно лучше, чем векторы. Если вы всегда манипулируете набором объектов фиксированной длины, лучше использовать массивы. Рассмотрим следующие фрагменты кода:

int main() {
int v[3];
v[0]=1; v[1]=2;v[2]=3;
int sum;
int starttime=time(NULL);
cout << starttime << endl;
for (int i=0;i<50000;i++)
for (int j=0;j<10000;j++) {
X x(v);
sum+=x.first();
}
int endtime=time(NULL);
cout << endtime << endl;
cout << endtime - starttime << endl;

}

где векторная версия X

class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};

и версия массива X:

class X {
int f[3];

public:
X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];}
int first() { return f[0];}
};

Версия массива будет main () быстрее, потому что мы избегаем издержек «new» каждый раз во внутреннем цикле.

(Этот код был размещен мной на comp.lang.c ++).

Дули
источник
1

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

Векторы 2d + вызывают снижение производительности?

Суть в том, что есть небольшой объем служебной информации, когда каждый субвектор имеет информацию о размере, и не обязательно будет сериализация данных (как это происходит с многомерными массивами c). Это отсутствие сериализации может предложить больше возможностей, чем микрооптимизация. Если вы работаете с многомерными массивами, может быть лучше просто расширить std :: vector и запустить собственную функцию get / set / resize bits.

Сеф Рид
источник
0

Предполагая, что массив фиксированной длины (например, int* v = new int[1000];vs std::vector<int> v(1000);, с размером v, установленным на уровне 1000), единственное соображение производительности, которое действительно имеет значение (или, по крайней мере, имело значение для меня, когда я находился в подобной дилемме), это скорость доступа к элемент. Я посмотрел векторный код STL, и вот что я нашел:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

Эта функция наверняка будет встроена компилятором. Таким образом, пока единственное, что вы планируете делать, v- это обращаться к его элементам operator[], похоже, что не должно быть никакой разницы в производительности.

Subh_b
источник