ผลต่างระหว่างรุ่นของ "ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัส/map"

จาก วิกิตำรา
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzero (คุย | ส่วนร่วม)
หน้าที่ถูกสร้างด้วย '{{ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัส/แถบนำทา...'
 
Nullzero (คุย | ส่วนร่วม)
ไม่มีความย่อการแก้ไข
บรรทัดที่ 2: บรรทัดที่ 2:
'''map''' เป็น[[โครงสร้างข้อมูล]]แบบ [[:w:Associative array]] ข้อมูลหนึ่ง ๆ จะประกอบไปด้วยสองส่วนคือ ''คีย์'' และ ''ค่าข้อมูล'' ในการที่จะเข้าถึงค่าหนึ่ง ๆ สามารถกระทำได้ผ่านการระบุ key ดังนั้นจึงอาจมอง map เป็นแถวลำดับซึ่งไม่มีข้อจำกัดด้านพิสัยของดัชนีหรือชนิดข้อมูลของดัชนี
'''map''' เป็น[[โครงสร้างข้อมูล]]แบบ [[:w:Associative array]] ข้อมูลหนึ่ง ๆ จะประกอบไปด้วยสองส่วนคือ ''คีย์'' และ ''ค่าข้อมูล'' ในการที่จะเข้าถึงค่าหนึ่ง ๆ สามารถกระทำได้ผ่านการระบุ key ดังนั้นจึงอาจมอง map เป็นแถวลำดับซึ่งไม่มีข้อจำกัดด้านพิสัยของดัชนีหรือชนิดข้อมูลของดัชนี


map ของไลบรารีแม่แบบมาตรฐานนี้อิมพลีเมนต์โดยใช้[[:w:ต้นไม้แดงดำ]] ซึ่งจากการที่เก็บข้อมูลบนต้นไม้ค้นหาแบบทวิภาคจึงทำให้มีคุณสมบัติต่าง ๆ เพิ่มขึ้นมาจาก [[:w:Associative array]] ปกติ เช่น คุณสมบัติในการหา[[:w:ขอบเขตบน]]หรือ[[:w:ขอบเขตล่าง]]ผ่าน[[:w:การค้นหาแบบทวิภาค]]บนต้นไม้ อย่างไรก็ตาม เนื่องจากการเก็บข้อมูลบนต้นไม้แดงดำต้องอาศัยการเปรียบเทียบของคีย์จึงจำเป็นที่จะต้องระบุฟังก์ชัน/คลาสสในการเปรียบเทียบให้ด้วย (หากไม่ระบุจะใช้ [[../less/]] เป็นคลาสเปรียบเทียบโดยอัตโนมัติ)
map ของไลบรารีแม่แบบมาตรฐานนี้อิมพลีเมนต์โดยใช้[[:w:ต้นไม้แดงดำ]] ซึ่งจากการที่เก็บข้อมูลบนต้นไม้ค้นหาแบบทวิภาคจึงทำให้มีคุณสมบัติต่าง ๆ เพิ่มขึ้นมาจาก [[:w:Associative array]] ปกติ เช่น คุณสมบัติในการหาค่าที่มากกว่าสมาชิกดังกล่าว ผ่าน[[:w:การค้นหาแบบทวิภาค]]บนต้นไม้ อย่างไรก็ตาม เนื่องจากการเก็บข้อมูลบนต้นไม้แดงดำต้องอาศัยการเปรียบเทียบของคีย์จึงจำเป็นที่จะต้องระบุฟังก์ชัน/คลาสสในการเปรียบเทียบให้ด้วย (หากไม่ระบุจะใช้ [[../less/]] เป็นคลาสเปรียบเทียบโดยอัตโนมัติ)


== การใช้งานและประกาศตัวแปร ==
== การใช้งานและประกาศตัวแปร ==
ก่อนอื่นให้ทำการ <code>#include <map></code>
ก่อนอื่นให้ทำการ <code>#include <map></code>


สมมุติถ้าต้องการจะประกาศตัวแปร <code>var</code> โดยคีย์มีชนิดข้อมูลเป็น <code>datatype1</code> และค่าข้อมูลมีชนิดข้อมูลเป็น <code>datatype2</code> สามารถเขียนโค้ดได้ดังนี้: <code>map <datatype1,datatype2> var;</code>
สมมุติถ้าต้องการจะประกาศตัวแปร <code>var</code> โดยคีย์มีชนิดข้อมูลเป็น <code>type1</code> และค่าข้อมูลมีชนิดข้อมูลเป็น <code>type2</code> สามารถเขียนโค้ดได้ดังนี้: <code>map <datatype1,datatype2> var;</code>


== method ==
== method ==
=== push ===
=== lower_bound ===

{{STLdata
{{STLdata
| เป็นการเพิ่มข้อมูลชนิด <code>T</code> ลงทางด้านปลายของ stack ใช้เวลา <math>O(1)</math>
| <!-- คำอธิบาย --> ใช้เวลา <math>O(\log n)</math>
| มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง stack
| มีเพียงตัวเดียวคือข้อมูลชนิด <code>type1</code>
| iterator ที่ชี้ไปยังโหนดที่มีบนต้นไม้แดงดำ
|
| void push(T);
| iter lower_bound(type1);
}}
}}

=== upper_bound ===
{{โครงส่วน}}

=== erase ===
{{โครงส่วน}}

== operator ==
=== [] ===
{{โครงส่วน}}
=== ++ ===
{{โครงส่วน}}
=== -- ===
{{โครงส่วน}}

รุ่นแก้ไขเมื่อ 18:40, 21 กุมภาพันธ์ 2556

ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัส
map


map เป็นโครงสร้างข้อมูลแบบ w:Associative array ข้อมูลหนึ่ง ๆ จะประกอบไปด้วยสองส่วนคือ คีย์ และ ค่าข้อมูล ในการที่จะเข้าถึงค่าหนึ่ง ๆ สามารถกระทำได้ผ่านการระบุ key ดังนั้นจึงอาจมอง map เป็นแถวลำดับซึ่งไม่มีข้อจำกัดด้านพิสัยของดัชนีหรือชนิดข้อมูลของดัชนี

map ของไลบรารีแม่แบบมาตรฐานนี้อิมพลีเมนต์โดยใช้w:ต้นไม้แดงดำ ซึ่งจากการที่เก็บข้อมูลบนต้นไม้ค้นหาแบบทวิภาคจึงทำให้มีคุณสมบัติต่าง ๆ เพิ่มขึ้นมาจาก w:Associative array ปกติ เช่น คุณสมบัติในการหาค่าที่มากกว่าสมาชิกดังกล่าว ผ่านw:การค้นหาแบบทวิภาคบนต้นไม้ อย่างไรก็ตาม เนื่องจากการเก็บข้อมูลบนต้นไม้แดงดำต้องอาศัยการเปรียบเทียบของคีย์จึงจำเป็นที่จะต้องระบุฟังก์ชัน/คลาสสในการเปรียบเทียบให้ด้วย (หากไม่ระบุจะใช้ less เป็นคลาสเปรียบเทียบโดยอัตโนมัติ)

การใช้งานและประกาศตัวแปร

ก่อนอื่นให้ทำการ #include <map>

สมมุติถ้าต้องการจะประกาศตัวแปร var โดยคีย์มีชนิดข้อมูลเป็น type1 และค่าข้อมูลมีชนิดข้อมูลเป็น type2 สามารถเขียนโค้ดได้ดังนี้: map <datatype1,datatype2> var;

method

lower_bound

คำอธิบาย ใช้เวลา
พารามิเตอร์ มีเพียงตัวเดียวคือข้อมูลชนิด type1
คืนค่า iterator ที่ชี้ไปยังโหนดที่มีบนต้นไม้แดงดำ
ฟังก์ชั่นต้นแบบ iter lower_bound(type1);

ข้อควรระวัง ไม่มี

upper_bound

erase

operator

[]

++

--