Форум программистов, компьютерный форум CyberForum.ru

Базовые знания - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.75
nikeo
0 / 0 / 0
Регистрация: 25.10.2012
Сообщений: 20
11.11.2012, 00:09     Базовые знания #1
Всем доброго времени суток!

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

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

Заранее благодарю и прошу прощения за незнание таких элементарных вещей!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Черный ворон
129 / 123 / 6
Регистрация: 31.01.2012
Сообщений: 435
11.11.2012, 00:40     Базовые знания #2
по поводу первого вопроса - массивов, списков и прочих структур данных лично я бы посоветовал почитать книгу Кнут, Д. Искусство программирования.
ответы на 2-й и 3-й можно поискать в литературе указанной здесь Литература C++ (лично я начинал со Страуструпа)
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
11.11.2012, 00:52     Базовые знания #3
Цитата Сообщение от nikeo Посмотреть сообщение
1.Как в памяти представляются Массивы,Списки,Очереди,Деревья,Стеки.
Массивы - непрерывный кусок памяти, где каждай последующий элемент лежит за предыдущим. Т.е. адрес a[1] == адрес a[0] + sizeof(тип а).
Списки, очереди и прочие монстры - это структуры для хранения данных (контейнеры), которые могут быть реализованы соверешенно как угодно (в том числе и на основе массива). Так что как они в памяти лежат - вопрос к разработчику контейнеров.

Добавлено через 4 минуты
Цитата Сообщение от nikeo Посмотреть сообщение
2.Что мы можем узнать из адреса переменной?

Не по теме:

Телефон, и долг по уплате коммуналки.


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

Добавлено через 5 минут
Цитата Сообщение от nikeo Посмотреть сообщение
3.Как в памяти представляются Статические члены,глобальные и локальные объекты,константные объекты?
Статические члены классов - это в принципе те же глобальные объекты, но их область видимости ограничена областью видимости класса. Глобальные переменные где-то в памяти лежат. Локальные объекты, как правило, создаются в стеке. Константные объекты компилятор может поместить в область памяти, доступной только для чтения.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2012, 00:55     Базовые знания #4
1.
а) массив - это непрерывный блок данных. Это означает, что зная, где этот блок начинается и какой размер имеет, мы можем легко переместиться в любую часть этого блока по номеру искомого элемента;
б) список - структура данных, в которой мы можем, имея некоторый элемент, получить следующий (для односвязного списка) или следующий и предыдущий (для двусвязного списка). Фактически же список представляется в памяти как обособленные куски данных - узлы списка, связываются которые посредством указателей - каждый узел содержит указатель на следующий (или следующий и предыдущий) узел;
в) очередь - это просто абстракция, структура данных, в которую элементы можно складывать только в конец, а доставать только из начала. Представлена может быть как в виде списка, так и в виде массива, так и в виде любой последовательной структуры данных;
г) дерево, аналогично списку - разрозненные элементы данных в памяти. Однако структура связей уже другая. В каждом элементе (предке) хранится некоторое количество указателей на другие элементы (на потомков), которые являются корнями поддеревьев. Эти корни поддеревьев, в свою очередь, хранят указатели на своих потомков и так далее. Тут есть два исключения: существует один элемент, на которого не ссылается указатель ни в каком другом элементе - это корень всего дерева, а также есть элементы, которые не ссылаются ни на какие другие элементы (корни поддеревьев) - они называются листами дерева;
д) стек - смотри пункт в) про очередь.

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

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

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

Добавлено через 1 минуту
Да, говоря про списки, я имел ввиду наиболее известные связные списки. Сам по себе список - абстрактная структура данных, и может быть реализована как угодно (как я описал, на основе массивов, на основе массивов указателей на элементы и т.д.).
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6167 / 2896 / 282
Регистрация: 04.12.2011
Сообщений: 7,702
Записей в блоге: 3
11.11.2012, 01:15     Базовые знания #5
Александреску A. "Современное проектирование на С++", гл.4 Размещение в памяти небольших объектов.
Вообще глобальность как область видимости, часто путается со статичностью как способом хранения. Однако, легко себе представить динамический объект с глобальной видимостью, хотя память выделяется в куче или наоборот статический объект для которого известен размер, но видимость ограничена, функцией например, и при этом память используется в области данных. Что касается массивов, то уже для 2-мерного динамического массива нет гарантии размещения элементов подряд, так как это массив одномерных массивов и память выделяется последовательно для каждого массива. Вообще тема очень большая и мне тоже интересно узнать больше.

Не по теме:

А сейчас, - главный вопрос забьет ли Кличко Баку баки?!

silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2012, 01:20     Базовые знания #6
Цитата Сообщение от IGPIGP Посмотреть сообщение
уже для 2-мерного динамического массива нет гарантии размещения элементов подряд
Тут уже от уровня абстракции зависит. Строго говоря, в языке такого понятия, как "двумерный динамический массив", не существует. Да, часто двумерный динамический массив представляется как массив указателей на одномерные динамические массивы, однако если внутренняя реализация двумерного динамического массива - одномерный массив, расположенный по строкам, для которого из двух индексов элемента (по строке и столбцу) вычисляется один индекс для доступа во внутреннем представлении, и с виду это всё дело выглядит и работает как двумерный массив, почему бы не считать его двумерным динамическим массивом?
nikeo
0 / 0 / 0
Регистрация: 25.10.2012
Сообщений: 20
11.11.2012, 01:31  [ТС]     Базовые знания #7
Спасибо вам за ответы)
1.По поводу адреса и подразумевался указатель,а точнее его значение,и суть вопроса была в том,что можно сказать о переменной,глядя на 16-ое значение указателя,то есть как определить тип.
2.Первый вопрос подразумевал как раз таки контейнеры STL(и кстати ни кто не знает отличие его от Tulip?)
3.Какие методы отладки существуют?(помимо точек останова и вывода информации в консоль)
Можно ли использовать данные дизассемблера для отладки?(если я правильно выразился,а то был у меня случай,когда выполнение программы останавливалось и выдавлся лист со значениями)

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

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

Не по теме:

А сейчас, - главный вопрос забьет ли Кличко Баку баки?!

Как раз вот это и читаю!)
LK
Заблокирован
11.11.2012, 01:42     Базовые знания #8
nikeo, правила - один вопрос - одна тема
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2012, 01:42     Базовые знания #9
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 внутренняя реализация".
nikeo
0 / 0 / 0
Регистрация: 25.10.2012
Сообщений: 20
11.11.2012, 22:43  [ТС]     Базовые знания #10
Спасибо что открыли!)

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

Добавлено через 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 контейнеры я знаю)как то меня просто спросили,как они представляются в памяти,на что я не смог ответить,так как не задумывался над этим.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.11.2012, 22:46     Базовые знания #11
Цитата Сообщение от nikeo Посмотреть сообщение
Вот я не могу понять одной вещи,говорят что в связанном списке,элемент содержит информацию о другом элементе,но как?в чем это выражается?
В хранимом указателе на другой элемент.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2012, 22:48     Базовые знания #12
nikeo, с помощью указателя.
C++
1
2
3
4
5
6
7
struct LinkedListNode
{
    DataType data;
    
    LinkedListNode *prev;
    LinkedListNode *next;
};
И да, в своих предыдущих сообщениях я расписывал внутреннюю представление различных контейнеров, а главное сказать забыл: стандарт на самом не определяет внутреннюю структуру. Он определяет только какие-то общие особенности, например, для вектора стандарт гарантирует, что внутренне он представлен как непрерывная область памяти, для множества и отображения определяет сложность "О большое" алгоритмов вставки, удаления и доступа (просто красно-чёрное дерево соответствует определённой стандартом сложности). Но в известных мне реализациях STL используются именно описанные мной структуры, хотя никто не ограничивает разработчиков в выборе другого внутреннего представления.

Добавлено через 54 секунды
Цитата Сообщение от nikeo Посмотреть сообщение
Что такое STL контейнеры я знаю)как то меня просто спросили,как они представляются в памяти,на что я не смог ответить,так как не задумывался над этим.
Так я и описал, как они в памяти представляются.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11822 / 6801 / 769
Регистрация: 27.09.2012
Сообщений: 16,869
Записей в блоге: 2
Завершенные тесты: 1
11.11.2012, 22:50     Базовые знания #13
Цитата Сообщение от nikeo Посмотреть сообщение
Вот я не могу понять одной вещи,говорят что в связанном списке,элемент содержит информацию о другом элементе,но как?в чем это выражается?
Он содержит адрес следующего (если список двусвязный, то еще и предыдущего) элемента списка.
nikeo
0 / 0 / 0
Регистрация: 25.10.2012
Сообщений: 20
13.11.2012, 20:22  [ТС]     Базовые знания #14
Цитата Сообщение от Croessmah Посмотреть сообщение
Он содержит адрес следующего (если список двусвязный, то еще и предыдущего) элемента списка.
вот в том то и дело,что где он этот адрес содержит?как его "вытащить"?

Добавлено через 2 минуты
Или смысл в том,что элементы "разбросаны" по памяти?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11822 / 6801 / 769
Регистрация: 27.09.2012
Сообщений: 16,869
Записей в блоге: 2
Завершенные тесты: 1
13.11.2012, 20:24     Базовые знания #15
Цитата Сообщение от nikeo Посмотреть сообщение
что где он этот адрес содержит?
C++
1
2
3
4
struct A{
   int value;
   A* nextelement;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2012, 20:28     Базовые знания
Еще ссылки по теме:

Базовые и порожденные классы C++
Базовые операции над углами C++
C++ C++ и базовые функции PHP

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nikeo
0 / 0 / 0
Регистрация: 25.10.2012
Сообщений: 20
13.11.2012, 20:28  [ТС]     Базовые знания #16
Цитата Сообщение от Croessmah Посмотреть сообщение
C++
1
2
3
4
struct A{
   int value;
   A* nextelement;
}
Спасибо!Простите что затупил
Yandex
Объявления
13.11.2012, 20:28     Базовые знания
Ответ Создать тему
Опции темы

Текущее время: 04:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru