Psl/stl intro

หน้านี้เป็นส่วนหนึ่งของวิชา Problem solving lab

หน้านี้จะอธิบายการใช้งาน Standard Template Library แบบคร่าว ๆ ไลบรารีดังกล่าวจะประกอบไปด้วยโครงสร้างข้อมูลและอัลกอริทึมพื้นฐาน รวมไปถึงฟังก์ชันเบ็ดเตล็ดต่าง ๆ

ด้านล่างเป็นลิงก์สำหรับอ่านรายละเอียดและใช้อ้างอิงเกี่ยวกับ STL

• Reference ที่ cplusplus.com
• เอกสารที่ geeksforgeeks

แรงบันดาลใจของรูปแบบ container และ iterator

การออกแบบ "interface" หรือรูปแบบการใช้งานของ STL พยายามจะล้อกับการใช้งาน array โดยผ่านทาง pointer ซึ่งเป็นรูปแบบที่ใช้ประจำในภาษา C (นิยมเรียกว่า iterator pattern) พิจารณาตัวอย่างเปรียบเทียบด้านล่าง

ด้านล่างเป็นโค้ดที่ใช้ array

  int a[100];
  int x = 0;
  
  int* i = a;
  while(i != (a+100)) {
    *i = x;
    cout << *i;
    i++;
  }

ลองเปรียบเทียบกับโค้ดที่ใช้ vector

  vector<int> a(100);
  int x = 0;

  vector<int>::iterator i = a.begin();
  while(i != a.end()) {
    *i = x;
    cout << *i;
    i++;
  }

ความแตกต่างในการใช้งานมีแค่การเรียก a.begin() กับ a (แทนตัวชี้ไปยังข้อมูลตัวแรก) และ a.end() แทน a+100 (แทนตัวชี้ไปยังข้อมูลที่ เลย ตัวสุดท้ายไปหนึ่งตำแหน่ง)

เรานิยมเรียกโครงสร้างข้อมูลว่า container ส่วนตัวแปร i ที่มี type เป็น vector<int>::iterator นั้นจะเรียกว่า iterator หรือตัววิ่งนั่นเอง

เราจะแนะนำการใช้งาน template เล็กน้อย จากนั้นในส่วนถัด ๆ ไปเราจะพิจารณาการใช้งาน container และ iterator

Template

ในภาษา C++ เรามีวิธีการเขียนอัลกอริทึมและโครงสร้างข้อมูลให้ทำงานได้กับข้อมูลหลายรูปแบบ (เรียกรวม ๆ ว่า generic programming) โดยการเขียนเป็น template โดยโค้ดของ template จะถูกแปลงเป็นโค้ดจริง ๆ เมื่อมีการเรียกใช้งาน

ยกตัวอย่างเช่น ฟังก์ชัน sum ด้านล่างเขียนให้ใช้ได้กับข้อมูลประเภทอะไรก็ได้ (ที่เมื่อแทนเข้าไปใน T แล้วคอมไพล์ผ่าน)

template <class T>
T sum(T a, T b)
{
  return a + b;
}

main()
{
  cout << sum(10,20) << endl;
  cout << sum(10.5,20.4) << endl;
}

หรือด้านล่างเป็นการประกาศ ListNode<T> ให้ใช้กับข้อมูลประเภทอะไรก็ได้

template <class T>
struct ListNode {
  T val;
  ListNode<T>* next;
};

ในการใช้งาน STL นั้น เราไม่จำเป็นต้องเขียน template เป็นก็ได้ ขอให้ทราบไว้ว่าชื่อ type ในวงเล็บ < > ท้ายชื่อ container คือชนิดข้อมูลที่ต้องการเก็บหรือชนิดข้อมูลที่ใช้เป็นกุญแจเท่านั้นก็เพียงพอ

หมายเหตุ: โดยทั่วไปแล้ว STL จะใช้ข้อมูลที่เป็น value type ในการเก็บเป็นหลัก ถ้าเราใช้ pointer อาจจะทำงานผิดพลาดได้ ต้องพิจารณาให้ดี