ฟังก์ชัน list::merge() ใน C++ STL

list::merge() คืออะไร?

รวม list สองอันที่ เรียงแล้ว (sorted) เข้าด้วยกันเป็น list เดียวที่ยังเรียงอยู่ ได้ผลลัพธ์ใน list ตัวแรก (list2 จะว่างเปล่าหลัง merge)

Syntax

list1.merge(list2);                    // merge แบบ default (operator<)
list1.merge(list2, comparator);        // merge พร้อม comparator

พารามิเตอร์

list2 - list ที่จะ merge เข้าไปใน list1
comparator - binary predicate คืน true ถ้า element ของ list1 ควรอยู่ก่อน list2

คืนค่า

void

ตัวอย่าง 1: Merge โดยไม่มี Comparator (ทั้งคู่เรียงแล้ว)

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

int main() {
    list<int> myList_1 = {2, 4, 6, 8};
    list<int> myList_2 = {1, 3, 5, 7};
    
    myList_2.merge(myList_1);  // myList_2 จะมีผลรวม, myList_1 ว่าง
    
    cout << "Lists after merging: ";
    for (auto i = myList_2.begin(); i != myList_2.end(); ++i)
        cout << *i << " ";
    return 0;
}

Output: Lists after merging: 1 2 3 4 5 6 7 8

ตัวอย่าง 2: Merge พร้อม Comparator

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

bool compare(int a, int b) {
    return a < b;  // เรียงน้อยไปมาก
}

int main() {
    list<int> myList_1 = {2, 4, 1};
    list<int> myList_2 = {7, 6, 5};
    
    myList_1.sort();  // 1 2 4
    myList_2.sort();  // 5 6 7
    
    myList_1.merge(myList_2);       // 1 2 4 5 6 7
    myList_2.push_back(3);          // myList_2 = {3}
    myList_1.merge(myList_2, compare); // merge อีกรอบ
    
    cout << "List Elements are: ";
    for (auto i = myList_1.begin(); i != myList_1.end(); ++i)
        cout << ' ' << *i;
    return 0;
}

Output: List Elements are: 1 2 3 4 5 6 7

ข้อสังเกตสำคัญ

ทั้งสอง list ต้อง เรียงแล้ว ก่อน merge (undefined behavior ถ้าไม่เรียง)
หลัง merge list2 จะว่างเปล่า (elements ถูกย้าย ไม่ได้ copy)
Stable: relative order ของ equivalent elements คงอยู่
Complexity: O(n+m)