Что занимает больше памяти массив или вектор

Обновлено: 06.07.2024

Мне нужно представить 2D-поле (оси x, y), и я сталкиваюсь с проблемой: следует ли мне использовать 1D-массив или 2D-массив?

Я могу себе представить, что пересчет индексов для одномерных массивов (y + x * n) может быть медленнее, чем использование двухмерного массива (x, y), но я могу представить себе, что 1D может находиться в кеше процессора.

Я немного погуглил, но нашел только страницы, касающиеся статического массива (и заявил, что 1D и 2D в основном одинаковы). Но мои массивы должны быть динамическими.

Динамические массивы 1D или динамические массивы 2D?

Tl; dr: Вам, вероятно, следует использовать одномерный подход.

Примечание. Нельзя вдаваться в подробности, влияющие на производительность при сравнении динамических 1d или динамических 2d шаблонов хранения без заполнения книг, поскольку производительность кода зависит от очень большого количества параметров. Профилируйте, если возможно.

1. Что быстрее?

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

2. Что меньше?

Dynamic-1D потребляет меньше памяти, чем 2D-подход. Последнее также требует дополнительных ассигнований.

Замечания

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

Я могу представить, что пересчет индексов для одномерных массивов (y + x * n) может быть медленнее, чем использование 2D-массива (x, y)

Сравним эти две функции:

(Не встроенная) сборка, созданная Visual Studio 2015 RC для этих функций (с включенной оптимизацией):

Разница составляет mov (2d) против lea (1d). Первый имеет задержку 3 цикла и максимальную пропускную способность 2 за цикл, в то время как второй имеет задержку 2 цикла и максимальную пропускную способность 3 за цикл. (Согласно таблицам инструкций - Agner Fog Поскольку различия незначительны, я думаю, что не должно быть большой разницы в производительности, связанной с пересчетом индексов. Я полагаю, маловероятно, что это различие будет узким местом в какой-либо программе.

Это подводит нас к следующему (и более интересному) пункту:

. но я мог представить, что 1D может быть в кеше процессора .

Верно, но 2d тоже может быть в кеше процессора. См. Недостатки: расположение в памяти , чтобы узнать, почему 1d все же лучше.

Примечание. Речь идет о динамических массивах / схемах размещения [malloc / new / vector и т. д.]. Статический 2-мерный массив представляет собой непрерывный блок памяти и поэтому не подвержен недостаткам, которые я собираюсь здесь представить.

Проблема

Чтобы понять, почему динамический массив динамических массивов или вектор векторов, скорее всего, не является предпочтительным шаблоном хранения данных, вам необходимо понять структуру памяти таких структур.

Пример использования синтаксиса указателя на указатель

Минусы

Местоположение памяти

Для этой «матрицы» вы выделяете один блок из четырех указателей и четыре блока из четырех целых чисел. Все выделения не связаны и поэтому могут привести к произвольной позиции в памяти.

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

Для реального 2-мерного случая :

  • Фиолетовый квадрат - это позиция памяти, занятая самим p .
  • Зеленые квадраты составляют область памяти, p указывает на (4 x int* ).
  • Четыре области из 4 смежных синих квадратов - это те области, на которые указывает каждый int* зеленой области.

Для двухмерного сопоставления с одномерным случаем :

  • Зеленый квадрат - единственный обязательный указатель int *
  • Синие квадраты объединяют область памяти для всех элементов матрицы (16 x int ).

Real 2d vs mapped 2d memory layout

Это означает, что (при использовании левого макета) вы, вероятно, увидите худшую производительность, чем для непрерывного шаблона хранения (как показано справа), например, из-за кеширования.

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

Если у вас есть правильно выровненная 4 раза 4 матрица 32-битных значений, процессор с 64-байтовой строкой кэша (типичное значение) может «однократно» выполнить данные (4 * 4 * 4 = 64 байта). Если вы начнете обработку, а данных еще нет в кеше, вы столкнетесь с ошибкой в ​​кеше, и данные будут извлечены из основной памяти. Эта загрузка может получить сразу всю матрицу, поскольку она помещается в строку кэша, если и только если она хранится непрерывно (и правильно выровнена). Вероятно, при обработке этих данных больше не будет промахов.

В случае динамической, «реальной двумерной» системы с несвязанными местоположениями каждой строки / столбца процессору необходимо загружать каждую ячейку памяти отдельно. Несмотря на то, что требуется всего 64 байта, загрузка 4 строк кэша для 4 несвязанных позиций памяти в худшем случае приведет к передаче 256 байтов и потере 75% пропускной способности. Если вы обрабатываете данные с использованием 2d-схемы, вы снова (если еще не кэшируете) столкнетесь с отсутствием кеширования первого элемента. Но теперь только первая строка / столбец будет в кеше после первой загрузки из основной памяти, потому что все остальные строки находятся в другом месте в памяти, а не рядом с первой. Как только вы дойдете до новой строки / столбца, снова произойдет промах в кэше, и будет выполнена следующая загрузка из основной памяти.

Короче говоря: шаблон 2d имеет более высокую вероятность промахов в кеше, а схема 1d предлагает лучший потенциал для производительности из-за локальности данных.

Частое перераспределение / перераспределение

  • Для создания желаемой матрицы NxM (4 × 4) необходимо до N + 1 (4 + 1 = 5) выделений (с использованием new, malloc, allocator :: allocate или чего-то еще).
  • Также должно быть применено такое же количество соответствующих операций освобождения.

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

Ситуация становится еще хуже с ростом количества строк.

Накладные расходы на потребление памяти

Я предполагаю размер 32 бита для int и 32 бита для указателей. (Примечание: зависимость от системы.)

Напомним: мы хотим сохранить матрицу int размером 4 × 4, что означает 64 байта.

Для матрицы NxM, хранящейся с представленной схемой указателя на указатель, мы потребляем

  • N*M*sizeof(int) [актуальные синие данные] +
  • N*sizeof(int*) [зеленые указатели] +
  • sizeof(int**) [фиолетовая переменная p] байтов.

В данном примере получается 4*4*4 + 4*4 + 4 = 84 байтов, а при использовании std::vector<std::vector<int>> становится еще хуже. Для этого потребуется N * M * sizeof(int) + N * sizeof(vector<int>) + sizeof(vector<vector<int>>) байтов, то есть всего 4*4*4 + 4*16 + 16 = 144 байтов, не считая 64 байтов для 4 x 4 int.

Вдобавок - в зависимости от используемого распределителя - каждое отдельное выделение вполне может (и, скорее всего, будет) иметь еще 16 байт служебных данных памяти. (Некоторые «информационные байты», в которых хранится количество выделенных байтов с целью надлежащего освобождения.)

Это означает, что в худшем случае:

N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)
= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_

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

Риск утечки памяти

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

Если new пробегает память и следующая строка не может быть выделена (особенно вероятно, когда матрица очень большая), std::bad_alloc выбрасывает new .

Пример :

В вышеупомянутом примере new / delete мы столкнемся с дополнительным кодом, если мы хотим избежать утечек в случае исключений bad_alloc .

Резюме

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

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

«Способ C ++» для этого, вероятно, состоит в том, чтобы написать класс, который управляет вашей памятью, учитывая такие важные вещи, как

Примере

Чтобы представить себе, как может выглядеть такой класс, вот простой пример с некоторыми основными функциями:

  • 2-мерный конструктивный
  • 2d-изменяемый размер
  • operator(size_t, size_t) для доступа к основному элементу 2-й строки
  • at(size_t, size_t) для проверенного доступа к основному элементу 2-й строки
  • Соответствует требованиям концепции для контейнера

Обратите внимание на несколько моментов:

  • T должен соответствовать требованиям используемых функций-членов std::vector
  • operator() не выполняет никаких проверок "вне диапазона"
  • Нет необходимости управлять данными самостоятельно
  • Не требуется деструктор, конструктор копирования или операторы присваивания

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

Могут быть случаи, когда предпочтительна динамическая «реальная» двумерная структура. Это, например, случай, если

  • матрица очень большая и разреженная (если какую-либо из строк даже не нужно выделять, но можно обрабатывать с помощью nullptr) или если
  • в строках разное количество столбцов (то есть, если у вас вообще нет матрицы, а есть еще одна двумерная конструкция).

Если вы не говорите о статических массивах, 1D быстрее .

Вот схема памяти одномерного массива ( std::vector<T> ):

То же самое для динамического 2D-массива ( std::vector<std::vector<T>> ):

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

Размер: для обоих потребуется одинаковый объем памяти.

Скорость . Можно предположить, что разницы в скорости не будет, поскольку память для обоих этих массивов должна быть непрерывной ( весь 2D-массив должен отображаться в памяти как один фрагмент, а не как куча кусков разлетаются по памяти). (Это может быть компилятор зависимый однако.)

Размер: для 2D-массива потребуется немного больше памяти, чем для 1D-массива, так как в 2D-массиве необходимы указатели, указывающие на набор выделенных 1D-массивов. (Этот крошечный бит является крошечным, только когда мы говорим о действительно больших массивах. Для небольших массивов крошечный бит может быть относительно большим.)

Скорость: 1D-массив может быть быстрее, чем 2D-массив, потому что память для 2D-массива не будет непрерывной, поэтому промахи в кэше могут стать проблемой.

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

Все существующие ответы сравнивают только одномерные массивы с массивами указателей.

В C (но не в C ++) есть третий вариант; у вас может быть непрерывный двумерный массив, который динамически выделяется и имеет размеры времени выполнения:

И доступ к нему осуществляется как p[row_index][col_index] .

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

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

Еще одно различие 1D и 2D массивов проявляется в распределении памяти. Мы не можем быть уверены, что элементы 2D-массива будут последовательными.

Это действительно зависит от того, как реализован ваш 2D-массив.

Рассмотрите код ниже:

Здесь есть 3 реализации: b, c и d

Не будет большой разницы в доступе к b[x][y] или a[x*20 + y] , поскольку в одном случае вы выполняете вычисления, а в другом - компилятор. c[x][y] и d[x][y] работают медленнее, потому что машина должна найти адрес, на который указывает c[x] , а затем получить оттуда доступ к y-му элементу. Это не одно прямое вычисление. На некоторых машинах (например, AS400 с 36-байтовыми (не битовыми) указателями) доступ к указателям происходит очень медленно. Все зависит от используемой архитектуры. На архитектурах типа x86 a и b имеют одинаковую скорость, c и d медленнее, чем b.

Мне нравится подробный ответ, предоставленный Pixelchemist. Более простой вариант этого решения может быть следующим. Сначала объявите размеры:

Затем создайте псевдоним и методы получения и установки:

Наконец, вектор может быть создан и проиндексирован следующим образом:

Определение размера вектора при инициализации обеспечивает оптимальная производительность. Это решение изменено на основе этого ответа. Функции могут быть перегружены для поддержки различных измерений с одним вектором. Обратной стороной этого решения является то, что параметры M, N, P неявно передаются функциям get и set. Эту проблему можно решить, реализовав решение в классе, как это делает Pixelchemist.

Ниже приведен пример передачи параметров в документ fxml через пространство имен.

Определить значение External Text для переменной пространства имен labelText :

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

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

Теперь станд. вектор по сравнению с собственными массивами C++ (взятый из Интернета):

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

ответ дан Johannes Schaub - litb 4 November 2019 в 14:49

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

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

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

желание версии массива основных () будет быстрее, потому что мы избегаем издержек "новых" каждый раз во внутреннем цикле.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(спасибо метаморфозы для полной цитаты)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Static с размером, известным во время компиляции. --- std::array<T, N>
  2. динамический с размером, известным во время выполнения и никогда не изменялся. Типичная оптимизация здесь заключается в том, что если массив может быть выделяется непосредственно в стеке. -- недоступен. Может быть!--1--> В C++ TS после C++14. В C есть VLAs
  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]; заключается в том, что вы можете изменить его размер и что он не будет распадаться на указатель, как простые массивы делать.

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

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

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

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

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

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

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

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

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

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

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

на в C++ спецификаций на std:vector конструктор принимая

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

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

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

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

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

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

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

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

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

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

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

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

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

ОТВЕТЫ

Ответ 1

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

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

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

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

Ответ 2

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

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

(Благодаря metamorphosis для полной цитаты)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

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

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

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

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

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

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

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

Сложность

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

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

Ответ 11

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

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

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

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

Ответ 12

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

Ответ 13

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

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

Ответ 14

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

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

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

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

(Этот код был отправлен на comp.lang.С++ мной).

Ответ 15

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

Ответ 16

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

Ответ 17

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

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

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

Ответ 18

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

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

Ответ 19

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

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

Читайте также: