Apakah ada batas panjang larik maksimal dalam C ++?

Apakah ada panjang maksimum untuk array di C ++?

Apakah ini batas C ++ atau tergantung pada mesin saya? Apakah itu dapat diubah? Apakah itu tergantung pada jenis array terbuat dari apa?

Dapatkah saya melanggar batas itu atau saya harus mencari cara yang lebih baik untuk menyimpan informasi? Dan apa yang seharusnya menjadi cara paling sederhana?

Yang harus saya lakukan adalah menyimpan int lama pada array, saya bekerja di lingkungan Linux. Pertanyaan saya adalah: apa yang harus saya lakukan jika saya perlu menyimpan array bilangan bulat panjang N dengan N> 10 digit?

Saya memerlukan ini karena saya sedang menulis beberapa algoritma kriptografi (seperti misalnya p-Pollard) untuk sekolah, dan menabrak dinding bilangan bulat dan panjang representasi array.

Ada dua batasan, keduanya tidak ditegakkan oleh C ++ tetapi oleh perangkat keras.

Batas pertama (seharusnya tidak pernah tercapai) ditetapkan oleh pembatasan jenis ukuran yang digunakan untuk menggambarkan indeks dalam array (dan ukurannya). Itu diberikan oleh nilai maksimum yang std::size_tbisa diambil sistem . Tipe data ini cukup besar untuk memuat ukuran dalam byte dari objek apa pun

Batas lainnya adalah batas memori fisik. Semakin besar objek Anda dalam array, semakin cepat batas ini tercapai karena memori penuh. Sebagai contoh, a vector<int>dari ukuran yang diberikan n biasanya membutuhkan beberapa kali lebih banyak memori daripada array jenis vector<char>(minus nilai konstan kecil), karena intbiasanya lebih besar dari char. Oleh karena itu, a vector<char>dapat berisi lebih banyak item daripada vector<int>sebelum memori penuh. Jumlah yang sama untuk array gaya C mentah seperti int[]dan char[].

Selain itu, batas atas ini dapat dipengaruhi oleh jenis yang allocatordigunakan untuk membangun vectorkarena allocatorbebas mengatur memori apa pun yang diinginkan. Alokasi pengalokasi yang sangat aneh tapi nontheless dapat menyatukan memori sedemikian rupa sehingga contoh identik dari objek berbagi sumber daya. Dengan cara ini, Anda bisa memasukkan banyak objek identik ke dalam wadah yang seharusnya menggunakan semua memori yang tersedia.

Selain itu, C ++ tidak menerapkan batasan apa pun.

Tidak ada yang menyebutkan batas ukuran bingkai tumpukan .

Ada dua tempat memori dapat dialokasikan:

• Di heap (memori yang dialokasikan secara dinamis).
  Batas ukuran di sini adalah kombinasi dari perangkat keras yang tersedia dan kemampuan OS untuk mensimulasikan ruang dengan menggunakan perangkat lain untuk sementara menyimpan data yang tidak digunakan ( yaitu memindahkan halaman ke hard disk).
• Di tumpukan (variabel yang dideklarasikan secara lokal).
  Batas ukuran di sini ditentukan oleh kompiler (dengan batasan perangkat keras yang memungkinkan). Jika Anda membaca dokumentasi kompiler, Anda sering dapat mengubah ukuran ini.

Jadi, jika Anda mengalokasikan array secara dinamis (batasnya besar dan dijelaskan secara rinci oleh posting lain.

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

Atau jika array dialokasikan pada stack maka Anda dibatasi oleh ukuran frame stack. Vektor NB dan wadah lain memiliki kehadiran kecil di tumpukan tetapi biasanya sebagian besar data akan berada di tumpukan.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame

Melihatnya dari sudut pandang praktis dan bukan teori, pada sistem Windows 32 bit, jumlah total maksimum memori yang tersedia untuk satu proses adalah 2 GB. Anda dapat mematahkan batasan dengan masuk ke sistem operasi 64 bit dengan lebih banyak memori fisik, tetapi apakah melakukan ini atau mencari alternatif sangat tergantung pada pengguna yang Anda tuju dan anggaran mereka. Anda juga dapat mengembangkannya menggunakan PAE .

Jenis array sangat penting, karena penyelarasan struktur default pada banyak kompiler adalah 8 byte, yang sangat boros jika penggunaan memori menjadi masalah. Jika Anda menggunakan Visual C ++ untuk menargetkan Windows, lihat arahan paket #pragma sebagai cara mengatasi hal ini.

Hal lain yang harus dilakukan adalah melihat apa yang dalam teknik kompresi memori dapat membantu Anda, seperti matriks jarang, kompresi cepat, dll ... Sekali lagi ini sangat tergantung pada aplikasi. Jika Anda mengedit posting Anda untuk memberikan lebih banyak informasi tentang apa yang sebenarnya ada dalam array Anda, Anda mungkin mendapatkan jawaban yang lebih berguna.

Sunting: Diberikan sedikit informasi lebih lanjut tentang persyaratan Anda, kebutuhan penyimpanan Anda tampaknya antara 7,6 GB dan 76 GB tidak terkompresi, yang akan membutuhkan kotak 64 bit yang agak mahal untuk disimpan sebagai larik dalam memori di C ++. Ini menimbulkan pertanyaan mengapa Anda ingin menyimpan data dalam memori, di mana seseorang mengandaikan kecepatan akses, dan untuk memungkinkan akses acak. Cara terbaik untuk menyimpan data ini di luar array cukup banyak berdasarkan pada bagaimana Anda ingin mengaksesnya. Jika Anda perlu mengakses anggota array secara acak, untuk sebagian besar aplikasi cenderung ada cara pengelompokan rumpun data yang cenderung diakses pada saat yang sama. Misalnya, dalam database GIS dan spasial yang besar, data sering kali dibuat berdasarkan wilayah geografis. Dalam istilah pemrograman C ++, Anda dapat mengganti operator array [] untuk mengambil bagian data Anda dari penyimpanan eksternal sebagaimana diperlukan.

Saya setuju dengan hal di atas, bahwa jika Anda menginternalisasi array Anda dengan

 int myArray[SIZE] 

maka SIZE dibatasi oleh ukuran bilangan bulat. Tetapi Anda selalu dapat malloc sepotong memori dan memiliki pointer ke sana, sebesar yang Anda inginkan selama malloc tidak mengembalikan NULL.

Untuk meringkas tanggapan, luaskan, dan untuk menjawab pertanyaan Anda secara langsung:

Tidak, C ++ tidak memberlakukan batasan apa pun untuk dimensi array.

Tetapi karena array harus disimpan di suatu tempat dalam memori, maka batas terkait memori yang dikenakan oleh bagian lain dari sistem komputer berlaku. Perhatikan bahwa batas-batas ini tidak secara langsung berhubungan dengan dimensi (= jumlah elemen) dari array, tetapi lebih kepada ukurannya (= jumlah memori yang diambil). Dimensi ( D ) dan ukuran dalam memori ( S ) dari array tidak sama, karena mereka terkait oleh memori yang diambil oleh elemen tunggal ( E ): S = D * E . SekarangE

tergantung pada:

• jenis elemen array (elemen bisa lebih kecil atau lebih besar)
• penyelarasan memori (untuk meningkatkan kinerja, elemen ditempatkan pada alamat yang merupakan kelipatan dari beberapa nilai, yang memperkenalkan
  'ruang terbuang' (padding) antara elemen
• ukuran bagian statis objek (dalam pemrograman berorientasi objek, komponen statis objek dengan tipe yang sama hanya disimpan satu kali, terlepas dari jumlah objek dengan tipe yang sama)

Perhatikan juga bahwa Anda biasanya mendapatkan batasan terkait memori yang berbeda dengan mengalokasikan data array pada stack (sebagai variabel otomatis:) int t[N], atau di heap (alokasi dinamis dengan malloc()/ newatau menggunakan mekanisme STL), atau di bagian statis dari memori proses (seperti variabel statis:) static int t[N]. Bahkan ketika mengalokasikan pada heap, Anda masih membutuhkan sejumlah kecil memori pada stack untuk menyimpan referensi ke blok memori yang dialokasikan heap (tetapi biasanya diabaikan).

Ukuran size_ttipe tidak memiliki pengaruh pada programmer (saya berasumsi programmer menggunakan size_ttipe untuk pengindeksan, seperti yang dirancang untuk itu), karena penyedia kompiler harus ke typedeftipe integer yang cukup besar untuk mengatasi jumlah memori maksimal yang mungkin untuk platform yang diberikan Arsitektur.

Sumber keterbatasan ukuran memori berasal dari

• jumlah memori yang tersedia untuk proses (yang dibatasi 2 ^ 32 byte untuk aplikasi 32-bit, bahkan pada kernel OS 64-bit),
• pembagian memori proses (mis. jumlah memori proses yang dirancang untuk stack atau heap),
• fragmentasi memori fisik (banyak fragmen memori bebas kecil yang tersebar tidak berlaku untuk menyimpan satu struktur monolitik),
• jumlah memori fisik,
• dan jumlah memori virtual.

Mereka tidak dapat 'tweak' pada tingkat aplikasi, tetapi Anda bebas untuk menggunakan kompiler yang berbeda (untuk mengubah batas ukuran tumpukan), atau port aplikasi Anda ke 64-bit, atau port ke OS lain, atau ubah fisik / konfigurasi memori virtual dari mesin (virtual? fisik?).

Ini tidak biasa (dan bahkan disarankan) untuk memperlakukan semua faktor di atas sebagai gangguan eksternal dan dengan demikian sebagai sumber kesalahan runtime yang mungkin terjadi, dan untuk secara hati-hati memeriksa & bereaksi terhadap kesalahan terkait alokasi memori dalam kode program Anda.

Jadi akhirnya: sementara C ++ tidak memaksakan batasan apa pun, Anda masih harus memeriksa kondisi terkait memori yang merugikan saat menjalankan kode Anda ... :-)

Seperti banyak jawaban bagus yang dicatat, ada banyak batasan yang bergantung pada versi kompiler C ++, sistem operasi dan karakteristik komputer Anda. Namun, saya menyarankan skrip berikut pada Python yang memeriksa batas pada mesin Anda.

Ini menggunakan pencarian biner dan pada setiap iterasi memeriksa apakah ukuran menengah dimungkinkan dengan membuat kode yang mencoba membuat array ukuran. Skrip mencoba mengompilasinya (maaf, bagian ini hanya berfungsi di Linux) dan menyesuaikan pencarian biner tergantung pada keberhasilannya. Saksikan berikut ini:

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)

Anda dapat menyimpannya di mesin Anda dan meluncurkannya, dan itu akan mencetak ukuran maksimum yang dapat Anda buat. Untuk mesin saya adalah 2305843009213693951.

Satu hal yang menurut saya tidak disebutkan dalam jawaban sebelumnya.

Saya selalu merasakan "bau busuk" dalam arti refactoring ketika orang menggunakan hal-hal seperti itu dalam desain mereka.

Itu adalah array yang sangat besar dan mungkin bukan cara terbaik untuk merepresentasikan data Anda baik dari sudut pandang efisiensi maupun dari sudut pandang kinerja.

Bersulang,

rampok

Jika Anda harus berurusan dengan data sebesar itu, Anda harus membaginya menjadi beberapa bagian yang dapat dikelola. Itu tidak akan masuk ke memori di komputer kecil mana pun. Anda mungkin dapat memuat sebagian data dari disk (apa pun yang cukup masuk akal), melakukan perhitungan dan mengubahnya, menyimpannya ke disk, lalu ulangi hingga selesai.

Menjengkelkan tidak spesifik seperti semua jawaban saat ini, mereka sebagian besar benar tetapi dengan banyak peringatan, tidak selalu disebutkan. Intinya adalah, Anda memiliki dua batas atas, dan hanya satu yang benar-benar didefinisikan, jadi YMMV :

1. Batas waktu kompilasi

Pada dasarnya, apa yang akan diizinkan oleh kompiler Anda. Untuk Visual C ++ 2017 pada kotak Windows 10 x64, ini adalah batas maksimal saya pada waktu kompilasi sebelum mencapai batas 2GB,

unsigned __int64 max_ints[255999996]{0};

Jika saya melakukan ini sebagai gantinya,

unsigned __int64 max_ints[255999997]{0};

Saya akan mendapatkan:

Error C1126 automatic allocation exceeds 2G

Saya tidak yakin bagaimana 2G terkoreksi ke 255999996/ 7. Saya mencari-cari kedua nomor di Google, dan satu-satunya hal yang dapat saya temukan yang mungkin terkait adalah * T&J ini tentang masalah presisi dengandc . Apa pun itu, tampaknya bukan masalah jenis int array mana yang Anda coba isi, berapa banyak elemen yang dapat dialokasikan.

2. Batas waktu berjalan

Tumpukan dan tumpukan Anda memiliki batasannya sendiri. Batasan ini adalah nilai yang berubah berdasarkan sumber daya sistem yang tersedia, serta seberapa "berat" aplikasi Anda. Misalnya, dengan sumber daya sistem saya saat ini, saya bisa menjalankannya:

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

Tetapi jika saya mengubah sedikit saja ...

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

Bam! Stack overflow!

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).

Dan untuk merinci seluruh titik aplikasi Anda, ini bagus untuk dilakukan:

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

Tapi ini menyebabkan stack overflow:

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

Saya terkejut fungsi anggota max_size () dari std :: vector belum disebutkan di sini.

"Mengembalikan jumlah maksimum elemen yang bisa ditampung oleh kontainer karena batasan implementasi sistem atau pustaka, yaitu std :: distance (begin (), end ()) untuk container terbesar."

Kita tahu bahwa std::vectordiimplementasikan sebagai array dinamis di bawah kap, jadi max_size()harus memberikan perkiraan yang sangat dekat dari panjang maksimum dinamis array pada mesin Anda.

Program berikut membuat tabel perkiraan panjang array maksimum untuk berbagai tipe data.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

template <typename T>
std::string mx(T e) {
    std::vector<T> v;
    return std::to_string(v.max_size());
}

std::size_t maxColWidth(std::vector<std::string> v) {
    std::size_t maxWidth = 0;

    for (const auto &s: v)
        if (s.length() > maxWidth)
            maxWidth = s.length();

    // Add 2 for space on each side
    return maxWidth + 2;
}

constexpr long double maxStdSize_t = std::numeric_limits<std::size_t>::max();

// cs stands for compared to std::size_t
template <typename T>
std::string cs(T e) {
    std::vector<T> v;
    long double maxSize = v.max_size();
    long double quotient = maxStdSize_t / maxSize;
    return std::to_string(quotient);
}

int main() {
    bool v0 = 0;
    char v1 = 0;

    int8_t v2 = 0;
    int16_t v3 = 0;
    int32_t v4 = 0;
    int64_t v5 = 0;

    uint8_t v6 = 0;
    uint16_t v7 = 0;
    uint32_t v8 = 0;
    uint64_t v9 = 0;

    std::size_t v10 = 0;
    double v11 = 0;
    long double v12 = 0;

    std::vector<std::string> types = {"data types", "bool", "char", "int8_t", "int16_t",
                                      "int32_t", "int64_t", "uint8_t", "uint16_t",
                                      "uint32_t", "uint64_t", "size_t", "double",
                                      "long double"};

    std::vector<std::string> sizes = {"approx max array length", mx(v0), mx(v1), mx(v2),
                                      mx(v3), mx(v4), mx(v5), mx(v6), mx(v7), mx(v8),
                                      mx(v9), mx(v10), mx(v11), mx(v12)};

    std::vector<std::string> quotients = {"max std::size_t / max array size", cs(v0),
                                          cs(v1), cs(v2), cs(v3), cs(v4), cs(v5), cs(v6),
                                          cs(v7), cs(v8), cs(v9), cs(v10), cs(v11), cs(v12)};

    std::size_t max1 = maxColWidth(types);
    std::size_t max2 = maxColWidth(sizes);
    std::size_t max3 = maxColWidth(quotients);

    for (std::size_t i = 0; i < types.size(); ++i) {
        while (types[i].length() < (max1 - 1)) {
            types[i] = " " + types[i];
        }

        types[i] += " ";

        for  (int j = 0; sizes[i].length() < max2; ++j)
            sizes[i] = (j % 2 == 0) ? " " + sizes[i] : sizes[i] + " ";

        for  (int j = 0; quotients[i].length() < max3; ++j)
            quotients[i] = (j % 2 == 0) ? " " + quotients[i] : quotients[i] + " ";

        std::cout << "|" << types[i] << "|" << sizes[i] << "|" << quotients[i] << "|\n";
    }

    std::cout << std::endl;

    std::cout << "N.B. max std::size_t is: " <<
        std::numeric_limits<std::size_t>::max() << std::endl;

    return 0;
}

Di macOS saya (dentang versi 5.0.1), saya mendapatkan yang berikut:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775807   |             2.000000             |
|        char |   9223372036854775807   |             2.000000             |
|      int8_t |   9223372036854775807   |             2.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   9223372036854775807   |             2.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Pada ideone gcc 8.3 saya mendapatkan:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775744   |             2.000000             |
|        char |   18446744073709551615  |             1.000000             |
|      int8_t |   18446744073709551615  |             1.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   18446744073709551615  |             1.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

Perlu dicatat bahwa ini adalah batas teoretis dan pada kebanyakan komputer, Anda akan kehabisan memori jauh sebelum Anda mencapai batas ini. Misalnya, kita melihat bahwa untuk tipe charaktif gcc, jumlah maksimum elemen sama dengan maks std::size_t. Mencoba ini , kami mendapatkan kesalahan:

prog.cpp: In function ‘int main()’:
prog.cpp:5:61: error: size of array is too large
  char* a1 = new char[std::numeric_limits<std::size_t>::max()];

Terakhir, seperti yang ditunjukkan oleh @MartinYork, untuk array statis ukuran maksimum dibatasi oleh ukuran tumpukan Anda.

Seperti yang telah ditunjukkan, ukuran array dibatasi oleh perangkat keras dan OS Anda (man ulimit). Perangkat lunak Anda, mungkin hanya dibatasi oleh kreativitas Anda. Misalnya, dapatkah Anda menyimpan "array" di disk? Apakah Anda benar-benar membutuhkan int panjang panjang? Apakah Anda benar-benar membutuhkan array yang padat? Apakah Anda bahkan memerlukan array sama sekali?

Salah satu solusi sederhana adalah menggunakan Linux 64 bit. Bahkan jika Anda secara fisik tidak memiliki ram yang cukup untuk array Anda, OS akan memungkinkan Anda untuk mengalokasikan memori seolah-olah Anda melakukannya karena memori virtual yang tersedia untuk proses Anda cenderung jauh lebih besar daripada memori fisik. Jika Anda benar-benar perlu mengakses semua yang ada di array, ini berarti menyimpannya di disk. Tergantung pada pola akses Anda, mungkin ada cara yang lebih efisien untuk melakukan ini (yaitu: menggunakan mmap (), atau hanya menyimpan data secara berurutan dalam file (dalam hal ini cukup Linux 32 bit sudah mencukupi)).

saya akan berkeliling dengan membuat array dinamis 2d:

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

lebih lanjut tentang ini di sini https://stackoverflow.com/a/936702/3517001