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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.79
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
#1

Создать отдельный стек для функции - C++

29.11.2011, 22:26. Просмотров 2449. Ответов 44
Метки нет (Все метки)

необходимо. Мне надо вызывать рекурсивную функцию; при этом происходит переполнение стека, мне бы хотелось бы это контролировать.
g++ не поддерживает обработку SEH- исключений, отловить переполнение стека, как, впрочем и другие я не могу. Программа падает просто и всё.
вызов рекурсивной функции в отдельном потоке с созданным и, как следствие, контролируемым стеком (билиотека pthread) рассамтриваю только в качестве ПОСЛЕДНЕГО варианта.

Спасибо, кто откликнется

Добавлено через 48 минут
Только что в отладчике OllyDbg исполоьзовал такой приём: выделял объём памяти и вручную менял регистр ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек.
Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2011, 22:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Создать отдельный стек для функции (C++):

Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода и вывода элементов стека. Ввести эталонный символ. - C++
Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода и вывода элементов стека. Ввести...

Создать отдельный управляемый поток для бесконечного процесса - C++
Пишу простую визуализацию броуновского движения в С++ Builder-e рисуя кружочки на имейдже. Подскажите самый простой пример как запихнуть...

Функции для записи данных в отдельный файл txt - C++
Прошу помочь с такой проблемой:какие функции используются для записи данных,в моём случае массива данных ,в отдельный файл txt Всем...

создать стек для с++ - C++
сформировать стек не более чем из 5-ти элементов. Начиная с 6-го введенного символа головной элемент "выталкивается" из очереди и выводить...

Создать стек, для суммирования чисел - C++
Столкнулся с заданием в котором нужно создать стек при этом необходимо реализовать разбор строки для суммирования чисел. Они представляются...

при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"? - C++
Сабж g++ 4.5.0

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nameless One
01.12.2011, 13:58     Создать отдельный стек для функции
  #31

Не по теме:

Цитата Сообщение от alex_x_x Посмотреть сообщение
с ассемблерными вставками
чем бы дитя не тешилось, лишь бы не пыталось делать такое

0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
01.12.2011, 15:44  [ТС] #32
Цитата Сообщение от Nameless One Посмотреть сообщение
да не нужен для этого "отдельный стек"! Вот держи:

Так и мне не нужен! Вы читайте внимателльно, вы же не читаете тему. И код мне ваш без надобности, чай у меня свой есть и мой покомпактнее будет.
C++
1
Другое дело, что глубина рекурсии невысока, поэтому вряд ли стек переполнится.
Вы даже не спросили, какая глубина рекурсии. Потому, что вам всё равно, вам просто надо код выложить сюда. Вам чё, коды негде демонстрировать свои?

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Так вот, докладываю, если я вывожу сочетавния из m по n, у меня глубина рекурсии n. Считаем: каждая функция принимает пять параметров, плюс адрес возврата плюс ещё какая-нибудь херь, максимум ячеек 10, каждая занимает 4 байта, итого 40 ячеек. На одну функцию.
Переполнится стек. если я буду применять рекурсию? А прикинем

Предположим, ввыводим сочетания из 30 по 15 (ибо 30/2== 15, наибольшее количество вариантов). Так вот, по моим подсчётам, это займёт три года. Примерно, конечно. Я выводил эти значения на экран и перикидывал в меньшую (то есть невыгодну для меня сторону) как часто меняется одно из полей... Проверяйте, в общем

Если будем брать ещё большие значения,например из 32 по 16, то это уже 30 лет

Так, а глубина рекурсии составит всего 16*40= 640 байт при том, что стандартный стек 22E000 байт.

То есть стандарнтый стек windows, он не то, что не переполнится. Он в ПРИНЦИПЕ не переполнется.
Плюс код такой аккуратный. Ну это ладно, каждый кулик своё болото хвалит

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Вопрос: а на фига тогда мне сдался этот отдельный стек?
Ответ: компактный безопасный я не умею писать сразу, так вот в процессе тык скыть написания кода у меня частенько переполняется стек. Вот отдельный стек мне нужен для процесса тык скыть написания программ. Это основное. Понимаете, для отладки. А для готового кода мне отдельный стек без надобности.
Я, конечно, мог это написать в первом сообщении но смысл? Тем более, челу и так всё понятно чё мне надо.

Вы меня можете спросить, а чем тебя стандартный-то стек не устраивает, ведь вновь созданный точно также переполнится (хоть в процессе отладки, хоть как)?
Отвечаю: переполниться-то он переполнгится, но я хочу сделать так, чтобы вывести предупреждающее сообщение. А так как у меня компилятор g++, он напрось не ловит системные исключения, то есть абсолютно. И переполнение вновь созданного стека я хотел отслеживать вручную

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
01.12.2011, 18:28 #33
Цитата Сообщение от kravam Посмотреть сообщение
Потому, что вам всё равно, вам просто надо код выложить сюда. Вам чё, коды негде демонстрировать свои?
ну не ты ли говорил, что твою функцию нельзя заменить на рекурсивную? А мы просто опровергали твое утверждение. А лучшим аргументом, естественно, является работающий код
Цитата Сообщение от kravam Посмотреть сообщение
Вы меня можете спросить, а чем тебя стандартный-то стек не устраивает, ведь вновь созданный точно также переполнится (хоть в процессе отладки, хоть как)?
Отвечаю: переполниться-то он переполнгится, но я хочу сделать так, чтобы вывести предупреждающее сообщение. А так как у меня компилятор g++, он напрось не ловит системные исключения, то есть абсолютно. И переполнение вновь созданного стека я хотел отслеживать вручную
система какая? Если *nix, то valgrind вроде бы умеет ловить переполнение стека. В принципе, его (переполнение) можно и в отладчике увидеть, если внимательно посмотреть на бэктрейс.
Также посмотри в сторону ключей -fstack-check и -fstack-protector, может что полезного нагуглишь.
А твое решение с собственным стеком (ИМХО) выглядит слишком костыльно.
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
01.12.2011, 23:12  [ТС] #34
Цитата Сообщение от Nameless One Посмотреть сообщение
ну не ты ли говорил, что твою функцию нельзя заменить на рекурсивную? А мы просто опровергали твое утверждение. А лучшим аргументом, естественно, является работающий код
а ну тогда прошу прощения.

Добавлено через 3 часа 36 минут
Nameless One, а вообще извольте прояснить ситуацию с этим кодом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <stdio.h>
using namespace std;
 
 
bool next_combination (std::vector<int>& a, int k)
{
    int n = (int)a.size();
    for (int i=k-1; i>=0; --i)
    {
        if (a[i] < n-k+i)
        {
            ++a[i];
            for (int j=i+1; j<k; ++j)
                a[j] = a[j-1]+1;
            return true;
        }
    }
    
    return false;
}
 
void dump(const std::vector<int>& v, size_t k)
{
    std::copy(v.begin(), v.begin() + k, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}
 
int main()
{
    std::vector<int> ivec;
    ivec.push_back (0);
    ivec.push_back (1);
    ivec.push_back (3);
    ivec.push_back (4);
    ivec.push_back (5);
    ivec.push_back (6);
    ivec.push_back (7);
 
    size_t k = 3;
 
    size_t cnt = 0;
 
    do
    {
        dump(ivec, k);
        ++cnt;
    }
    while(next_combination(ivec, k));
    
    std::cout << std::endl << "Count = " << cnt << std::endl;
    getchar ();
    
    return 0;
}
Это ваш код. Только я вектор по-своему заполнил. В векторе-результате появилась двойка. Прошу вас!
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
02.12.2011, 04:19 #35
kravam, ограничение данного алгоритма в том, что исходный вектор должен представлять первые n натуральных чисел (с нулем), т.е. {0, 1, 2, ..., n - 1}. Но это ограничение легко обойти, если ввести дополнительный вектор. Причем изменить нужно будет только функцию dump
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
02.12.2011, 11:36  [ТС] #36
я бы обязательно предупредил, а вдруг бы я взялся его использовать?!
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 11:51 #37
Цитата Сообщение от kravam Посмотреть сообщение
То есть стандарнтый стек windows, он не то, что не переполнится. Он в ПРИНЦИПЕ не переполнется.
При условии, что у тебя нет бесконечной рекурсии...

Добавлено через 2 минуты
Как сделать чтоб не рухалась: Добавляешь счётчик глубины рекурсии. статическая переменная, которая увеличивается при входе и уменьшается при выходе из рекурсивной функции. Глубину рекурсии ты примерно знаешь, поэтому проверяешь значение счётчика и выкидываешь исключение при необходимости.
4 страницы галимотьи читать не стал, если это уже было написано - извиняюсь.
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
02.12.2011, 12:30  [ТС] #38
Цитата Сообщение от Deviaphan Посмотреть сообщение
Как сделать чтоб не рухалась: Добавляешь счётчик глубины рекурсии.
Я этот способ рассматриваю и имею ввиду, но дело в том, что при отладке установить глубину рекурсии- это дорогого стоит. Это я щас по готовому продукту могу определить глубину рекурсии. А в процессе его изготовления- нет.
Хотя способ, несомненно хорош ДАЖЕ В ПРОЦЕССЕ НАПИСАНИЯ ПРОГРАММЫ, но привязываться итогда придётся к верхушке стека, к регистру ESP и размеру стека. Троудоёмко довольно.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

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

Но если алгоритм построен так, что рекурсивная функция вызывает не только себя, а какую-нибудь другую функцию, нерекурсивную? А если ещё и вызывает по некоторому условию? А если и в цикле?

Так что к сожалению этот счётчик должен увеличиваться на чёрт его знает какое значение байт.
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 12:38 #39
Цитата Сообщение от kravam Посмотреть сообщение
каждому вызову функции этот счётчик должен увеличиваться на величину
На единицу. ++ на входе и -- перед выходом.
Точное максимальное значение не обязательно. Примерную сложность алгоритма всегда можно оценить. Если навскидку у тебя глубина 20 вызовов, поставь счётчик на 1000. Или на 100.
Предполагать, сколько переменные займут в стеке - бесполезно. Есть выравнивание, есть "перетусовывание" компилятором. Кое что вообще в стек не попадает. В дебаге добавляется "неизвестное" количество дополнительных данных для контроля повреждений стека.
Счётчик считает глубину. Всё. +1 и -1.
Я даже на "бесконечных" циклах счётчик использую иногда.
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
02.12.2011, 12:55  [ТС] #40
Ну ясно всё, неубедительно. Я уже говорил у меня очень низкая квалификация для некоторых вещей. В частности, я не возьмусь определять глубину стека до определённого момента ни примерно, никак. Такой момент наступает, как правило, когда прога готова.

Но при готовой проге вступают в силу другие соображения, а именно: я железно знаю, чо глубина рекурсии не превысит, например 100. То есть счётчик мне просто не нужен, я знаю, что он никогда не будет больше 100 и всё тут.

Видишь, как получается: пока проги нет, хорошо бы использовать счётчик да глубину рекурсии не определить. А когда прога готова и можно определить глубину рекурсии- счётчик уже не нужен.

Жизнь вообще сложная штука.
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 13:10 #41
Цитата Сообщение от kravam Посмотреть сообщение
В частности, я не возьмусь определять глубину стека до определённого момента ни примерно, никак
Ставь 100. Если после запуска глубины не хватает, ставь 1000. Потом 10000. Любая вменяемая функция может 10000 раз рекурсивно вызваться. В противном случае ты используешь стековую память там, где нужно использовать динамическую.
Потом 100000 поставь, если приспичит.
Можно увеличить размер стека, если это действительно нужно.
Но писать собственный стек функций (на ассемблере подменяя ESP (OMG) ), чтобы отловить ошибку с бесконечной рекурсией... мягко выражаясь - маразм.

Цитата Сообщение от kravam Посмотреть сообщение
хорошо бы использовать счётчик да глубину рекурсии не определить
ВСЕГДА известная расчётная глубина. До одного-двух порядков она известна ВСЕГДА. В противном случае ты кидаешься программировать даже не пытаясь проектировать.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
02.12.2011, 13:20 #42
Цитата Сообщение от Deviaphan Посмотреть сообщение
Любая вменяемая функция может 10000 раз рекурсивно вызваться.
под вменяемостью надо понимать, что у нее на стеке выделяется не очень много данных
те что у нее нет больших локальных нестатических массивов итп
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 13:23 #43
Цитата Сообщение от alex_x_x Посмотреть сообщение
под вменяемостью надо понимать
Ну да, именно это.)
Рекурсивные функции с большим количеством данных на стеке, заставляют задумываться о вменяемости программиста.)
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
02.12.2011, 14:04  [ТС] #44
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но писать собственный стек функций (на ассемблере подменяя ESP (OMG) ), чтобы отловить ошибку с бесконечной рекурсией... мягко выражаясь - маразм.
прошу больше меня не беспокоить
0
Deviaphan
02.12.2011, 14:15     Создать отдельный стек для функции
  #45

Не по теме:

Не верю в искренность просьбы.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 14:15
Привет! Вот еще темы с ответами:

Различные функции, для которых можно создать массив указателей на функции - C++
Придумайте не менее 3-х различных функций, для которых можно создать массив указателей на функции.

Функции в отдельный файл - C++
Всем доброго времени суток! У меня есть основной файл в нем main и парочка больших функций. Я вынес эти две функции в отдельный файл...

Перенести функции в отдельный файл - C++
Сейчас у меня всё в одном файле Source.cpp, как перенести все функции в другой файл Header.h(или какой-нибудь другой), где его создать?...

Создать стек - C++
Задание: Создать стек. Написать функцию, определяющую, есть ли заданная компонента в стеке. В программу включить меню работы с...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.12.2011, 14:15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru