Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

ขอสวัสดี เพื่อน ๆ พี่ ๆ น้อง ๆ กับ Blog Entry แรก โดยผมเอง

เนื้อหาที่ผมจะเขียนส่วนใหญ่ คงจะไม่ได้สอนอะไรมากมาย แต่จะเน้นการนำไปใช้เฉพาะกิจเพื่อการเขียนโปรแกรมภาษา C/C++
ซึ่งจะสะดวกในการเขียนโปรแกรมแข่งขันมากขึ้นครับ

ผมก็ขอแทนตัวเองด้วยผมแล้วกันนะครับ หวังว่าผู้อ่านจะได้รับความรู้และเอาไปใช้ประโยชน์ได้บ้างนะครับ
หัวข้อแรกที่ผมจะเขียนเลยคือ

Standard Template Library

หรือที่ชาวบ้านอย่างเรา ๆ ติดปากว่า STL นั่นเอง
เริ่มต้นด้วยคำถามสิ้นคิด

STL คืออะไร

ผมก็ไม่รู้หรอกน่า เอาเป็นว่าพอใช้เป็นก็แล้วกัน (จะบ้าเรอะ)
เข้าเรื่องดีกว่า

STL คือ Library มาตรฐานของภาษา C++ (ภาษา C ใช้ไม่ได้นะ) ที่ใช้จัดการสร้าง แก้ไข เพิ่ม ลบ คูณ หาร โครงสร้างข้อมูลแบบพลวัต
(นั่น ยังกระแดะใช้คำว่า Dynamic เป็นภาษาไทยอีก)
ตัวอย่าง ประเภทโครงสร้างข้อมูลที่มีให้ใช้คือ

• list ก็คือ linked list นั่นเอง มีทั้งแบบ singly และ doubly ให้ใช้มากมาย
• queue ชื่อมัน Self-explanatory นะ
• stack ชื่อมัน Self-explanatory เหมือนกันแหละ
• deque Double ended queue หรือก็คือคิวแบบมีปลายสองด้าน
• vector เป็น random access คล้าย ๆ Array
• set อันนี้ไม่แน่ใจ แต่ผมเชื่อว่ามันเป็น AVL-tree นั่นแหละครับ (สิ่งมีชีวิตที่ทานแมวบอกว่า เค้า implement ด้วย red-black tree ครับ)
• map คล้าย ๆ กับ set แต่ดูเหมือนจะพิเศษตรงเรื่องของ key กับ value นั่นเอง
• hash_ ก็พวกคล้าย ๆ เดิมแต่ใช้ hash อิมพลิเมนท์แทน

พูดเกริ่น ๆ แล้วก็คือว่า มันคือโครงสร้างข้อมูลง่าย ๆ ที่เรารู้จักเป็น class ไว้ให้เราใช้อยู่แล้วครับ
เขาสร้างให้เราใช้ เราก็ใช้สิครับ ไม่เห็นต้องไปเขียนใหม่เองเลย
(อย่างไรก็ดี มันก็มีข้อควรระวัง ขอให้อ่านต่อไปก่อนนะครับ)

แนะนำการใช้งาน STL + ทำไมต้องใช้

เริ่มด้วยคำถาม “ทำไมต้องใช้ STL กันก่อนดีกว่า”
ว่ากันว่า นานมาแล้ว ในการแข่งขันรายการหนึ่ง (เหตุการณ์สมมติ)
มีเด็กชาย A นามสมมติ สามารถใช้สติปัญญาฉลาดเลิศล้ำของเขา
แก้ปัญหาโจทย์สำหรับ … แต่ปรากฏว่าเขาต้องเขียน AVL tree ด้วย
ผลปรากฏว่า เขาเสียเวลาส่วนใหญ่ไปกับการเขียนและดีบักโปรแกรม
สุดท้ายเขาก็เสียเวลาและไม่ได้คะแนนใด ๆ จากโจทย์ข้อนั้นไป

(เหมือนว่าเนื้อเรื่องมันสนุกอย่างนั้นแหละ)
ผู้อ่านคงจะเห็นความเศร้าจากการไม่ได้ใช้ STL แล้วนะครับ

เป็นเรื่องธรรมดา ถ้า STL เป็นของดีจริง แล้วทำไมไม่ใช้กันให้หมดเลยละ
เรื่องของ STL ก็มีข้อเสียของมันอยู่คือ

มันเป็น Library ที่เขียนมาให้รองรับการทำงานที่กว้าง แต่เราใช้งานเพียงนิดเดียว
แม้ว่าผู้พัฒนาจะเขียน Library มาค่อนข้าง optimize แล้ว แต่อย่าวางใจมากนักเพราะ ถ้าเราไม่เข้าใจการทำงานของมัน อาจทำให้โปรแกรมเรารันช้าโดยที่เราไม่รู้มาก่อน เช่น เวลา search ข้อมูลใน list จะใช้ O(n) เป็นต้น

ฉะนั้นคำแนะนำของผมก็คือ ควรจะเข้าใจหลักการทำงานของโครงสร้างข้อมูลพื้นฐานก่อน รวมทั้ง complexity ของแต่ละ operation ด้วย
และอาจลอง Implement โครงสร้างข้อมูลดูเองก่อน แล้วจึงหันมาใช้ STL กัน

เมื่อจะเริ่มศึกษา STL คู่มือที่ดีที่สุดคงจะเป็นของเว็บ SGI
ซึ่งมีคำอธิบายพร้ิอม แต่คงไม่เหมาะจะใช้เริ่มต้นเท่าไหร่นัก

คราวหน้าผมจะพูดถึงวิธีการใช้งาน STL อย่างเบื้องต้น พร้อมกับยกตัวอย่างการใช้งานให้เห็นภาพ
สุดท้ายมีคำพูดเกี่ยวกับ STL จะฝากทิ้งไว้คือ

มี STL เหมือนมีอาวุธอยู่ในมือ
อาวุธยิ่งใหญ่ ยิ่งหนัก ใช้ได้ผลดี แต่ตอนถือก็เหนื่อยตามไปด้วย

พบกันคราวหน้าครับ