В чем разница в производительности при использовании массивов или std :: vectors в C++?

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

Следует избегать использования массивов 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, может иметь преимущества в производительности, потому что std::vector инициализирует все элементы значениями по умолчанию (например, 0 для int) при построении (спасибо @bernie за напоминание мне).

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

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

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

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

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

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

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

However, there might be cases where you still need arrays. When interfacing with low level code (i.e. assembly) or old libraries that require arrays, you might not be able to use vectors.

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

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

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

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

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

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

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

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

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 () будет быстрее, потому что мы избегаем накладные расходы «нового» каждый раз во внутреннем цикле.

(Этот код был опубликован мной на comp.lang.C++).

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

Векторы - это массивы под капотом. Спектакль такой же.

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

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

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

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

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

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

Преамбула для людей, занимающихся микрооптимизаторами

Помнить:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%".

(Спасибо метаморфоза за полную цитату)

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

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

При этом мы можем вернуться к исходному вопросу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

О вкладе дули с моими собственными измерениями.

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

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

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

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

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

У вас еще меньше причин использовать простые массивы в 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]; заключается в том, что вы можете изменять его размер, и он не будет преобразовываться в указатель, как это делают простые массивы.

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

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

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

`Constructs a new container from a variety of data sources, optionally using a user supplied allocator alloc.

3. Constructs the container with count default-inserted instances of T. No copies are made.

Complexity

2-3) Linear in count

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

Обратите внимание, что с помощью настраиваемого распределителя можно избежать «инициализации» элементов вектора (т.е. использовать инициализацию по умолчанию вместо инициализации значения). См. Эти вопросы для получения более подробной информации:

• Правильно ли это поведение vector :: resize (size_type n) в C++ 11 и Boost.Container?
• Как избежать инициализации всех элементов std :: vector <>?

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

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

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

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

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

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

Для массивов фиксированной длины производительность такая же (по сравнению с вектором <>) в сборке выпуска, но в отладочной сборке низкоуровневые массивы выигрывают в 20 раз, по моему опыту (MS Visual Studio 2015, C++ 11).

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

Во вторую группу иногда попадают опытные разработчики, работающие над численно насыщенным кодом (особенно если они используют вектор :)).