Векторы STL с неинициализированным хранилищем?

StackOverflow https://stackoverflow.com/questions/96579

  •  01-07-2019
  •  | 
  •  

Вопрос

Я пишу внутренний цикл, который необходимо разместить structхранятся в смежных хранилищах.Я не знаю, сколько их structэто произойдет загодя.Моя проблема в том, что STL vector инициализирует его значения равными 0, поэтому независимо от того, что я делаю, я несу расходы на инициализацию плюс затраты на установку structчленов организации к их ценностям.

Есть ли какой-нибудь способ предотвратить инициализацию, или существует STL-подобный контейнер с изменяемым размером непрерывного хранилища и неинициализированными элементами?

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

Кроме того, смотрите мои комментарии ниже для получения разъяснений о том, когда происходит инициализация.

КАКОЙ - ТО КОД:

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size()
    memberVector.resize(mvSize + count); // causes 0-initialization

    for (int i = 0; i < count; ++i) {
        memberVector[mvSize + i].d1 = data1[i];
        memberVector[mvSize + i].d2 = data2[i];
    }
}
Это было полезно?

Решение

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

Лучший способ - это использовать reserve() и push_back(), так что используется конструктор копирования, избегающий построения по умолчанию.

Используя ваш пример кода:

struct YourData {
    int d1;
    int d2;
    YourData(int v1, int v2) : d1(v1), d2(v2) {}
};

std::vector<YourData> memberVector;

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size();

    // Does not initialize the extra elements
    memberVector.reserve(mvSize + count);

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a temporary.
        memberVector.push_back(YourData(data1[i], data2[i]));
    }
}

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

В текущей версии C ++ внутренний цикл немного неэффективен, поскольку временное значение создается в стеке, копируется в память векторов и, наконец, временное значение уничтожается.Однако в следующей версии C ++ появилась функция, называемая ссылками на R-значения (T&&), который поможет.

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

template <typename T>
class my_vector_replacement {

    // ...

    template <typename F>
    my_vector::push_back_using_factory(F factory) {
        // ... check size of array, and resize if needed.

        // Copy construct using placement new,
        new(arrayData+end) T(factory())
        end += sizeof(T);
    }

    char* arrayData;
    size_t end; // Of initialized data in arrayData
};

// One of many possible implementations
struct MyFactory {
    MyFactory(int* p1, int* p2) : d1(p1), d2(p2) {}
    YourData operator()() const {
        return YourData(*d1,*d2);
    }
    int* d1;
    int* d2;
};

void GetsCalledALot(int* data1, int* data2, int count) {
    // ... Still will need the same call to a reserve() type function.

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a factory
        memberVector.push_back_using_factory(MyFactory(data1+i, data2+i));
    }
}

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

Другие советы

C ++ 0x добавляет новый шаблон функции-члена emplace_back Для vector (который опирается на переменные шаблоны и идеальную пересылку), который полностью избавляет от любых временных ограничений:

memberVector.emplace_back(data1[i], data2[i]);

Для уточнения ответов reserve():вам нужно использовать reserve() в сочетании с push_back().Таким образом, конструктор по умолчанию вызывается не для каждого элемента, а скорее для конструктора копирования.Вы по-прежнему несете ответственность за настройку своей структуры в стеке, а затем копируете ее в вектор.С другой стороны, вполне возможно, что если вы используете

vect.push_back(MyStruct(fieldValue1, fieldValue2))

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

В C ++ 11 (и boost) вы можете использовать версию массива unique_ptr чтобы выделить неинициализированный массив.Это не совсем контейнер stl, но он по-прежнему управляется памятью и работает на C ++, чего будет достаточно для многих приложений.

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]);

Итак, вот проблема, resize вызывает insert, который выполняет построение копии из созданного по умолчанию элемента для каждого из вновь добавленных элементов.Чтобы получить значение 0, вам нужно написать свой собственный конструктор по умолчанию И свой собственный конструктор копирования в виде пустых функций.Выполнение этого с вашим конструктором копирования является очень плохая идея потому что это нарушит внутренние алгоритмы перераспределения std::vector.

Краткие сведения:Вы не сможете сделать это с помощью std::vector.

Эр...

попробуйте этот метод:

std::vector<T>::reserve(x)

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

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

После проверки на g++ следующий код:

#include <iostream>
#include <vector>

struct MyStruct
{
   int m_iValue00 ;
   int m_iValue01 ;
} ;

int main()
{
   MyStruct aaa, bbb, ccc ;

   std::vector<MyStruct> aMyStruct ;

   aMyStruct.push_back(aaa) ;
   aMyStruct.push_back(bbb) ;
   aMyStruct.push_back(ccc) ;

   aMyStruct.resize(6) ; // [EDIT] double the size

   for(std::vector<MyStruct>::size_type i = 0, iMax = aMyStruct.size(); i < iMax; ++i)
   {
      std::cout << "[" << i << "] : " << aMyStruct[i].m_iValue00 << ", " << aMyStruct[0].m_iValue01 << "\n" ;
   }

   return 0 ;
}

дает следующие результаты:

[0] : 134515780, -16121856
[1] : 134554052, -16121856
[2] : 134544501, -16121856
[3] : 0, -16121856
[4] : 0, -16121856
[5] : 0, -16121856

Инициализация, которую вы видели, вероятно, была артефактом.

[РЕДАКТИРОВАТЬ] После комментария к изменению размера я изменил код, чтобы добавить строку изменения размера.Изменение размера эффективно вызывает конструктор объекта по умолчанию внутри вектора, но если конструктор по умолчанию ничего не делает, то ничего не инициализируется...Я все еще верю, что это был артефакт (в первый раз мне удалось обнулить весь вектор с помощью следующего кода:

aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;

Итак...:-/

[ПРАВКА 2] Как уже предлагал Arkadiy, решение состоит в использовании встроенного конструктора, принимающего нужные параметры.Что -то вроде

struct MyStruct
{
   MyStruct(int p_d1, int p_d2) : d1(p_d1), d2(p_d2) {}
   int d1, d2 ;
} ;

Вероятно, это будет встроено в ваш код.

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

Используйте метод std::vector::reserve().Это не изменит размер вектора, но выделит пространство.

Судя по вашим комментариям к другим постерам, похоже, что вы остались с malloc() и друзьями.Vector не позволит вам создавать неструктурированные элементы.

Из вашего кода похоже, что у вас есть вектор структур, каждая из которых состоит из 2 целых чисел.Не могли бы вы вместо этого использовать 2 вектора целых чисел?Тогда

copy(data1, data1 + count, back_inserter(v1));
copy(data2, data2 + count, back_inserter(v2));

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

Если вы действительно настаиваете на неинициализации элементов и жертвуете некоторыми методами, такими как front(), back(), push_back(), используйте boost vector из numeric .Это позволяет вам даже не сохранять существующие элементы при вызове resize()...

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

template <typename T>
struct no_init
{
    T value;

    no_init() { static_assert(std::is_standard_layout<no_init<T>>::value && sizeof(T) == sizeof(no_init<T>), "T does not have standard layout"); }

    no_init(T& v) { value = v; }
    T& operator=(T& v) { value = v; return value; }

    no_init(no_init<T>& n) { value = n.value; }
    no_init(no_init<T>&& n) { value = std::move(n.value); }
    T& operator=(no_init<T>& n) { value = n.value; return this; }
    T& operator=(no_init<T>&& n) { value = std::move(n.value); return this; }

    T* operator&() { return &value; } // So you can use &(vec[0]) etc.
};

Для использования:

std::vector<no_init<char>> vec;
vec.resize(2ul * 1024ul * 1024ul * 1024ul);

Должны ли сами структуры находиться в непрерывной памяти, или вам может сойти с рук наличие вектора struct *?

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

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

int *memberArray;
int arrayCount;
void GetsCalledALot(int* data1, int* data2, int count) {
    memberArray = realloc(memberArray, sizeof(int) * (arrayCount + count);
    for (int i = 0; i < count; ++i) {
        memberArray[arrayCount + i].d1 = data1[i];
        memberArray[arrayCount + i].d2 = data2[i];
    }
    arrayCount += count;
}

Я бы сделал что-то вроде:

void GetsCalledALot(int* data1, int* data2, int count)
{
  const size_t mvSize = memberVector.size();
  memberVector.reserve(mvSize + count);

  for (int i = 0; i < count; ++i) {
    memberVector.push_back(MyType(data1[i], data2[i]));
  }
}

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top