動態變化的std ::通過路口

Question

設置我寫的函數

void update(set<int> &dynamic, const set<int> &compare){ 
    set<int> res_set; 
    set_intersection(dynamic.begin(), dynamic.end(), compare.begin(), compare.end(), 
     std::inserter(res_set, res_set.end())); 
    dynamic = res_set; 
} 

不過，我想知道如果這實際上使得res_set第一，然後將其分配給dynamic複印件（這將是低效），還是隻分配已存儲在內存中的變量dynamic到res_set（這是有效的，我想要的）。我不想複製一個集合，裏面可能有非常多的元素，從而使整個程序變慢。

我的目標是能夠有效地改變dynamic，我通過傳遞許多不同的set<int> s轉換compare（這將會對搜索樹更有效的修剪路徑）調用該函數。

有沒有辦法做到這一點？

謝謝。

Answer 1

並行地對兩組中的每一組進行迭代器迭代，即在一個單一的for循環中，該循環在每個循環中遞增一個或兩個迭代器。每當您注意到dynamic中的當前指向的項目（我將調用d）小於compare中的當前指向的項目（我將其稱爲c）時，它只能表示d不存在於compare - - 那麼您應該從dynamic中刪除它，並將迭代器推進到dynamic。每當你注意到d > c時，你應該提前迭代器爲compare（在這種情況下，你不要執行任何刪除操作，因爲你想不改變compare）。每當d == c時，推進這兩個迭代器。這是可行的，因爲std::set<T>的迭代器按遞增順序訪問元素 - 你基本上執行列表合併。

只要你之前獲得迭代器的未來價值進行刪除，這是安全的，因爲C++標準保證從std::set<T>刪除項目不能違反對其他迭代器。它的效率很高：如果dynamic和compare的長度分別爲m和n，則需要花費時間O（m + n）。