מערכים ב-C: הצהרה, אתחול ומעבר בלולאה

מערך הוא בלוק בגודל קבוע של איברים מאותו טיפוס, שמסודרים אחד אחרי השני בזיכרון. הסידור הרציף הזה הוא כל הסיפור: בגללו גישה לפי אינדקס היא מיידית, בגללו מערכים ומצביעים קשורים כל כך, ובגללו C יכולה לתת לכם את הכתובת של איבר אפס ולתת לכם למצוא את השאר בחשבון.

הצהרה על מערך

טיפוס האיברים, שם וגודל בסוגריים מרובעים:

int    scores[5];       // 5 ints
double prices[100];     // 100 doubles
char   initials[3];     // 3 chars

הגודל הוא מספר האיברים, והוא חייב להיות ידוע במקום שבו המערך מוצהר, בדרך כלל ערך מילולי או קבוע שהוגדר עם #define. הזיכרון נשמר מיד; שום דבר לא מוקצה מאוחר יותר.

מערך מקומי שזה עתה הוצהר מכיל זבל, לא אפסים:

#include <stdio.h>

int main(void) {
    int uninitialized[5];        // contents are indeterminate
    int zeroed[5] = {0};         // every element is 0

    printf("zeroed:        ");
    for (int i = 0; i < 5; i++) printf("%d ", zeroed[i]);

    printf("\nuninitialized: ");
    for (int i = 0; i < 5; i++) printf("%d ", uninitialized[i]);
    printf("   <-- whatever was in that memory\n");

    return 0;
}

השורה השנייה עשויה להדפיס אפסים, עשויה להדפיס מספרים ענקיים, ועשויה להשתנות בין הרצות או בין גרסת debug לגרסת release. קריאת הערכים האלה היא התנהגות לא מוגדרת; אתחלו לפני שאתם קוראים.

אתחול

כמה צורות, כולן שימושיות:

#include <stdio.h>

int main(void) {
    int a[5] = {10, 20, 30, 40, 50};   // full list
    int b[5] = {1, 2};                 // rest are zero-filled: 1 2 0 0 0
    int c[5] = {0};                    // the whole array is zero
    int d[]  = {7, 8, 9};              // size deduced: 3 elements
    int e[5] = {[4] = 99, [0] = 1};    // designated initializers (C99)

    int n = sizeof d / sizeof d[0];

    printf("a: "); for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\nb: "); for (int i = 0; i < 5; i++) printf("%d ", b[i]);
    printf("\nc: "); for (int i = 0; i < 5; i++) printf("%d ", c[i]);
    printf("\nd: "); for (int i = 0; i < n; i++) printf("%d ", d[i]);
    printf("  (size deduced as %d)", n);
    printf("\ne: "); for (int i = 0; i < 5; i++) printf("%d ", e[i]);
    printf("\n");

    return 0;
}

את הניב {0} כדאי לזכור: כל איבר שלא רשמתם מאותחל לאפס, כך שאפס יחיד מאפס את כל המערך. מאתחלים ממוענים ([4] = 99) מאפשרים לקבוע מיקומים מסוימים ולהשאיר את השאר באפס, וזה נוח לטבלאות חיפוש שרובן ריקות.

דבר אחד שאי אפשר לעשות הוא להשים ערך למערך אחרי שהוא נוצר:

int a[3] = {1, 2, 3};
int b[3];
b = a;                    // error: an array is not assignable
memcpy(b, a, sizeof a);   // this is how you copy one

האינדקס מתחיל מאפס

האיבר הראשון הוא arr[0] והאחרון הוא arr[n-1]. אין arr[n].

#include <stdio.h>

int main(void) {
    int scores[5] = {88, 92, 75, 60, 100};

    printf("first  scores[0] = %d\n", scores[0]);
    printf("third  scores[2] = %d\n", scores[2]);
    printf("last   scores[4] = %d\n", scores[4]);

    scores[1] = 95;                       // write to an element
    printf("after update, scores[1] = %d\n", scores[1]);

    printf("\naddresses (note the even spacing):\n");
    for (int i = 0; i < 5; i++) {
        printf("  scores[%d] at %p\n", i, (void *)&scores[i]);
    }

    return 0;
}

הריצו את הלולאה האחרונה והסתכלו על הכתובות: כל אחת נמצאת בדיוק sizeof(int) בתים אחרי הקודמת. האיברים באמת מסודרים ברצף:

 index      0         1         2         3         4
         +--------+--------+--------+--------+--------+
 value   |   88   |   95   |   75   |   60   |  100   |
         +--------+--------+--------+--------+--------+
 offset   +0       +4       +8       +12      +16      bytes
          ^
          &scores[0], which is also what `scores` decays to

אינדקס שמתחיל מאפס אינו בחירה שרירותית: הוא הופך את האינדקס להיסט מההתחלה, וזה בדיוק מה שחשבון הכתובות צריך. scores[i] מוגדר כ-*(scores + i); ראו מצביעים ומערכים.

מציאת האורך

C לא שומרת את אורך המערך בשום מקום בזמן ריצה, אבל הקומפיילר יודע אותו, ו-sizeof נותן לכם גישה אליו:

#include <stdio.h>

int main(void) {
    double prices[] = {4.99, 12.50, 0.99, 7.25};

    printf("total bytes    = %zu\n", sizeof prices);
    printf("bytes per item = %zu\n", sizeof prices[0]);
    printf("length         = %zu\n", sizeof prices / sizeof prices[0]);

    return 0;
}

sizeof(arr) / sizeof(arr[0]) הוא הניב המקובל. חלוקה ב-arr[0] במקום ב-sizeof(double) קבוע בקוד פירושה שהשורה ממשיכה לעבוד גם אם תשנו את טיפוס האיברים.

המלכודת: זה עובד רק במקום שבו המערך הוצהר. העבירו את המערך לפונקציה, והפרמטר הוא מצביע, כך ש-sizeof מודד את המצביע במקום, בדרך כלל 8 בתים, ומקבלים "אורך" של 1 או 2. זו הסיבה שכל פונקציה ב-C שמקבלת מערך מקבלת גם מספר איברים:

#include <stdio.h>

int sum(const int *arr, int n) {       // the length must be passed in
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

int main(void) {
    int data[6] = {3, 1, 4, 1, 5, 9};
    int n = sizeof data / sizeof data[0];   // computed HERE, where it is correct

    printf("length = %d\n", n);
    printf("sum    = %d\n", sum(data, n));

    return 0;
}

מעבר על מערך בלולאה

הצורה המקובלת היא לולאת for מ-0 כל עוד i < n:

#include <stdio.h>

int main(void) {
    int temps[7] = {18, 21, 25, 22, 19, 17, 24};
    int n = sizeof temps / sizeof temps[0];

    int total = 0, hottest = temps[0], coldest = temps[0];

    for (int i = 0; i < n; i++) {
        total += temps[i];
        if (temps[i] > hottest) hottest = temps[i];
        if (temps[i] < coldest) coldest = temps[i];
    }

    printf("readings: ");
    for (int i = 0; i < n; i++) printf("%d ", temps[i]);

    printf("\naverage:  %.1f\n", (double)total / n);
    printf("hottest:  %d\n", hottest);
    printf("coldest:  %d\n", coldest);

    return 0;
}

שימו לב ל-i < n, לא i <= n. עם n איברים האינדקסים החוקיים הם 0 עד n - 1, כך ש-<= מריץ סיבוב נוסף וקורא מעבר לסוף. אתחול hottest ו-coldest מ-temps[0] במקום מ-0 הוא ההרגל השני שכדאי להעתיק: מקסימום שמתחיל מאפס נשבר בשקט על נתונים שכולם שליליים.

חריגה מהגבולות היא התנהגות לא מוגדרת

זה החלק ב-C שמפתיע אנשים שמגיעים משפות אחרות. אין בדיקת גבולות. לא בזמן קומפילציה ולא בזמן ריצה. arr[10] על מערך של חמישה איברים אינו שגיאה: זה חישוב כתובת שהקומפיילר מבצע בלי להעיר דבר.

int arr[5] = {1, 2, 3, 4, 5};
arr[7] = 99;     // writes 8 bytes past the end of the array
int x = arr[-1]; // reads before the start

מה שקורה אחר כך הוא התנהגות לא מוגדרת, והתסמינים שלה מגוונים באופן לא מועיל:

• זה נראה עובד, כי הזיכרון שנפגע לא היה בשימוש;
• משתנה אחר משתנה בלי סיבה נראית לעין;
• התוכנית קורסת עם segmentation fault, אולי הרבה יותר מאוחר;
• ההתנהגות שונה בין -O0 ל--O2.

"נראה עובד" הוא המקרה המסוכן, כי פירושו שהבאג מגיע לייצור. שלוש הגנות:

1. כתבו לולאות עם i < n. רוב החריגות הן טעויות של אחד בתנאי הלולאה.
2. בדקו אינדקסים שמגיעים מקלט.

#include <stdio.h>

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};
    int n = 5;

    int requests[4] = {2, 5, -1, 4};    // two of these are out of range

    for (int i = 0; i < 4; i++) {
        int idx = requests[i];
        if (idx >= 0 && idx < n) {
            printf("arr[%d] = %d\n", idx, arr[idx]);
        } else {
            printf("index %d rejected (valid range is 0..%d)\n", idx, n - 1);
        }
    }

    return 0;
}

3. בנו עם sanitizer בזמן הפיתוח. gcc -fsanitize=address -g prog.c הופך את רוב החריגות לדיווח מיידי שמציין את הקובץ, השורה והמערך המעורב.

מערכים של טיפוסים אחרים

אותו תחביר עובד לכל טיפוס איברים, כולל מבנים (structs):

#include <stdio.h>

typedef struct {
    const char *name;
    int         score;
} Player;

int main(void) {
    Player players[3] = {
        {"Ada",   91},
        {"Grace", 78},
        {"Ken",   85}
    };
    int n = sizeof players / sizeof players[0];

    for (int i = 0; i < n; i++) {
        printf("%-6s %3d\n", players[i].name, players[i].score);
    }

    // an array of char is a string when it ends with '\0'
    char word[6] = "hello";        // 5 characters plus the terminator
    printf("\nword = %s (%zu bytes of storage)\n", word, sizeof word);

    return 0;
}

השורה char word[6] = "hello"; שווה עצירה: מחרוזת ב-C היא פשוט מערך של char שהבית המשמעותי האחרון שלו הוא '\0'. התו המסיים הזה הוא הסיבה שהמערך צריך שישה תאים עבור חמש אותיות.

מערכים באורך משתנה, בקצרה

C99 מתירה מערך שהגודל שלו הוא ערך בזמן ריצה:

int n = get_count();
int buffer[n];        // a variable-length array

שתי אזהרות. הגודל קבוע ברגע שהמערך נוצר, כך ש-VLA אינו רשימה שיכולה לגדול. והזיכרון מגיע מהמחסנית, כך ש-n גדול או כזה שתוקף שולט בו עלול לגרום לה לגלוש ולהקריס את התוכנית, ולכן פרויקטים רבים, כולל ליבת Linux, אוסרים על VLA לחלוטין. בנוסף, ב-C11 התמיכה בהם היא אופציונלית למימושים.

כשהגודל באמת לא ידוע עד זמן הריצה, הקצו זיכרון במקום:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int n = 6;                              // pretend this came from input

    int *arr = malloc(n * sizeof *arr);     // heap, not stack
    if (arr == NULL) {
        return 1;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = (i + 1) * (i + 1);
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);              // indexing works exactly the same
    }
    printf("\n");

    free(arr);
    return 0;
}

שימו לב ש-arr[i] נקרא בדיוק אותו דבר בין אם arr הוא מערך ובין אם הוא מצביע לזיכרון שהוקצה: לתחביר האינדקס זה לא משנה. כל הפרטים בזיכרון דינמי.