11.3 struct ซ้อนกัน ขนาด และ union

สมาชิกของ struct เป็นชนิดอะไรก็ได้ รวมถึงอาเรย์ และ struct อีกตัว โจทย์เรขาคณิตใช้เรื่องนี้มากที่สุด จุดมีพิกัดสองตัว เส้นตรงมีจุดสองจุด สี่เหลี่ยมมีมุมสองมุม หน้านี้ประกอบชนิดเหล่านี้ขึ้นทีละชั้น แล้วใช้หาพื้นที่ที่สี่เหลี่ยมสองรูปทับกัน จากนั้นดูว่า struct หนึ่งก้อนใช้หน่วยความจำเท่าไรจริงๆ และปิดท้ายด้วย union ซึ่งหน้าตาคล้าย struct แต่ทำงานต่างกันมาก

จุด เส้นตรง สี่เหลี่ยม

#include <stdio.h>

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point from;
    Point to;
} Segment;

typedef struct { // (1)!
    Point low;
    Point high;
} Rect;

int main()
{
    Segment road = {{1, 2}, {4, 6}}; // (2)!
    Rect park = {{0, 0}, {10, 5}};
    int dx = road.to.x - road.from.x; // (3)!
    int dy = road.to.y - road.from.y;
    printf("road from (%d, %d) to (%d, %d)\n", road.from.x, road.from.y, road.to.x, road.to.y);
    printf("road length squared = %d\n", dx * dx + dy * dy);
    Point corner = park.high; // (4)!
    printf("park top right = (%d, %d)\n", corner.x, corner.y);
    printf("park area = %d\n", (park.high.x - park.low.x) * (park.high.y - park.low.y));
    return 0;
}

สี่เหลี่ยมผืนผ้าที่ด้านขนานกับแกน x และแกน y กำหนดได้ด้วยมุมซ้ายล่าง low กับมุมขวาบน high สองมุมก็พอ อีกสองมุมหาได้จากสองมุมนี้
ปีกกาซ้อนปีกกา ชั้นนอกคือ Segment ชั้นในแต่ละคู่คือ Point หนึ่งจุด
อ่านจากซ้ายไปขวา road แล้วเอา to แล้วเอา x ซ้อนกี่ชั้นก็ใส่จุดต่อไปเรื่อยๆ
สมาชิกที่เป็น struct ก็คัดลอกทั้งก้อนด้วย = ได้เหมือนกัน

road from (1, 2) to (4, 6)
road length squared = 25
park top right = (10, 5)
park area = 50

ถนนยาว 3 หน่วยตามแกน x และ 4 หน่วยตามแกน y กำลังสองของความยาวคือ 9 + 16 = 25 ส่วนสวนกว้าง 10 สูง 5 พื้นที่ 50 การแยก Point ออกมาเป็นชนิดของตัวเองทำให้ทุกที่ที่พูดถึงจุด ใช้ .x กับ .y แบบเดียวกันหมด ไม่ต้องตั้งชื่อ from_x from_y to_x to_y เป็นตัวแปรแยกสี่ตัว

พื้นที่ที่สี่เหลี่ยมสองรูปทับกัน

โจทย์แนวนี้ออกบ่อย สองพื้นที่ทับกันเท่าไร ห้องสองห้องชนกันไหม กล้องสองตัวเห็นพื้นที่ร่วมกันเท่าไร ถ้านั่งแยกกรณีว่าสี่เหลี่ยม B อยู่ซ้าย ขวา บน ล่าง หรือคร่อม A จะได้ if หลายสิบกรณีและพลาดง่ายมาก มีวิธีที่สั้นกว่านั้น

มองทีละแกน ส่วนที่ทับกันต้องอยู่ในทั้ง A และ B

ขอบซ้ายของส่วนที่ทับ คือขอบซ้ายที่อยู่ ขวากว่า ระหว่างสองรูป จึงเป็นค่ามากของ low.x ทั้งสอง ในรูปคือ max(1, 4) = 4
ขอบขวาของส่วนที่ทับ คือขอบขวาที่อยู่ ซ้ายกว่า จึงเป็นค่าน้อยของ high.x ทั้งสอง คือ min(6, 9) = 6
แกน y ทำแบบเดียวกัน ขอบล่างคือ max(1, 3) = 3 ขอบบนคือ min(5, 8) = 5

ส่วนที่ทับจึงเป็นสี่เหลี่ยมจาก (4, 3) ถึง (6, 5) กว้าง 2 สูง 2 พื้นที่ 4 และถ้าสองรูปไม่ทับกันเลย ขอบซ้ายที่ได้จะอยู่ขวากว่าหรือตรงกับขอบขวา ความกว้างจึงติดลบหรือเป็นศูนย์ ใช้ข้อนี้ตรวจได้ทันทีว่าทับกันจริงไหม

#include <stdio.h>

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point low;
    Point high;
} Rect;

int max_int(int a, int b)
{
    return a > b ? a : b;
}

int min_int(int a, int b)
{
    return a < b ? a : b;
}

int main()
{
    Rect a, b;
    scanf("%d %d %d %d", &a.low.x, &a.low.y, &a.high.x, &a.high.y);
    scanf("%d %d %d %d", &b.low.x, &b.low.y, &b.high.x, &b.high.y);
    Rect common;
    common.low.x = max_int(a.low.x, b.low.x);
    common.low.y = max_int(a.low.y, b.low.y);
    common.high.x = min_int(a.high.x, b.high.x);
    common.high.y = min_int(a.high.y, b.high.y);
    int width = common.high.x - common.low.x;
    int height = common.high.y - common.low.y;
    if (width > 0 && height > 0) { // (1)!
        printf("overlap = %d\n", width * height);
    } else {
        printf("overlap = 0\n");
    }
    return 0;
}

ต้องตรวจ ทั้งสองแกน ถ้าแกนใดแกนหนึ่งไม่ทับกัน สองรูปก็ไม่ทับกัน ใช้ > ไม่ใช่ >= เพราะถ้ากว้างเป็น 0 แปลว่าแค่ขอบแตะกัน พื้นที่ที่ทับคือ 0

1 1 6 5
4 3 9 8

overlap = 4

ทดสอบให้ครบทุกแบบ ป้อน 0 0 2 2 กับ 2 0 4 2 ซึ่งขอบแตะกันพอดี ต้องได้ 0 ป้อน 0 0 10 10 กับ 2 2 3 3 ซึ่งรูปหนึ่งอยู่ในอีกรูป ต้องได้ 1 คือพื้นที่ของรูปเล็ก และลองแบบที่อยู่ห่างกันแนวทแยง ซึ่งเป็นกรณีที่คนลืมบ่อยที่สุด ดูในส่วนลองทำให้พัง

วิธีเดียวกันขยายเป็นสี่เหลี่ยม N รูปได้ ส่วนที่ทุกรูปทับกันมีขอบซ้ายเป็นค่ามากของ low.x ทุกรูป และขอบขวาเป็นค่าน้อยของ high.x ทุกรูป ไล่หาด้วยลูปเดียว

อาเรย์ที่อยู่ใน struct

นักเรียนหนึ่งคนสอบสามวิชา เก็บคะแนนเป็นอาเรย์ไว้ในตัวนักเรียนเลย ไม่ต้องมีสมาชิก score1 score2 score3

#include <stdio.h>

typedef struct {
    char name[21];
    int scores[3];
} Student;

Student students[100];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", students[i].name);
        for (int j = 0; j < 3; j++) {
            scanf("%d", &students[i].scores[j]);
        }
    }
    for (int i = 0; i < n; i++) {
        int total = 0;
        for (int j = 0; j < 3; j++) {
            total += students[i].scores[j];
        }
        printf("%s %d\n", students[i].name, total);
    }
    return 0;
}

3
Mali 87 75 90
Krit 92 68 81
Ploy 78 88 85

Mali 252
Krit 241
Ploy 251

students[i].scores[j] อ่านจากซ้ายไปขวาเหมือนเดิม นักเรียนคนที่ i แล้วเอาอาเรย์คะแนน แล้วเอาวิชาที่ j

struct ใหญ่แค่ไหน

ในบทที่ 1 เห็นแล้วว่า int ใช้ 4 byte และ char ใช้ 1 byte ดูขนาดของอะไรก็ได้ด้วย sizeof ถ้าเดา struct ที่มี char int char น่าจะได้ 1 + 4 + 1 = 6 byte ลองรันดูจริง

#include <stdio.h>

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point low;
    Point high;
} Rect;

typedef struct {
    char grade;
    int score;
    char room;
} Loose;

typedef struct {
    int score;
    char grade;
    char room;
} Tight;

int main()
{
    printf("Point = %d bytes\n", (int)sizeof(Point)); // (1)!
    printf("Rect = %d bytes\n", (int)sizeof(Rect));
    printf("Loose = %d bytes\n", (int)sizeof(Loose));
    printf("Tight = %d bytes\n", (int)sizeof(Tight));
    return 0;
}

sizeof ให้ขนาดเป็นจำนวน byte ชนิดของผลไม่ใช่ int จึงแปลงเป็น int ด้วย cast จากบทที่ 1 ก่อนพิมพ์ด้วย %d

Point = 8 bytes
Rect = 16 bytes
Loose = 12 bytes
Tight = 8 bytes

Point กับ Rect ตรงตามที่บวกกัน แต่ Loose ได้ 12 ไม่ใช่ 6 และ Tight ซึ่งมีสมาชิกเหมือนกันทุกตัว แค่สลับลำดับ ได้ 8

เหตุผลคือ CPU อ่าน int ได้เร็วที่สุดเมื่อ int ตัวนั้นเริ่มที่ตำแหน่งที่หารด้วย 4 ลงตัว compiler จึงเว้นช่องว่างให้ score ไปเริ่มที่ byte ที่ 4 ช่องว่างที่ไม่ได้เก็บอะไรนี้เรียกว่า padding ส่วน padding ท้าย struct มีไว้ให้ก้อนถัดไปในอาเรย์เริ่มที่ตำแหน่งหารด้วย 4 ลงตัวเหมือนกัน ขนาดของ struct จึงปัดขึ้นเป็นพหุคูณของ alignment ของชนิดพื้นฐานที่ใหญ่ที่สุดในนั้น alignment คือตัวเลขที่ตำแหน่งเริ่มของชนิดนั้นต้องหารลงตัว บนเครื่องนี้ int คือ 4 char คือ 1 สมาชิกที่เป็นอาเรย์นับตามชนิดของช่อง ไม่ใช่ขนาดทั้งอาเรย์ เช่น struct ที่มี char name[10] กับ int score ได้ 16 byte ซึ่งหารด้วย 4 ลงตัว ไม่ใช่พหุคูณของ 10

เรื่องนี้ไม่ต้องคำนวณเองให้แม่น เพราะขึ้นกับชนิดของสมาชิกและเครื่อง สิ่งที่ต้องจำมีสามข้อ

อย่าบวกขนาดสมาชิกเอง อยากรู้ขนาดให้ใช้ sizeof เสมอ โดยเฉพาะตอนขอหน่วยความจำด้วย malloc ซึ่งจะเห็นในหน้า 11.4
เรียงสมาชิกจากชนิดใหญ่ไปเล็ก เช่น long long ก่อน int ก่อน char มักได้ struct ที่เล็กที่สุด
ขนาดสำคัญตอนเก็บเป็นอาเรย์ใหญ่ อาเรย์ Loose หนึ่งล้านช่องใช้ 12 ล้าน byte แต่ Tight ใช้ 8 ล้าน byte ต่างกัน 4 MB ทั้งที่เก็บข้อมูลเท่ากัน คิดเทียบกับหน่วยความจำที่โจทย์ให้ทุกครั้ง

union แบบสั้นๆ

union เขียนเหมือน struct ทุกอย่าง แค่เปลี่ยนคำว่า struct เป็น union แต่สมาชิกทุกตัว ใช้หน่วยความจำที่เดียวกัน ขนาดของ union จึงเท่ากับสมาชิกตัวที่ใหญ่ที่สุด และเก็บค่าที่มีความหมายได้ทีละสมาชิกเท่านั้น

#include <stdio.h>

typedef union {
    int whole;
    double real;
} Number;

typedef struct {
    int whole;
    double real;
} Both;

int main()
{
    printf("union = %d bytes\n", (int)sizeof(Number));
    printf("struct = %d bytes\n", (int)sizeof(Both));
    Number n;
    n.whole = 42;
    printf("%d\n", n.whole);
    n.real = 2.75;
    printf("%f\n", n.real);
    return 0;
}

union = 8 bytes
struct = 16 bytes
42
2.750000

union มีขนาด 8 byte เท่ากับ double ส่วน struct ที่มีสมาชิกเหมือนกันใช้ 16 byte คือ int 4 byte padding 4 byte และ double 8 byte ตามเหตุผลในหัวข้อที่แล้ว

เมื่อเขียน n.real แล้ว ค่า 42 ใน n.whole ก็ถูกเขียนทับไป เพราะเป็นหน่วยความจำก้อนเดียวกัน บนเครื่องที่เขียนเอกสารนี้ ใส่ n.whole = 42; แล้ว n.real = 0.1; จากนั้นพิมพ์ n.whole ได้ -1717986918 ซึ่งคือ byte ครึ่งหนึ่งของเลข 0.1 ที่ถูกอ่านเป็น int ไม่ใช่ 42 อีกแล้ว ใครใช้ union ต้องจำเองว่าตอนนี้เก็บสมาชิกตัวไหนอยู่

union ใช้ในงานที่หน่วยความจำจำกัดมาก เช่นโปรแกรมบนไมโครคอนโทรลเลอร์ หรือเก็บข้อมูลที่เป็นได้หลายแบบแต่ทีละแบบ การแข่งขันแทบไม่ได้ใช้ เพราะหน่วยความจำที่โจทย์ให้มักพอ และใช้ผิดแล้วได้ค่าขยะแบบที่เห็น ให้รู้จักไว้พออ่านโค้ดคนอื่นออก แล้วใช้ struct ตามปกติ

ลองทำให้พัง

แบบที่ 1 ข้ามชั้นของ struct

Rect r = {{1, 2}, {6, 5}};
printf("%d\n", r.high.x - r.x);

rect.c:16:32: error: 'Rect' has no member named 'x'
   16 |     printf("%d\n", r.high.x - r.x);
      |                                ^

Rect มีสมาชิกแค่ low กับ high ไม่มี x โดยตรง ต้องบอกให้ครบทุกชั้นว่าเป็น x ของมุมไหน คือ r.low.x ข้อความ has no member named ยังขึ้นเมื่อพิมพ์ชื่อสมาชิกผิดด้วย เช่น r.hight

แบบที่ 2 ลืมตรวจว่าทับกันจริงไหม

ถ้าตัด if ในโปรแกรม overlap ออก แล้วพิมพ์ width * height เลย

#include <stdio.h>

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point low;
    Point high;
} Rect;

int max_int(int a, int b)
{
    return a > b ? a : b;
}

int min_int(int a, int b)
{
    return a < b ? a : b;
}

int main()
{
    Rect a, b;
    scanf("%d %d %d %d", &a.low.x, &a.low.y, &a.high.x, &a.high.y);
    scanf("%d %d %d %d", &b.low.x, &b.low.y, &b.high.x, &b.high.y);
    int width = min_int(a.high.x, b.high.x) - max_int(a.low.x, b.low.x);
    int height = min_int(a.high.y, b.high.y) - max_int(a.low.y, b.low.y);
    printf("overlap = %d\n", width * height);
    return 0;
}

0 0 2 2
5 5 8 8

overlap = 9

สองรูปนี้อยู่ห่างกันคนละมุม ไม่ทับกันเลย แต่โปรแกรมตอบ 9 เพราะความกว้างได้ 2 - 5 = -3 และความสูงก็ได้ -3 ลบคูณลบกลายเป็นบวก ถ้าทดสอบแค่กรณีที่ห่างกันแนวนอนอย่างเดียว ความกว้างติดลบแต่ความสูงเป็นบวก จะได้ค่าติดลบ ซึ่งยังพอเห็นว่าผิด แต่กรณีแนวทแยงได้ค่าบวกที่ดูเหมือนถูก ชุดทดสอบของโจทย์แบบนี้มักมีกรณีนี้เสมอ

สรุป

สมาชิกของ struct เป็น struct อีกตัวหรืออาเรย์ก็ได้ เข้าถึงด้วยการต่อจุดไปเรื่อยๆ เช่น r.low.x หรือ students[i].scores[j]
สี่เหลี่ยมด้านขนานแกนเก็บด้วยมุมซ้ายล่างกับมุมขวาบน
ส่วนที่ทับกันคือ max ของขอบล่าง และ min ของขอบบน ทีละแกน ต้องตรวจว่ากว้างและสูงเป็นบวกทั้งคู่
sizeof บอกขนาดจริง ซึ่งอาจใหญ่กว่าผลรวมของสมาชิกเพราะ padding เรียงสมาชิกจากใหญ่ไปเล็กช่วยลดได้
union ให้สมาชิกทุกตัวใช้หน่วยความจำร่วมกัน เก็บได้ทีละค่า การแข่งขันแทบไม่ได้ใช้