17.2 deque และ list

stack ทำงานที่หัวเดียว queue เข้าทางหนึ่งออกอีกทาง แต่บางงานต้องเพิ่มและเอาออกได้ทั้งสองหัว เช่น ห้องฉุกเฉินในหน้า 14.5 ที่คนไข้หนักแซงไปหัวคิว และคนท้ายคิวกลับบ้านได้ งานแบบนี้ใช้ deque ซึ่งในบทที่ 14 ต้องเขียนเองด้วย circular queue พร้อมสูตร (head - 1 + capacity) % capacity ท้ายหน้ามี list ซึ่งคือ linked list สองทางแบบหน้า 14.3 ที่ C++ ทำไว้ให้

deque

deque มีทุกอย่างที่ stack กับ queue มี และมีมากกว่านั้นอีกสองเรื่อง คือเพิ่มลบได้ทั้งสองหัว และดูหรือแก้ช่องไหนก็ได้ด้วยวงเล็บเหลี่ยมเหมือน vector

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

int main()
{
    deque<int> d;
    d.push_back(20);
    d.push_back(30);
    d.push_front(10); // (1)!
    d.push_front(5);
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    cout << "d[2] = " << d[2] << '\n'; // (2)!
    d.pop_front();
    d.pop_back();
    d[0] = 15;
    cout << "size = " << d.size() << '\n';
    for (int i = 0; i < (int)d.size(); i++) { // (3)!
        if (i > 0) {
            cout << ' ';
        }
        cout << d[i];
    }
    cout << '\n';
    return 0;
}

1. เพิ่มที่หัว ตัวที่เพิ่มทีหลังอยู่หน้าสุด หลังบรรทัดนี้กับบรรทัดถัดไป deque คือ 5 10 20 30
2. ช่องที่ 2 นับจากหัว เริ่มนับจาก 0 เหมือนอาเรย์ ได้ 20
3. (int) แปลง size() เป็น int ก่อนเทียบกับ i แบบเดียวกับ vector ในหน้า 16.1 ถ้าไม่แปลงจะได้คำเตือน ดูในส่วนลองทำให้พัง

front = 5, back = 30
d[2] = 20
size = 2
15 20

หลัง pop หัวและท้าย เหลือ 10 20 แล้วเปลี่ยนช่อง 0 เป็น 15 ส่วนวนดูทุกตัวจะใช้ for (int x : d) แบบเดียวกับ vector ก็ได้

ความจริง stack กับ queue ในหน้าที่แล้วก็สร้างจาก deque ข้างในนี่เอง แค่ปิดคำสั่งที่ไม่ควรใช้ไว้ เช่น queue ไม่ให้ push ที่หัว คำถามคือ ถ้า deque ทำได้ทุกอย่าง ทำไมไม่ใช้ deque ตลอด คำตอบคือชื่อ container บอกคนอ่านโค้ดได้ทันทีว่างานนี้ใช้ของแบบไหน และ compiler ช่วยกันไม่ให้เผลอเรียกคำสั่งผิดฝั่ง

ห้องฉุกเฉินด้วย deque

โจทย์เดียวกับโปรแกรม deque ในหน้า 14.5 คนไข้ทั่วไป (N x) ต่อท้ายคิว คนไข้อาการหนัก (U x) ไปอยู่หัวคิว หมอเรียกคนหัวคิว (D) และคนท้ายคิวกลับบ้าน (L)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    deque<int> patients;
    for (int i = 0; i < q; i++) {
        char command;
        cin >> command;
        if (command == 'N' || command == 'U') {
            int patient;
            cin >> patient;
            if (command == 'N') {
                patients.push_back(patient);
            } else {
                patients.push_front(patient);
            }
        } else if (patients.empty()) {
            cout << "no patient\n";
        } else if (command == 'D') {
            cout << "doctor sees " << patients.front() << '\n';
            patients.pop_front();
        } else {
            cout << patients.back() << " goes home\n";
            patients.pop_back();
        }
    }
    return 0;
}

9
N 21
N 22
U 23
N 24
D
L
D
D
D

doctor sees 23
24 goes home
doctor sees 21
doctor sees 22
no patient

ผลเหมือนหน้า 14.5 ทุกบรรทัด โปรแกรมในบทที่ 14 ยาว 60 บรรทัด อันนี้ 31 บรรทัด ที่หายไปคืออาเรย์แสนช่อง ตัวแปร head tail count และฟังก์ชันสี่ตัวที่ต้องเขียนสูตรถอยหลังแบบวนกลับให้ถูก ซึ่งเป็นที่มาของบั๊กแบบที่ 3 ในหน้า 14.5

ทำไมไม่ใช้ vector

vector ก็มี v.insert(v.begin(), x) ที่แทรกไว้หน้าสุดได้ แต่ข้างใน vector คืออาเรย์ธรรมดา แทรกหน้าสุดจึงต้องเลื่อนทุกตัวไปทางขวาหนึ่งช่องแบบหน้า 5.5 ยิ่งมีของมากยิ่งช้า ส่วน deque เก็บของเป็นก้อนหลายก้อน มีที่ว่างเผื่อไว้ทั้งสองหัว เพิ่มที่หัวจึงไม่ต้องเลื่อนใคร ลองวัดให้ทั้งสองแบบเพิ่มของที่หัว n ครั้ง

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

int main()
{
    int n;
    cin >> n;
    clock_t start = clock();
    vector<int> v;
    for (int i = 0; i < n; i++) {
        v.insert(v.begin(), i);
    }
    clock_t middle = clock();
    deque<int> d;
    for (int i = 0; i < n; i++) {
        d.push_front(i);
    }
    clock_t end = clock();
    cout << v[0] << ' ' << d[0] << '\n';
    cout << fixed << setprecision(3);
    cout << "vector: " << (double)(middle - start) / CLOCKS_PER_SEC << " seconds\n";
    cout << "deque: " << (double)(end - middle) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

วัดบนเครื่องเดียวกับหน้า 17.1 รันแบบละ 5 ครั้ง ตารางเป็นค่ากลาง 0.000 แปลว่าน้อยกว่าที่ clock() วัดได้

n เพิ่ม 3 เท่า vector ช้าลงราว 10 เท่า โตตาม n กำลังสองแบบ sort ในหน้า 13.3 เพราะการแทรกครั้งที่ i ต้องเลื่อน i ตัว ส่วน deque แทบไม่ใช้เวลาเลย และ -O2 ก็ช่วย vector ไม่ได้ เพราะงานจริงคือการย้ายข้อมูลจำนวนมาก ไม่ใช่โค้ดที่เขียนไม่ดี หลักเลือกจึงง่าย ใช้แค่ท้ายใช้ vector ต้องใช้หัวด้วยใช้ deque

list แบบสั้น

list คือ doubly linked list แบบหน้า 14.3 ทุกตัวรู้จักตัวก่อนหน้าและตัวถัดไป จึงแทรกหรือลบตรงกลางได้โดยไม่ต้องเลื่อนใคร แลกกับการที่ ไม่มี l[i] อยากได้ตัวที่ i ต้องเดินจากหัวไปทีละตัว

การบอกตำแหน่งใน list ใช้ iterator แบบเดียวกับ v.begin() และ v.end() ที่ส่งให้ sort ในหน้า 16.3 line.begin() คือตำแหน่งของตัวแรก line.end() คือตำแหน่งถัดจากตัวสุดท้าย ถ้า it เป็น iterator แล้ว *it คือค่าตรงตำแหน่งนั้น

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

int main()
{
    list<int> line;
    for (int i = 1; i <= 5; i++) {
        line.push_back(i);
    }
    line.push_front(0);
    auto it = find(line.begin(), line.end(), 3); // (1)!
    cout << "found " << *it << '\n';
    line.insert(it, 9); // (2)!
    line.erase(it); // (3)!
    cout << "size = " << line.size() << '\n';
    bool first = true;
    for (int x : line) {
        if (!first) {
            cout << ' ';
        }
        cout << x;
        first = false;
    }
    cout << '\n';
    return 0;
}

1. find จาก algorithm เดินหาเลข 3 ตั้งแต่หัว ได้ iterator ที่ชี้ตัวนั้น การเดินหาใช้เวลาโตตามความยาวของ list
2. แทรก 9 ไว้หน้าตำแหน่ง it ใช้เวลาคงที่ ไม่ต้องเลื่อนใคร
3. ลบตัวที่ it ชี้ ใช้เวลาคงที่เหมือนกัน หลังลบแล้ว it ชี้ไปที่ที่ไม่มีอยู่แล้ว ห้ามใช้ต่อ

found 3
size = 6
0 1 2 9 4 5

list จะเร็วจริงก็ต่อเมื่อรู้ตำแหน่งอยู่แล้ว ไม่ต้องเดินหา ตัวอย่างคือโปรแกรม line-up ในหน้า 14.3 ที่นักเรียนออกจากแถว ย้ายไปหัวแถว หรือย้ายไปท้ายแถว ถ้าเก็บ iterator ของนักเรียนทุกคนไว้ในอาเรย์ ทุกคำสั่งก็ใช้เวลาคงที่

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    list<int> line;
    vector<list<int>::iterator> where(n + 1); // (1)!
    for (int i = 1; i <= n; i++) {
        where[i] = line.insert(line.end(), i); // (2)!
    }
    for (int i = 0; i < q; i++) {
        char command;
        int x;
        cin >> command >> x;
        line.erase(where[x]);
        if (command == 'F') {
            where[x] = line.insert(line.begin(), x);
        } else if (command == 'B') {
            where[x] = line.insert(line.end(), x);
        }
    }
    bool first = true;
    for (int x : line) {
        if (!first) {
            cout << ' ';
        }
        cout << x;
        first = false;
    }
    cout << '\n';
    return 0;
}

1. vector ของ iterator ชนิดเต็มของ iterator ของ list<int> เขียนว่า list<int>::iterator ช่อง where[x] จำว่านักเรียน x อยู่ตรงไหนในแถว
2. insert คืน iterator ของตัวที่เพิ่งแทรกมาให้ แทรกหน้า line.end() คือต่อท้าย

5 4
L 3
F 5
B 1
L 2

5 4 1

ผลตรงกับหน้า 14.3 โปรแกรมบทที่ 14 ยาว 43 บรรทัด อันนี้ 34 บรรทัด สั้นลงไม่มากเท่า deque เพราะต้องดูแล iterator เอง ในการแข่งขัน list ถูกใช้น้อยกว่า stack queue deque มาก คนแข่งส่วนใหญ่เขียน prev[] กับ next[] แบบหน้า 14.3 (ใน C++ ต้องเปลี่ยนชื่อเป็น prv กับ nxt เพราะชนกับชื่อใน std ตามหน้า 15.1) ซึ่งเข้าใจง่ายกว่าและไม่ต้องจำชนิดยาวๆ ให้รู้จัก list ไว้พออ่านโค้ดคนอื่นออก

ลองทำให้พัง

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

วงเล็บปีกกาหลัง = ใส่ค่าเริ่มต้นให้ deque ได้เหมือน vector

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

int main()
{
    deque<int> scores = {70, 85, 90};
    for (int i = 0; i < scores.size(); i++) {
        cout << scores[i] << '\n';
    }
    return 0;
}

70
85
90

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

คำเตือนเดียวกับ vector ในหน้า 16.1 ทุกตัวอักษร ต่างกันแค่ชื่อชนิด size() ของ container ทุกตัวในบทนี้เป็น unsigned เหมือนกันหมด และกับดัก size() - 1 ตอนว่างที่ได้ 18446744073709551615 ก็เกิดกับ deque ได้เหมือนกัน เลขนี้คือเลขเดียวกับที่ stack ว่างแล้วถูก pop ในแบบที่ 3 ของหน้า 17.1 นิสัยที่ปลอดภัยยังเป็นแบบเดิม คือแปลงเป็น (int)scores.size() ก่อนคำนวณหรือเปรียบเทียบทุกครั้ง แบบโปรแกรม deque-basics

แบบที่ 2 ดูช่องที่ไม่มี

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

int main()
{
    deque<int> scores = {70, 85, 90};
    cout << scores[3] << '\n';
    cout << scores[100] << '\n';
    return 0;
}

มีแค่ช่อง 0 ถึง 2 แต่คอมไพล์ผ่านโดยไม่มีคำเตือน บนเครื่องที่เขียนเอกสารนี้ รันสามครั้ง scores[3] ได้ 618 457 และ 555 ส่วน scores[100] ได้ 0 ทุกครั้ง ไม่มี error ไม่พัง แต่ค่าเปลี่ยนไปทุกครั้งที่รัน เป็นอาการเดียวกับอ่านเลยท้ายอาเรย์ในหน้า 5.5 วงเล็บเหลี่ยมของ deque และ vector ไม่ได้ตรวจขอบให้

แบบที่ 3 ใช้วงเล็บเหลี่ยมกับ list

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

int main()
{
    list<int> line = {1, 2, 3};
    cout << line[1] << '\n';
    return 0;
}

line.cpp:7:17: error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int')
    7 |     cout << line[1] << '\n';
      |                 ^

ข้อความแบบเดียวกับ stack ในหน้า 17.1 std::__cxx11::list คือชื่อเต็มที่ compiler ใช้เรียก list ข้างใน ถ้างานไหนต้องใช้ทั้งวงเล็บเหลี่ยมและเพิ่มที่หัว ให้ใช้ deque

สรุป

• deque เพิ่มลบได้ทั้งสองหัวด้วย push_front push_back pop_front pop_back และใช้ d[i] ได้ ทุกคำสั่งเป็น O(1)
• vector เพิ่มที่หัวต้องเลื่อนทุกตัว ช้าลงตาม n กำลังสอง ต้องใช้หัวด้วยให้ใช้ deque
• list แทรกลบตรงกลางได้ O(1) ถ้ามี iterator อยู่แล้ว แต่ไม่มี l[i] และการเดินหาช้า
• size() ไม่มีเครื่องหมาย แปลงเป็น (int) ก่อนเทียบหรือลบ
• วงเล็บเหลี่ยมไม่ตรวจขอบ ช่องที่ไม่มีได้ค่าขยะเงียบๆ