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

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

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

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

    Теперь std :: vector vs. native 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  struct S { int padding; std::vector v; int * p; std::vector::iterator i; }; int pointer_index (S & s) { return sp[3]; } // movq 32(%rdi), %rax // movl 12(%rax), %eax // ret int vector_index (S & s) { return sv[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 *sp; } // movq 32(%rdi), %rax // movl (%rax), %eax // ret int iterator_deref (S & s) { return *si; } // 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) { ++sp; } // addq $4, 32(%rdi) // ret void iterator_increment (S & s) { ++si; } // addq $4, 40(%rdi) // ret // Conclusion: Incrementing a vector iterator is the same damn thing as // incrementing a pointer. 

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

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

    Запомнить:

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

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

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

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

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

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

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

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

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

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

    Поэтому используйте std :: vector.

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

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

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

    Поэтому используйте std :: array .

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

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

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

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

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

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

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

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

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

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

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

     vector vector; vector.push_back(42); double *array = &(*vector.begin()); // pass the array to whatever low-level code you have 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     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 vec; public: X(const vector& 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 ++ мной).

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

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

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

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

    сложность

    2-3) Линейный счетчик

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

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

    Давайте будем гением компьютера.