Какой тип структуры данных у QVector, QList, QMap? Опции

[AXELman4ever]

Доброго времени суток. Перечитал множество информации касательно работы этих контейнеров, но так и не нашел ответ на вопрос "Так где же хранится то, что находится в контейнере?" - в стеке или куче?

К примеру, я имею:

QVector<int> vect_int;

и

QVector<QWidget *> vect_widget;

вызывая метод push_back() для обеих случаев, что происходит в памяти, что кладется в мой вектор, и где хранится то, что кладется в мой вектор? или другими словами - где вектор хранит ссылки на объекты или же сами объекты?

в контейнерах QList и QMap происходит тоже самое? (о том что такое QList, QMap, и о принципах их роботы мне известно)

Убедительная просьба - растолковать. Перекопал весь инет - нигде ничего об этом не упоминается.
Заранее благодарен.

[Алексей1153]

AXELman4ever, полагаю, что QVector устроен аналогично std::vector.

Кратко о последнем: по стандарту весь массив данных должен быть выделен в памяти в виде одного сплошного блока, что позволяет переходить к работе как с обычным массивом:

std::vector<int> vec(10,0); //контейнер на 10 элементов, инициализированных 0

int* pArray=&vec[0]; //указатель на начало массива
 //vec.size()  - количество элементов в массиве

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

когда меняем размер контейнера в бОльшую сторону, то контейнер смотрит, хватает ли ему уже выделенной заранее памяти (см.методы reserve , capacity) . Если хватает, то массив в памяти не меняет адрес, только увеличивается в размере (увеличивается соответствующая переменная в классе, хранящая текущую длину массива). Если памяти мало, то происходит переаллокация - выделяется новый блок памяти нужного размера, данные копируются, старый блок возвращается в кучу. Операция очень "тяжёлая" в плане быстродействия, поэтому всегда нужно планировать и контролировать возникновение переаллокаций всех алгоритмах, где производится очень много изменений размера массива. Заранее зарезервировать память можно через reserve. При переаллокации становятся невалидными все итераторы и указатели, связанные с данными в контейнере. При уменьшении размера вектора (а также при вызове метода clear или методов resize/assign с мЕньшим размером, чем size() ) переаллокации не происходит, освободившаяся часть памяти остаётся висеть "мёртвым грузом" (вернее - быть зарезервированной). Это часто удобно, когда содержимое вектора часто меняется, не превышая определённый размер массива.

У вектора есть особенность: при добавлении N элементов типа T, конструктор T() вызывется один раз, затем этот объект копируется во все элементы оператором = (он должен быть определён для T). Поэтому, если в конструкторе T() имеется, к примеру, некий статический счётчик экземпляров класса T , то этот счётчик будет считать некорректно (меньше, чем на самом деле). Деструкторы для каждого элемента вызываются исправно


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

Сообщение отредактировал Алексей1153 - 23.9.2011, 18:37

[BRE]

QList и QMap используют внутри себя узлы с указателями на соседние узлы, ...

Это не про QList. Связанный список в Qt это QLinkedList.
QList это скорее умный std::vector.