所以這裏的基本問題是碰撞檢測。我通常會尋找一種將元素添加到某種關聯集合中的解決方案。由於即將添加新元素,您需要能夠判斷集合是否已經包含類似的元素,表明發生了碰撞。在這裏你似乎需要一個允許重複元素的集合類型,比如STL multimap。 Quadraple(quadruple?)顯然是關聯集合中的值類型,關鍵字類型將包含確定兩個元素是否表示衝突(即內存地址和時間)所必需的數據。爲了使用像STL multimap這樣的標準關聯集合,你需要通過爲鍵類型定義運算符<來定義鍵的一些排序(我假設C++在這裏,你沒有指定)。您將衝突定義爲兩個元素,其中內存位置相同,時間值相差少於某個閾值量。密鑰類型的排序必須使得表示衝突的兩個密鑰在排序中等同出現。在<操作下等效表示爲< b爲假且b <一個是假的一樣,所以訂貨會由該運營商定義:
bool operator<(Key const& a, Key const& b) {
if (a.address == b.address) {
if (abs(a.time - b.time) < threshold) {
return false;
}
return a.time < b.time;
}
return a.address < b.address;
}
有這種設計的一個問題,由於事實上兩個密鑰在<下可能是等效的,而不相等。這意味着兩個不同但相似的四元組,即兩個相互碰撞的值將被存儲在集合中的相同密鑰下。你可以在一個輕鬆的使用排序
bool operator<(Key const& a, Key const& b) {
if (a.address == b.address) {
return a.time < b.time;
}
return a.address < b.address;
}
在此排序定義的簡單的定義,碰撞元素結尾相鄰的有序關聯容器(但在不同的密鑰),所以你能找到他們後處理步驟全部添加到集合後。