16.1 vector อาเรย์ที่ยืดได้

อาเรย์ในบทที่ 5 ต้องบอกขนาดตั้งแต่ตอนเขียนโค้ด โจทย์บอกว่า N ไม่เกินแสน เราก็จองแสนช่องไว้นอก main ทั้งที่ชุดทดสอบส่วนใหญ่ใช้ไม่กี่สิบช่อง ถ้าโจทย์ไม่บอกจำนวนมาก่อน ก็ต้องเดาเอาเอง และต้องเก็บจำนวนที่ใช้จริงไว้ในตัวแปรอีกตัวเสมอ vector ของ C++ แก้ทุกเรื่องนี้ มันคืออาเรย์ที่จองขนาดตอนรันได้ ยืดออกได้ทีละช่องเมื่อมีข้อมูลเพิ่ม และรู้ขนาดของตัวเอง โค้ดแข่งขันที่เขียนด้วย C++ แทบทั้งหมดใช้ vector แทนอาเรย์ธรรมดา

vector ตัวแรก

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score; // (1)!
    score.push_back(72); // (2)!
    score.push_back(85);
    score.push_back(64);
    cout << "size = " << score.size() << '\n'; // (3)!
    cout << score[0] << ' ' << score[1] << ' ' << score[2] << '\n'; // (4)!
    return 0;
}

1. ประกาศ vector ที่เก็บ int ชนิดของสมาชิกเขียนในวงเล็บแหลม <int> ถ้าจะเก็บ long long ก็เขียน vector<long long> vector ที่ประกาศแบบนี้เริ่มต้นว่าง มี 0 ช่อง
2. push_back เพิ่มค่าต่อท้าย vector ยืดออกหนึ่งช่อง
3. size() บอกว่าตอนนี้มีกี่ช่อง ไม่ต้องเก็บจำนวนไว้ในตัวแปรแยกเหมือนอาเรย์
4. ใช้ [] เหมือนอาเรย์ทุกอย่าง ช่องแรกคือช่องที่ 0

size = 3
72 85 64

วนทุกช่องด้วย range-for

วนทุกช่องได้สองแบบ แบบ index เหมือนอาเรย์ หรือแบบ range-for จากบทที่ 15 ซึ่งไม่ต้องยุ่งกับ index เลย ถ้าจะแก้ค่าในช่อง ต้องใส่ & ให้ตัวแปรในลูปเป็น reference ของช่องนั้น

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score = {72, 85, 64};
    for (int &s : score) {
        s += 5;
    }
    int total = 0;
    for (int s : score) {
        total += s;
    }
    for (int i = 0; i < (int)score.size(); i++) {
        cout << "score[" << i << "] = " << score[i] << '\n';
    }
    cout << "total = " << total << '\n';
    return 0;
}

score[0] = 77
score[1] = 90
score[2] = 69
total = 236

• บรรทัดที่ 6 สร้าง vector พร้อมค่าเริ่มต้นสามค่าในปีกกา เหมือนกำหนดค่าเริ่มต้นของอาเรย์
• บรรทัดที่ 7 int &s คือ s เป็นชื่อเล่นของช่องนั้นจริงๆ บวก 5 ให้ s จึงเปลี่ยนค่าในช่อง
• บรรทัดที่ 11 ใช้แค่อ่าน ไม่ต้องมี & s เป็นสำเนาของค่าในช่อง
• บรรทัดที่ 14 วนแบบ index ต้องเขียน (int)score.size() เหตุผลอยู่ในส่วนลองทำให้พังท้ายหน้า

อ่านข้อมูลที่ไม่รู้จำนวน

น้องจดระยะทางที่วิ่งในแต่ละวันเป็นเมตร แล้วปิดท้ายด้วย 0 โปรแกรมต้องพิมพ์จำนวนวัน และระยะของทุกวันย้อนจากวันล่าสุด ก่อนอ่านไม่รู้ว่ามีกี่วัน ถ้าเป็นอาเรย์ต้องจองเผื่อไว้ แต่ vector แค่ push_back ไปเรื่อยๆ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> run;
    int meters;
    while (cin >> meters && meters != 0) {
        run.push_back(meters);
    }
    cout << "days = " << run.size() << '\n';
    for (int i = (int)run.size() - 1; i >= 0; i--) {
        cout << run[i];
        if (i > 0) {
            cout << ' ';
        }
    }
    cout << '\n';
    return 0;
}

2400 3100 1800
5000 2600 0

days = 5
2600 5000 1800 3100 2400

บรรทัดที่ 10 ใช้ cin >> meters เป็นเงื่อนไขแบบหน้า 15.2 เป็นจริงเมื่ออ่านตัวเลขได้ และเป็นเท็จเมื่อข้อมูลหมด ลูปจึงหยุดทั้งตอนเจอ 0 และตอนข้อมูลหมดโดยไม่มี 0 ปิดท้าย

สร้างพร้อมขนาดและค่าเริ่มต้น

ถ้ารู้จำนวนก่อน สร้าง vector ให้มีขนาดตามนั้นไปเลย แล้วอ่านใส่ทีละช่องแบบอาเรย์ แบบที่ใช้บ่อยมีสามแบบ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> a(4);
    vector<int> b(4, -1);
    vector<int> c = {90, 75, 82};
    cout << a.size() << ": " << a[0] << ' ' << a[3] << '\n';
    cout << b.size() << ": " << b[0] << ' ' << b[3] << '\n';
    cout << c.size() << ": " << c[0] << ' ' << c[2] << '\n';
    return 0;
}

4: 0 0
4: -1 -1
3: 90 82

ขนาดมาจากข้อมูลเข้าได้ ตัวอย่างนี้คือการนับคะแนนโหวตแบบหน้า 5.3 มีผู้สมัคร K คน หมายเลข 1 ถึง K และบัตรลงคะแนน N ใบ จำนวนผู้สมัครรู้ตอนรันเท่านั้น จึงสร้างอาเรย์นับเป็น vector ขนาด K + 1 ช่อง ทิ้งช่องที่ 0 ไว้ ให้หมายเลขผู้สมัครตรงกับ index

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> votes(k + 1, 0);
    for (int i = 0; i < n; i++) {
        int choice;
        cin >> choice;
        votes[choice]++;
    }
    for (int c = 1; c <= k; c++) {
        cout << c << ": " << votes[c] << '\n';
    }
    return 0;
}

4 10
2 1 2 4 2 1 4 2 1 2

1: 3
2: 5
3: 0
4: 2

[] ไม่ตรวจขอบ at() ตรวจ

[] ของ vector ไม่ตรวจว่า index อยู่ในขอบเขตหรือเปล่า เหมือนอาเรย์ในหน้า 5.5 ใช้ช่องที่ไม่มีอยู่จริงแล้วอาจได้ค่าแปลกๆ เงียบๆ ส่วน at() ทำงานเหมือน [] แต่ตรวจทุกครั้ง ถ้าเกินขอบจะหยุดโปรแกรมทันทีพร้อมบอกสาเหตุ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score = {72, 85, 64, 90, 58};
    cout << score[2] << '\n';
    cout << score.at(2) << '\n';
    cout << score.at(5) << '\n';
    return 0;
}

64
64
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

Process returned -1073740791 (0xC0000409)

รหัสนี้เหมือนตอน substr ตัดเกินความยาวในหน้า 15.4 ข้อความบอกตรงๆ ว่าขอช่อง __n ที่ 5 แต่ size() มีแค่ 5 ช่อง คือ 0 ถึง 4 โปรแกรมหยุดที่บรรทัดนั้น ไม่ไปต่อ ส่วนถ้าเขียน score[5] แทน บนเครื่องที่เขียนเอกสารนี้ได้ 0 ออกมาเฉยๆ ไม่มีอะไรเตือน คำว่า exception กับ throw ในข้อความคือกลไกแจ้งข้อผิดพลาดของ C++ ซึ่งไม่อยู่ในเนื้อหาของเอกสารนี้ จำแค่ว่าเห็นข้อความนี้แปลว่าใช้ index เกินขอบ

ทำอะไรกับ vector ได้อีก

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score = {72, 85, 64};
    cout << score.front() << ' ' << score.back() << '\n';
    score.pop_back();
    cout << score.size() << ' ' << score.back() << '\n';
    score.clear();
    cout << score.size() << ' ' << score.empty() << '\n';
    score.resize(3);
    cout << score.size() << ' ' << score[2] << '\n';
    score.assign(2, 50);
    cout << score.size() << ' ' << score[0] << ' ' << score[1] << '\n';
    return 0;
}

72 64
2 85
0 1
3 0
2 50 50

empty() คืน bool cout พิมพ์จริงเป็น 1 และเท็จเป็น 0 ระวัง front() back() และ pop_back() กับ vector ที่ว่าง ไม่มีช่องให้หยิบ ผลเหมือนใช้ index เกินขอบ ให้เช็ก empty() ก่อนเสมอ

คัดลอกและเทียบได้ทั้งก้อน

อาเรย์ของภาษา C คัดลอกด้วย = ไม่ได้ และ a == b ไม่ได้เทียบค่าในช่อง ต้องวนลูปเองทั้งสองเรื่อง vector ทำได้ในคำสั่งเดียว

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> before = {72, 85, 64};
    vector<int> after = before;
    after[1] = 90;
    cout << before[1] << ' ' << after[1] << '\n';
    cout << (before == after) << '\n';
    after[1] = 85;
    cout << (before == after) << '\n';
    return 0;
}

85 90
0
1

บรรทัดที่ 7 คัดลอกทุกช่องไปเป็น vector ใหม่อีกตัว แก้ after แล้ว before ไม่เปลี่ยน ส่วน == เป็นจริงเมื่อขนาดเท่ากันและทุกช่องเท่ากัน ต้องมีวงเล็บรอบ before == after เพราะ << ทำก่อน ==

การคัดลอกทั้งก้อนสะดวก แต่ใช้เวลาตามจำนวนช่อง vector ล้านช่องก็คัดลอกล้านค่า หน้า 16.2 จะเห็นว่าการคัดลอกโดยไม่ตั้งใจทำให้โปรแกรมช้าลงได้เป็นพันเท่า

vector ใหญ่ประกาศใน main ได้

หน้า 5.5 เห็นแล้วว่า int a[10000000]; ใน main พังด้วย stack overflow เพราะ stack มีแค่ราว 2 MB vector ขนาดเท่ากันใน main รันผ่านสบาย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> a(10000000);
    a[9999999] = 7;
    cout << a.size() << ' ' << a[9999999] << '\n';
    return 0;
}

10000000 7

ตัวแปร a ที่อยู่ใน stack เป็นแค่กล่องเล็กๆ ที่จำว่าข้อมูลอยู่ที่ไหนและมีกี่ช่อง ส่วนช่องข้อมูลจริง 40 ล้าน byte อยู่ในหน่วยความจำอีกส่วนหนึ่งที่เรียกว่า heap ซึ่งใหญ่กว่า stack มาก จึงไม่ต้องย้ายไปไว้นอก main อีกแล้ว แต่ขีดจำกัดหน่วยความจำของ grader ยังมีอยู่ เช่น ถ้าโจทย์ให้ 256 MB ก็เก็บ int ได้ไม่ถึง 70 ล้านช่อง และยังต้องเหลือที่ให้ตัวแปรอื่นด้วย

ลองทำให้พัง

แบบที่ 1 สร้างพร้อมขนาดแล้วยัง push_back

สองวิธีอ่านข้อมูลเข้าในหน้านี้ คือสร้างขนาด n แล้วอ่านใส่ score[i] หรือสร้างว่างแล้ว push_back ถ้าเอาสองวิธีมาปนกัน

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> score(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        score.push_back(x);
    }
    cout << "size = " << score.size() << '\n';
    for (int i = 0; i < (int)score.size(); i++) {
        cout << score[i];
        if (i + 1 < (int)score.size()) {
            cout << ' ';
        }
    }
    cout << '\n';
    return 0;
}

3
72 85 64

size = 6
0 0 0 72 85 64

บรรทัดที่ 8 สร้างไว้แล้ว 3 ช่องที่เป็น 0 push_back ต่อท้ายอีก 3 ช่อง ได้ 6 ช่อง ถ้าเอาไปหาค่าน้อยสุดหรือค่าเฉลี่ย จะผิดเพราะมี 0 ปนมาสามตัว เลือกอย่างใดอย่างหนึ่ง สร้าง score(n) คู่กับ cin >> score[i] หรือสร้างว่างคู่กับ push_back

แบบที่ 2 vector ว่างแล้วใช้ []

กลับกันกับแบบที่ 1 ถ้าสร้างว่างแต่อ่านใส่ score[i]

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> score;
    for (int i = 0; i < n; i++) {
        cin >> score[i];
    }
    cout << score[0] << '\n';
    return 0;
}

คอมไพล์ผ่านไม่มีคำเตือน พอป้อน 3 แล้วตามด้วย 72 85 64 โปรแกรมปิดตัวทันทีโดยไม่พิมพ์อะไร

Process returned -1073741819 (0xC0000005)

รหัสเดียวกับการใช้ช่องที่ไม่มีอยู่จริงในหน้า 5.5 vector ว่างยังไม่ได้จองช่องข้อมูลไว้เลย score[0] จึงชี้ไปที่ที่ไม่มีสิทธิ์เขียน [] ไม่ได้ทำให้ vector ยืด มีแค่ push_back ที่ยืด

แบบที่ 3 เทียบ int กับ size()

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score = {72, 85, 64};
    for (int i = 0; i < score.size(); i++) {
        cout << score[i] << '\n';
    }
    return 0;
}

72
85
64

scores.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < score.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

โปรแกรมทำงานถูก แต่มีคำเตือนแบบเดียวกับ name.size() ของ string ในหน้า 15.4 size() ของ vector ก็คืนจำนวนเต็มชนิด unsigned คือไม่มีค่าติดลบ (long long unsigned int เก็บได้ 0 ถึงราว 1.8 × 10¹⁹) ในภาษา C++ แค่เปิด -Wall ก็เตือนทุกครั้งที่เทียบ int กับ unsigned (ภาษา C ต้องเปิด -Wextra ด้วยถึงจะเตือน) เพราะถ้าฝั่ง int ติดลบ ผลการเทียบจะผิด แก้ได้สองแบบ เขียน i < (int)score.size() แบบในหน้านี้ หรือใช้ range-for ไปเลยเมื่อไม่ต้องใช้ index

แบบที่ 4 size() - 1 ตอน vector ว่าง

ทำไมการเป็น unsigned ถึงอันตราย ลองดูตัวเลขนี้

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score;
    cout << score.size() - 1 << '\n';
    cout << (int)score.size() - 1 << '\n';
    return 0;
}

18446744073709551615
-1

0 ลบ 1 ในชนิด unsigned ไม่ได้ -1 แต่วนไปเป็นค่ามากสุดของชนิดนั้น แบบเดียวกับเลขไมล์ในหน้า 1.3 และแบบเดียวกับ word.size() - 3 ที่ทำให้ substr พังในหน้า 15.4 ลูปที่ตั้งใจเทียบช่องที่ติดกันทุกคู่แบบนี้จึงอันตราย

for (int i = 0; i < score.size() - 1; i++) {
    if (score[i] > score[i + 1]) {
        count++;
    }
}

ถ้า score มีข้อมูล ลูปทำงานถูก แต่ถ้า score ว่าง ขอบบนกลายเป็นเลขยี่สิบหลัก ลูปจึงเข้าไปอ่าน score[0] ทั้งที่ไม่มีช่องนั้น บนเครื่องที่เขียนเอกสารนี้ เมื่อขนาดมาจากข้อมูลเข้าแล้วป้อน 0 โปรแกรมพังทันทีด้วย 0xC0000005 แบบเดียวกับแบบที่ 2 ทั้งแบบ Code::Blocks และแบบ -O2 แต่ถ้า compiler รู้ตั้งแต่ตอนคอมไพล์ว่า vector ว่าง เช่น ประกาศ vector<int> score; แล้ววนลูปนี้ทันที แบบ -O2 จะมีคำเตือนเพิ่มมาอีกชุด

empty.cpp:9:32: warning: iteration 2147483647 invokes undefined behavior [-Waggressive-loop-optimizations]
    9 |         if (score[i] > score[i + 1]) {
      |                              ~~^~~
empty.cpp:8:23: note: within this loop
    8 |     for (int i = 0; i < score.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~

คำเตือนนี้บอกว่า i จะถูกบวกจนเกินค่ามากสุดของ int ซึ่งเป็นพฤติกรรมที่มาตรฐานไม่กำหนด compiler จึงปรับลูปไปตามใจ บนเครื่องที่เขียนเอกสารนี้โปรแกรมแบบ -O2 นั้นไม่จบเลย รอห้าวินาทีก็ยังทำงานอยู่ ส่วนแบบ Code::Blocks พังด้วย 0xC0000005 เหมือนเดิม ผลต่างกันตามแฟล็กแบบนี้เป็นอาการของ undefined behavior ทางแก้คือ cast เป็น int ก่อนลบ แบบบรรทัดที่ 8 ของโปรแกรมข้างบน ซึ่งได้ -1 ตามที่คิด และนี่คือเหตุผลที่ตัวอย่าง running เขียน (int)run.size() - 1

สรุป

• vector<int> v; เริ่มว่าง push_back เพิ่มต่อท้าย size() บอกจำนวนช่อง
• vector<int> v(n); ได้ n ช่องที่เป็น 0 v(n, x) ได้ n ช่องที่เป็น x ขนาดมาจากข้อมูลเข้าได้
• [] ไม่ตรวจขอบ at() ตรวจและหยุดโปรแกรมพร้อมบอกสาเหตุ ใช้ at() ช่วยหาบั๊ก
• วนอ่านด้วย for (int x : v) วนแก้ด้วย for (int &x : v)
• คัดลอกด้วย = เทียบด้วย == ได้ทั้งก้อน และ vector ใหญ่ประกาศใน main ได้
• size() เป็น unsigned เทียบกับ int ให้ cast เป็น (int) และอย่าลบ size() - 1 โดยไม่ cast
• สร้างพร้อมขนาดคู่กับ [] สร้างว่างคู่กับ push_back อย่าปนกัน