Какой самый быстрый способ реинициализации вектора?

Question

Какой самый быстрый способ сбросить все значения большого вектора до значений по умолчанию?

struct foo
{
  int id;
  float score;
};

std::vector<foo> large_vector(10000000);

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

Мне нужно перебрать вектор, чтобы собрать ненулевые баллы (может быть тысячи или миллионы), прежде чем его сбросить. Должен ли я сбросить структуры по одному в этом цикле?

Edit:

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

Answer 1

Какой самый быстрый способ реинициализации вектора?

Не.

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

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

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

Вам просто нужно будет push_back или emplace_back, когда вы будете писать в вектор после clear() ing, вместо использования operator[].

Чтобы сделать это совместимым с первым использованием, не инициализируйте ваш вектор 10000000 сконструированными значениями элементов, но используйте reserve(10000000) для предварительного выделения без инициализации.

например.

int main() {
  vector<foo> v;
  v.reserve(10000000);

  while(keep_running) {
    use(v);
    v.clear();
  }
}

// precondition: v is empty, so
// don't access v[i] until you've done
//   v.push_back({id,score})
// at least i+1 times
void use(vector<foo> &v) {
}

---

Так как вам нужно обнулить ваши элементы на месте, второе самое быстрое решение общего назначения, вероятно, состоит в том, чтобы изменить цикл выше на

  while(keep_running) {
    v.resize(10000000);
    use(v);
    v.clear();
  }

или, альтернативно, удалите clear() и используйте fill(), чтобы перезаписать все элементы на месте.

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

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

Answer 2

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

Существует несколько различных способов «реинициализации» вектора:

1. Позвоните clear(), для тривиальных типов это должно быть примерно эквивалентно простому выполнению vector.size = 0. Емкость вектора не меняется, и никакие элементы не освобождаются. Деструкторы будут вызываться для элементов, если они существуют. Поскольку вы push_back, emplace_back или resize вектор, старые значения будут перезаписаны.
2. Звоните assign(), например, large_vector.assign( large_vector.size(), Foo() );. Это будет перебирать весь вектор, сбрасывая каждый элемент к его значению по умолчанию. Надеемся, что компилятору удастся оптимизировать это под memset или подобное.
3. Поскольку ваш тип тривиален, если вы хотите просто сбросить каждый элемент на 0, вы можете сделать memset, например: memset( large_vector.data(), 0, sizeof(Foo)*large_vector.size() );.
4. Звоните std::fill например std::fill( large_vector.begin(), large_vector.end(), Foo() );, это должно быть похоже на assign или memset.

Answer 3

Какой самый быстрый способ сбросить все значения большого вектора до значений по умолчанию?

Зависит от того, что означает вектор в его "значениях по умолчанию".

Если вы хотите удалить все элементы, наиболее эффективным является std::vector::clear.

Если вы хотите сохранить все элементы в векторе, но установить их состояние, вы можете использовать std::fill:

std::fill(large_vector.begin(), large_vector.end(), default_value);

---

Если тип элемента тривиален, а «значение по умолчанию» равно нулю ^† , тогда std::memset может быть оптимальным:

static_assert(std::is_trivially_copyable_v<decltype(large_vector[0])>);
std::memset(large_vector.data(), 0, large_vector.size() * sizeof(large_vector[0]));

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

^† Ноль в том смысле, что все биты не установлены. C ++ не гарантирует, что это представление для нулевого числа с плавающей запятой. Это также не гарантирует, что он будет нулевым указателем, если ваш неминимальный вариант использования использует указатели.