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 อาจจะทำงานผิดพลาดได้ ต้องพิจารณาให้ดี

การใช้งานพื้นฐาน: container และ iterator

ในการใช้งานโครงสร้างข้อมูลใน STL เราจะต้องเลือก container ให้เหมาะสมกับงาน เพราะประสิทธิภาพในการทำงานและความสามารถก็จะแตกต่างกัน

โดยทั่วไปถ้าต้องการเก็บรายการที่ไม่ได้มีการสลับสับเปลี่ยนมาก เรานิยมใช้ vector เพราะว่าสามารถเข้าถึงข้อมูลแบบสุ่ม (random access) ได้เช่นเดียวกับอาร์เรย์ (และมีประสิทธิภาพทัดเทียมกัน) เราอาจจะคิดว่า vector เป็น array ที่สามารถสร้างได้โดยไม่ต้องระบุขนาดก็ได้ ในการแนะนำพื้นฐานนี้เราจะเริ่มจาก vector จากนั้นจะแนะนำ list ต่อไป

การประกาศและการเพิ่มข้อมูลเข้าที่ท้าย vector

จะใช้ vector อย่าลืม include header (เราใส่ using namespace std ไว้ด้วย ไม่เช่นนั้นต้องเรียก std::vector ตลอด)

#include <vector>

using namespace std;

เราสามารถประกาศตัวแปร a ที่เป็น vector ของ int ที่ไม่มีข้อมูลอะไรเลยได้ดังด้านล่าง

vector<int> a;

container แต่ละชนิดจะมีวิธีเพิ่มข้อมูลแตกต่างกัน สำหรับ vector นั้น เราสามารถเพิ่มข้อมูลเข้าไปที่ท้ายของ vector โดยสั่ง push_back ด้านล่างใส่ข้อมูล 0 - 99 ลงใน vector

for(int x=0; x<100; x++) {
  a.push_back(x);
}

เนื่องจาก vector สามารถใช้งานได้เหมือน array เราจึงสั่งเช่นด้านล่าง เพื่อพิมพ์ข้อมูลใน a ได้

cout << a[0] << a[20] << endl;