Когда векторы распределяются, они используют память в куче или стеке?

152

Все ли следующие утверждения верны?

vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

Как выделяется внутренняя память для Typeодного vectorили любого другого контейнера STL?

Phelodas
источник

Ответы:

223
vector<Type> vect;

выделит vector, т.е. информацию заголовка, в стеке, но элементы в свободном хранилище («куча»).

vector<Type> *vect = new vector<Type>;

распределяет все по бесплатному магазину.

vector<Type*> vect;

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

Фред Фу
источник
3
Но у меня есть сценарий, где я получаю ошибку сегментации, когда Type становится большим во втором объявлении. Я предполагал, что это потому, что тип был размещен в стеке.
Фелодас
4
@Phelodas: не видя ваш код, это невозможно оценить. Пожалуйста, откройте новый вопрос.
Фред Фу
2
О , vector<Type> vect;так как элементы на куче и информация заголовка находится в стеке, когда информация заголовка удаляется из памяти, как возвращение функции, что будет происходить с элементами памяти? Они исправлены с информацией заголовка или нет? Если нет, это приведет к утечке памяти?
Flyrain
3
@flyrain: векторы убирают за собой. Читайте о RAII .
Фред Фу
1
@flyrain: это должно работать. Пожалуйста, отправьте новый вопрос с более подробной информацией. Если вы разместите ссылку здесь, я мог бы взглянуть на нее.
Фред Фу
25
vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

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

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

Нет. То же, что и выше, за исключением того, что vectorкласс тоже будет в куче.

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

vectбудет в стеке, его элементы (указатели Type) будут в куче, и вы не можете сказать, где будут те, Typeна которые указывают указатели. Может быть в стеке, может быть в куче, может быть в глобальных данных, может быть нигде (т.е. NULLуказатели).

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

jpalecek
источник
23

Предполагая реализацию, которая на самом деле имеет стек и кучу (стандарт C ++ не требует таких вещей), единственное верное утверждение - последнее.

vector<Type> vect;
//allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

Это верно, за исключением последней части ( Typeне будет в стеке). Представить:

  void foo(vector<Type>& vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec.push_back(Type());
  }

  int main() {
    vector<Type> bar;
    foo(bar);
  }

Точно так же:

 vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

True, за исключением последней части, с аналогичным контрпримером:

  void foo(vector<Type> *vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec->push_back(Type());
  }

  int main() {
    vector<Type> *bar = new vector<Type>;
    foo(bar);
  }

Для:

vector<Type*> vect; //vect will be on stack and Type* will be on heap. 

это правда, но обратите внимание, что Type*указатели будут в куче, но Typeэкземпляры, на которые они указывают, не обязательно должны быть:

  int main() {
    vector<Type*> bar;
    Type foo;
    bar.push_back(&foo);
  }
Флексо
источник
в каком контексте у вас не было бы стека? Я понимаю, что вы говорите, что стандарт не требует этого, но практически говоря, когда бы вы были без стека?
Nerdtron
3
@Nerdtron - IIRC на некоторых небольших микроконтроллерах у вас есть стек вызовов, который не может хранить ничего, кроме ПК (счетчик программ) в точке последнего вызова, готовый к RET. Следовательно, ваш компилятор может выбрать «автоматическое хранение» (для нерекурсивных функций) в фиксированном месте, практически не имея отношения к потоку выполнения. Это может довольно разумно сгладить всю программу. Даже для рекурсивного случая у вас может быть политика «стек на функцию» или отдельный стек для автоматических переменных и адресов возврата, что делает фразу «стек» несколько бессмысленной.
Flexo
Вы можете использовать выделение на основе кучи для всего и иметь «стек очистки», который управляет автоматическим хранением (и, возможно, deleteтоже).
Flexo
3

Только это утверждение верно:

vector <Type*> vect; //vect will be on stack and Type* will be on heap.

Type* указатели размещаются в куче, потому что количество указателей может изменяться динамически.

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

Алексей Хлебников
источник
2
Тип * не указывает на выделение кучи, просто указатель на объект типа. Тем не менее, вектор сохраняет указатель на кучу. int a = 5; int * ptr_to_a = & a; vector <int *> vec; vec.push_back (ptr_to_a); (см. ответ jpalecek)
Мэтью Рассел
1

У вектора есть внутренняя часть, allocatorкоторая отвечает за распределение / освобождение памяти heapдля vector element. Поэтому независимо от того, как вы создаете вектор, elementон всегда располагается на heap. Что касается метаданных вектора, это зависит от того, как вы их создаете.

бинго
источник