[問題] list vector之間的取捨
學校作業有一個題目裡面會遇到一個問題
就是要在一個已經排序過的數列
在插入一個數值進去 插入之後還是排序好的
我想大概是二分搜尋之後插入就好 所以整體應該會O(logN)這樣
我一開始用Vector寫一寫 寫到後面發現 Vector的insert是O(N)
就換成List來寫
可是寫一寫發現 我用STL::upper_bound很慢
(我以為是O(LogN))
可是查了一下 因為iterator的關係 他會退化成O(N)
想想好像也對 List好像沒辦法像Vector一樣直接跳到我想要的位置
(要從頭一個一個走....
想請問這個問題有解嗎??
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.66.45
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1397068306.A.53B.html
推
04/10 02:37, , 1F
04/10 02:37, 1F
推
04/10 02:38, , 2F
04/10 02:38, 2F
→
04/10 02:42, , 3F
04/10 02:42, 3F
→
04/10 02:43, , 4F
04/10 02:43, 4F
→
04/10 02:43, , 5F
04/10 02:43, 5F
推
04/10 02:44, , 6F
04/10 02:44, 6F
→
04/10 02:45, , 7F
04/10 02:45, 7F
→
04/10 02:46, , 8F
04/10 02:46, 8F
→
04/10 03:34, , 9F
04/10 03:34, 9F
推
04/10 10:50, , 10F
04/10 10:50, 10F
→
04/10 10:53, , 11F
04/10 10:53, 11F
→
04/10 10:53, , 12F
04/10 10:53, 12F
→
04/10 11:36, , 13F
04/10 11:36, 13F
推
04/10 12:20, , 14F
04/10 12:20, 14F
→
04/10 12:21, , 15F
04/10 12:21, 15F
→
04/10 12:22, , 16F
04/10 12:22, 16F
→
04/10 12:22, , 17F
04/10 12:22, 17F
→
04/10 12:23, , 18F
04/10 12:23, 18F
→
04/10 12:23, , 19F
04/10 12:23, 19F
→
04/10 12:24, , 20F
04/10 12:24, 20F
→
04/10 12:25, , 21F
04/10 12:25, 21F
推
04/10 13:32, , 22F
04/10 13:32, 22F
→
04/10 13:33, , 23F
04/10 13:33, 23F
→
04/13 10:52, , 24F
04/13 10:52, 24F