Вектор: инициализация или резерв?

Question

Я знаю размер вектора, как лучше всего его инициализировать?:

вариант 1

vector<int> vec(3); //in .h
vec.at(0)=var1;     //in .cpp
vec.at(1)=var2;     //in .cpp
vec.at(2)=var3;     //in .cpp

option2

vector<int> vec;     //in .h
vec.reserve(3);     //in .cpp
vec.push_back(var1);     //in .cpp
vec.push_back(var2);     //in .cpp
vec.push_back(var3);     //in .cpp

Полагаю, вариант 2 лучше, чем 1. Не так ли? другие варианты?

Answer 1

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

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

Выберите, что лучше соответствует вашим потребностям, т.е. что лучше в определенной ситуации.

Answer 2

«Лучший» способ:

vector<int> vec = {var1, var2, var3};

доступен с компилятором, поддерживающим C ++ 11.

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

В противном случае обычно используется вариант 1, если вы знаете, сколько элементов вы собираетесь использовать, и значения по умолчанию (0 дляint) было бы полезно.Использование at здесь означает, что вы не можете гарантировать, что индекс действителен.Такая ситуация вызывает тревогу сама по себе.Даже несмотря на то, что вы сможете надежно обнаруживать проблемы, определенно проще использовать push_back и перестать беспокоиться о правильной настройке индексов.

В случае варианта 2 обычно нулевая разница в производительности независимо от того, резервируете ли вы памятьили нет, так что проще не бронировать *.Возможно, если вектор содержит типы, которые очень дороги для копирования (и не обеспечивают быстрого перемещения в C ++ 11), или размер вектора будет огромным.

---

*Из Stroustrups Часто задаваемые вопросы по стилю и технике C ++ :

Люди иногда беспокоятся о том, что стоимость std :: vector будет расти постепенно.Раньше я беспокоился об этом и использовал Reserve () для оптимизации роста.После измерения моего кода и неоднократных затруднений с поиском преимуществ производительности reserve () в реальных программах я перестал его использовать, за исключением случаев, когда это необходимо, чтобы избежать аннулирования итераторов (редкий случай в моем коде).Еще раз: измеряйте, прежде чем оптимизировать.

Answer 3

Хотя ваши примеры, по сути, совпадают, может случиться так, что когда используемый тип не является int, выбор за вами. Если ваш тип не имеет конструктора по умолчанию или если вам все равно придется заново конструировать каждый элемент позже, я бы использовал reserve. Только не попадитесь в ловушку, которую я сделал, и используйте reserve, а затем operator[] для инициализации!

---

Конструктор

std::vector<MyType> myVec(numberOfElementsToStart);
int size = myVec.size();
int capacity = myVec.capacity();

В этом первом случае, используя конструктор, size и numberOfElementsToStart будут равны, а capacity будет больше или равно им.

Думайте о myVec как о векторе, содержащем множество элементов MyType, к которым можно получить доступ и изменить, push_back(anotherInstanceOfMyType) добавит его в конец вектора.

---

Резерв

std::vector<MyType> myVec;
myVec.reserve(numberOfElementsToStart);
int size = myVec.size();
int capacity = myVec.capacity();

При использовании функции reserve, size будет 0, пока вы не добавите элемент в массив, и capacity не будет равен или больше numberOfElementsToStart.

Думайте о myVec как о пустом векторе, к которому можно добавлять новые элементы, используя push_back без выделения памяти как минимум для первых numberOfElementsToStart элементов.

Обратите внимание, что push_back() все еще требует внутренней проверки, чтобы гарантировать, что размер <емкость </em> и размер приращения , так что вы можете взвесить это по сравнению со стоимостью конструкции по умолчанию.

---

Инициализация списка

std::vector<MyType> myVec{ var1, var2, var3 };

Это дополнительная опция для инициализации вашего вектора, и хотя она возможна только для очень маленьких векторов, это простой способ инициализировать небольшой вектор с известными значениями. size будет равно количеству элементов, с которыми вы его инициализировали, а capacity будет равно или больше размера. Современные компиляторы могут оптимизировать создание временных объектов и предотвратить ненужное копирование.

Answer 4

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

Для C-подобные типы, вероятно, будут одинаковыми.

Answer 5

Каким-то образом, ответ без ответа, который является полностью неправильным, остался принят и большинство проголосовало за ~ 7 лет.Это не вопрос яблок и апельсинов.Это не вопрос, на который нужно отвечать расплывчатыми клише.

Для простого правила:

Вариант № 1 быстрее ...

... но это, вероятно, не должно быть вашей самой большой проблемой.

Во-первых, разница заключается в том,довольно незначительныйВо-вторых, когда мы запускаем оптимизацию компилятора, разница становится еще меньше.Например, на моем gcc-5.4.0 разница, возможно, тривиальна, когда выполняется оптимизация компилятора уровня 3 (-O3):

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

---

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

main.cpp:

/* 
 * Test constructing and filling a vector in two ways: construction with size
 * then assignment versus construction of empty vector followed by push_back
 * We collect dummy sums to prevent the compiler from optimizing out computation
 */

#include <iostream>
#include <vector>

#include "rng.hpp"
#include "timer.hpp"

const size_t kMinSize = 1000;
const size_t kMaxSize = 100000;
const double kSizeIncrementFactor = 1.2;
const int kNumVecs = 10000;

int main() {
  for (size_t mean_size = kMinSize; mean_size <= kMaxSize;
       mean_size = static_cast<size_t>(mean_size * kSizeIncrementFactor)) {
    // Generate sizes from normal distribution
    std::vector<size_t> sizes_vec;
    NormalIntRng<size_t> sizes_rng(mean_size, mean_size / 10.0); 
    for (int i = 0; i < kNumVecs; ++i) {
      sizes_vec.push_back(sizes_rng.GenerateValue());
    }
    Timer timer;
    UniformIntRng<int> values_rng(0, 5);
    // Method 1: construct with size, then assign
    timer.Reset();
    int method_1_sum = 0;
    for (size_t num_els : sizes_vec) {
      std::vector<int> vec(num_els);
      for (size_t i = 0; i < num_els; ++i) {
        vec[i] = values_rng.GenerateValue();
      }
      // Compute sum - this part identical for two methods
      for (size_t i = 0; i < num_els; ++i) {
        method_1_sum += vec[i];
      }
    }
    double method_1_seconds = timer.GetSeconds();
    // Method 2: reserve then push_back
    timer.Reset();
    int method_2_sum = 0;
    for (size_t num_els : sizes_vec) {
      std::vector<int> vec;
      vec.reserve(num_els);
      for (size_t i = 0; i < num_els; ++i) {
        vec.push_back(values_rng.GenerateValue());
      }
      // Compute sum - this part identical for two methods
      for (size_t i = 0; i < num_els; ++i) {
        method_2_sum += vec[i];
      }
    }
    double method_2_seconds = timer.GetSeconds();
    // Report results as mean_size, method_1_seconds, method_2_seconds
    std::cout << mean_size << ", " << method_1_seconds << ", " << method_2_seconds;
    // Do something with the dummy sums that cannot be optimized out
    std::cout << ((method_1_sum > method_2_sum) ? "" : " ") << std::endl;
  }

  return 0;
}

Используемые мной заголовочные файлы находятся здесь:

• rng.hpp
• timer.hpp

Answer 6

Как это работает

Это зависит от конкретной реализации, однако в общем случае внутренняя структура векторных данных будет иметь указатель на блок памяти, в котором фактически располагаются элементы.И GCC, и VC ++ выделяют для 0 элементов по умолчанию.Таким образом, вы можете думать, что указатель внутренней памяти Vector по умолчанию равен nullptr.

Когда вы вызываете vector<int> vec(N);, как в вашем варианте 1, N объектов создаются с помощью конструктора по умолчанию.Это называется конструктор заполнения .

Когда вы делаете vec.reserve(N); после конструктора по умолчанию, как в варианте 2, вы получаете блок данных, содержащий 3 элемента, но объекты несоздается в отличие от варианта 1.

Зачем выбирать вариант 1

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

Зачем выбирать опцию 2

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

Answer 7

Другой вариант - довериться компилятору (tm) и выполнить push_back s, не вызывая reserve.Он должен выделять некоторое пространство, когда вы начинаете добавлять элементы.Возможно, он делает это так же хорошо, как и вы?

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

Answer 8

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

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

vector<int> vec;
for(int i=0; i<50; i++)
{
  cout << "size=" << vec.size()  << "capacity=" << vec.capacity() << endl;
  vec.push_back(i);
}

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

Answer 9

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

Метод # 1 : мы передаем в вектор параметр начального размера (назовем его n. Это означает, что вектор заполнен n элементами, которые будут инициализированы до значения по умолчанию Например, если вектор содержит int с, он будет заполнен n нулями.

Метод # 2 : сначала мы создаем пустой вектор. Затем мы резервируем место для n элементов. В этом случае мы никогда не создаем элементы n и, следовательно, никогда не выполняем инициализацию элементов в векторе. Поскольку мы планируем немедленно перезаписать значения каждого элемента, отсутствие инициализации не принесет нам никакого вреда. С другой стороны, поскольку мы сделали меньше в целом, это был бы лучший вариант *.

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

---

Вывод : используйте метод № 2.