พึ่งเคยใช้งานครั้งแรกโปรดอ่านที่นี่! howtouse!
x
  • Register
หางานด้าน IT อยู่เหรอ?

forward_list เหมาะกับงานใด และมีข้อเสียอย่างไร

+2 votes
forward_list เป็น STL container ตัวใหม่ใน C++11 ซึ่งเท่าที่ทราบ มันสามารถแทรกและลบ element ได้ในเวลา O(1)

อยากทราบว่า forward_list นี้เหมาะกับงานแบบไหน และอะไรคือข้อเสียของมันครับ?
ถามเมื่อ Apr 16, 2012 in C/C++ โดย K. Chaowanawatee (565 คะแนน)
retagged Apr 16, 2012 โดย admin
   

2 Answers

0 votes
 
Best answer

ก่อนอื่นเลยอยากแนะนำให้รู้จักกับ linked list 2 แบบนี้ก่อนนะครับ

รายการโยงชั้นเดียว (singly linked list) หมายถึง รายการโยงที่เก็บตัวชี้ไปยังปมถัดไปเท่านั้น จะไม่มีปมชี้ไปปมก่อนหน้า กล่าวคือ จะรู้ว่าสมาชิกถัดจากตัวเองมีค่าเท่าใด แต่ไม่รู้สมาชิกตัวที่อยู่ก่อนหน้า
 
รายการโยงสองชั้น (doubly linked list) เป็นรายการโยงที่เก็บตัวชี้ทั้งตัวก่อนหน้าและตัวถัดไป ทำให้สะดวกต่อการค้นหา แต่เพิ่มความซับซ้อนในการเพิ่มลดข้อมูลเล็กน้อย
 
ซึ่ง std::list ที่เรารู้จักกันนั้น มีการ implement แบบ doubly linked list
ข้อดี - วนไล่ไปตามการเชื่อมโยงแบบย้อนกลับได้, ค้นหาข้อมูลตัวสุดท้ายได้เร็วเพราะมีปมทั้ง 2 ด้าน
ข้อเสีย - ใช้หน่วยความจำเยอะและทำงานช้าเนื่องจากโอเวอร์เฮดสูง
 
ส่วน std::forward_list นั้น มีการ implement แบบ singly linked list
ข้อดี - มีโอเวอร์เฮดน้อยทำให้ใช้หน่วยความจำน้อยกว่า list แบบปกติ
ข้อเสีย - วนไล่ไปตามการเชื่อมโยงของข้อมูลได้เพียงทิ้งทางเดียว(แบบไปข้างหน้า), หาข้อมูลตัวสุดท้ายได้ช้า
 
ส่วนประสิทธิภาพในการทำงานในการ insert, delete นั้นเป็น O(1) ด้วยกันทั้ง 2 แบบเพราะเป็นคุณสมบัติพื้นฐานของ linked list อยู่แล้ว
ประสิทธิภาพในการค้นหานั้นจะแตกต่างกันขึ้นอยู่กับลักษณะงานที่เราจะนำไปใช้งานนั่นเอง ต้องเลือกให้เหมาะสมกับงานที่จะนำไปใช้ด้วยนะครับ
 
ดังนั้นข้อดีข้อเสียและความสามารถในการทำงานก็จะเป็นไปตามรูปแบบของการเชื่อมโยงของข้อมูลตามรูปแบบที่มันถูก implement นั่นเอง
 
(ข้อมูลบางส่วนและรูปภาพ จาก th.wikipedia.org)
ตอบเมื่อ May 22, 2012 โดย HuaNaa (455 คะแนน)
selected Jul 1, 2012 โดย K. Chaowanawatee
+1 vote
มัน  implement link list ก็คิดว่าน่าจะใช้กับงานที่ link list ใช้เลยนะครับ มันน่าจะเอามาใช้แทนของเดิมหรือป่าวครับ?
ตอบเมื่อ Apr 17, 2012 โดย Thanabodee Charoenpi (666 คะแนน)
ตามที่ได้หาข้อมูลมาบ้างแล้ว พบว่ามันพัฒนาจากแนวคิดของ SGI::slist น่ะครับ คิดว่ามันคงเป็น linked list ที่ปรับปรุงอะไรบางอย่างแล้วแน่ๆ คิดว่าอาจจะเหมาะกับงานที่ต้องใช้โครงสร้างข้อมูลในลักษณะ linked list แต่ forward_list ทำประสิทธิภาพได้เหนือกว่า .... รึปล่าว?

Related questions

0 votes
0 คำตอบ
0 votes
0 คำตอบ
267 views ถามเมื่อ Jun 5, 2015 in C/C++ โดย ThE_cAt (102 คะแนน)
0 votes
1 คำตอบ
186 views ถามเมื่อ Oct 27, 2014 in C/C++ โดย nonnnn (104 คะแนน)
0 votes
0 คำตอบ
267 views ถามเมื่อ Sep 7, 2014 in C/C++ โดย kaakaa (102 คะแนน)
0 votes
0 คำตอบ
620 views ถามเมื่อ Nov 28, 2013 in C/C++ โดย Aonerayongzer Chiang (102 คะแนน)
...