刪除從所述第二組包含不迭代

我有兩組對第一組元素的元素（我不能使用C++ 11）刪除從所述第二組包含不迭代

std::set<std::pair<int,int> > first; 
std::set<std::pair<int,int> > second;

和我需要從它們在第一組的所有元素中刪除第二組（如果第一個包含元素從第二個刪除）。我可以通過遍歷第二組來完成此操作，如果第一個元素包含相同的元素擦除，但是我想知道是否有辦法在沒有迭代的情況下執行此操作？

來源

2013-03-23 Damir

如果我理解正確，基本上你想計算第一和第二的差異。有一個<algorithm>功能。

std::set<std::pair<int, int>> result; 
std::set_difference(first.begin(), first.end(), second.begin(), second.end(), inserter(result, result.end()));

來源

2013-03-23 18:06:18

這實際上並沒有從第一組中刪除元素，但我認爲它是一樣的好。 – Oswald 2013-03-23 18:11:22

@Oswald：好吧，你總是可以在後面交換（第一個，結果）;） – 2013-03-23 18:48:57

我不知道有沒有辦法做到這一點不迭代。

不。在內部，集合是平衡的二叉樹 - 如果不迭代結構，就無法對它們進行操作。（我假設你對實現的效率感興趣，而不是代碼的便利性，所以我故意忽略必須在內部進行迭代的庫例程）。

集合被排序，所以你可以對每個元素進行迭代，隨着你去掉（所以＃操作是集合大小的總和）而不是迭代和每個元素的查找（其中操作的數量是您正在迭代的元素數量是另一個集合中元素數量的記錄基數2）。只有當你的一個集合比另一個集合小得多時，迭代/查找方法纔會勝出。如果你看看你的庫的實現（在Amen的答案中提到）set_difference函數） - 它應該告訴你如何很好地完成這兩個迭代。

如果你想要更有效率的東西，你需要考慮如何實現這一點：例如，把你的對作爲標誌存儲在相同大小的二維矩陣中，這樣你就可以和第二組的相反。這是否實際取決於您存儲的int值的範圍，所需的內存量是否適合您的用途......

來源

2013-03-23 18:17:30

*「集合是平衡的二叉樹 - 如果不迭代結構就無法對它們進行操作」* - 這是一件很奇怪的事情說一個二叉樹。聽起來更適合作爲鏈表的描述。當然，這取決於你對「操作」的定義。它是否排除搜索，插入和刪除元素？ – 2013-03-23 18:27:10

@BenjaminLindley：取決於你對操作和迭代的定義...樹基本上是一個遞歸的一對多鏈表 - 我的觀點是你只能通過上下鏈接來移動/迭代它。。沒有像散列表或數組那樣的隨機/直接訪問。 – 2013-03-23 19:38:46

是的，您可以。

如果你想刪除，不只是來檢測，也就是這裏的另一個<algorithm>功能：remove_copy_if（）：

http://www.cplusplus.com/reference/algorithm/remove_copy_if/

恕我直言。瞭解它的工作原理並不難。

來源

2013-03-23 18:26:56 Alex

你不能在'std :: set'上使用'std :: remove_if'，因爲它的元素是const。但是，您可以使用['std :: remove_copy_if']（http://en.cppreference.com/w/cpp/algorithm/remove_copy）。 – 2013-03-23 18:43:17

是的，這是我的錯，remove_if不適用於關聯容器） – Alex 2013-03-23 18:58:25

刪除從所述第二組包含不迭代

回答

相關問題