ไลบรารีแม่แบบมาตรฐาน

จากวิกิพีเดีย สารานุกรมเสรี

ไลบรารีแม่แบบมาตรฐาน (อังกฤษ: Standard Template Library / STL) เป็นไลบรารีของภาษาซีพลัสพลัส ประกอบไปด้วยคลาสของขั้นตอนวิธี คอนเทนเนอร์ (โครงสร้างข้อมูลและชนิดข้อมูล) ฟังก์เตอร์ และ ตัววนซ้ำ[1] ไลบรารีแม่แบบมาตรฐานของ ISO C++ ได้อ้างอิงตามไลบรารีแม่แบบมาตรฐานของ Silicon Graphics (SGI)[ต้องการอ้างอิง]

ส่วนประกอบ[แก้]

คอนเทนเนอร์[แก้]

คอนเทนเนอร์ คือโครงสร้างข้อมูลและชนิดข้อมูล ประกอบไปด้วยรายการลำดับ ได้แก่ vector deque list คอนเทนเนอร์แบบจับคู่ ได้แก่ set multiset map multimap คอนเทนเนอร์ดัดแปลงได้แก่ priority_queue queue stack และคอนเทนเนอร์ประเภทอื่นๆ

คอนเทนเนอร์ ชื่อภาษาอังกฤษ รายละเอียด
คอนเทนเนอร์อย่างง่าย
aคู่อันดับ pair คู่อันดับ เป็นคอนเทนเนอร์อย่างง่าย เป็นคู่อันดับของวัตถุซึ่งเรียกว่า first และ second คู่อันดับสามารถกำหนดค่า คัดลอกค่า และเปรียบเทียบได้ คอนเทนเนอร์คู่อันดับนี้มีลักษณะคล้ายคู่อันดับในคณิตศาสตร์ สำหรับคอนเทนเนอร์ map และ hash_map (รายละเอียดอยู่ด้านล่าง) ข้อมูลแต่ละตัวจะเป็นคู่อันดับ โดยที่ first เป็นคีย์ ส่วน second เป็นข้อมูล
รายการลำดับ
เวกเตอร์ vector เป็นแถวลำดับที่สามารถปรับขนาดได้ มีความสามารถการเข้าถึงโดยสุ่ม เหมือนอาเรย์ทั่วไป แต่สามารถปรับขนาดได้เมื่อมีการเพิ่มหรือลดข้อมูล โดยทั่วไป เวกเตอร์ จะทำการจองพื้นที่มากกว่าข้อมูลที่มีอยู่ เมื่อมีการเพิ่มข้อมูลจนเต็ม เวกเตอร์ก็จะทำการของพื้นที่เพิ่มเป็น 2 เท่าของพื้นที่เดิม การกระทำเช่นนี้เมื่อถัวเฉลี่ยออกมาแล้วจะได้ว่าการเพิ่ม/ลดข้อมูลในแต่ละครั้งทางปลายด้านหลัง ใช้เวลาคงตัว (ส่วนการเพิ่ม/ลบข้อมูล ณ ตำแหน่งใดๆใช้เวลาแปรผันตามจำนวนข้อมูล)

สำหรับ เวกเตอร์ ของชนิดข้อมูลแบบบูล จะมีการปรับแต่งให้ใช้เนื้อที่เพียงแค่ 1 บิตต่อสมาชิก 1 ตัวเท่านั้น

รายการโยง list เป็นรายการโยง 2 ทาง สมาชิกแต่ละตัวไม่ได้มีพื้นที่ในหน่วยความจำติดกันเหมือนกับอาเรย์ มีประสิทธิภาพตรงกันข้ามกับอาเรย์ กล่าวคือ การเข้าถึงข้อมูลใช้เวลาแปรผันตามจำนวนข้อมูล แต่การเพิ่ม/ลบข้อมูล ณ ตำแหน่งใดๆใช้เวลาคงตัว
แถวคอยสองหน้า deque เหมือนรายการโยง สามารถเข้าถึงข้อมูลและเพิ่ม / ลบข้อมูลที่ปลายทั้งด้านหน้าและด้านหลังได้ภายในเวลาคงตัว
คอนเทนเนอร์ดัดแปลง
แถวคอย queue เป็นคอนเทนเนอร์ที่มีลักษณะแบบ เข้าก่อนออกก่อน สามารถเพิ่มข้อมูลทางด้านหลัง และนำข้อมูลออกทางด้านหน้า
แถวคอยลำดับความสำคัญ priority_queue เป็นแถวคอยซึ่งมีการเรียงโดยอัตโนมัติ ข้อมูลที่สำคัญที่สุดจะอยู่บนสุดและจะถูกนำเอาออกเป็นอันดับแรก
กองซ้อน stack เป็นคอนเทนเนอร์แบบเข้าทีหลังออกก่อน สามารถเพิ่มข้อมูลทางด้านหลัง และนำข้อมูลออกทางด้านหลังด้วยเช่นกัน
คอนเทนเนอร์แบบจับคู่
เซต set เป็นคอนเทนเนอร์ชนิดหนึ่งที่สมาชิกห้ามซ้ำกัน มีความสามารถเหมือนเซต กล่าวคือสามารถยูเนียน อินเตอร์เซกชัน หาผลต่าง หาผลต่างสมมาตร และทดสอบการเป็นสมาชิกได้ โดยปกติจะอิมพลีเมนต์เซตด้วยต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ ดังนั้นจึงจำเป็นที่ข้อมูลจะต้องสามารถถูกเปรียบเทียบได้ (ด้วยโอเปอเรเตอร์ < หรือการกำหนดฟังก์ชันเปรียบเทียบ) นอกจากนี้ข้อมูลยังต้องมีลักษณะ strict weak ordering ไม่เช่นนั้นอาจทำให้เกิดข้อผิดพลาดขึ้นได้
มัลติเซต multiset เหมือนเซต แต่สมาชิกมีข้อมูลซ้ำกันได้
แมพ map เป็นแถวลำดับแบบจับคู่ ซึ่งสามารถจับคู่จากคีย์ไปยังข้อมูลได้ ดังนั้นคีย์จึงห้ามซ้ำกัน ข้อมูลจะถูกเก็บเป็นคู่อันดับโดยที่ first เป็นคีย์ ส่วน second เป็นข้อมูล เช่นเดียวกับเซต แมพอิมพลีเมนต์โดยใช้ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ ดังนั้นจึงจำเป็นที่ข้อมูลจะต้องสามารถถูกเปรียบเทียบได้ (ด้วยตัวดำเนินการ < หรือการกำหนดฟังก์ชันเปรียบเทียบ) นอกจากนี้ข้อมูลยังต้องมีลักษณะ strict weak ordering ไม่เช่นนั้นอาจทำให้เกิดข้อผิดพลาดขึ้นได้
มัลติแมพ multimap เหมือนแมพ แต่มีคีย์ซ้ำกันได้
แฮชเซต
แฮชมัลติเซต
แฮชแมพ
แฮชมัลติแมพ
hash_set
hash_multiset
hash_map
hash_multimap
คล้ายเซต มัลติเซต แมพ มัลติแมพ แต่การอิมพลีเมนต์กลับใช้ตารางแฮชแทนต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ ซึ่งในตารางแฮช คีย์จะไม่เรียง และไม่จำเป็นต้องมีตัวดำเนินการเพื่อเปรียบเทียบข้อมูลด้วย แต่ต้องการฟังก์ชันแฮชแทน ข้อได้เปรียบของการใช้ตารางแฮชแทนคือสามารถเข้าถึงข้อมูลโดยคาดหวังให้ใช้เวลาคงที่ได้ คอนเทนเนอร์เหล่านี้ไม่ได้รวมอยู่ในมาตรฐานภาษาซีพลัสพลัส แต่อยู่ในแม่แบบมาตรฐานของ SGI สำหรับ C++11 ซึ่งจะเป็นมาตรฐานภาษาซีพลัสพลัสรุ่นใหม่มีการใช้ unordered_set, unordered_multiset, unordered_map และ unordered_multimap แทนแฮชเซต, แฮชมัลติเซต, แฮชแมพ และแฮชมัลติแมพ ตามลำดับ
คอนเทนเนอร์ประเภทอื่นๆ
บิตเซต bitset รอการเพิ่มข้อมูล
valarray valarray รอการเพิ่มข้อมูล


ตัววนซ้ำ[แก้]


ขั้นตอนวิธี[แก้]


ฟังก์เตอร์[แก้]


ประวัติ[แก้]


อ้างอิง[แก้]

  1. Holzner, Steven (2001). C++ : Black Book. Scottsdale, Ariz.: Coriolis Group. p. 648. ISBN 1-57610-777-9. "The STL is made up of containers, iterators, function objects, and algorithms" 

แหล่งข้อมูลอื่น[แก้]

Wikibooks
วิกิตำรา มีคู่มือ ตำรา หรือวิธีการเกี่ยวกับ:
ไลบรารีแม่แบบมาตรฐาน