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

Question

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

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

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

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

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

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

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

20

c++ vector stack allocator

Источник

user2101187 25 июн '13 в 14:24

6 ответов

Решение

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

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

7

Источник

user2380830 25 июн '13 в 14:27

То, как вы строите свой вектор (стек или куча), для этого не имеет значения.

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

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

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

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

Для простоты он объявляет вектор как класс с одним защищенным членом типа _Vector_impl,

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

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

6

Источник

user1594913 25 июн '13 в 14:28

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

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

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

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

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

Память может выглядеть так:

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

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

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

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

4

Источник

user241536 25 июн '13 в 15:04

Вы также можете зарезервировать зарезервированный размер,

vect.reserve(10000);

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

1

Источник

user2347994 25 июн '13 в 15:17

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

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

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

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

1

Источник

user212858 25 июн '13 в 15:29

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

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

0

Источник

user8405366 07 июн '19 в 18:36

Другие вопросы по тегам c++ vector stack allocator

user951423 25 июн '13 в 16:17 2013-06-25 16:17 · Accepted Answer · 2013-06-25 16:17

Вы написали

[...] скопируйте себя в новое местоположение [...]

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

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

Общий std::vector layout*

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

std:: векторный макет

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

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 в стеке

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

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

Вектор в куче

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

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

Давайте снова посмотрим на память.

std:: vector в куче

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

Вставка элементов в вектор

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

T a;
vect1.push_back(a);

std:: vector после одиночного push_back

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

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

vect1.push_back(a);

std:: vector после второго нажатия

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

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

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

vect1.pop_back();

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

std:: vector после 2х нажатий и 1х всплывающих окон

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