C ++ STL вектор против массива в реальном мире

Question

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

Автор имеет Q / A в конце каждой главы, и одна из них была:

Q: Когда я должен использовать вектор вместо массива?

A: Почти всегда.Векторы эффективны и гибки.Они требуют немного больше памяти, чем массивы, но этот компромисс почти всегда стоит преимуществ.

Что вы, ребята, думаете?Я помню, как узнал о векторах в книге по Java, но мы не рассматривали их вообще в моем вступлении к Comp.Sci.класс, ни мой класс Data Structures в колледже.Я также никогда не видел, чтобы они использовались в каких-либо программных заданиях (Java и C).Это заставляет меня чувствовать, что они не очень часто используются, хотя я знаю, что школьный код и код реального мира могут быть очень разными.

Мне не нужно говорить о различиях между этими двумя даннымиструктуры;Я очень осведомлен о них.Все, что я хочу знать, это то, дает ли автор хороший совет в своей Q / A, или он просто пытается избавить начинающих программистов от разрушения себя сложностями управления структурами данных фиксированного размера.Кроме того, независимо от того, что вы думаете о совете автора, что вы видите в реальном мире чаще?

Спасибо,

Джерард

Answer 1

A: Почти всегда [использовать вектор вместо массива].Векторы эффективны и гибки.Они требуют немного больше памяти, чем массивы, но этот компромисс почти всегда стоит преимуществ.

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

• элементы указаны во время компиляции, например, const char project[] = "Super Server";, const Colours colours[] = { Green, Yellow };

  • с C ++ 11 будет одинаково кратко инициализировать std::vector s со значениями

• количество элементов по своей природе фиксировано, например const char* const bool_to_str[] = { "false", "true" };,Piece chess_board[8][8];

• производительность при первом использовании имеет решающее значение: с массивами констант компилятор может часто записывать снимок памяти полностью предварительно инициализированных объектов в исполняемый образ, который затем- непосредственно передается на место, готовое к использованию, поэтому обычно намного быстрее выполняется выделение кучи во время выполнения (new[]) с последующим сериализованным построением объектов

  • сгенерированных компилятором таблиц const данные всегда могут быть безопасно прочитаны несколькими потоками, в то время как данные, созданные во время выполнения, должны завершить построение до того, как другой код, запущенный конструкторами для не-локальных static переменных, попытается использовать эти данные:в конечном итоге вам понадобится какой-то тип Singleton (возможно, многопоточный, который будет еще медленнее)

  • В C ++ 03, vector s, созданные с начальным размером, будут создавать один прототипный элемент элементазатем скопируйте конструкцию каждого члена данных.Это означало, что даже для типов, в которых конструирование было намеренно оставлено как бездействие, все равно стоило копировать элементы данных - копировать их значения «что угодно, что осталось в памяти».Ясно, что массив неинициализированных элементов работает быстрее.

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

• Существует десятилетний взлом для размещения массива из 1 элемента (или даже 0, если ваш компилятор разрешает это какрасширение) в конце структуры / класса, направляя указатель на тип структуры в некоторой большей области данных и получая доступ к элементам массива за пределами структуры, основываясь на предварительных знаниях о доступности памяти и ее содержимом (при чтении до записи) - см. Зачем нужен массив с нулевыми элементами?

• классы / структуры, содержащие массивы, все еще могут быть POD-типами

• *Массивы 1060 * облегчают доступ в разделяемую память от нескольких процессов (по умолчанию внутренние указатели vector на фактические динамически распределяемые данные не будут находиться в разделяемой памяти или не имеют смысла для разных процессов, и было крайне сложно заставить C ++ 03vector s для использования разделяемой памяти, подобной этой, даже при указании пользовательского параметра шаблона распределителя).

• встраивание массивов может локализовать требования к доступу к памяти, улучшая попадания в кэш и, следовательно, производительность

Тем не менее, если не активно использовать vector (в краткости кода, читаемости илипроизводительность), тогда вам лучше сделать это: они size(), проверили произвольный доступ через at(), итераторы, изменение размера (что часто становится необходимым, когда приложение «созревает») и т. д. Также часто легче изменитьот vector до какого-либо другого стандартного контейнера, если в этом есть необходимость, и более безопасные / более простые в применении стандартные алгоритмы (x.end() лучше, чем x + sizeof x / sizeof x[0] в любой день).

ОБНОВЛЕНИЕ: введен C ++ 11std::array<>, что позволяет избежать некоторых затрат vector с - внутренне использовать массив фиксированного размера, чтобы избежать дополнительного выделения / освобождения кучи, - при этом предлагая некоторые преимущества и функции API: http://en.cppreference.com/w/cpp/container/array.

Answer 2

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

Когда исключение не обрабатывается, ТОЛЬКО вещи, которые гарантированно вызываются, являются деструкторами объектов в стеке.Если вы динамически распределяете память вне объекта, и перед удалением возникает где-то неперехваченное исключение, у вас возникает утечка памяти.

Это также хороший способ избежать необходимости помнить использование delete.

Вы также должны проверить std::algorithm, который предоставляет множество общих алгоритмов для vector и других контейнеров STL.

Я несколько раз писал код с vector, которыйВ ретроспективе, вероятно, было бы лучше с собственным массивом.Но во всех этих случаях Boost::multi_array или Blitz::Array были бы лучше, чем любой из них.

Answer 3

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

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

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

В науке и технике выбор зависит от проекта. Насколько важна скорость и время отладки? Например, LAAMPS, являющаяся программным обеспечением для моделирования, использует необработанные указатели, которые обрабатываются через их класс управления памятью. Скорость является приоритетом для этого программного обеспечения. Программное обеспечение, которое я создаю, я должен сбалансировать скорость, объем памяти и время отладки. Я действительно не хочу тратить много времени на отладку, поэтому я использую вектор STL.

Я хотел добавить к этому ответу еще немного информации, которую я обнаружил в результате обширного тестирования крупномасштабных массивов и большого чтения в Интернете. Таким образом, другая проблема с векторным массивом stl и массивами большого размера (более миллиона) возникает в том, как выделяется память для этих массивов. Stl vector использует класс std :: allocator для обработки памяти. Этот класс является распределителем памяти на основе пула. При небольшой загрузке распределение на основе пула чрезвычайно эффективно с точки зрения скорости и использования памяти. Когда размер вектора исчисляется миллионами, стратегия, основанная на пуле, становится проблемой памяти. Это происходит потому, что тенденция к пулам всегда состоит в том, чтобы держать больше места, чем в настоящее время используется вектором stl.

Для крупномасштабных векторов вам лучше либо написать собственный векторный класс, либо использовать указатели (raw или какая-то система управления памятью из boost или библиотеки c ++). У обоих подходов есть свои преимущества и недостатки. Выбор действительно зависит от конкретной проблемы, которую вы решаете (слишком много переменных, чтобы добавить сюда). Если вам случится написать свой собственный векторный класс, убедитесь, что вектор простой способ очистить его память. В настоящее время для вектора Stl вам нужно использовать операции подкачки, чтобы сделать что-то, что действительно должно быть встроено в класс.

Answer 4

Std :: vector - это просто массив с изменяемым размером. Это не намного больше, чем это. Это не то, чему вы научитесь в классе Data Structures, потому что это не интеллектуальная структура данных.

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

Answer 5

Практическое правило: если вы заранее не знаете количество элементов или ожидается, что количество элементов будет большим (скажем, более 10), используйте вектор.В противном случае вы также можете использовать массив.Например, я пишу много кода для обработки геометрии и определяю линию как массив из двух координат.Линия определяется двумя точками, и она ВСЕГДА будет определяться ровно двумя точками.Использование вектора вместо массива было бы излишним во многих отношениях, в том числе с точки зрения производительности.

Другое дело: когда я говорю «массив», я действительно ДЕЛАЮ СЕБЕ массив: переменная, объявленная с использованием синтаксиса массива, такого какint evenOddCount[2]; Если вы рассматриваете выбор между вектором и динамически выделяемым блоком памяти, таким как int *evenOddCount = new int[2];, ответ ясен: ИСПОЛЬЗУЙТЕ ВЕКТОР!

Answer 6

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

Возьмем эти (тривиальные) сценарии в качестве примеров:

• Вы реализовали контроллер вида для отслеживания бойцов ИИ в FPS.Логика игры порождает случайное количество бойцов в различных зонах каждые пару секунд.Игрок сбивает бойцов AI со скоростью, известной только во время выполнения.
• Адвокат зашел на сайт муниципального суда в своем штате и запрашивает количество новых случаев DUI, которые поступили за ночь.Он решает отфильтровать список по набору переменных, в том числе по времени возникновения аварии, почтовому индексу и сотруднику по аресту.
• Операционная система должна поддерживать список адресов памяти, используемых различными программами, работающими на ней,Количество программ и их использование памяти изменяются непредсказуемым образом.

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

Answer 7

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