Comments 27
Кто в армии не служил сложно понять, что такое стек и очередь.
Из стека легко очередь сделать.
Из стека легко очередь сделать.
We need to go deeper: нужно объяснение что такое linked list
Мило, что вы пишете что-то "от чайника к чайнику", но вы немного запутались. Обратите внимание: стек из вашего первого примера (стопка книг) не лезет в рамки последующего объяснения (связный список).
Стек — штука абстрактная, не раскрывающая детали реализации (только требования к операциям push и pop). И реализация поверх массива на практике встречается чаще, чем поверх связного списка.
Эх, зря вы все-таки пропустили лекции по структурам данных и, видимо, С++)
Для новичков, кто действительно хочет чему-то научиться: ни в коем случае не реализуйте стеки таким образом, как это продемонстрировал автор. Это один из наихудших вариантов, как с точки зрения понимания, так и с точки зрения эффективности. А на С++, вообще, больно смотреть, максимум тянет на С. Для начала:
вполне хватит. Потом можно аккуратненько завернуть это в классик, добавить проверку граничных условий, и т.д.
Для новичков, кто действительно хочет чему-то научиться: ни в коем случае не реализуйте стеки таким образом, как это продемонстрировал автор. Это один из наихудших вариантов, как с точки зрения понимания, так и с точки зрения эффективности. А на С++, вообще, больно смотреть, максимум тянет на С. Для начала:
std::vector<int> stack;
// Положить
stack.push_pack(5);
// Забрать
const int value = stack.back();
stack.pop_back();
вполне хватит. Потом можно аккуратненько завернуть это в классик, добавить проверку граничных условий, и т.д.
На тех парах, что я пропустил как раз разбирали реализацию стека именно таким способом :) Моей задачей было объяснение именно этого способа реализации стека. А за отзыв спасибо большое, действительно, думаю стоит в начале привести пример работы стандартных функций, а потом переходить к классике! В будущем учту.
std::stack же
UFO just landed and posted this here
Vector медленнее от 11 до 13 раз при комплексном тесте.
Код в студию :)
UFO just landed and posted this here
По поводу производительности. Из вектора элемент выбирается с помощью at. at проверяет, есть ли в векторе такой индекс и, если его нет — бросает исключение. Было бы неплохо попробовать выбирать значения из вектора простым [ ]. И писать тоже. [ ] проверок не делает и, соответственно, работает немного быстрее. Плюс, возможно, проверка внутри push_back, не надо ли увеличить внутренний массив, даёт свой вклад.
По поводу CharStack. У вас там хранится int и только int, соответственно, чего бы не сделать просто массив интов? memcpy тогда не нужен, можно просто писать значения в массив по индексу.
Плюс традиционный вопрос. Какой компилятор использовали и с какими флагами оптимизации :)?
В вашем коде последний аргумент (size) при всех вызовах memcpy равен offset = sizeof(int); При включенной оптимизации компилятор преобразует это выражение в константу времени компиляции, а следовательно, memcpy выродится в intrinsinc — простое копирование значения без вызова функции.
В итоге, вы сравниваете методы std::vector: at() и push_back() в которых присутствует проверка граничных условий и выброс исключений, в случае неудачи (такие методы, как правило, не могут быть заинлайнены), и просто копирование значения по указателю, даже, без проверки выхода за границы.
Простое копирование значения по адресу и приращение указателя действительно может быть на порядок медленнее честного вызова функции с обработкой исключений. Но сравнение не корректно, на мой взгляд.
В итоге, вы сравниваете методы std::vector: at() и push_back() в которых присутствует проверка граничных условий и выброс исключений, в случае неудачи (такие методы, как правило, не могут быть заинлайнены), и просто копирование значения по указателю, даже, без проверки выхода за границы.
Простое копирование значения по адресу и приращение указателя действительно может быть на порядок медленнее честного вызова функции с обработкой исключений. Но сравнение не корректно, на мой взгляд.
В вашем коде последний аргумент (size) при всех вызовах memcpy равен offset = sizeof(int); При включенной оптимизации компилятор преобразует это выражение в константу времени компиляции, а следовательно, memcpy выродится в intrinsinc — простое копирование значения без вызова функции.
Из этого ничего не следует — причины просты: а) intrinsinc никакого отношения к константе времени компиляции не имеет. Это имеет отношение к оптимальности кода. б) инфа про медленный вызов функции устарела лет на 15.
В итоге, вы сравниваете методы std::vector: at() и push_back() в которых присутствует проверка граничных условий и выброс исключений, в случае неудачи (такие методы, как правило, не могут быть заинлайнены), и просто копирование значения по указателю, даже, без проверки выхода за границы.
C at() ладно, но push_back() — это проблема вектора. throw никак не влияет на возможность инлайнинга. Придирки к чему-то, кроме at() — не имеют смысла.
Но сравнение не корректно, на мой взгляд.
Никаких обоснований некорректности, кроме ат, приведено не было. Особенности работы push_back() к делу отношения не имеют. Если мне не нужен какой-то функционал и он есть, но его убрать я не могу — это не значит, что сравнение некорректно.
Из этого ничего не следует — причины просты: а) intrinsinc никакого отношения к константе времени компиляции не имеет. Это имеет отношение к оптимальности кода. б) инфа про медленный вызов функции устарела лет на 15.Intrinsinc — это hint для компилятора, а не вызов функции. Чем больше информации у компилятора в точке где он раскрывается, тем сильнее компилятор способен соптимизировать. В вашем случае оптимизация превращается в в вставку одной команды mov.
По поводу «быстроты» вызова функции. Быстрее или медленнее это относительные понятия. Относительно простой команды mov вызов функции, как раз, медленнее раз в 10.
Никаких обоснований некорректности, кроме ат, приведено не было. Особенности работы push_back() к делу отношения не имеют. Если мне не нужен какой-то функционал и он есть, но его убрать я не могу — это не значит, что сравнение некорректно.Для утверждения что ваша реализация быстрее чем STL вы должны, для начала, разобраться с семантикой операций std::vector. Ваши же две реализации не являются полностью эквивалентными. В случае «не STL» версии у вас UB в случае выхода за границы стека во всех функциях. На мой взгляд, начинать изучать С++ с написания кода с UB не самая удачная идея.
free(q);//очищаем ячейку
q->Data = NULL;//обнуляем переменные
q->next = NULL;
Так делать нельзя, это доступ к освобождённой памяти — undefined behavior.
www.securecoding.cert.org/confluence/display/cplusplus/MEM50-CPP.+Do+not+access+freed+memory
По опыту, если у ученика проблемы с пониманием стека, то у ученика проблемы с пониманием того, что такое структуры данных и зачем они нужны. Ну то есть если абстрактно начать ни с того ни с сего рассказывать про стек, то единственным вопросом будет «эээ, ну ок, и че дальше?».
Нужно для начала показать зачем нужны разные структуры данных, как с помощью них можно опускать большие куски размышлений.Что это не то как мы организуем память, а то как мы работаем с нашими данными.
Нужно для начала показать зачем нужны разные структуры данных, как с помощью них можно опускать большие куски размышлений.Что это не то как мы организуем память, а то как мы работаем с нашими данными.
Стоит добавить, что тот стек, который работает в исполняемых файлах, устроен немного не так. Есть просто указатель вершины (хранится в регистре ESP/RSP), а данные располагаются в памяти друг за другом. Стек находится в конце региона памяти и растет в обратную сторону. При добавлении данных указатель уменьшается на их размер.
Что-то какой-то связный список получился, а не стек. На рисунке книжки у вас физически лежат стопкой, а в сишном варианте — беспорядочно, связанные через указатели.
- Вы называете «код на C++» код, написанный на C. То, что Вы один раз использовали оператор new, делает этот код не компилируемым в C, но отнюдь не кодом на C++
- Использование для выделения памяти оператора new в паре с функцией освобождения памяти free() — очень плохая практика. Либо new/delete, либо malloc()/free(), но не смесь их.
- Фрагмент
вообще не выдерживает никакой критики: Вы освободили память, занимаемую объектом, больше она Вам не принадлежит и Вы не имеете права к ней обращаться. То же самое в этом же фрагменте чуть ниже.free(q);//очищаем ячейку q->Data = NULL; //Далее во избежание ошибок мы обнуляем п
- Поле comp::Data у Вас типа int, а Вы присваиваете ему NULL — нулевой указатель. Кстати, если уж Вы говорите о C++, то используйте nullptr, а не C-шный NULL (естественно, не для int, а для указателей)
А зачем мне может понадобиться стек?
Где почитать про «указатель на указатель»?
Где почитать про «указатель на указатель»?
Sign up to leave a comment.
О стеке простыми словами — для студентов и просто начинающих