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 cplusplus ref

จะใช้ 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;

การใช้ iterator

ปกติถ้าเราต้องการวิ่งจากต้น container ไปยังท้าย container เราจะใช้ iterator begin() และ end() โดย begin จะระบุตำแหน่งข้อมูลตัวแรก ส่วน end จะระบุตำแหน่งที่ถัดจากข้อมูลตัวสุดท้าย (ไม่ใช่ข้อมูลตัวสุดท้าย) ดังแสดงในรูปด้านล่าง

สมมติว่า a มีข้อมูล 5 ตัว (a[0] - a[4])

 a: [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ ? ]
      ^                        ^
      |                         \--- end
       \--- begin

ดังนั้นโค้ดทั่วไปในการวิ่งไปใน vector จะเป็นดังนี้

while loop:

  vector<int>::iterator i = a.begin();
  while(i != a.end()) {
    // ... do something
    i++;
  }

for loop:

  for(vector<int>::iterator i = a.begin(); i != a.end(); i++) {
    // ... do something
  }

ถ้าเราใช้ C++11 (รุ่นเกือบใหม่) เราสามารถใช้ automatic type inference ได้ โดยแทนที่จะเขียน type ยาว ๆ เราจะใส่ว่า auto ดังด้านล่าง

  for(auto i = a.begin(); i != a.end(); i++) {
    // ... do something
  }

ตัวอย่างโค้ดที่หาข้อมูล y ในเวกเตอร์ a แสดงด้านล่าง

  for(auto i = a.begin(); i != a.end(); i++) {
    if(*i == y) {
      cout << "found it!" << endl;
      break;
    }
  }

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

begin และ end เป็น iterator ที่วิ่งไปด้านหน้า (forward) ในกรณีของ vector เรายังมี rbegin และ rend ถ้าเราต้องการวิ่งถอยหลังด้วย

รายการ (list)

อ่านเอกสารอ้างอิง ที่เว็บ cpluscplus ref

ในกรณีที่เราต้องการแทรกข้อมูลในรายการบ่อย ๆ เรานิยมใช้ list ใน STL โครงสร้างข้อมูล list จะเป็น doubly-linked list ทำให้สามารถใช้งานได้สะดวกมาก (เราสามารถลดค่า iterator ด้วย operator -- เพื่อวิ่งย้อนหลังได้)

ด้านล่างเป็นตัวอย่างการใช้ linked list แบบง่าย ๆ แสะแสดงการเลื่อน iterator ไปมา

#include <iostream>
#include <list>
using namespace std;
void printlist(list<int>& b)
{
  for(auto i = b.begin(); i != b.end(); i++) {
    cout << *i << " ";
  }
  cout << endl;
}

main()
{
  list<int> a;
  int x;
  
  while(true) { cin >> x; if(x == 0) { break; } a.push_back(x); }
  printlist(a);
  auto p = a.begin();
  p++;
  p++;
  *p = 10000;
  printlist(a);

  p--;
  *p = 100000;
  printlist(a);
  
  a.insert(p, -1000);
  printlist(a);
}

ด้านล่างเป็นตัวอย่างการเขียน โปรแกรมจะสุ่มเลขและเพิ่มใน list out ด้วยวิธีแบบเดียวกับ insertion sort

#include <iostream>
#include <list>

using namespace std;

main()
{
  list<int> out;
  
  for(int i = 0; i < 100; i++) {
    int x = rand();  // pick a random number
                     //   DON'T do this in real code, without using srand

    // หาตำแหน่งที่จะเพิ่ม (วิ่งไปในรายการจนกว่าจะเจอข้อมูลที่มากกว่าหรือเท่ากับ x
    auto li = out.begin();
    while((li != out.end()) && (*li < x)) {
      li++;
    }

    // เพิ่ม x ในรายการ **ด้านหน้า** li
    out.insert(li, x);
  }

  // พิมพ์ผลลัพธ์
  for(auto li = out.begin(); li != out.end(); li++) {
    cout << *li << endl;
  }
}

นอกจากฟังก์ชัน insert แล้ว list ยังรองรับ push_front, push_back, pop_front, pop_back อีกด้วย

ถ้าต้องการลบใช้ erase (ดูรายละเอียดใน reference)

ตัวอย่าง container อื่น ๆ ที่นิยมใช้

จะมาเพิ่มทีหลัง ตอนนี้ดูที่ ตัวอย่างจากหน้านี้ก่อน

algorithm มาตรฐาน

• ตัวอย่างการใช้ sort