แผนการเรียน
/

C++ Standard Template Library (STL)
อาวุธลับของนักโปรแกรมเชิงแข่งขัน

วันที่ 3 ช่วงเช้า: โครงสร้างข้อมูลพื้นฐาน (Sequential Containers)

สิ่งที่จะเรียนรู้ในส่วนที่ 1

1
ภาพรวมของ STL และการประยุกต์ใช้ในการแข่งขัน
2
std::vector: อาเรย์ที่ยืดหยุ่นและทรงพลัง
3
Stack, Queue และ Priority Queue

Standard Template Library (STL)

"STL คือคลังโปรแกรมมาตรฐานของ C++ ที่รวบรวม โครงสร้างข้อมูล และ อัลกอริทึม ที่ผ่านการปรับแต่งประสิทธิภาพมาอย่างดีเยี่ยม"

  • ประหยัดเวลาในการเขียนโค้ดพื้นฐานเอง
  • ลดโอกาสเกิดข้อผิดพลาด (Bug) ในการจัดการหน่วยความจำ

3 เสาหลักของ STL

Containers

ใช้สำหรับเก็บข้อมูล (เช่น vector, set, map)

Iterators

ตัวชี้ตำแหน่งเพื่อเข้าถึงข้อมูลใน Container

Algorithms

ฟังก์ชันสำเร็จรูป (เช่น sort, binary_search)

The "Magic" Header

#include <bits/stdc++.h>
  • รวมไลบรารีมาตรฐานทุกตัวไว้ในคำสั่งเดียว
  • ช่วยให้ไม่ต้องจำชื่อ Header ของแต่ละ Container
  • ข้อระวัง: ใช้สำหรับการแข่งขันเท่านั้น ไม่แนะนำในงานโปรดักชันเพราะคอมไพล์ช้า

std::vector

"อาเรย์ที่มีความยืดหยุ่น สามารถปรับขนาดได้เองระหว่างการทำงาน"

จุดเด่น

  • • เข้าถึงข้อมูลทุกตำแหน่งใน \(O(1)\)
  • • เพิ่มข้อมูลต่อท้ายใน Amortized \(O(1)\)
  • • จัดการหน่วยความจำให้อัตโนมัติ

ข้อจำกัด

การเพิ่มหรือลบข้อมูลตรงกลางทำได้ช้า (\(O(N)\)) เพราะต้องขยับข้อมูลตัวอื่น

Vector Declaration

vector<int> v; // สร้างเวกเตอร์ว่าง
vector<int> v(5, 0); // ขนาด 5 ตัว เริ่มต้นด้วยเลข 0
vector<int> v = {1, 2, 3, 4, 5}; // C++11 initializer list

"เราต้องระบุประเภทข้อมูลภายในเครื่องหมาย < > เสมอ"

Basic Operations

push_back(x) เพิ่มค่า x ต่อท้ายเวกเตอร์
pop_back() ลบค่าตัวสุดท้ายทิ้ง
size() คืนค่าจำนวนสมาชิกปัจจุบัน
empty() เช็คว่าเวกเตอร์ว่างหรือไม่ (true/false)

Accessing Elements

cout << v << endl; // ตัวแรก (เริ่มที่ 0)
cout << v.back() << endl; // ตัวสุดท้าย

ข้อควรระวัง!

การเรียก v[i] ที่อยู่นอกเหนือช่วงที่มีอยู่ จะทำให้เกิดพฤติกรรมที่ไม่คาดคิด (Undefined Behavior)

Range-based For Loop

วิธีที่สั้นและปลอดภัยที่สุดในการเข้าถึงข้อมูลทุกตัวในเวกเตอร์

for (auto x : v) {
  cout << x << "\n";
}

Keyword auto จะช่วยเดาประเภทข้อมูลในเวกเตอร์ให้เราโดยอัตโนมัติ

เมื่อไหร่ควรใช้ Vector?

Vector (แนะนำ)

- ไม่รู้จำนวนข้อมูลล่วงหน้า
- ต้องการส่งเวกเตอร์ไปในฟังก์ชันได้ง่าย
- ต้องการใช้ฟังก์ชัน v.clear() เพื่อใช้ซ้ำ

Static Array

- รู้ขนาดที่แน่นอนและข้อมูลใหญ่มาก (เช่น 10^7)
- ทำงานเร็วกว่านิดหน่อยเนื่องจากไม่มี overhead
- ประกาศแบบ Global เพื่อกัน Stack Overflow

std::stack

LIFO Concept

"Last-In First-Out: สิ่งที่เข้าทีหลังสุด จะได้ออกก่อนเสมอ"

นึกถึงการวาง "จาน" ที่วางทับซ้อนกันอยู่

การทำงานของ Stack

push(x): เพิ่มข้อมูลที่หัวแถว
pop(): ลบข้อมูลที่หัวแถวทิ้ง
top(): ดูข้อมูลที่หัวแถว

Time Complexity

\[O(1)\]

ทุกการดำเนินการทำงานด้วยความเร็วคงที่

Stack Implementation

#include <stack>
stack<int> s;
s.push(3); s.push(2); s.push(5);

cout << s.top(); // ผลลัพธ์: 5
s.pop();
cout << s.top(); // ผลลัพธ์: 2

std::queue

FIFO Concept

"First-In First-Out: สิ่งที่เข้ามาก่อน จะได้ออกไปก่อน"

นึกถึงการ "เข้าแถว" ซื้อของในชีวิตจริง

Queue Operations

push(x): เพิ่มข้อมูลที่ท้ายแถว
pop(): ลบข้อมูลที่หน้าแถวทิ้ง
front(): ดูข้อมูลตัวหน้าสุด

Time Complexity

\(O(1)\)

มีประสิทธิภาพเท่ากับ Stack

Queue Implementation

#include <queue>
queue<int> q;
q.push(1); q.push(2); q.push(3);

cout << q.front(); // ผลลัพธ์: 1
q.pop();
cout << q.front(); // ผลลัพธ์: 2

Priority Queue

"เหมือน Queue แต่สมาชิกที่ถูกดึงออกมาจะเป็นตัวที่มี ความสำคัญ (ค่า) สูงสุด เสมอ"

ชื่อเล่นใน CP

มักเรียกว่า "Heap"

Default

เป็น Max-Heap (เอาค่ามากสุดขึ้นก่อน)

Time Complexity Analysis

push / pop

\[O(\log N)\]

top

\[O(1)\]

การทำงานเบื้องหลังคือ Binary Heap

Max-Heap Example

priority_queue<int> pq;
pq.push(3); pq.push(10); pq.push(5);

cout << pq.top(); // ผลลัพธ์: 10
pq.pop();
cout << pq.top(); // ผลลัพธ์: 5

Customizing Priority

หากต้องการดึง ค่าน้อยที่สุด ออกมาก่อน ต้องประกาศแบบนี้:

priority_queue<int, vector<int>, greater<int>> pq;

"พบบ่อยมากใน Dijkstra's Algorithm และ Prim's Algorithm"

Complexity Summary Table

Container Insert (Average) Access
Vector\(O(1)\) amortized \(O(1)\)
Stack / Queue\(O(1)\) \(O(1)\) (เฉพาะตัวหัว/ท้าย)
Priority Queue\(O(\log N)\) \(O(1)\) (เฉพาะค่าสูงสุด)

Decision Tree

1. ต้องการหาข้อมูลตามตำแหน่ง Index?

\(\rightarrow\) ใช้ std::vector

2. ต้องการดึงค่าที่เพิ่งใส่เข้าไปล่าสุด?

\(\rightarrow\) ใช้ std::stack

3. ต้องการจัดการข้อมูลตามลำดับก่อน-หลัง?

\(\rightarrow\) ใช้ std::queue

Test Your Understanding

ถ้าข้อมูลมีขนาด 1,000,000 ตัว การเรียกใช้ pq.push() จะใช้การเปรียบเทียบข้อมูลสูงสุดกี่ครั้ง?

~1,000,000 ครั้ง
~20 ครั้ง
~1 ครั้ง

คำใบ้: \(\log_2(10^6) \approx 20\)

Code Optimization: Typedef

ลดความยาวของโค้ดเมื่อใช้ Container ที่ซับซ้อน

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

vi v = {1, 2, 3}; // สั้นลงมาก!

"ช่วยประหยัดเวลาพิมพ์ได้มหาศาลในการแข่งขัน"

Up Next...

เหนือกว่า Sequential Containers คือ...

Associative Containers

เจาะลึก std::set และ std::map เพื่อการค้นหาใน \(O(\log N)\)

พัก 15 นาที ก่อนเข้าสู่ส่วนที่ 2 ครับ!

Iterators และ STL II
การจัดการข้อมูลขั้นสูงด้วย Tree และ Hash

วันที่ 3 ช่วงเช้า (ต่อ): เจาะลึก Iterator และ Associative Containers

หัวข้อในส่วนนี้

1
Iterators: ตัวชี้ตำแหน่งสากลสำหรับทุกโครงสร้างข้อมูล
2
std::set & std::multiset: การเก็บข้อมูลแบบเรียงลำดับ
3
std::map & Unordered Containers: พจนานุกรมความเร็วสูง

รู้จักกับ Iterator

"Iterator คือวัตถุที่ทำหน้าที่ 'ชี้ตำแหน่ง' ของสมาชิกในโครงสร้างข้อมูล "

  • ใช้เพื่อเข้าถึงข้อมูลใน Container ที่ไม่ได้เก็บแบบอาเรย์ปกติ (เช่น set)
  • มีพฤติกรรมคล้าย Pointer ในภาษา C

begin() และ end()

{ 3, 4, 6, 8, 12, 13, 14, 17 }
↑                      ↑
s.begin()             s.end()

s.begin()

ชี้ที่ สมาชิกตัวแรก ของ Container

s.end()

ชี้ที่ ตำแหน่งถัดจากตัวสุดท้าย (ว่างเปล่า)

Iterator Syntax

// แบบยาว (ไม่นิยม)
vector<int>::iterator it = v.begin();

// แบบสั้นด้วย auto (แนะนำ)
auto it = v.begin();
cout << *it; // ใช้ * เพื่อดึงค่าที่ชี้อยู่

Moving Iterators

it++ หรือ ++it เลื่อนไปสมาชิกถัดไป
it-- หรือ --it ถอยกลับไปสมาชิกก่อนหน้า
it + n กระโดดไป n ตำแหน่ง (ใช้ได้กับ vector เท่านั้น)

std::set

โครงสร้างข้อมูลที่เก็บสมาชิกแบบ เรียงลำดับ (Sorted) และ ไม่มีตัวซ้ำ (Unique)

คุณสมบัติสำคัญ

  • • สมาชิกทุกตัวต้องแตกต่างกัน (Distinct)
  • • แทรก/ลบ/ค้นหา ในเวลา \(O(\log N)\)
  • • ภายในคือ Balanced Binary Search Tree (Red-Black Tree)

Set Operations

set<int> s;
s.insert(3); s.insert(2); s.insert(5);
s.insert(5); // จะไม่มีอะไรเกิดขึ้นเพราะ 5 มีอยู่แล้ว

cout << s.count(3); // 1 (มีค่าอยู่)
s.erase(3); // ลบค่า 3 ออก

Iterating through a Set

ข้อมูลจะถูกพิมพ์ออกมาแบบ เรียงจากน้อยไปมาก เสมอ

for (auto x : s) {
  cout << x << "\n";
}

"หมายเหตุ: set ไม่สามารถใช้ [index] เข้าถึงข้อมูลได้เหมือน vector "

find(x) Member Function

auto it = s.find(x);
if (it == s.end()) {
  // x ไม่ได้อยู่ในเซต
}

การใช้ s.find(x) เร็วกว่า std::find(begin, end, x) มากเพราะใช้โครงสร้างต้นไม้ช่วยค้นหา (\(O(\log N)\) vs \(O(N)\))

Binary Search in Set

lower_bound(x)

ชี้ที่ตัวแรกที่มีค่า \(\ge x\)

upper_bound(x)

ชี้ที่ตัวแรกที่มีค่า \(> x\)

หากไม่มีตัวที่เข้าเงื่อนไข ทั้งคู่จะคืนค่าเป็น s.end()

std::multiset

"เหมือน set ทุกอย่าง แต่สามารถมีค่าที่ ซ้ำกันได้ "

multiset<int> ms;
ms.insert(5); ms.insert(5); ms.insert(5);
cout << ms.count(5); // ผลลัพธ์: 3

Multiset Erase Caution!

s.erase(5)

จะลบเลข 5 "ทุกตัว" ทิ้งไป

s.erase(s.find(5))

จะลบเลข 5 เพียง "ตัวเดียว" (ตัวที่ iterator ชี้)

std::map

"อาเรย์แบบทั่วไปที่ใช้ข้อมูลอะไรก็ได้เป็น Index (Key) เพื่อเก็บข้อมูล (Value) "

ภายในเป็น Balanced BST เหมือน set

  • เก็บข้อมูลเป็นคู่ pair<Key, Value>
  • Key ต้องไม่ซ้ำกัน และจะถูก เรียงลำดับ เสมอ
  • Time Complexity: \(O(\log N)\)

Map Usage

map<string, int> m;
m["banana"] = 4;
m["apple"] = 10;

cout << m["banana"] << endl; // 4
cout << m["orange"] << endl; // 0 (สร้างให้อัตโนมัติถ้าไม่มี!)

"ระวัง: การเรียก m[key] ที่ไม่มีอยู่จริง จะทำให้ map จองที่และใส่ค่า default ให้ทันที"

Iterating with Pairs

เมื่อวนลูป สมาชิกแต่ละตัวจะเป็น pair:

for (auto x : m) {
  cout << x.first << " " << x.second << endl;
}
x.first คือ Key
x.second คือ Value

std::unordered_map / set

"ทำงานด้วย Hash Table แทนที่จะเป็น Tree "

ข้อดี

เร็วมาก! ค่าเฉลี่ยคือ \(O(1)\)

ข้อเสีย

ข้อมูลไม่เรียงลำดับ และ Worst-case อาจเป็น \(O(N)\)

STL Complexity Table

Container Data Structure Time Complexity
Set / MapRed-Black Tree\(O(\log N)\)
Unordered Set/MapHash Table\(O(1)\) (Avg)
Priority QueueHeap\(O(\log N)\)
VectorDynamic Array\(O(1)\) amortized

Which Data Structure?

1. ต้องการความเร็วในการค้นหา \(O(1)\) และไม่สนลำดับ?

\(\rightarrow\) ใช้ unordered_set / map

2. ต้องการข้อมูลที่เรียงลำดับตลอดเวลา?

\(\rightarrow\) ใช้ set / map

3. ต้องการรับสมาชิกที่มีค่าซ้ำกันได้และเรียงลำดับ?

\(\rightarrow\) ใช้ multiset

Utilities: pair & tuple

std::pair

เก็บข้อมูล 2 ตัว (มักเป็น Key, Value)

pair<int, string> p = {1, "hi"};

std::tuple

เก็บข้อมูลกี่ตัวก็ได้ (C++11+)

tuple<int, int, int> t = {1, 2, 5};

"STL Sort สามารถเรียงลำดับ pair/tuple ได้ทันทีโดยเปรียบเทียบจากตัวแรกไปตัวหลัง "

std::sort

vector<int> v = {4, 2, 5, 3, 1};
sort(v.begin(), v.end());
// v จะกลายเป็น {1, 2, 3, 4, 5}
ความซับซ้อน: \(O(N \log N)\)

Ready-to-use Algorithms

reverse(begin, end)
random_shuffle(begin, end)
next_permutation(begin, end)
max_element(begin, end)

ทุกตัวรับพารามิเตอร์เป็น Iterator ช่วง [begin, end)

next_permutation Pattern

sort(v.begin(), v.end()); // ต้องเรียงลำดับก่อนเสมอ
do {
  // ประมวลผลแต่ละวิธีเรียงสับเปลี่ยน
} while (next_permutation(v.begin(), v.end()));

มีประโยชน์มากในโจทย์ Complete Search ที่ต้องลองทุกรูปแบบการสลับ

Competitive Tip!

"ระวังการแก้ไข Container (เช่น push_back หรือ insert) ขณะที่ยังมี Iterator ชี้อยู่"

การขยายขนาดของ vector อาจทำให้ memory ถูกย้ายตำแหน่ง
ซึ่งจะทำให้ Iterator ตัวเดิม "เสียไป" (Invalidated) และโปรแกรมอาจแครชได้

Test Your Knowledge

หากต้องการลบเลข 5 เพียง 1 ตัวออกจาก multiset s จะต้องใช้คำสั่งใด?

s.erase(5)
s.erase(s.find(5))