Re: [問題] 在特定條件下，deque與vector的效能比較

[yoco (眠月)]

想到一個有趣的東西

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
→ Caesar08: 既然不需要成長，你怎麼知道push比較慢呢？
→ Caesar08: deque與vector都有一個last(end)指向最後一個
→ Caesar08: 所以push的時候，都可以直接存取要放入的那一個
→ Caesar08: 然後我們就發現priority_queue的default是vector...
→ yoco: 對不起我的錯，剛剛腦袋不知道去哪了..
→ yoco: 剛剛想到 random access 比較慢，不知道為什麼接錯線
→ yoco: qriority queue 用 vector 倒是很合理，因為他需要 random a
→ Caesar08: ccess
→ pikachu2421: 這上面的接字XDD