Векторы или динамические массивы (5 видео)

Преимущества вектора над массивом в C ++

Мы уже обсуждали массивы и векторы . В этом посте мы обсудим преимущества вектора перед обычным массивом.

Преимущества Vector над массивами :

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

using namespace std;

int array[100]; // Статическая реализация

int * arr = new int [100]; // Динамическая реализация

vector int > v; // Реализация вектора

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

using namespace std;

int array[100]; // Статическая реализация

cout «Size of Array » sizeof (array) / sizeof (array[0]) «n» ;

vector int > v; // Реализация вектора

// Вставка значений в вектор

cout «Size of vector Before Removal=» «n» ;

// Выходные значения вектора

for ( auto it : v)

v.erase(v.begin() + 2); // Удалить 3-й элемент

cout «nSize of vector After removal=» «n» ;

// Выходные значения вектора

for ( auto it : v)

Выход :

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

using namespace std;

int * arr = new int [100]; // Динамическая реализация

delete [] arr; // массив явно освобожден

vector int > v; // Автоматическое освобождение, когда переменная выходит из области видимости

Размер массива не может быть определен при динамическом размещении, тогда как размер вектора может быть определен за O (1) раз .

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

using namespace std;

int * arr = new int [100]; // Динамическая реализация

cout «Size of array= » ;

cout sizeof (arr) / sizeof (*arr) «n» ; // Указатель не может быть использован для получения размера

// блок, указанный им

Выход :

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

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

// Программа для демонстрации массивов не может быть возвращена
#include

using namespace std;

int arr[10]; // Массив, определенный локально

for ( int i = 0; i // Помещаем значения в массив

return arr; // возвращаем указатель на массив

int * array; // указатель типа int

array = getValues(); // Вызов функции для получения обр

for ( int i = 0; i // Печать значений

Выход :

// Программа для демонстрации вектора может быть возвращена
#include

using namespace std;

// Функция, возвращающая вектор

vector int > getValues()

vector int > v; // Вектор определяется локально

for ( int i = 0; i // Вставка значений в Vector

return v; // возвращаем указатель на массив

vector int > get;

get = getValues(); // Вызов функции для получения v

// Выходные значения вектора

for ( auto it : get)

Выход :

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

using namespace std;

vector int > v; // Вектор определяется локально

for ( int i = 0; i

vector int > get;

get = v; // Копируем вектор v в вектор

cout «vector get:n» ;

for ( auto it : get)

for ( int i = 0; i // Помещаем значения в массив

Содержание

Динамические массивы против векторов STL точную разницу?
Используя массивы или std :: vectors в C ++, какова разница в производительности?
Преамбула для микрооптимизаторов
Статический / Динамический Массив?
Динамические массивы
Статические массивы
Неинициализированная память
🎥 Видео

Видео:#7. Реализация динамического массива на С++ с помощью std::vector | Структуры данныхСкачать

Динамические массивы против векторов STL точную разницу?

Какова точная разница между динамическими массивами и векторами. Это был вопрос для меня.

Я сказал, что обе имеют последовательную память.

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

Я сказал, что векторы свободны от ошибок, так как они находятся в стандартной библиотеке. Он сказал, что предоставит как .so файл динамических массивов, который является безошибочным и обладает всеми качествами наравне с STL.

Я смущен и не ответил на точную разницу. Когда я искал в Интернете, я видел только указанные выше утверждения.

Может кто-нибудь объяснить мне точную разницу? И что ожидал от меня интервьюер?

Он сказал, что предоставит в качестве .so файла динамических массивов, который без ошибок и обладает всеми качествами наравне с STL.

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

std::vector стандартизованный и все это знают. Если я вижу std::vector в некотором фрагменте кода, я точно знаю, что он делает и как он должен использоваться. Если, однако, я вижу a my::dynamic_array , я этого не знаю. Мне нужно будет посмотреть на его документацию или даже – вздохнуть! – реализация, чтобы выяснить, выполняет ли my_dynamic_array::resize() то же самое, что и std::vector::resize() .

Здесь многое зависит от того, что он подразумевает под “динамическим массивом”. Большинство людей означает что-то, где память распределяется с помощью массива-new и освобождается с помощью массива-delete. Если это намерение здесь, то наличие качеств на уровне с std::vector просто невозможно.

Причина довольно проста: std::vector обычно выделяет кусок памяти больше, чем необходимо, чтобы удерживать количество элементов, которые в настоящее время хранятся. Затем он создает объекты в этой памяти по мере необходимости для расширения. Но с новым массивом у вас нет выбора – вы выделяете массив объектов, поэтому, если вы выделите пространство для (скажем) 100 объектов, вы получите 100 объектов, созданных в этом пространстве (сразу). Он просто не имеет резерва для наличия буфера, часть которого содержит реальные объекты, а другая часть – просто простая память, не содержащая ничего.

Я полагаю, что если yo хочет растянуть точку, возможно подражать std::vector и по-прежнему выделять пространство с помощью массива-new. Для этого вам просто нужно выделить массив char , а затем использовать place new для создания объектов в этом необработанном пространстве памяти. Это позволяет почти такие же вещи, как std::vector , потому что это почти то же самое, что и std::vector . Мы по-прежнему не обладаем (потенциальным) уровнем косвенности, хотя – std::vector фактически выделяет память через объект Allocator, поэтому вы можете точно изменить, как он распределяет свою необработанную память (по умолчанию используется std::allocator , который использует operator new , но если бы вы захотели, вы могли бы написать распределитель, который использовал бы new char[size] , хотя я не могу себе представить, почему вы бы это сделали.)

Можно, конечно, написать динамический массив, чтобы использовать объект-распределитель. В этот момент для всех практических целей вы только что заново изобрели std::vector под (предположительно) новым именем. В этом случае @sbi по-прежнему прав: сам факт, что он не стандартизован, означает, что он по-прежнему не имеет одного из главных качеств std. vector – качества стандартизации и уже известного всем, кто знает С++. Однако даже без этого мы должны растянуть выражение “динамический массив” до (и я установил за пределами) точку прерывания, чтобы получить те же качества, что и std::vector , даже если мы игнорируем стандартизацию.

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

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

Здесь говорится: “Внутри векторы используют динамически выделенный массив для хранения своих элементов”.
Базовое понятие векторов представляет собой динамически распределенный массив.

Видео:Динамический массив с++ пример. Создание, заполнение, удаление, размер динамического массива. #55Скачать

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

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

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

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

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

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

Видео:Массив объектов класса. Динамический. Статический. Создание Особенности. ООП C++ Для начинающих #96Скачать

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

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

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

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

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

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

Видео:Двумерный динамический массив c++ пример. Создание, заполнение, удаление. Динамические массивы. #56Скачать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 раза больше копий, если вы не смогли reserve() .

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

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

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

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

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

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

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

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

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

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

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