Re: [問題] 在特定條件下，deque與vector的效能比較
想到一個有趣的東西
std::stack 其實是個包裝品，底下是包裝別的容器
有趣的是他底層預設的 container
template<
class T,
class Container = std::deque<T>
> class stack;
是時間複雜度常數項比較高的 std::deque
而不是常數項複雜度比較低的 std::vector
OK，stack 不需要 random access，所以不用 std::vector 好像也沒關係
但講到 stack，一般想到的底層應該都會是類似 linked list 的實作
可是 std::stack 底下用的也不是 std::list
原因在於 std::vector 每次需要長大的時候
需要重新重新配置記憶體，也需要拷貝本來容器裡面的元素
而 std::list 雖然不用拷貝本來容器裡面的元素
但是每 push 一個元素都要動態記憶體配置，就慢了
std::deque 既不用拷貝原有元素
動態記憶體配置也久久才需要一次，不錯不錯
雖然每 push 一個，再不需要成長的時候比 std::vector 慢 qq
好像太淺了，沒什麼分享到，大家應該都知道答案
--
To iterate is human, to recurse, divine. L. Peter Deutsch 嫩嫩迴圈 大大遞迴
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.185.95.121
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1457271067.A.1BF.html
→
03/06 21:53, , 1F
03/06 21:53, 1F
→
03/06 21:54, , 2F
03/06 21:54, 2F
→
03/06 21:54, , 3F
03/06 21:54, 3F
→
03/06 21:57, , 4F
03/06 21:57, 4F
→
03/06 22:02, , 5F
03/06 22:02, 5F
→
03/06 22:02, , 6F
03/06 22:02, 6F
→
03/06 22:03, , 7F
03/06 22:03, 7F
→
03/06 22:59, , 8F
03/06 22:59, 8F
→
03/06 23:19, , 9F
03/06 23:19, 9F
討論串 (同標題文章)