Подтвердить что ты не робот

С++ Vector, что происходит, когда он расширяется/перераспределяется в стеке?

Я новичок в С++, и я использую класс vector в моем проекте. Я нашел это весьма полезным, потому что у меня может быть массив, который автоматически перераспределяется всякий раз, когда это необходимо (т.е. Если я хочу push_back элемент, и вектор достиг максимальной емкости, он перераспределяет себя, запрашивая больше памяти для ОС), поэтому доступ к элементу вектора очень быстрый (это не похоже на список, который для достижения "n-го" элемента должен пройти через "n" первых элементов).

Я нашел этот вопрос очень полезным, потому что их ответы прекрасно объясняли, как работает "распределитель памяти", когда я хочу сохранить свой вектор в куче/стеке:

[1] vector<Type> vect;
[2] vector<Type> *vect = new vector<Type>;
[3] vector<Type*> vect;

Однако, какое-то сомнение вызывает у меня какое-то время, и я не могу найти ответ: Всякий раз, когда я создаю вектор и начинаю нажимать много элементов, он достигнет момента, когда вектор будет заполнен, поэтому для продолжения роста ему нужно будет перераспределить, скопировать себя в новое место и затем продолжите pushing_back элементы (очевидно, это перераспределение скрыто для реализации класса, поэтому оно полностью прозрачно для меня)

Хорошо, если я создал вектор в куче [2], у меня нет проблем, представляющих, что может случиться: вызовы класса vector malloc, приобретают новое пространство, а затем копируют себя в новую память и, наконец, удаляют старую память звоните бесплатно.

Тем не менее, вуаль скрывает то, что происходит, когда я конструирую вектор в стеке [1]: что происходит, когда вектор должен перераспределяться? AFAIK, всякий раз, когда на C/С++ вы вводите новую функцию, компьютер будет искать объявление переменных, а затем развернуть стек, чтобы получить необходимое пространство для размещения этих переменных, но вы не можете выделить больше места в стеке, когда функция уже запущена. Как вектор класса решает эту проблему?

4b9b3361

ОТВЕТЫ

Ответ 1

Вы написали

[...] скопировать себя в новое место [...]

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

Мой ответ должен дать вам представление о том, как вектор создан.

Общий макет std::vector *

Примечание. std::allocator скорее всего будет пустым классом, а std::vector, вероятно, не будет содержать экземпляр этого класса. Это может быть неверно для произвольного распределителя.

std::vector layout

В большинстве реализаций он состоит из трех указателей, где

  • begin указывает на начало памяти данных вектора в куче (всегда на куче, если не nullptr)
  • end указывает на одну ячейку памяти за последний элемент векторных данных - > size() == end-begin
  • capacity указывает на местоположение памяти за последний элемент векторной памяти → capacity() == capacity-begin

Вектор в стеке

Объявляем переменную типа std::vector<T,A>, где T - любой тип, а A - тип распределителя для T (т.е. std::allocator<T>).

std::vector<T, A> vect1;

Как это выглядит в памяти?

std::vector on the stack

Как мы видим: в куче ничего не происходит, но переменная занимает память, которая необходима всем ее членам в стеке. Там он и останется там до тех пор, пока vect1 не выйдет из области видимости, так как vect1 - это просто объект, как любой другой объект типа double, int или что-то еще. Он будет сидеть там в позиции стека и ждать, пока он не будет уничтожен, независимо от того, сколько памяти он обрабатывает в куче.

Указатели vect1 не указывают нигде, так как вектор пуст.

Вектор на куче

Теперь нам нужно указать указатель на вектор и использовать некоторое динамическое распределение кучи для создания вектора.

std::vector<T, A> * vp = new std::vector<T, A>;

Вернемся к памяти.

std::vector on the heap

У нас есть переменная vp в стеке, и наш вектор теперь находится в куче. Опять же, сам вектор не будет перемещаться по куче, поскольку его размер постоянный. Только указатели (begin, end, capacity) будут перемещаться, чтобы следовать за положением данных в памяти, если происходит перераспределение. Давайте посмотрим на это.

Нажатие элементов на вектор

Теперь мы можем начать нажимать элементы на вектор. Посмотрим на vect1.

T a;
vect1.push_back(a);

std::vector after single push_back

Переменная vect1 все еще находится там, где она была, но память в куче была выделена, чтобы содержать один элемент T.

Что произойдет, если мы добавим еще один элемент?

vect1.push_back(a);

std::vector after second push

  • Пространство, выделенное в куче для элементов данных, будет недостаточным (так как это только одна ячейка памяти).
  • Новый блок памяти будет выделен для двух элементов
  • Первый элемент будет скопирован/перенесен в новое хранилище.
  • Старая память будет освобождена.

Мы видим: новое расположение памяти отличается.

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

vect1.pop_back();

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

std::vector after 2x push and 1x pop

Как вы можете видеть: capacity() == capacity-begin == 2 while size() == end-begin == 1

Ответ 2

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

(Тривиальный класс class foo {int* data;}; имеет эту характеристику)

Ответ 3

Способ построения вашего вектора (стек или куча) для этого не имеет значения.

Смотрите документацию для std::vector

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

Когда вектор "растет", векторный объект не растет, изменяется только внутренний динамический массив.

Что касается его реализации, вы можете посмотреть реализацию вектора GCC.

Чтобы сохранить его простым, он объявляет вектор как класс с одним защищенным членом, типа _Vector_impl.

Как вы можете видеть, он объявлен как структура, содержащая три указателя:

  • То, что указывает на начало хранилища (и начало данных)
  • То, что указывает на конец данных
  • Один для конца хранилища

Ответ 4

В основном вы спрашиваете о деталях реализации vector. Стандарт С++ не определяет способ реализации vector - он определяет только то, что должен делать vector и какие операции необходимо выполнить. Никто не может сказать вам с 100% точностью, что происходит, когда vector перераспределяется, потому что каждый компилятор теоретически отличается.

Таким образом, нетрудно понять, как обычно реализуется vector. Сам вектор представляет собой просто структуру данных, которая имеет указатель на фактические данные, хранящиеся "в" vector. Что-то в этом роде:

template <typename Val> class vector
{
public:
  void push_back (const Val& val);
private:
  Val* mData;
}

Выше, очевидно, psudocode, но вы получаете идею. Когда a vector выделяется в стеке (или в куче):

vector<int> v;
v.push_back (42);

Память может выглядеть следующим образом:

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +=======+

Когда вы push_back до полного вектора, данные будут перераспределены:

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +-------+
                |  43   |
                +-------+
                |  44   |
                +-------+
                |  45   |
                +=======+

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

Ответ 5

вы также можете зарезервировать резерв ожидаемого размера,

vect.reserve(10000);

это зарезервирует 10000 пространство объектов используемого типа

Ответ 6

Вектор не является массивом элементов или памятью, используемой для хранения таких файлов.

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

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

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

Ответ 7

Если вы сделаете некоторый растущий вектор, от пустого до некоторого размера, будете использовать стратегию удвоения, и большую часть времени перераспределять, в этом примере используя целое число от 1 до 10000, и clang (std = 2a -O3) получит это Это просто для удовольствия, показывая важность использования резерва. vector :: begin() указывает на начало фактического массива, а vector ::acity показывает фактическую емкость. С другой стороны, итератор признан недействительным.

std::vector<int> my_vec;
auto it=my_vec.begin();
for (int i=0;i<10000;++i) {
    auto cap=my_vec.capacity();
    my_vec.push_back(i);
    if(it!=my_vec.begin()) {
        std::cout<<"it!=my_vec.begin() :";
        it=my_vec.begin();
    }
    if(cap!=my_vec.capacity())std::cout<<my_vec.capacity()<<'\n';
}

Это дает следующий результат:

it!=my_vec.begin() :1
it!=my_vec.begin() :2
it!=my_vec.begin() :4
it!=my_vec.begin() :8
it!=my_vec.begin() :16
it!=my_vec.begin() :32
it!=my_vec.begin() :64
it!=my_vec.begin() :128
it!=my_vec.begin() :256
it!=my_vec.begin() :512
it!=my_vec.begin() :1024
it!=my_vec.begin() :2048
it!=my_vec.begin() :4096
it!=my_vec.begin() :8192
it!=my_vec.begin() :16384