[問題] 自定義排序的規則

看板C_and_CPP作者 (15357)時間10年前發表 (2015/01/13 06:11), 10年前編輯推噓5(5015)
留言20則, 4人參與, 最新討論串1/1
各位前輩好,小弟有一個問題想請教各位高手 假設說今天我程式跑一個迴圈後,會取得多筆字串, 並且存在容器(vector、list皆可)裡,例如存到conditionVector 假設取得的字串是:"111"、"10"、"50"、"30"、"200" 接著程式就要去讀取data,例如讀近來的資料存到dataVector 假設讀近來的資料是:"10"、"111"、"200"、"50"、"800" 我想請問的是, 有什麼方法可以快速且有效率去依照conditionVector的順序來排序 而conditionVector沒有的string就捨去 例如dataVector排序好後會變成"111"、"10"、"50"、"200" 我目前的方法是 vector<string> sortVector for(auto conIter: conditionVector) for(auto dataIter: dataVector) if( conIter == dataIter ){ sortVector.push_back(dataIter); break; } 這方法雖然可行,可是效率極差@@ 因為我conditionVector跟dataVector也許會有幾千、幾萬筆 本來想說把dataVector改存成unsorted_set,用find的方式來加速收尋 雖然有比較快,可是insert跟find的部分卻花了太多時間 所以想請教各位高手能否指導一下小弟是否有更快速的方法 感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.64.91.83 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1421129513.A.1BE.html

01/13 14:28, , 1F
用 condition.find(currentData) 紀錄 index 再依據
01/13 14:28, 1F

01/13 14:28, , 2F
把 conditionVector 裡面的東西做成 map
01/13 14:28, 2F
請問一下,conditionVector裡面塞map,可是我該怎麼去依照map做排序@@? 不知道是不是我理解錯了,請問妳意思是說意思是說 conditionVector.push_back(map(1,"111")) conditionVector.push_back(map(2,"10")) ... conditionVector.push_back(map(5,"200")) 這樣嗎@@?

01/13 14:29, , 3F
index搜尋? 至少複雜度不是走訪整個condition
01/13 14:29, 3F

01/13 14:29, , 4F
依據 index sort, 說錯
01/13 14:29, 4F

01/13 14:29, , 5F
condition 可用 std::unordered_set
01/13 14:29, 5F
不好意思,小弟比較愚笨一點 unordered_set的find找到之後,要怎麼記錄該筆資料在set的index? unordered_set不是不會有順序嗎@@? 謝謝各位 ※ 編輯: googled (203.64.91.83), 01/13/2015 15:27:25

01/13 15:27, , 6F
不是應該用set就好了嗎
01/13 15:27, 6F

01/13 15:32, , 7F
顛倒, dataVector 裡面的東西要是 key, 然後用找出來的
01/13 15:32, 7F

01/13 15:33, , 8F
值排序(應該要寫個 compare function 會比較方便)
01/13 15:33, 8F
這方法聽起來好好用,感謝你 可是還想在請問一下 condition是:"111"、"10"、"50"、"30"、"200" dataVec是:"10"、"111"、"200"、"50"、"800" 那這樣找出來的順序會是:2、1、5、3 我目前想到的方法是用swap不斷的交換dataVec的值 而像"800"這種不存在condition的在特別去處理, 想請問前輩的方法也差不多是這樣嗎@@? 我怕我的實作技巧反而沒辦法充分的加快速度 謝謝妳

01/13 15:33, , 9F
我想錯了 腦袋不清楚 XD
01/13 15:33, 9F

01/13 15:33, , 10F
condition有order要求 不能用 unordered set
01/13 15:33, 10F
仔細看也發現我文章也打錯了,已經修正好了 我存成unordered_set的不是conditionVec,而是dataVec,哈哈XD

01/13 15:35, , 11F
可以用map 保持排序 而用map的value當index, 2樓正解
01/13 15:35, 11F
也很謝謝你唷 ※ 編輯: googled (203.64.91.83), 01/13/2015 15:54:57

01/13 15:42, , 12F
不過你data的內容會重複出現嗎? 要求似乎只要標記那些
01/13 15:42, 12F

01/13 15:42, , 13F
condition 有出現在 data 裡面?
01/13 15:42, 13F

01/13 15:43, , 14F
如果是這樣那 value type bool 用來標記就好
01/13 15:43, 14F
一筆data不會有重複的資料。 請問value type bool用來標記是什麼意思@@? 用bool來標記哪些data有出現在condition嗎? 謝謝 ※ 編輯: googled (203.64.91.83), 01/13/2015 16:04:12

01/13 16:06, , 15F
對啊 沒必要再排序吧?
01/13 16:06, 15F

01/13 16:06, , 16F
用內建的 sort 然後自己給一個 Compare object
01/13 16:06, 16F

01/13 16:07, , 18F
不存在的就給他一個超大值丟到最後面, 最後再一次清掉
01/13 16:07, 18F

01/13 16:10, , 19F
不過如果不存在的值會很多, 自己寫一個 sort 可能更好
01/13 16:10, 19F

01/15 01:09, , 20F
成功做出來了,速度的確提升不少,感謝各位前輩
01/15 01:09, 20F
文章代碼(AID): #1KjBSf6- (C_and_CPP)