Есть ли ограничение максимальной длины массива в C ++? - PullRequest
160 голосов
/ 19 октября 2008

Есть ли максимальная длина массива в C ++?

Это ограничение C ++ или оно зависит от моей машины? Это настраивается? Зависит ли это от типа массива?

Могу ли я как-то нарушить этот лимит или мне нужно искать лучший способ хранения информации? А какой должен быть самый простой способ?

Что мне нужно сделать, так это хранить long long int в массиве, я работаю в среде Linux. Мой вопрос: что мне делать, если мне нужно хранить массив из N длинных целых чисел с N> 10 цифр?

Мне это нужно, потому что я пишу некоторый криптографический алгоритм (например, p-Pollard) для школы и попал в эту стену целых чисел и длины представления массивов.

Ответы [ 11 ]

153 голосов
/ 19 октября 2008

Никто не упомянул ограничение размера фрейма стека .

Память может быть выделена в двух местах:

  • На куче (динамически выделяемая память).
    Ограничение размера здесь представляет собой сочетание доступного оборудования и способности ОС имитировать пространство с помощью других устройств для временного хранения неиспользуемых данных (, т.е. перемещение страниц на жесткий диск).
  • В стеке (локально объявленные переменные).
    Ограничение размера здесь определяется компилятором (с возможными аппаратными ограничениями). Если вы читаете документацию компилятора, вы часто можете настроить этот размер.

Таким образом, если вы выделяете массив динамически (ограничение велико и подробно описано в других публикациях.

int* a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

В качестве альтернативы, если массив размещен в стеке, вы ограничены размером кадра стека. N.B. векторы и другие контейнеры имеют небольшое присутствие в стеке, но обычно большая часть данных будет в куче.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame
153 голосов
/ 19 октября 2008

Есть два ограничения, оба не навязанные C ++, а аппаратными.

Первый предел (никогда не должен быть достигнут) устанавливается ограничениями типа размера, используемого для описания индекса в массиве (и его размера). Он задается максимальным значением, которое может принять std::size_t системы. Этот тип данных всегда должен быть самым большим целочисленным типом системы.

Другим ограничением является ограничение физической памяти. Чем больше ваши объекты в массиве, тем раньше будет достигнут этот предел, поскольку память заполнена. Например, vector<int> данного размера n обычно занимает в четыре раза больше памяти, чем массив типа vector<char> (минус небольшое постоянное значение). Следовательно, vector<char> может содержать больше элементов, чем vector<int> до заполнения памяти. То же самое относится к массивам в стиле C * int[] и char[].

Кроме того, на этот верхний предел может влиять тип allocator, используемый для построения vector, поскольку allocator может свободно управлять памятью любым удобным для него способом. Очень странный, но, тем не менее, мыслимый распределитель может объединять память таким образом, чтобы идентичные экземпляры объекта совместно использовали ресурсы. Таким образом, вы можете вставить много одинаковых объектов в контейнер, который в противном случае использовал бы всю доступную память.

Кроме того, C ++ не устанавливает никаких ограничений.

13 голосов
/ 19 октября 2008

Если смотреть на это с практической, а не теоретической точки зрения, в 32-битной системе Windows максимальный общий объем памяти, доступный для одного процесса, составляет 2 ГБ. Вы можете преодолеть ограничение, перейдя на 64-битную операционную систему с гораздо большей физической памятью, но то, делать это или искать альтернативы, во многом зависит от ваших предполагаемых пользователей и их бюджетов. Вы также можете несколько расширить его, используя PAE .

Тип массива очень важен, так как выравнивание структуры по умолчанию на многих компиляторах составляет 8 байтов, что очень расточительно, если использование памяти является проблемой. Если вы используете Visual C ++ для работы с Windows, воспользуйтесь директивой # pragma pack , чтобы преодолеть это.

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

Редактировать: Учитывая немного больше информации о ваших точных требованиях, ваши потребности в хранилище, по-видимому, составляют от 7,6 ГБ до 76 ГБ без сжатия, что потребовало бы довольно дорогого 64-битного блока для хранения в виде массива в памяти в C ++. Возникает вопрос, почему вы хотите хранить данные в памяти, где предполагается скорость доступа, и разрешить произвольный доступ. Лучший способ хранить эти данные вне массива в значительной степени основан на том, как вы хотите получить к ним доступ. Если вам нужен случайный доступ к элементам массива, для большинства приложений существуют способы группировки групп данных, к которым обычно обращаются одновременно. Например, в больших ГИС и пространственных базах данных данные часто разбиваются по географическим областям. В терминах программирования на C ++ вы можете переопределить оператор массива [], чтобы при необходимости извлекать части ваших данных из внешнего хранилища.

4 голосов
/ 16 мая 2016

Чтобы суммировать ответы, расширить их и ответить на ваш вопрос напрямую:

Нет, C ++ не накладывает никаких ограничений на размеры массива.

Но так как массив должен храниться где-то в памяти, применяются ограничения, связанные с памятью, налагаемые другими частями компьютерной системы. Обратите внимание, что эти ограничения напрямую не относятся к измерениям (= количество элементов) массива, а скорее к его размеру (= количеству занятой памяти). Размеры ( D ) и размер в памяти ( S ) массива не совпадают, так как они связаны с памятью, занятой одним элементом ( E * 1018) *): S = D * E .

Теперь E зависит от:

  • тип элементов массива (элементы могут быть меньше или больше)
  • выравнивание памяти (для повышения производительности элементы размещаются по адресам, кратным некоторому значению, которое вводит
    «Потерянное пространство» (заполнение) между элементами
  • размер статических частей объектов (в объектно-ориентированном программировании статические компоненты объектов одного и того же типа сохраняются только один раз, независимо от количества таких объектов одного типа)

Также обратите внимание, что вы обычно получаете различные ограничения, связанные с памятью, выделяя данные массива в стеке (как автоматическая переменная: int t[N]) или в куче (динамическое размещение с malloc() / new или используя механизмы STL ) или в статической части памяти процесса (как статическая переменная: static int t[N]). Даже при выделении в куче вам все еще нужно небольшое количество памяти в стеке для хранения ссылок на выделенные в куче блоки памяти (но обычно это незначительно).

Размер типа size_t не влияет на программиста (я полагаю, что для индексации программист использует тип size_t, так как он предназначен для него), так как поставщик компилятора должен typedef преобразовать его в достаточно большой целочисленный тип для адресации максимально возможный объем памяти для данной архитектуры платформы.

Источники ограничений объема памяти проистекают из

  • объем памяти, доступной для процесса (который ограничен 2 ^ 32 байтами для 32-битных приложений, даже в ядрах 64-битных ОС),
  • деление памяти процесса (например, объем памяти процесса, предназначенной для стека или кучи),
  • фрагментация физической памяти (многие разбросанные небольшие фрагменты свободной памяти не применимы для хранения одной монолитной структуры),
  • объем физической памяти,
  • и объем виртуальной памяти.

Они не могут быть «подправлены» на уровне приложения, но вы можете использовать другой компилятор (для изменения пределов размера стека), либо перенести свое приложение на 64-битную версию, либо перенести его на другую ОС, либо изменить конфигурация физической / виртуальной памяти (виртуальной? физической?) машины.

Нередко (и даже желательно) рассматривать все вышеперечисленные факторы как внешние помехи и, следовательно, как возможные источники ошибок времени выполнения, а также тщательно проверять и реагировать на ошибки, связанные с выделением памяти, в программном коде.

Итак, наконец: хотя C ++ не накладывает никаких ограничений, вам все равно придется проверять наличие неблагоприятных условий, связанных с памятью, при запуске вашего кода ...: -)

4 голосов
/ 19 октября 2008

Я бы согласился с вышесказанным, что если вы инициализируете свой массив с помощью

 int myArray[SIZE] 

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

3 голосов
/ 08 августа 2016

Как отмечалось много отличных ответов, существует множество ограничений, которые зависят от вашей версии компилятора C ++, операционной системы и характеристик компьютера. Однако я предлагаю следующий скрипт на Python, который проверяет ограничение на вашем компьютере.

Он использует бинарный поиск и на каждой итерации проверяет, возможен ли средний размер, путем создания кода, который пытается создать массив такого размера. Сценарий пытается скомпилировать его (извините, эта часть работает только в Linux) и настроить бинарный поиск в зависимости от успеха. Проверьте это:

import os

cpp_source = 'int a[{}]; int main() {{ return 0; }}'

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name='1.cpp', mode='w')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system('g++ 1.cpp 2> errors')
        #  Read the errors files
        errors = open('errors', 'r').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print '{} is the maximum avaliable length'.format(answer)

Вы можете сохранить его на своем компьютере и запустить, и он напечатает максимальный размер, который вы можете создать. Для моей машины это 2305843009213693951.

2 голосов
/ 19 декабря 2009

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

2 голосов
/ 19 октября 2008

Одна вещь, о которой я не думаю, упоминалась в предыдущих ответах.

Я всегда ощущаю «неприятный запах» в смысле рефакторинга, когда люди используют такие вещи в своем дизайне.

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

ура

Rob

1 голос
/ 27 сентября 2018

Как ни досадно неспецифичны все текущие ответы, они в основном правильные, но со многими оговорками, не всегда упоминаемыми. Суть в том, что у вас есть два верхних предела, и только один из них действительно определен, поэтому YMMV :

1. Ограничение времени компиляции

По сути, что позволит ваш компилятор. Для Visual C ++ 2017 в 64-разрядной версии Windows 10 это мой максимальный лимит во время компиляции до ограничения в 2 ГБ,

unsigned __int64 max_ints[255999996]{0};

Если бы я сделал это вместо этого,

unsigned __int64 max_ints[255999997]{0};

Я бы получил:

Error C1126 automatic allocation exceeds 2G

Я не уверен, как 2G коррелирует с 255999996 / 7. Я гуглил оба числа, и единственное, что я мог найти, возможно, было связано с этим * nix Q & A о проблеме точности с dc. В любом случае, кажется, что не имеет значения, какой тип массива int вы пытаетесь заполнить, сколько элементов может быть выделено.

2. Ограничения времени выполнения

У вашего стека и кучи есть свои ограничения. Эти ограничения являются значениями, которые изменяются в зависимости от доступных системных ресурсов, а также от того, насколько «тяжелым» является само ваше приложение. Например, с моими текущими системными ресурсами я могу заставить это работать:

int main()
{
    int max_ints[257400]{ 0 };
    return 0;
}

Но если я немного подправлю ...

int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

Bam! Переполнение стека!

Exception thrown at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000). Unhandled exception at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).

И просто для того, чтобы подробно описать всю тяжесть вашего приложения, все было хорошо:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[400]{ 0 };
    return 0;
}  

Но это вызвало переполнение стека:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  
0 голосов
/ 25 октября 2015

Я бы обошёл это, создав 2d динамический массив:

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

подробнее об этом здесь https://stackoverflow.com/a/936702/3517001

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...