[討論] list 高效實作

[EdisonX (卡卡獸)]

雖然和 algorithm 比較相關 , 但比較相知道的是 std::list ..

目前我所知道的是 std::list 是用 double-list ,

而一般人所知在 head 部份做頻繁的 插入 / 刪除 效率比 vector 來得快 ,

tail 部份做操作也不慢，不過不管怎麼想就是有很多優化空間，

拿常見的 new / delete node 來講 , 不管怎麼想就是累計到一定程度後，

再一次刪除 / 新增即可，省下頻繁的記憶體操作時間

(嗯 ... 這樣好像和 vector 的配置策略相似了 .. )

我想一般學校只是為了 了解原理 ，所以沒再講後面這部份，

想知道 std::list 是不是有我所說上述的概念 ?

或是有 open source 有用到之類的？

還是我所提的跟垃圾沒兩樣，實務上沒人會這麼搞？

謝謝各位的討論指教。

~
~

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」
                                          < Kuso 星爺語錄 >

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.165.160
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1409986154.A.4CB.html
→ azureblaze: 只是頭尾用deque就好了，通常有做這種處理
→ azureblaze: list真正的優勢是中間插入刪除
→ azureblaze: 如果作這種處理會很容易浪費大量空間
推 GoalBased: 你應該找符合你狀況的"容器"(list array ...)
推 suhorng: new, delete 那個交給 allocator ?
→ EdisonX: @azureblaze,想到後來其實就是效率和空間在折磨,打入死結
→ EdisonX: @GlobalBased:是的,有時覺得挺難挑的,用 vector<list>,
→ EdisonX: list<vector>, 都沒 vector 來得快 @@
→ EdisonX: @suhorng : 這也是我目前想到最簡單的方式 @@
推 GoalBased: 效能這個東西，等你發生效能問題再來處理就好了
→ GoalBased: 除非你做的東西本來就是為了效能..應該是這樣說的吧
→ GoalBased: 不然0.01秒和0.02秒 效能差了一倍 但可能對你系統
→ GoalBased: 可能根本沒有影響
→ jackace: 這種東西跟你的data有密切關係 不能以一論之
→ azureblaze: 有種說法是插頭尾插中間有懷疑的時候用vector就對了
→ azureblaze: vector在cache上的效能通常會壓勝其他缺點
→ azureblaze: 真的發現有問題要改也不會太麻煩
→ EdisonX: @Goal~:我知道你說的,不過有時"部份功能"就是這麼要求Orz
→ EdisonX: @azureblaze:這結論真重要了,謝謝 :D
→ Killercat: 可能跟原文無關，我猜原po其實是project碰到scaling
→ Killercat: issue? 我會建議直接profile/unit test催下去了
→ Killercat: gap用猜的按我的經驗是10猜9錯 命中率超驚人的 :P
推 fanntone: 大量的插入或刪除等操作就要考慮用hash去實作
→ fanntone: 如果你的資料量到達上百萬的list的話就要考慮
→ EdisonX: @Killercat : 我沒聽過 scaling issue, 跪求翻譯 @@
→ Killercat: 噢就是因為大量資料造成的效能問題的意思
→ EdisonX: @Killercat : 是你說的沒錯, 資料量真不小...