Что происходит, когда вы увеличиваете размер структуры в векторе? - PullRequest
Новая
       16

Что происходит, когда вы увеличиваете размер структуры в векторе?

1 голос
/ 15 апреля 2011

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

Вот ультра базовый, никаких проверок безопасности ни на одном примере: 

struct DataStructure
{
    std::vector<Entry> mCollection;
};

struct Entry
{
    char mValue;
    std::vector<unsigned int> mOffsetCollection; //a vector of indexes that are offsets to other entries.
};

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

DataStructure d;
Entry entry;
entry.mValue = 'a';
d.push_back(entry);
.
.
.//add some more entries...
.
.
//now suppose I add a bunch of offsets to these various entries in my array.
Entry& firstEntry = d.at(0);
firstEntry.mOffsetCollection.push_back(4);
firstEntry.mOffsetCollection.push_back(9);
firstEntry.mOffsetCollection.push_back(32);
..

Так что размер этой первой записи увеличивается. Что именно происходит? Я просто пробежался по маленькому примеру, и он, кажется, работал нормально. Другие записи в структуре данных не были затронуты. Сначала я был обеспокоен тем, что, возможно, если размер структуры станет большим, это приведет к следующему элементу в массиве, но я предполагаю, что этого не происходит. Это заставляет меня понять, что я действительно не знаю, что происходит за кулисами. vector<Entry> в DataStructure d необходимо перераспределить память?

Ответы [ 4 ]

3 голосов
/ 15 апреля 2011

Да, std::vector динамически управляет собственной памятью.

Размер структуры (в действительности, любого типа данных) фиксируется во время компиляции;это не затрагивается во время выполнения.

1 голос
/ 15 апреля 2011

Вы не используете динамическое размещение, но векторный класс.Внутренний vector<int> хранит свой массив переменной длины внешне для объекта Entry, который вы помещаете во внешний вектор.

0 голосов
/ 16 апреля 2011

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

Что происходит, когда вы увеличиваете размерstruct in vector?

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

Если вы выполните sizeof(DataStructure) в начале программы, затем отодвинете кучу вещей назад и снова выполните sizeof(DataStructure), результаты будут точно такими же.Это потому, что данные, которые вы возвращаете, не часть из DataStructure iself, а указывает на чем-то в DataStructure.

Гдеэто указатели, о которых я говорю?В vector.vector также никогда не меняет размер - но количество элементов в нем меняется.vector управляет указателем на некоторый динамически размещенный массив вещей, которые вы отбрасываете назад.Когда вы отодвигаете больше материала, управляемый массив заполняется.Когда управляемый массив, наконец, заполнен до capacity(), vector должен выделить новый, больший массив и скопировать в него ваши данные (именно поэтому объекты, содержащиеся в STL, должны быть «копируемыми»).

0 голосов
/ 15 апреля 2011

Размер std::vector является постоянным, поскольку он хранит данные с использованием указателей для внутренней кучи блоков, как правило, он имеет указатель начала, конца и текущий указатель, и не намного, что делает его довольно маленьким.

...