[問題] vector與linked list

看板C_and_CPP作者 (夜夜米)時間15年前 (2009/10/26 14:42), 編輯推噓7(7推 0噓 13→)
留言20則, 13人參與, 最新討論串1/1
各位大大好 小弟有一個疑問在心中許久 但是尚未解惑 想問問各位前輩 在我的觀念中 對於一般的陣列 我們在宣告之初就必須把陣列大小決定 這是陣列最大的限制 可以晚一點決定大小的方法也不過就是宣告一個陣列指標 等決定大小的時候再來new他 但是new了之後其陣列大小也是死的 不能動態變更 所以這時候 C++程設老師會教我們用vector 這樣就可以方便的pop與push變數 不用怕大小寫死 資料結構的老師會教我們linked list 說這樣就可以動態的配置記憶體 也不會有大小不夠的問題 那問題就來了 既然vector與linked list都可以克服陣列大小的問題 linked list相對比vector複雜且難寫許多 而且取出特定值的時候還必須用迴圈慢慢跑 vector就可以直接抓出來 那都用vector就可以了啊 所以小弟的問題就是 linked List到底還有什麼其他用途 使linked list如此重要呢? 感謝各位前輩解惑QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.44.243.14
推
10/26 22:44, , 1F
學術探討用
10/26 22:44, 1F
推
10/26 22:49, , 2F
vector也不是這麼萬能 不夠用他還是會重配空間
10/26 22:49, 2F
→
10/26 22:51, , 3F
如果物件copy很貴的話linked list是你的首選
10/26 22:51, 3F
→
10/26 22:52, , 4F
不過大部分時間用vector還是比較方便 & 划算
10/26 22:52, 4F
→
10/26 22:53, , 5F
且各個operation的成本也不太一樣 視情況而用吧
10/26 22:53, 5F
→
10/26 22:55, , 6F
linked list 之後就是tree了阿 還沒有學到吧...
10/26 22:55, 6F
→
10/26 22:58, , 7F
資料結構上完應該就會知道了，各種操作的時間複雜度有差。
10/26 22:58, 7F
→
10/26 22:59, , 8F
考慮看看在第 N 個位置插入元素、取第 N 個元素的效率問題
10/26 22:59, 8F
→
10/26 23:03, , 9F
其實我已經上完資料結構了 我覺得tree算是指標應用
10/26 23:03, 9F
→
10/26 23:05, , 10F
如果把tree與圖也算linked list的一種 那我得到答案了
10/26 23:05, 10F
推
10/26 23:07, , 11F
原 PO 資料結構要重修
10/26 23:07, 11F
→
10/26 23:08, , 12F
我們資結很好過的 (茶
10/26 23:08, 12F
推
10/26 23:17, , 13F
linked list不是只有動態配置記憶體的優點而已
10/26 23:17, 13F
→
10/26 23:18, , 14F
你如果要大量在sequence前面插入物件呢?
10/26 23:18, 14F
→
10/26 23:19, , 15F
當資料需要大量的插入跟刪除 用vector就哭哭了
10/26 23:19, 15F
推
10/26 23:21, , 16F
而且STL除了vector也提供list, 說難寫實在是非戰之罪
10/26 23:21, 16F
→
10/26 23:22, , 17F
vector只是一個會幫你自動配置與搬家的array (吧)
10/26 23:22, 17F
推
10/27 00:16, , 18F
要比難寫 stl container最難寫的應該是用rb-tree的map..
10/27 00:16, 18F
→
10/27 11:17, , 19F
就像自己寫quick sort 跟 用qsort
10/27 11:17, 19F
推
10/29 05:37, , 20F
vector裡面大小不夠會Resize, 時間使用特別多
10/29 05:37, 20F
‣ 更多 yayarice 的文章
文章代碼(AID): #1AvRLJaB (C_and_CPP)