雖然和 algorithm 比較相關 , 但比較相知道的是 std::list ..
目前我所知道的是 std::list 是用 double-list ,
而一般人所知在 head 部份做頻繁的 插入 / 刪除 效率比 vector 來得快 ,
tail 部份做操作也不慢，不過不管怎麼想就是有很多優化空間，
拿常見的 new / delete node 來講 , 不管怎麼想就是累計到一定程度後，
再一次刪除 / 新增即可，省下頻繁的記憶體操作時間
(嗯 ... 這樣好像和 vector 的配置策略相似了 .. )
我想一般學校只是為了 了解原理 ，所以沒再講後面這部份，
想知道 std::list 是不是有我所說上述的概念 ?
或是有 open source 有用到之類的？
還是我所提的跟垃圾沒兩樣，實務上沒人會這麼搞？
謝謝各位的討論指教。
~
~

只是頭尾用deque就好了，通常有做這種處理list真正的優勢是中間插入刪除如果作這種處理會很容易浪費大量空間

你應該找符合你狀況的"容器"(list array ...)

new, delete 那個交給 allocator ?

@azureblaze,想到後來其實就是效率和空間在折磨,打入死結@GlobalBased:是的,有時覺得挺難挑的,用 vector<list>,list<vector>, 都沒 vector 來得快 @@@suhorng : 這也是我目前想到最簡單的方式 @@

效能這個東西，等你發生效能問題再來處理就好了除非你做的東西本來就是為了效能..應該是這樣說的吧不然0.01秒和0.02秒 效能差了一倍 但可能對你系統可能根本沒有影響

這種東西跟你的data有密切關係 不能以一論之

有種說法是插頭尾插中間有懷疑的時候用vector就對了vector在cache上的效能通常會壓勝其他缺點真的發現有問題要改也不會太麻煩

@Goal~:我知道你說的,不過有時"部份功能"就是這麼要求Orz@azureblaze:這結論真重要了,謝謝 :D

可能跟原文無關，我猜原po其實是project碰到scalingissue? 我會建議直接profile/unit test催下去了gap用猜的按我的經驗是10猜9錯 命中率超驚人的 :P

大量的插入或刪除等操作就要考慮用hash去實作如果你的資料量到達上百萬的list的話就要考慮

@Killercat : 我沒聽過 scaling issue, 跪求翻譯 @@

噢就是因為大量資料造成的效能問題的意思

@Killercat : 是你說的沒錯, 資料量真不小...