Расположение контейнеров STL в памяти
Привет всем.
Собственно вопрос: знает ли кто-нибудь, как котнейнеры STL (в частности интересует vector) располагаются в памяти? Насколько я знаю контейнер типа list совсем не обязательно должен располагаться последовательно, т.к. каждый элемент его хранит указатель на следующий и предыдущий, т.е. в памятит они могут лежать разрывно. А что с вектором? с очередью?
Простейший код + дебаггер показывают, что хранение вектора по крайней мере последовательное. но всегда ли это так?
Буду рад любым идеям и инфе )
p.s. Стек не рассматриваем, не подходит в силу специфики задачи ))
Собственно вопрос: знает ли кто-нибудь, как котнейнеры STL (в частности интересует vector) располагаются в памяти? Насколько я знаю контейнер типа list совсем не обязательно должен располагаться последовательно, т.к. каждый элемент его хранит указатель на следующий и предыдущий, т.е. в памятит они могут лежать разрывно. А что с вектором? с очередью?
Простейший код + дебаггер показывают, что хранение вектора по крайней мере последовательное. но всегда ли это так?
Буду рад любым идеям и инфе )
p.s. Стек не рассматриваем, не подходит в силу специфики задачи ))
Насчет вектора - это некоторая абстрактная модель, представляющая интерфейс динамического массива при операциях с элементами. Но стандартом, насколько я знаю, не оговорено ,как именно должен быть внутренне реализован вектор, особенности реализации определяются требованиями STL к сложности поддерж. контейнером операций.Потому подавляющее большинство реализаций использует для внутреннего представления дин. массив, потому элементы в нем всегда хранятся в определенном порядке (упорядоченная коллекция).
Цитата: Azaze1
Собственно вопрос: знает ли кто-нибудь, как котнейнеры STL (в частности интересует vector) располагаются в памяти?
Рекомендую читать стандарт C++ (2003г).
Там все подробно описано, в т.ч. что "The elements of a vector are stored contiguously".
Исключение - vector<bool>
Все контейнеры располагаются там, где их объявили: локальные - в стеке программы; глобальные/статические - в области глобальных перемен; поля класса - смотря где объект класса создан.
А данные контейнера располагаются в "куче". Но программист об этом думать не должен, ибо хороший контейнер скрывает операции выделения, перераспределения и освобождения памяти.
А данные контейнера располагаются в "куче". Но программист об этом думать не должен, ибо хороший контейнер скрывает операции выделения, перераспределения и освобождения памяти.
Цитата:
Простейший код + дебаггер показывают, что хранение вектора по крайней мере последовательное. но всегда ли это так?
Значит так ;)
В крайнем случае, ещё можно посмотреть исходники.
Цитата: el scorpio
Все контейнеры располагаются там, где их объявили: локальные - в стеке программы; глобальные/статические - в области глобальных перемен; поля класса - смотря где объект класса создан.
Мне показалось, автора скорее интересовала внутренняя структура контейнеров.
Цитата: el scorpio
А данные контейнера располагаются в "куче". Но программист об этом думать не должен, ибо хороший контейнер скрывает операции выделения, перераспределения и освобождения памяти.
В крайнем случае, ещё можно посмотреть исходники.
Думаю, их нужно cмотреть, куски хотя бы, чтобы знать особенности реализации.
el scorpio , интересует именно физическое расположение в памяти, а точнее "разрывность" расположения элементов )) То что дебаггер даже раз пять-шесть показал связное расположение в памяти ничего не значит - это может быть не доказательством, а наоборот, исключением из правил. ))
судя по исходникам вроде как должно быть связным, хотя я могу ошибаться.
2Green: спасибо ) в следующий раз буду смотреть внимательней )
судя по исходникам вроде как должно быть связным, хотя я могу ошибаться.
2Green: спасибо ) в следующий раз буду смотреть внимательней )
Вектор располагается в памяти непрерывной областью.Это позволяет получать эффективный прямой доступ к элементам операцией [ ]. Стандартом рекомендуется использовать по умолчанию вектор .
deque - располагается в памяти по кускам,но то же позволяет получать прямой доступ к элементам посредством [ ].( несколько медленее ?)
Кроме стандарта все контейнеры и последовательные и ассоциативные хорошо описаны (с рисунками) в книге Николай Джосьютис. С++Стандартная библиотека для профессионалов.(читаю - супер).
deque - располагается в памяти по кускам,но то же позволяет получать прямой доступ к элементам посредством [ ].( несколько медленее ?)
Кроме стандарта все контейнеры и последовательные и ассоциативные хорошо описаны (с рисунками) в книге Николай Джосьютис. С++Стандартная библиотека для профессионалов.(читаю - супер).