STL векторы с неинициализированным хранилищем? - PullRequest
40 голосов
/ 19 сентября 2008

Я пишу внутренний цикл, который должен поместить struct s в непрерывное хранилище. Я не знаю, сколько из этих 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];
    }
}

Ответы [ 14 ]

24 голосов
/ 19 сентября 2008

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-Value (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));
    }
}

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

10 голосов
/ 09 мая 2010

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

memberVector.emplace_back(data1[i], data2[i]);
8 голосов
/ 19 сентября 2008

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

vect.push_back(MyStruct(fieldValue1, fieldValue2))

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

7 голосов
/ 27 августа 2013

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

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]);
4 голосов
/ 19 сентября 2008

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

Резюме: вы не сможете сделать это с помощью std :: vector.

3 голосов
/ 19 сентября 2008

Эээ ...

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

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

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

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

После проверки на 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

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

[EDIT] После комментария к изменению размера я изменил код, добавив строку изменения размера. При изменении размера эффективно вызывается конструктор по умолчанию для объекта внутри вектора, но если конструктор по умолчанию ничего не делает, то ничего не инициализируется ... Я все еще считаю, что это был артефакт (мне впервые удалось сделать нулевым весь вектор с помощью следующий код:

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

Итак ... : - /

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

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

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

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

1 голос
/ 28 февраля 2017

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

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);
1 голос
/ 07 сентября 2011

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

1 голос
/ 19 сентября 2008

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

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

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

1 голос
/ 19 сентября 2008

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...