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

[AXELman4ever]

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

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

QVector<int> vect_int;

и

QVector<QWidget *> vect_widget;

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

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

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

[Авварон]

Всегда в куче. Имея размер стека 2мб много данных не похранишь.

[AXELman4ever]

Всегда в куче. Имея размер стека 2мб много данных не похранишь.

Ок, а каким образом получается так, что объекты, хранящиеся в куче занимают места по порядку? Об этом заботится архитектура класса?

[Vass]

Ок, а каким образом получается так, что объекты, хранящиеся в куче занимают места по порядку? Об этом заботится архитектура класса?

Да, если вы откроете qvector.h/cpp

Вы увидите там приватный класс QVectorData

С такими методами:

 static QVectorData *malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init);
    static QVectorData *allocate(int size, int alignment);
    static QVectorData *reallocate(QVectorData *old, int newsize, int oldsize, int alignment);
    static void free(QVectorData *data, int alignment);

Если внимательно изучить код, то становится видно, что класс QVector выделяет на куче кусок памяти и в нем по порядку размещает элементы, соответсвенно если не хватает места вызывается reallocate ну и т.д.

[Алексей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.

[Алексей1153]

BRE, я с ним не работал, если честно ) Ну а в чём его умность ?

[BRE]

BRE, я с ним не работал, если честно ) Ну а в чём его умность ?

Он сам решает, в зависимости от типа данных, как их хранить. Если sizeof типа меньше или равен размеру указателя, то данные хранятся как в обычном std::vector, а если больше или тип не POD, то хранить указатели на данные.

Сообщение отредактировал BRE - 23.9.2011, 10:43

[Алексей1153]

BRE, понятно ) Никогда не буду им пользоваться, зачем мне такая самодеятельность

[AXELman4ever]

Премного благодарен всем отписавшимся здесь, в отдельности - Алексей1153. Просто, точно и доступно