Базовые знания

Всем доброго времени суток!

У меня появилась нужда в систематизации знаний языка,и потому хотел бы узнать несколько интересующих меня тем,если есть возможность,то посоветуйте какую либо литературу или дайте ответ на несколько достаточно простых вопросов:

1.Как в памяти представляются Массивы,Списки,Очереди,Деревья,Стеки.
2.Что мы можем узнать из адреса переменной?
3.Как в памяти представляются Статические члены,глобальные и локальные объекты,константные объекты?
4.Методы отладки,дизассемблер.

Заранее благодарю и прошу прощения за незнание таких элементарных вещей!

0

по поводу первого вопроса - массивов, списков и прочих структур данных лично я бы посоветовал почитать книгу Кнут, Д. Искусство программирования.
ответы на 2-й и 3-й можно поискать в литературе указанной здесь Литература C++ (лично я начинал со Страуструпа)

0

Сообщение от nikeo 1.Как в памяти представляются Массивы,Списки,Очереди,Деревья,Стеки.

Массивы - непрерывный кусок памяти, где каждай последующий элемент лежит за предыдущим. Т.е. адрес a[1] == адрес a[0] + sizeof(тип а).
Списки, очереди и прочие монстры - это структуры для хранения данных (контейнеры), которые могут быть реализованы соверешенно как угодно (в том числе и на основе массива). Так что как они в памяти лежат - вопрос к разработчику контейнеров.

Добавлено через 4 минуты

Сообщение от nikeo 2.Что мы можем узнать из адреса переменной?

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

Добавлено через 5 минут

Сообщение от nikeo 3.Как в памяти представляются Статические члены,глобальные и локальные объекты,константные объекты?

Статические члены классов - это в принципе те же глобальные объекты, но их область видимости ограничена областью видимости класса. Глобальные переменные где-то в памяти лежат. Локальные объекты, как правило, создаются в стеке. Константные объекты компилятор может поместить в область памяти, доступной только для чтения.

1

1.
а) массив - это непрерывный блок данных. Это означает, что зная, где этот блок начинается и какой размер имеет, мы можем легко переместиться в любую часть этого блока по номеру искомого элемента;
б) список - структура данных, в которой мы можем, имея некоторый элемент, получить следующий (для односвязного списка) или следующий и предыдущий (для двусвязного списка). Фактически же список представляется в памяти как обособленные куски данных - узлы списка, связываются которые посредством указателей - каждый узел содержит указатель на следующий (или следующий и предыдущий) узел;
в) очередь - это просто абстракция, структура данных, в которую элементы можно складывать только в конец, а доставать только из начала. Представлена может быть как в виде списка, так и в виде массива, так и в виде любой последовательной структуры данных;
г) дерево, аналогично списку - разрозненные элементы данных в памяти. Однако структура связей уже другая. В каждом элементе (предке) хранится некоторое количество указателей на другие элементы (на потомков), которые являются корнями поддеревьев. Эти корни поддеревьев, в свою очередь, хранят указатели на своих потомков и так далее. Тут есть два исключения: существует один элемент, на которого не ссылается указатель ни в каком другом элементе - это корень всего дерева, а также есть элементы, которые не ссылаются ни на какие другие элементы (корни поддеревьев) - они называются листами дерева;
д) стек - смотри пункт в) про очередь.

2. Не совсем понятен вопрос. Можем узнать адрес (ваш кэп). Можем узнать значение, лежащее по этому адресу.

3. Представляются абсолютно одинаково - в виде блоков данных, которые и формируют эти объекты. Другое дело - в какой памяти и как с этой памятью можно работать, а также какое время жизни будет у таких объектов. Тут стоит оговориться про то, что константные объекты, если это объекты примитивных типов, могут быть подставлены компилятором в место их использования как значения этих объектов (т.н. оптимизация constant propagation), за счёт этого компилятор может вычислить значения некоторых выражений (подвыражения тоже можно считать выражениями), в которых используются только константы (т.н. оптимизация constant folding).

4. Тут даже и не знаю, что написать... Отлаживать с помощью отладчиков. А дизассемблер - для дизассемблирования .

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

2

Александреску A. "Современное проектирование на С++", гл.4 Размещение в памяти небольших объектов.
Вообще глобальность как область видимости, часто путается со статичностью как способом хранения. Однако, легко себе представить динамический объект с глобальной видимостью, хотя память выделяется в куче или наоборот статический объект для которого известен размер, но видимость ограничена, функцией например, и при этом память используется в области данных. Что касается массивов, то уже для 2-мерного динамического массива нет гарантии размещения элементов подряд, так как это массив одномерных массивов и память выделяется последовательно для каждого массива. Вообще тема очень большая и мне тоже интересно узнать больше.

0

Сообщение от IGPIGP уже для 2-мерного динамического массива нет гарантии размещения элементов подряд

Тут уже от уровня абстракции зависит. Строго говоря, в языке такого понятия, как "двумерный динамический массив", не существует. Да, часто двумерный динамический массив представляется как массив указателей на одномерные динамические массивы, однако если внутренняя реализация двумерного динамического массива - одномерный массив, расположенный по строкам, для которого из двух индексов элемента (по строке и столбцу) вычисляется один индекс для доступа во внутреннем представлении, и с виду это всё дело выглядит и работает как двумерный массив, почему бы не считать его двумерным динамическим массивом?

1

Спасибо вам за ответы)
1.По поводу адреса и подразумевался указатель,а точнее его значение,и суть вопроса была в том,что можно сказать о переменной,глядя на 16-ое значение указателя,то есть как определить тип.
2.Первый вопрос подразумевал как раз таки контейнеры STL(и кстати ни кто не знает отличие его от Tulip?)
3.Какие методы отладки существуют?(помимо точек останова и вывода информации в консоль)
Можно ли использовать данные дизассемблера для отладки?(если я правильно выразился,а то был у меня случай,когда выполнение программы останавливалось и выдавлся лист со значениями)

Прошу прощения если опять выразился не понятно!

Добавлено через 2 минуты

Сообщение от IGPIGP Александреску A. "Современное проектирование на С++", гл.4 Размещение в памяти небольших объектов. Вообще глобальность как область видимости, часто путается со статичностью как способом хранения. Однако, легко себе представить динамический объект с глобальной видимостью, хотя память выделяется в куче или наоборот статический объект для которого известен размер, но видимость ограничена, функцией например, и при этом память используется в области данных. Что касается массивов, то уже для 2-мерного динамического массива нет гарантии размещения элементов подряд, так как это массив одномерных массивов и память выделяется последовательно для каждого массива. Вообще тема очень большая и мне тоже интересно узнать больше. Не по теме: А сейчас, - главный вопрос забьет ли Кличко Баку баки?!

Как раз вот это и читаю!)

0

nikeo, правила - один вопрос - одна тема

0

nikeo, да в принципе ничего о переменной по указателю сказать нельзя. Если использовать RTTI, то typeof(*ptr_to_var) даст её тип, но особого смысла в этом я не вижу.
Если вопрос про STL-контейнеры, то std::vector основан на динамическом массиве, который обычно имеет большую, чем необходимо в данный момент, фактическую длину. Как только место заканчивается - выделяется новый массив большего размера (стандартные множители размера - 2 или 1,6 (золотое сечение, 1,618...)).
Список (std::list) реализуется так, как я рассказал выше, с учётом того, что он ещё и кольцевой (последний элемент хранит указатель на первый).
Как такового дерева в стандартных контейнерах нет, но такие структуры, как std::set и std::map (а также их мультиверсии) представляются красно-чёрными деревьями. Помимо самого хранения данных в виде бинарного дерева, во время вставок и удалений происходит балансировка дерева, с целью равномерно распределить элементы по всему дереву (чтобы не было так, что, например, левое поддерево корня имеет высоту 10, а правое - высоту 2).
Стек (std::stack) и очередь (std::queue) в контексте STL - адаптеры контейнеров (т.е. внутри представлены каким-либо контейнером, а наружу выдают только ту часть его интерфейса, которая характерна для конкретной структуры). Теоретически в качестве контейнера в стек и очередь можно при создании в качестве второго аргумента шаблона можно передать любой последовательный контейнер, но по умолчанию используется std::deque, так называемый дек, характерный тем, что имеет быструю вставку в начало и конец. Внутренне представлен как связный список небольших массивов (в первом приближении). Расширяется за счёт выделения нового такого узла-массива. Лень мне расписывать его внутреннюю структуру, можно поискать по ключевому слову "std::deque внутренняя реализация".

1

Спасибо что открыли!)

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

Добавлено через 2 минуты

Сообщение от silent_1991 nikeo, да в принципе ничего о переменной по указателю сказать нельзя. Если использовать RTTI, то typeof(*ptr_to_var) даст её тип, но особого смысла в этом я не вижу. Если вопрос про STL-контейнеры, то std::vector основан на динамическом массиве, который обычно имеет большую, чем необходимо в данный момент, фактическую длину. Как только место заканчивается - выделяется новый массив большего размера (стандартные множители размера - 2 или 1,6 (золотое сечение, 1,618...)). Список (std::list) реализуется так, как я рассказал выше, с учётом того, что он ещё и кольцевой (последний элемент хранит указатель на первый). Как такового дерева в стандартных контейнерах нет, но такие структуры, как std::set и std::map (а также их мультиверсии) представляются красно-чёрными деревьями. Помимо самого хранения данных в виде бинарного дерева, во время вставок и удалений происходит балансировка дерева, с целью равномерно распределить элементы по всему дереву (чтобы не было так, что, например, левое поддерево корня имеет высоту 10, а правое - высоту 2). Стек (std::stack) и очередь (std::queue) в контексте STL - адаптеры контейнеров (т.е. внутри представлены каким-либо контейнером, а наружу выдают только ту часть его интерфейса, которая характерна для конкретной структуры). Теоретически в качестве контейнера в стек и очередь можно при создании в качестве второго аргумента шаблона можно передать любой последовательный контейнер, но по умолчанию используется std::deque, так называемый дек, характерный тем, что имеет быструю вставку в начало и конец. Внутренне представлен как связный список небольших массивов (в первом приближении). Расширяется за счёт выделения нового такого узла-массива. Лень мне расписывать его внутреннюю структуру, можно поискать по ключевому слову "std::deque внутренняя реализация".

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

0

Сообщение от nikeo Вот я не могу понять одной вещи,говорят что в связанном списке,элемент содержит информацию о другом элементе,но как?в чем это выражается?

В хранимом указателе на другой элемент.

0

nikeo, с помощью указателя.
И да, в своих предыдущих сообщениях я расписывал внутреннюю представление различных контейнеров, а главное сказать забыл: стандарт на самом не определяет внутреннюю структуру. Он определяет только какие-то общие особенности, например, для вектора стандарт гарантирует, что внутренне он представлен как непрерывная область памяти, для множества и отображения определяет сложность "О большое" алгоритмов вставки, удаления и доступа (просто красно-чёрное дерево соответствует определённой стандартом сложности). Но в известных мне реализациях STL используются именно описанные мной структуры, хотя никто не ограничивает разработчиков в выборе другого внутреннего представления.

Добавлено через 54 секунды

Сообщение от nikeo Что такое STL контейнеры я знаю)как то меня просто спросили,как они представляются в памяти,на что я не смог ответить,так как не задумывался над этим.

Так я и описал, как они в памяти представляются.

0

Сообщение от nikeo Вот я не могу понять одной вещи,говорят что в связанном списке,элемент содержит информацию о другом элементе,но как?в чем это выражается?

Он содержит адрес следующего (если список двусвязный, то еще и предыдущего) элемента списка.

0

Сообщение от Croessmah Он содержит адрес следующего (если список двусвязный, то еще и предыдущего) элемента списка.

вот в том то и дело,что где он этот адрес содержит?как его "вытащить"?

Добавлено через 2 минуты
Или смысл в том,что элементы "разбросаны" по памяти?

0

Сообщение от nikeo что где он этот адрес содержит?

0

Сообщение от Croessmah C++ 1 2 3 4 struct A{    int value;    A* nextelement; }

Спасибо!Простите что затупил

0