Re: [問題] 在STL容器中增加元素的方法

看板C_and_CPP (C/C++)作者holymars時間16年前 (2009/09/10 11:55)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/3 (看更多)

※ 引述《yoco315 (眠月)》之銘言： : ※ 引述《holymars ()》之銘言： : : 有個STL容器 : : std::list<T> my_list; : : 要在容器最後面新增一個元素的時侯，下面兩種方法哪一種比較有效率呢.. : : 1. : : T temp; : : // 對temp的內容操作.. : : my_list.push_back(temp); : : 2. : : my_list.resize(my_list.size() + 1); : : T& temp = my_list.back(); : : // 對temp的內容操作.. : : 之前一直習慣的寫法都是1. : : 但是2.的作法好像少呼叫一次copy constructor : : 有人對這兩種作法的效率問題作過實際的測試嗎 @ @? : 直覺 2 完全佔不到便宜， : 因為 resize 的瞬間你就要呼叫一個預設建構子， : 不過還是看一下 VC++ 2008 Express 附的實作版本好了…… : void resize(size_type _Newsize) : { // determine new length, padding with _Ty() elements as needed : resize(_Newsize, _Ty()); : } : void resize(size_type _Newsize, _Ty _Val) : { // determine new length, padding with _Val elements as needed : if (size() < _Newsize) : _Insert_n(end(), _Newsize - size(), _Val); : else if (_Newsize < size()) : erase(begin() + _Newsize, end()); : } : 首先，resize 會呼叫一次預設建構子， : 然後，會一兩次條件判斷，第二次不可能發生，所以忽略。 : 接著會進行一次 insert_n，這裡頭有個迴圈，貴鬆鬆， : 雖然我們知道只會插一個，但是迴圈還是得跑，有迴圈就要破壞 pipeline 了， : 看了原始碼就知道所謂的 resize 最後該花的錢（建構子）還是得花， : 考慮最佳化以後也許一些多餘的複製成本省掉可以打平， : 但是那個條件判斷跟那個迴圈你還是要開銷…… : 結果蠻明顯的……真的要花時間測嗎 XD？？？剛剛把STL container在VC8的實作碼看了一遍發現不同容器的作法不太一樣以std::vector來說的話 push_back()和resize()　實作都是用_Insert_n 差別在push_back()第二個參數是傳(size_type)1 vector的_Insert_n底層是fill()，最底層是用memset作的其實沒有呼叫過copy constructor std::list就像上面說的那樣 resize()多了一個迴圈去呼叫多次的_Insert push_back() 直接去呼叫_Insert _Insert的裡面是_BuyNode，最底層是一個copy constructor 雖然reference上說resize()如果大於目前size() 空的位置會使用default constructor來建立物件但VC8的實作其實是像上述那樣XD 所以原本的問題變成是 1. T temp; temp.operate(); container.push_back(temp); 2. container.push_back(T()); T& temp = container.back(); temp.operate(); 從實作碼來看這兩者跑的code是一樣的差別在於default constructor和copy constructor被呼叫的時機不一樣 1.是先呼叫default ctor->對物件作操作->呼叫copy ctor 2.是呼叫default ctor->呼叫copy ctor->對物件作操作對std::vector這個用memset取代掉copy ctor的容器來說兩者應該是沒差的對std::list這種實際呼叫了copy ctor的容器來說除非最佳化能把2.的前兩個步驟合併成一個或者你自己定義了一個奇怪的ctor作有條件的copy 不然兩者要跑的code還是一樣多.. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.15.163