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

[googled (15357)]

各位前輩好，小弟有一個問題想請教各位高手

假設說今天我程式跑一個迴圈後，會取得多筆字串，

並且存在容器(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
推 BlazarArc: 用 condition.find(currentData) 紀錄 index 再依據
→ uranusjr: 把 conditionVector 裡面的東西做成 map
請問一下，conditionVector裡面塞map，可是我該怎麼去依照map做排序@@?

不知道是不是我理解錯了，請問妳意思是說意思是說

conditionVector.push_back(map(1,"111"))

conditionVector.push_back(map(2,"10"))
...
conditionVector.push_back(map(5,"200"))

這樣嗎@@?


→ BlazarArc: index搜尋? 至少複雜度不是走訪整個condition
→ BlazarArc: 依據 index sort, 說錯
→ BlazarArc: condition 可用 std::unordered_set
不好意思，小弟比較愚笨一點

unordered_set的find找到之後，要怎麼記錄該筆資料在set的index?

unordered_set不是不會有順序嗎@@?

謝謝各位
※ 編輯: googled (203.64.91.83), 01/13/2015 15:27:25
推 CaptainH: 不是應該用set就好了嗎
→ uranusjr: 顛倒, dataVector 裡面的東西要是 key, 然後用找出來的
→ uranusjr: 值排序（應該要寫個 compare function 會比較方便）
這方法聽起來好好用，感謝你

可是還想在請問一下

condition是："111"、"10"、"50"、"30"、"200"

dataVec是："10"、"111"、"200"、"50"、"800"

那這樣找出來的順序會是：2、1、5、3

我目前想到的方法是用swap不斷的交換dataVec的值

而像"800"這種不存在condition的在特別去處理，

想請問前輩的方法也差不多是這樣嗎@@?

我怕我的實作技巧反而沒辦法充分的加快速度

謝謝妳

推 BlazarArc: 我想錯了 腦袋不清楚 XD
→ BlazarArc: condition有order要求 不能用 unordered set
仔細看也發現我文章也打錯了，已經修正好了

我存成unordered_set的不是conditionVec，而是dataVec，哈哈XD

→ BlazarArc: 可以用map 保持排序 而用map的value當index, 2樓正解
也很謝謝你唷
※ 編輯: googled (203.64.91.83), 01/13/2015 15:54:57
推 BlazarArc: 不過你data的內容會重複出現嗎? 要求似乎只要標記那些
→ BlazarArc: condition 有出現在 data 裡面?
→ BlazarArc: 如果是這樣那 value type bool 用來標記就好
一筆data不會有重複的資料。

請問value type bool用來標記是什麼意思@@?

用bool來標記哪些data有出現在condition嗎?

謝謝

※ 編輯: googled (203.64.91.83), 01/13/2015 16:04:12
推 BlazarArc: 對啊 沒必要再排序吧?
→ uranusjr: 用內建的 sort 然後自己給一個 Compare object
→ uranusjr: http://www.cplusplus.com/reference/algorithm/sort/
→ uranusjr: 不存在的就給他一個超大值丟到最後面, 最後再一次清掉
→ uranusjr: 不過如果不存在的值會很多, 自己寫一個 sort 可能更好
→ googled: 成功做出來了，速度的確提升不少，感謝各位前輩