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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
#1

Непонятный Stack Overflow - C++

28.04.2013, 00:46. Просмотров 1202. Ответов 16
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане.Столкнулся с непонятной мне проблемой при решении одной лёгкой олимпидной задачи.

Вот условие задачи:
Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.

Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.

Требуется написать программу, которая решает данную задачу.
Входные данные

Первая строка входного файла INPUT.TXT содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 109. Все числа в строке разделены пробелом.
Выходные данные

В выходной файл OUTPUT.TXT выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.



вот код:
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
#include <cstdio>
#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    long long digit,temp=1,count=1,i,n,arr[200000],vyvod[200000];
    scanf("%I64d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%I64d",&arr[i]);
        vyvod[i]=arr[i];
    }
    sort(arr,arr+n);
    digit=arr[0];
    for(i=0;i<n-1;++i)
    {
        if(arr[i] == arr[i+1])
            ++temp;
        else
        {
            if(temp>count)
            {
                digit=arr[i];
                count=temp;
            }
            temp=1;
        }
    }
    for(i=0;i<n;++i)
        if(vyvod[i] != digit)
            printf("%I64d ",vyvod[i]);   
    for(i=0;i<count;++i)
        printf("%I64d ",digit);
    system("pause");
    return 0;
}
Так вот, решение простое вроде я придумал - вводим массив, дублируем его.Потом первый массив сортируем sort() из STL, потом ищем в отсортированном массиве минимальное число, которое встречается наибольшее число раз, и записываем в переменные, что это за число и сколько раз встречалось.Потом выводим сначала из исходного массива по порядку все числа кроме найденного, а потом уже выводим нужное кол-во раз найденное число.


Но вот в чём проблема - при запуске программы сразу же программа вылетает.Компилировал как g++, так и компилятором от MSVS 2010(забыл как он называется).Ошибка одна и та же - переполнение стека.Но где??? и оно идет в самом начале программы.Если размеры исходных массивов ставить не 200000, а допусти м 200, то ошибки нет.Но как размер массива влияет на стек?Первый раз с таким сталкиваюсь - я не думал, что массив сложно такого размера создать.

Прошу вас, помогите понять, в чём суть данной проблемы.

Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2013, 00:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Непонятный Stack Overflow (C++):

Stack overflow. - C++
У меня в программе есть реверсивная функция (много параметров) она вызывает себя очень много раз. Во время выполнения программы возникает...

Stack overflow - C++
Реализовал структуру данных стек на связном списке, очистку решил возложить на деструкторы узлов, т.е. каждый вызов деструктора узла...

Stack overflow - C++
Написал #include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; #include &lt;math.h&gt; #include &lt;iomanip&gt; #include...

Почему stack overflow? - C++
Почему приведенный ниже код сразу же приводит к переполнению стека? int _tmain(int argc, _TCHAR* argv) { unsigned lоng...

Переполнение (Stack overflow) - C++
Подскажите, пожалуйста, почему при перемещении int n, a, k; в локальную область программа при открытии консоли выдаёт ошибку и не работает,...

Необработанное исключение Stack overflow - C++
Здравствуйте. Такое дело: считываю файл в буфер, а он ругаиццо. ... DWORD bufferSize = 16777216; BYTE buffer1; DWORD...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
stima
463 / 312 / 26
Регистрация: 22.03.2011
Сообщений: 1,021
Завершенные тесты: 2
28.04.2013, 00:51 #2
Это ограничение стека http://www.cs.nyu.edu/exact/core/doc/stackOverflow.txt.
Создайте массивы на куче или расширьте стек.
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 01:13  [ТС] #3
да понимаете, пробовал увеличить просто стек так:

C++
1
#pragma comment(linker, "/STACK:32777216")
(вроде это так делается)
Не помогает

Добавлено через 19 минут
вот ещё что заметил - если юзать 2 vector, то ошибка пропадает.Но после использования sort() из STL, сортировка весь массив почему то запоняет нулями, а все значения, которые я туда записал, она заменяет на 0(само собой, ввод в вектор через cin).Чудеса одним словом.Но если писать квиксорт самому, и потом им сортить вектора, то всё проходит.Но мне этот вариант решения не подходит - мне нужно именно с простыми массивами.
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
28.04.2013, 08:30 #4
Вот твой код, я его упростил.
C++
1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    printf ("%d\n", sizeof(long long));
    long long arr[200000], vyvod[200000];
    getchar ();
    return 0;
}
long long это восемь байт, вот у тебя под массивы занято 3200000 байт, всё плохо, короче. Поэтому увеличиваем размер стека. В g++ это можно сделать используя такую опцию:

C++
1
-Wl,--stack,<новый размер стека>
Как в MSVS это сделать, не знаю.

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

Добавлено через 1 минуту
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Но как размер массива влияет на стек?
Так просто ж всё. Где по твоему массив размещается? В стеке и размещается.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 11:27 #5
Можно попробовать вынести массивы в глобальную область видимости.

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
по модулю 109
109 или 10^9?

В любом случае, зачем вам long long, если все влазит в обычный int?
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 19:54  [ТС] #6
diagon, просто в олимпиадном программировании обычно юзают сразу long long и не парятся.Прошу прощения, не досмотрел про условие - там 10 в 9 степени, а не 109.Сейчас попробую сделать массивы глобальными, хотя навряд ли это поможет.


kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает?
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
28.04.2013, 19:57 #7
взяли и засрали стек на ровном месте.
достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец.
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:02  [ТС] #8
DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому.
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
28.04.2013, 20:07 #9
вероятно от незнания вы так говорите. почему вектор нужно как-то по особенному заполнять?
C++
1
2
3
4
5
6
7
8
std::vector<long long> v(200000);
long long* arr = &v[0]
все. дальше работаем как и раньше.
единственная просадка тут - это то, что в векторе данные инициализируются.
если не хотим это делать, то
long long* arr = new long long[200000];
дальше не забыть только удалить. если фичами нового стандарта воспользоваться,
то там спартпоинтеры заточены под автоудаление.
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:10  [ТС] #10
diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования

Добавлено через 1 минуту
DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 20:21 #11
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Но почему?
Потому что глобальные массивы расположены не на стеке, и для них нет таких суровых ограничений на размер.
Можно было еще попробовать сделать массив static'ом, это тоже должно помочь.
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:24  [ТС] #12
diagon, а где расположены глобальные массивы?
kravam
быдлокодер
1694 / 881 / 44
Регистрация: 04.06.2008
Сообщений: 5,441
28.04.2013, 20:43 #13
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...
Да можно всяко, но от некоторых решений бросает в дрожь. Итак, решено НА ВСЯКИЙ СЛУЧАЙ иметь большие массивы? Получите...
C++
1
2
3
4
5
6
7
8
#include <stdio.h>
long long arr_0 [200000], arr_1 [200000], arr_2 [200000];
 
int main()
{
  getchar ();
  return 0;
}
Добавлено через 6 минут
А находятся эти массивы в области памяти, которую занимает секция неициализируемых переменых. Короче компилятор создаёт экзешник с разными секциями, одна из которых имеет имя .bss- это секция с неициализируемыми переменными. Но это не стандарт, насколько я знаю, просто так работает g++. При запуске программы секции проецируются в память и эта секция тоже. Вот в ней эти глобальные массивы и лежат. Если ты объявишь другие неициализированные переменные, они тоже будут в этой секции.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 20:49 #14
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
diagon, а где расположены глобальные массивы?
В .global секции. Ну, это уже уровень ассемблера.
Если вкратце, то они одни на всю программу, за счет этого у них дешевая инициализация. А вот локальные массивы заново создаются при каждом вызове функции (в данном случае при входе в main).
ZaMaZaN4iK
Мой лучший друг-отладчик!
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 21:02  [ТС] #15
kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

Добавлено через 9 минут
Всем спасибо за ответы!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2013, 21:02
Привет! Вот еще темы с ответами:

Возникает ошибка Stack overflow - C++
Задача должна рассчитывать функцию рекуррентного сложения. Но возникает ошибка &quot;Stack overflow&quot;. Пытался ставить double, long int - не...

Разобраться с рекурсией: stack overflow - C++
#include&lt;iostream&gt; #include&lt;vector&gt; #include&lt;string&gt; #include&lt;math.h&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; using namespace std; ...

Stack Overflow, перегруз буфера - C++
Добрый день, знаком с перегрузом буфера в теории, хотел бы перейти к практике. Написал простенькую программу, int main(int argc) ...

Stack overflow с тернарным оператором - C++
Так работает: unsigned long Ly(const string &amp;s) { ... } unsigned long Rs(const string &amp;s) { ... } unsigned long(*F)(const string...


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

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

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