Непонятный Stack Overflow

@ZaMaZaN4iK · Регистрация: 24.06.2012

Студворк — интернет-сервис помощи студентам

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

Вот условие задачи:
Задана последовательность, содержащая 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, то ошибки нет.Но как размер массива влияет на стек?Первый раз с таким сталкиваюсь - я не думал, что массив сложно такого размера создать.

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

Заранее спасибо.

@stima · 28.04.2013, 00:51

Это ограничение стека http://www.cs.nyu.edu/exact/co... erflow.txt.
Создайте массивы на куче или расширьте стек.

@ZaMaZaN4iK · 28.04.2013, 01:13 **[ТС]**

да понимаете, пробовал увеличить просто стек так:

C++
1
#pragma comment(linker, "/STACK:32777216")

(вроде это так делается)
Не помогает

Добавлено через 19 минут
вот ещё что заметил - если юзать 2 vector, то ошибка пропадает.Но после использования sort() из STL, сортировка весь массив почему то запоняет нулями, а все значения, которые я туда записал, она заменяет на 0(само собой, ввод в вектор через cin).Чудеса одним словом.Но если писать квиксорт самому, и потом им сортить вектора, то всё проходит.Но мне этот вариант решения не подходит - мне нужно именно с простыми массивами.

@kravam · 28.04.2013, 08:30

Вот твой код, я его упростил.

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 · 28.04.2013, 11:27

Можно попробовать вынести массивы в глобальную область видимости.

Сообщение от ZaMaZaN4iK

по модулю 109

109 или 10^9?

В любом случае, зачем вам long long, если все влазит в обычный int?

@ZaMaZaN4iK · 28.04.2013, 19:54 **[ТС]**

diagon, просто в олимпиадном программировании обычно юзают сразу long long и не парятся.Прошу прощения, не досмотрел про условие - там 10 в 9 степени, а не 109.Сейчас попробую сделать массивы глобальными, хотя навряд ли это поможет.

kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает?

@DU · 28.04.2013, 19:57

взяли и засрали стек на ровном месте.
достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец.

@ZaMaZaN4iK · 28.04.2013, 20:02 **[ТС]**

DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому.

@DU · 28.04.2013, 20:07

вероятно от незнания вы так говорите. почему вектор нужно как-то по особенному заполнять?

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 · 28.04.2013, 20:10 **[ТС]**

diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования

Добавлено через 1 минуту
DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...

@diagon · 28.04.2013, 20:21

Сообщение от ZaMaZaN4iK

Но почему?

Потому что глобальные массивы расположены не на стеке, и для них нет таких суровых ограничений на размер.
Можно было еще попробовать сделать массив static'ом, это тоже должно помочь.

@ZaMaZaN4iK · 28.04.2013, 20:24 **[ТС]**

diagon, а где расположены глобальные массивы?

@kravam · 28.04.2013, 20:43

Сообщение от 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 · 28.04.2013, 20:49

Сообщение от ZaMaZaN4iK

diagon, а где расположены глобальные массивы?

В .global секции. Ну, это уже уровень ассемблера.
Если вкратце, то они одни на всю программу, за счет этого у них дешевая инициализация. А вот локальные массивы заново создаются при каждом вызове функции (в данном случае при входе в main).

@ZaMaZaN4iK · 28.04.2013, 21:02 **[ТС]**

kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

Добавлено через 9 минут
Всем спасибо за ответы!

@kravam · 28.04.2013, 21:30

Сообщение от ZaMaZaN4iK

kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.

ну да

Сообщение от ZaMaZaN4iK

То есть если глобальная переменная инициализирована, то она помещается в стек.

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

Сообщение от ZaMaZaN4iK

если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

В стек. Все локальные переменные, независимо от того, инициализированы они или нет, помещаются в стек. И ты работаешь со стеком.

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

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

Ну просто. Пусть есть локальная переменная x:

C++
1
int x= 2;

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

Ну а глобальные в зависимости от инициализации в одной из секций, повторюсь, на имена секций стандарта, кажись нет. Просто их так обзывает g++.

@ZaMaZaN4iK · 28.04.2013, 22:32 **[ТС]**

kravam, большое спасибо - теперь понял, наконец-то, как оно всё хранится.

Новые блоги и статьи Все статьи Все блоги /
WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .

@stima 503 / 352 / 94 Регистрация: 22.03.2011 Сообщений: 1,112
	28.04.2013, 00:51
	Это ограничение стека http://www.cs.nyu.edu/exact/co... erflow.txt. Создайте массивы на куче или расширьте стек. 1

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 19:54 [ТС]
	diagon, просто в олимпиадном программировании обычно юзают сразу long long и не парятся.Прошу прощения, не досмотрел про условие - там 10 в 9 степени, а не 109.Сейчас попробую сделать массивы глобальными, хотя навряд ли это поможет. kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает? 0

@DU 1500 / 1146 / 165 Регистрация: 05.12.2011 Сообщений: 2,279
	28.04.2013, 19:57
	взяли и засрали стек на ровном месте. достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец. 1

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:02 [ТС]
	DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому. 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:10 [ТС]
	diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования Добавлено через 1 минуту DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++... 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:24 [ТС]
	diagon, а где расположены глобальные массивы? 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 21:02 [ТС]
	kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял? Добавлено через 9 минут Всем спасибо за ответы! 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 22:32 [ТС]
	kravam, большое спасибо - теперь понял, наконец-то, как оно всё хранится. 0