[0]zero-index clytie0x/zero-index

16.5 ฟังก์ชันใน algorithm ที่ใช้บ่อย

งานเล็กๆ ที่เขียนลูปเองมาตลอดตั้งแต่บทที่ 5 เช่น หาค่ามากสุดพร้อมตำแหน่ง รวมทุกช่อง นับว่าค่านี้มีกี่ตัว กลับลำดับ ตัดค่าซ้ำ C++ มีฟังก์ชันสำเร็จรูปให้ใน <algorithm> และ <numeric> ซึ่ง bits/stdc++.h รวมไว้ให้แล้ว ทุกตัวรับช่วงแบบเดียวกับ sort คือตำแหน่งเริ่มต้นกับตำแหน่งถัดจากตัวสุดท้าย ใช้ได้ทั้งกับ vector อาเรย์ และ string ข้อดีไม่ได้อยู่ที่เร็วกว่าลูปที่เขียนเอง แต่อยู่ที่สั้นและไม่มีที่ให้ผิดเรื่องขอบของลูป หน้านี้รวมตัวที่ใช้บ่อยที่สุด และปิดท้ายด้วย lower_bound กับ upper_bound ซึ่งตอบคำถามกับข้อมูลที่เรียงแล้วได้เร็วมาก

reverse กลับลำดับ

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> queue_number = {1, 2, 3, 4, 5};
    reverse(queue_number.begin(), queue_number.end());
    for (int i = 0; i < (int)queue_number.size(); i++) {
        cout << queue_number[i] << (i + 1 < (int)queue_number.size() ? ' ' : '\n');
    }
    string word;
    while (cin >> word) {
        string backward = word;
        reverse(backward.begin(), backward.end());
        cout << word << (word == backward ? " yes" : " no") << '\n';
    }
    return 0;
}

level racecar songkhla noon

5 4 3 2 1
level yes
racecar yes
songkhla no
noon yes

reverse แก้ลำดับในตัวเองเลย ไม่ได้สร้างอันใหม่ ถ้ายังอยากเก็บของเดิมไว้ ต้องคัดลอกก่อนแบบบรรทัดที่ 15 คำที่อ่านกลับหลังแล้วเหมือนเดิมเรียกว่า palindrome เทียบกับหน้า 6.5 ที่ต้องเขียนลูปสองตัวชี้เข้าหากันเอง

max_element และ min_element

max(a, b) หาค่าที่มากกว่าของสองค่า ส่วน max_element หาค่ามากสุดของทั้งช่วง และคืนตำแหน่งของมัน ไม่ใช่ค่า ใส่ * ข้างหน้าเพื่อหยิบค่า และลบด้วย begin() เพื่อแปลงเป็น index ถ้ามีหลายช่องที่มากสุดเท่ากัน ได้ช่องแรก

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

int main()
{
    int n;
    cin >> n;
    vector<int> rain(n);
    for (int &r : rain) {
        cin >> r;
    }
    auto most = max_element(rain.begin(), rain.end());
    auto least = min_element(rain.begin(), rain.end());
    cout << "max " << *most << " on day " << most - rain.begin() + 1 << '\n';
    cout << "min " << *least << " on day " << least - rain.begin() + 1 << '\n';
    return 0;
}

7
12 0 35 8 35 0 20

max 35 on day 3
min 0 on day 2

ปริมาณฝนมากสุด 35 มิลลิเมตรมีสองวัน คือวันที่ 3 กับ 5 ได้วันที่ 3 ซึ่งมาก่อน บวก 1 เพราะ index เริ่มที่ 0 แต่วันเริ่มที่ 1 ถ้า vector ว่าง ทั้งสองฟังก์ชันคืน end() ซึ่งไม่ใช่ช่องจริง ห้ามใส่ * ให้เช็ก empty() ก่อน

accumulate รวมทุกช่อง

accumulate(ต้น, ปลาย, ค่าเริ่มต้น) อยู่ใน <numeric> บวกทุกช่องเข้ากับค่าเริ่มต้น ค่าเริ่มต้นไม่ได้บอกแค่ว่าเริ่มนับจากเท่าไร แต่บอกชนิดของผลรวมด้วย ใส่ 0 ได้ผลรวมเป็น int ใส่ 0LL ได้ long long (LL ต่อท้ายตัวเลขแปลว่าเป็น long long)

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

int main()
{
    vector<int> score = {72, 85, 64, 90, 58};
    int total = accumulate(score.begin(), score.end(), 0);
    cout << total << ' ' << (double)total / score.size() << '\n';
    vector<int> price = {1000000000, 1000000000, 1000000000};
    cout << accumulate(price.begin(), price.end(), 0LL) << '\n';
    return 0;
}

369 73.8
3000000000

ผลรวมของ price เกิน int จึงต้องใช้ 0LL ถ้าใส่ 0 ผลจะล้นแบบหน้า 1.3 ดูในส่วนลองทำให้พัง

count นับว่ามีกี่ตัว

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

int main()
{
    vector<int> vote = {2, 1, 2, 4, 2, 1, 4, 2, 1, 2};
    cout << count(vote.begin(), vote.end(), 2) << '\n';
    cout << count(vote.begin(), vote.end(), 3) << '\n';
    string dna = "AGCTTAGCAA";
    cout << count(dna.begin(), dna.end(), 'A') << '\n';
    return 0;
}

5
0
4

count ไล่ดูทุกช่องทุกครั้งที่เรียก ถ้าต้องถามซ้ำเป็นพันๆ ครั้งกับข้อมูลชุดใหญ่ ใช้อาเรย์นับแบบหน้า 5.3 หรือเรียงแล้วใช้ lower_bound กับ upper_bound ท้ายหน้านี้

unique กับ erase ตัดค่าซ้ำ

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

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

int main()
{
    vector<int> plate = {427, 105, 427, 980, 105, 427, 311};
    sort(plate.begin(), plate.end()); // (1)!
    auto new_end = unique(plate.begin(), plate.end()); // (2)!
    cout << new_end - plate.begin() << ' ' << plate.size() << '\n';
    plate.erase(new_end, plate.end()); // (3)!
    cout << plate.size() << ':';
    for (int p : plate) {
        cout << ' ' << p;
    }
    cout << '\n';
    return 0;
}
  1. เรียงก่อน ได้ 105 105 311 427 427 427 980 ค่าซ้ำมาอยู่ติดกัน
  2. unique ย้ายค่าที่ไม่ซ้ำสี่ค่ามาไว้สี่ช่องแรก คืนตำแหน่งของช่องที่ 4 แต่ vector ยังยาว 7 ช่องเท่าเดิม
  3. erase(ต้น, ปลาย) ลบช่วงนั้นออกจาก vector จริงๆ ทำให้เหลือ 4 ช่อง
4 7
4: 105 311 427 980

ปกติเขียนสองบรรทัดหลังรวมเป็นบรรทัดเดียวจนจำได้ขึ้นใจ

sort(plate.begin(), plate.end());
plate.erase(unique(plate.begin(), plate.end()), plate.end());

next_permutation ไล่ทุกลำดับ

เพื่อนสามคน A B C จะนั่งเรียงกันได้กี่แบบ ในหน้า 9.5 เราเขียน recursion พิมพ์ทุกแบบเอง next_permutation เปลี่ยนช่วงให้เป็นลำดับถัดไปตามพจนานุกรม และคืน false เมื่อลำดับปัจจุบันเป็นลำดับสุดท้ายแล้ว ถ้าเริ่มจากลำดับที่เรียงจากน้อยไปมาก แล้ววนจนได้ false ก็จะผ่านครบทุกลำดับพอดี

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

int main()
{
    string seat;
    cin >> seat;
    sort(seat.begin(), seat.end());
    int ways = 0;
    do {
        cout << seat << '\n';
        ways++;
    } while (next_permutation(seat.begin(), seat.end()));
    cout << "ways = " << ways << '\n';
    return 0;
}

CAB

ABC
ACB
BAC
BCA
CAB
CBA
ways = 6
  • ใช้ do ... while เพราะต้องพิมพ์ลำดับแรกก่อนแล้วค่อยเลื่อน ถ้าใช้ while ธรรมดา ลำดับแรก ABC จะหายไป
  • ถ้ามีตัวซ้ำ เช่น AAB จะได้แค่ AAB ABA BAA สามแบบ ไม่ใช่หก เพราะ next_permutation ข้ามลำดับที่หน้าตาซ้ำกันให้เอง
  • n ตัวมี n! ลำดับ 8 ตัวคือ 40,320 ลำดับ 10 ตัวคือ 3,628,800 ลำดับ 12 ตัวคือ 479,001,600 ลำดับ ซึ่งเกินราว 108 รอบต่อวินาทีตามหลักในหน้า 4.5 ไปมากแล้ว การลองทุกแบบอย่างเป็นระบบจะเรียนต่อในบทที่ 21

lower_bound และ upper_bound

สองฟังก์ชันนี้ใช้กับช่วงที่เรียงจากน้อยไปมากแล้วเท่านั้น ให้ค่า x หนึ่งค่า แล้วตอบเป็นตำแหน่ง

ฟังก์ชันคืนตำแหน่งของ
lower_bound(ต้น, ปลาย, x)ช่องแรกที่ค่า ไม่น้อยกว่า x (≥ x)
upper_bound(ต้น, ปลาย, x)ช่องแรกที่ค่า มากกว่า x (> x)

ถ้าไม่มีช่องแบบนั้นเลย ทั้งสองคืน end() ลบด้วย begin() เพื่อแปลงเป็น index แล้วได้คำตอบหลายอย่างโดยไม่ต้องวนลูป

  • จำนวนค่าที่น้อยกว่า x คือ index ของ lower_bound
  • จำนวนค่าที่เท่ากับ x คือ upper_bound ลบ lower_bound
  • มี x อยู่หรือเปล่า ดูว่า lower_bound ไม่ใช่ end() และค่าที่ชี้อยู่เท่ากับ x
#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> score = {75, 60, 90, 50, 60, 60};
    sort(score.begin(), score.end());
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        int low = lower_bound(score.begin(), score.end(), x) - score.begin();
        int high = upper_bound(score.begin(), score.end(), x) - score.begin();
        bool found = low < (int)score.size() && score[low] == x;
        cout << "x = " << x << ": lower " << low << ", upper " << high << ", equal " << high - low << ", found " << found << '\n';
    }
    return 0;
}

4
60 65 100 10

x = 60: lower 1, upper 4, equal 3, found 1
x = 65: lower 4, upper 4, equal 0, found 0
x = 100: lower 6, upper 6, equal 0, found 0
x = 10: lower 0, upper 0, equal 0, found 0

หลังเรียง score คือ 50 60 60 60 75 90 ในแผนภาพ L คือช่องที่ lower_bound ชี้ U คือช่องที่ upper_bound ชี้

index     0   1   2   3   4   5   6
score    50  60  60  60  75  90
x = 60        L           U             มี 60 อยู่ 4 - 1 = 3 ตัว
x = 65                    LU            ไม่มี 65 ทั้งสองชี้ช่องที่ 4
x = 100                           LU    ทั้งสองเป็น end() index 6 เท่ากับ size()

บรรทัดที่ 15 ต้องเช็ก low < (int)score.size() ก่อนอ่าน score[low] เสมอ เพราะถ้า x มากกว่าทุกค่า low จะเป็น 6 ซึ่งเลยช่องสุดท้าย ต้องใช้ && ที่หยุดทันทีเมื่อเงื่อนไขซ้ายเป็นเท็จ แบบหน้า 3.3

ส่วน found ใช้ binary_search(ต้น, ปลาย, x) แทนได้ ซึ่งคืนจริงเท็จว่ามี x หรือไม่ ทั้งสามฟังก์ชันไม่ได้ไล่ดูทีละช่องแบบ count แต่ใช้การค้นแบบแบ่งครึ่งที่หน้า 13.5 กล่าวถึง จึงตอบได้เร็วมากแม้ข้อมูลเป็นล้าน บทที่ 19 จะอธิบายว่าข้างในทำงานอย่างไร เร็วแค่ไหน และเขียนเองอย่างไร ตอนนี้ให้ใช้เป็นก่อน

ลองทำให้พัง

แบบที่ 1 accumulate ด้วยค่าเริ่มต้น 0

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

int main()
{
    vector<long long> distance = {1500000000, 1500000000, 1500000000};
    cout << accumulate(distance.begin(), distance.end(), 0) << '\n';
    cout << accumulate(distance.begin(), distance.end(), 0LL) << '\n';
    return 0;
}

205032704
4500000000

vector เป็น long long แล้วก็ยังผิด เพราะผลรวมระหว่างทางถูกเก็บในชนิดของค่าเริ่มต้น คือ int พอรวมได้ 3 × 109 ก็ล้นไปแล้ว ไม่มีคำเตือนจาก -Wall เลย ให้ติดเป็นนิสัยว่าผลรวมที่อาจเกินสองพันล้าน ใส่ 0LL เสมอ

แบบที่ 2 unique โดยไม่เรียงก่อน

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

int main()
{
    vector<int> plate = {427, 105, 427, 980, 105, 427, 311};
    plate.erase(unique(plate.begin(), plate.end()), plate.end());
    cout << plate.size() << '\n';
    vector<int> again = {105, 105, 311, 427, 427, 427, 980};
    unique(again.begin(), again.end());
    cout << again.size() << '\n';
    return 0;
}

7
7

โปรแกรมนี้คอมไพล์ผ่าน แต่ Code::Blocks ขึ้นคำเตือนที่บรรทัดที่ 10 (ตามด้วยอีกหกบรรทัดที่ชี้ว่า unique ประกาศไว้ตรงไหนในไฟล์ของ STL จบด้วย note: declared here)

unique.cpp:10:11: warning: ignoring return value of '_FIter std::unique(_FIter, _FIter) [with _FIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]', declared with attribute 'nodiscard' [-Wunused-result]
   10 |     unique(again.begin(), again.end());
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

nodiscard คือป้ายที่ STL ติดไว้กับฟังก์ชันที่ค่าที่คืนสำคัญจนห้ามทิ้ง ignoring return value แปลว่าเราทิ้งค่านั้นไป คำเตือนนี้ชี้บั๊กที่สองข้างล่างให้ตรงๆ อ่านคำเตือนทุกครั้งก่อนรัน ส่วนบรรทัดที่ 7 ไม่มีคำเตือน เพราะ compiler ไม่รู้ว่าข้อมูลยังไม่ได้เรียง

ผิดสองแบบ บรรทัดที่ 7 ไม่ได้เรียงก่อน unique ตัดเฉพาะค่าซ้ำที่อยู่ติดกัน ซึ่งในข้อมูลนี้ไม่มีเลย ได้ 7 ทั้งที่ทะเบียนต่างกันมีแค่ 4 คัน บรรทัดที่ 10 เรียงแล้วแต่ลืม erase ค่าที่ไม่ซ้ำถูกย้ายไปต้น vector แล้วจริง แต่ size() ยังเป็น 7 ถ้าเอาไปวนลูปต่อจะเจอค่าที่ไม่ใช้แล้วปนอยู่ท้าย vector

แบบที่ 3 next_permutation โดยไม่เรียงก่อน

ในโปรแกรม seat ถ้าลบบรรทัดที่ 8 ซึ่งเรียง seat ออก แล้วป้อน CAB เหมือนเดิม

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

int main()
{
    string seat;
    cin >> seat;
    int ways = 0;
    do {
        cout << seat << '\n';
        ways++;
    } while (next_permutation(seat.begin(), seat.end()));
    cout << "ways = " << ways << '\n';
    return 0;
}

CAB

CAB
CBA
ways = 2

next_permutation เดินไปข้างหน้าตามพจนานุกรมอย่างเดียว เริ่มจาก CAB จึงได้แค่ลำดับที่มาหลัง CAB คือ CBA แล้วก็หมด ลำดับ ABC ACB BAC BCA ที่มาก่อนหายไปทั้งหมด ทดสอบกับข้อมูลที่บังเอิญเรียงมาแล้วอย่าง ABC จะไม่เห็นบั๊กนี้

แบบที่ 4 lower_bound กับข้อมูลที่ยังไม่เรียง

ในโปรแกรม bounds ถ้าลบบรรทัดที่ 7 ซึ่งเรียง score ออก คอมไพล์ผ่านและรันได้ไม่มีอะไรเตือน แต่บนเครื่องที่เขียนเอกสารนี้ คำถาม x = 60 ได้

x = 60: lower 4, upper 6, equal 2, found 1

บอกว่ามี 60 สองตัว ทั้งที่มีสามตัว lower_bound กับ upper_bound ไม่ตรวจว่าข้อมูลเรียงหรือยัง มันแค่ทำงานแบบที่สมมติว่าเรียงแล้ว กับข้อมูลที่ไม่เรียง คำตอบอาจถูกบ้างผิดบ้างโดยไม่มีอะไรบอก

สรุป

  • reverse(v.begin(), v.end()) กลับลำดับในตัวเอง ใช้กับ string ได้ด้วย
  • max_element min_element คืนตำแหน่งของช่องแรกที่มากสุดหรือน้อยสุด ใส่ * ได้ค่า ลบ begin() ได้ index
  • accumulate(v.begin(), v.end(), 0LL) รวมทุกช่อง ค่าเริ่มต้นกำหนดชนิดของผลรวม ใส่ 0 แล้วล้นได้
  • count(v.begin(), v.end(), x) นับช่องที่เท่ากับ x โดยไล่ทุกช่อง
  • ตัดค่าซ้ำด้วย sort แล้ว v.erase(unique(v.begin(), v.end()), v.end()) ขาดขั้นไหนก็ผิด
  • ไล่ทุกลำดับด้วย sort แล้ว do { ... } while (next_permutation(...));
  • กับข้อมูลที่เรียงแล้ว lower_bound ชี้ช่องแรกที่ ≥ x upper_bound ชี้ช่องแรกที่ > x ผลต่างคือจำนวนที่เท่ากับ x ไม่เจอได้ end() บทที่ 19 จะอธิบายข้างใน

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด