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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 00:46     Непонятный Stack Overflow #1
Здравствуйте, уважаемые форумчане.Столкнулся с непонятной мне проблемой при решении одной лёгкой олимпидной задачи.

Вот условие задачи:
Задана последовательность, содержащая 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
Почему stack overflow? C++
C++ Необработанное исключение Stack overflow
Переполнение (Stack overflow) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stima
430 / 285 / 16
Регистрация: 22.03.2011
Сообщений: 929
Завершенные тесты: 1
28.04.2013, 00:51     Непонятный Stack Overflow #2
Это ограничение стека http://www.cs.nyu.edu/exact/core/doc/stackOverflow.txt.
Создайте массивы на куче или расширьте стек.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 01:13  [ТС]     Непонятный Stack Overflow #3
да понимаете, пробовал увеличить просто стек так:

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

Добавлено через 19 минут
вот ещё что заметил - если юзать 2 vector, то ошибка пропадает.Но после использования sort() из STL, сортировка весь массив почему то запоняет нулями, а все значения, которые я туда записал, она заменяет на 0(само собой, ввод в вектор через cin).Чудеса одним словом.Но если писать квиксорт самому, и потом им сортить вектора, то всё проходит.Но мне этот вариант решения не подходит - мне нужно именно с простыми массивами.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.04.2013, 08:30     Непонятный Stack Overflow #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
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 11:27     Непонятный Stack Overflow #5
Можно попробовать вынести массивы в глобальную область видимости.

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

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


kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает?
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
28.04.2013, 19:57     Непонятный Stack Overflow #7
взяли и засрали стек на ровном месте.
достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:02  [ТС]     Непонятный Stack Overflow #8
DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
28.04.2013, 20:07     Непонятный Stack Overflow #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
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:10  [ТС]     Непонятный Stack Overflow #10
diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования

Добавлено через 1 минуту
DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 20:21     Непонятный Stack Overflow #11
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Но почему?
Потому что глобальные массивы расположены не на стеке, и для них нет таких суровых ограничений на размер.
Можно было еще попробовать сделать массив static'ом, это тоже должно помочь.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 20:24  [ТС]     Непонятный Stack Overflow #12
diagon, а где расположены глобальные массивы?
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.04.2013, 20:43     Непонятный Stack Overflow #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
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.04.2013, 20:49     Непонятный Stack Overflow #14
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
diagon, а где расположены глобальные массивы?
В .global секции. Ну, это уже уровень ассемблера.
Если вкратце, то они одни на всю программу, за счет этого у них дешевая инициализация. А вот локальные массивы заново создаются при каждом вызове функции (в данном случае при входе в main).
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 21:02  [ТС]     Непонятный Stack Overflow #15
kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

Добавлено через 9 минут
Всем спасибо за ответы!
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.04.2013, 21:30     Непонятный Stack Overflow #16
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.
ну да

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
То есть если глобальная переменная инициализирована, то она помещается в стек.
Нет. Если глобальная переменная инициализирована, то она помещается не в .bss и не в стек, а- в секцию с инициализированными данными. g++ обзывает эту секцию .data и во время работы ты работаешь именно с этой областью памяти.

Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?
В стек. Все локальные переменные, независимо от того, инициализированы они или нет, помещаются в стек. И ты работаешь со стеком.

//++++++++++++++++++++++++++++++++++++++++++++

Но тут есть одна факультативная тонкость и она касается локальных переменных. Дело в том, что коль скоро они инициализированы, то эта инициализация сохраняется и тогда, когда программа не работает.

Ну просто. Пусть есть локальная переменная x:
C++
1
int x= 2;
Программа начинает работать и под эту переменную, коль скоро она локальна, выделяется область в стеке. Но! Где-то же эта двойка хранится, когда программа не работает! Где? А вот, тоже где-то в одной из секций, может даже в той же .data выделяются 4 байта и там лежит двойка. Но, повторю, это вопрос хранения значения локальной переменной в экзешнике. Во время работы ты работаешь с глобальными или с локальными переменными, которые (если они локальные) находятся в стеке.

Ну а глобальные в зависимости от инициализации в одной из секций, повторюсь, на имена секций стандарта, кажись нет. Просто их так обзывает g++.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2013, 22:32     Непонятный Stack Overflow
Еще ссылки по теме:

Stack overflow C++
C++ Обработка исключений stack overflow
Возникает ошибка Stack overflow C++

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

Или воспользуйтесь поиском по форуму:
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 22:32  [ТС]     Непонятный Stack Overflow #17
kravam, большое спасибо - теперь понял, наконец-то, как оно всё хранится.
Yandex
Объявления
28.04.2013, 22:32     Непонятный Stack Overflow
Ответ Создать тему
Опции темы

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