在std :: list（即破壞性聚類）中合併（將兩個項目融合在一起，替換爲fusion）項目

Question

如果明顯，我是C++新手。似乎有相關的答案在stackoverflow，只是不是那些我理解足夠適用於我的情況。

我有一個代表視覺補丁的類實例列表。 當要素之間的距離低於閾值時，我想合併這些項目，用合併後的輸出替換父項。

事情是這樣的：

1. 遍歷所有項目使用嵌套的循環。當發現匹配（每個項目比較所有其它項目）

2. （也就是不一樣實例）：

   1. 從匹配對構造一個新的（子）實例，追加到新列表。

   2. 同時刪除（父）從名單

3. 項目繼續通過列表迭代找到其他比賽

4. 追加新的列表到原始列表。

我知道如何刪除從列表中的項目單，使用迭代循環，但我不清楚它是如何在適當的擦除（嵌套的循環工作）遞增到下一個項目。

我可能還需要使此函數遞歸，因爲最終合併應該通過合併合併將列表減少爲一組具有代表性的實例。

建議，將不勝感激。

以下是我的嘗試，它不起作用（嵌套循環干擾一個和其他）。在列表中進行這種成對比較的正確方法是什麼？

#include <iostream> 
#include <list> 
using namespace std; 

int main() { 
list<int> mylist; 
list<int>::iterator mylistiterOutter; 
list<int>::iterator mylistiterInner; 

for(int i=0; i<10; i++) { 
    mylist.push_back(i); 
    cout << i << endl; 
} 

for(int i=0; i<10; i++) { 
    mylist.push_back(i); 
    cout << i << endl; 
} 

int counter =0; 
for(mylistiterOutter = mylist.begin(); mylistiterOutter != mylist.end();) { 
    cout << "Size of mylist: " << mylist.size() << endl; 

    for(mylistiterInner = mylist.begin(); mylistiterInner != mylist.end();) { 
     cout << "mylistiterInner: " << *mylistiterInner << endl; 
     cout << "mylistiterOutter: " << *mylistiterOutter << endl; 
     //if (mylistiterOutter == mylistiterInner) {// match! 
     if (false) { 
      //mylistiterOutter = mylist.erase(mylistiterOutter); 
      //mylistiterInner = mylist.erase(mylistiterInner); 
     } else { 
      mylistiterOutter++; 
      mylistiterInner++; 
     } 

     counter++; 
    } 
} 
cout << endl << "Size of mylist: " << mylist.size() << endl << "NumIterations: " << counter << endl; 

return(0); 
} 

感謝@lalitm。我首先嚐試了你的方法，因爲它更接近我原先設想的方式，但J.N.的建議更優雅，所以我也會嘗試。不幸的是，我無法使@ lalitm的方法奏效。 （導致分段錯誤）。以下是稍微複雜的代碼，包括示例類和合並代碼，使用@ lalitm的做法：

#include <iostream> 
#include <list> 
#include <cmath> 
using namespace std; 

class percepUnit { 
public: 
    int cx, cy; // location of percept in frame 
    bool remove; // used to delete percepts 

    // constructor method 
    percepUnit(int ix, int iy) { 
     cx = ix; 
     cy = iy; 
     remove = false; 
    } 
}; 

bool canMerge(percepUnit unitA, percepUnit unitB) { 

    double dist = sqrt(pow(abs(unitA.cx-unitB.cx),2)+ pow(abs(unitA.cy-unitB.cy),2)); 
    return (dist < 3); 
} 

percepUnit merge(percepUnit unitA, percepUnit unitB) { 
    int x,y; 

    x = unitA.cx+unitB.cx/2; 
    y = unitA.cy+unitB.cy/2; 

    return (percepUnit(x,y)); 
} 

int main() { 
    list<percepUnit> mylist; 
    list<percepUnit> mergedlist; 
    list<percepUnit>::iterator mylistiterOutter; 
    list<percepUnit>::iterator mylistiterInner; 
    bool mylistiterOutterChanged; 

    mylist.push_back(percepUnit(0,0)); 
    mylist.push_back(percepUnit(2,2)); 

    mylist.push_back(percepUnit(5,5)); 
    mylist.push_back(percepUnit(7,7)); 

    //cout << "merge front/back? " << canMerge(mylist.front(),mylist.back()) << endl; 
    //percepUnit test = merge(mylist.front(),mylist.back()); 
    //cout << "merged front/back (x,y): " << test.cx << "," << test.cy << endl; 

    for(mylistiterOutter = mylist.begin(); mylistiterOutter != mylist.end();) { 
    cout << "Size of mylist: " << mylist.size() << endl; 

     mylistiterInner = mylistiterOutter; 
     mylistiterOutterChanged = false; 

     for (++mylistiterInner; mylistiterInner != mylist.end();) { 
      if (canMerge(*mylistiterOutter, *mylistiterInner)) { 
       mergedlist.push_back(merge(*mylistiterOutter, *mylistiterInner)); 
       mylistiterOutter = mylist.erase(mylistiterOutter); 
       mylistiterInner = mylist.erase(mylistiterInner); 
       mylistiterOutterChanged = true; 
      } else { 
       ++mylistiterInner; 
      } 
     } 
     if (!mylistiterOutterChanged) { 
      ++mylistiterOutter; 
     } 
    } 

    mylist.splice(mylist.end(), mergedlist); 


    return(0); 
} 

這裏是我的GDB信息：

Program received signal SIGSEGV, Segmentation fault. 
0x00007ffff7b31d97 in std::_List_node_base::unhook()() 
    from /usr/lib/libstdc++.so.6 
(gdb) bt 
#0 0x00007ffff7b31d97 in std::_List_node_base::unhook()() 
    from /usr/lib/libstdc++.so.6 
#1 0x0000000000401786 in std::list<percepUnit, std::allocator<percepUnit> >::_M_erase (this=0x7fffffffe4d0, __position=...) 
at /usr/include/c++/4.4/bits/stl_list.h:1424 
#2 0x000000000040153d in std::list<percepUnit, std::allocator<percepUnit> >::erase (this=0x7fffffffe4d0, __position=...) 
at /usr/include/c++/4.4/bits/list.tcc:111 
#3 0x0000000000401130 in main() at debug.cpp:61 

仍然沒有運氣。我認爲問題可能是上面的代碼沒有測試這兩個迭代器是否指向列表中的同一個項目，因此混淆了迭代器（當它們不應該是時遞增或不遞增）。

如何測試兩個迭代器是否指向相同的項目？（沒有比較所有類成員的蠻力？，但是同一個實例的兩個副本不是同一個實例）。

Answer 1

以下是我結束了。

1. 這是衣衫襤褸的：對不比較兩次（0,1和1,0）

2. 情況並不比自己（0,0）

   #include <iostream> 
   #include <list> 
   #include <cmath> 
   #include <algorithm> 
   using namespace std; 
   
   class percepUnit { 
       public: 
        int cx, cy; // location of percept in frame 
        bool remove; // used to delete percepts 
   
        // constructor method 
        percepUnit(int ix, int iy) { 
         cx = ix; 
         cy = iy; 
         remove = false; 
        } 
   }; 
   
   bool canMerge(percepUnit unitA, percepUnit unitB) { 
   
       double dist = sqrt(pow(abs(unitA.cx-unitB.cx),2)+ pow(abs(unitA.cy-unitB.cy),2)); 
       return (dist < 3); 
   } 
   
   percepUnit merge(percepUnit unitA, percepUnit unitB) { 
       int x,y; 
   
       x = unitA.cx+unitB.cx/2; 
       y = unitA.cy+unitB.cy/2; 
   
       return (percepUnit(x,y)); 
   } 
   
   // Predicate to use remove_if to delete merge inputs. 
   bool removePercepsMarkedForRemoval(const percepUnit &unit) { 
       return unit.remove; 
   } 
   
   int main() { 
       list<percepUnit> mylist; 
       list<percepUnit> mergedlist; 
       list<percepUnit>::iterator mylistiterOutter; 
       list<percepUnit>::iterator mylistiterInner; 
   
       mylist.push_back(percepUnit(0,0)); 
       mylist.push_back(percepUnit(2,2)); 
   
       mylist.push_back(percepUnit(5,5)); 
       mylist.push_back(percepUnit(7,7)); 
   
       mylist.push_back(percepUnit(15,15)); 
   
       for(mylistiterOutter = mylist.begin(); mylistiterOutter != mylist.end(); mylistiterOutter++) { 
   
        mylistiterInner = mylistiterOutter; // bypass the same pair twice 
   
        while (mylistiterInner != mylist.end()) { 
         if (canMerge(*mylistiterOutter, *mylistiterInner) and mylistiterOutter != mylistiterInner) { // bypass the same instance 
          mergedlist.push_back(merge(*mylistiterOutter, *mylistiterInner)); 
          mylistiterOutter->remove = true; 
          mylistiterInner->remove = true; 
         } 
         mylistiterInner++; 
        } 
       } 
   
       mylist.erase(remove_if(mylist.begin(), mylist.end(), removePercepsMarkedForRemoval), mylist.end()); 
   
       mylist.splice(mylist.end(), mergedlist); 
   
       return(0); 
   } 
   

Answer 2

您尚未提供很多洞察力，但這裏有一個很好的方法它：

#include <algorithm> 
#include <set> 

std::list<int> myList = {5,6,7,7,8,5}; 
std::set<int> uniques; // a set can only contain unique elements 

// copying the list in the set will overwrite the same elements when duplicates are found 
std::copy(myList.begin(), myList.end(), std::inserter(uniques, uniques.begin())); 

// clear the existing list 
myList.clear(); 

// copy back the unique elements. 
std::copy(uniques.begin(), uniques.end(), std::back_inserter(myList)); 

for (int i: myList) 
    cout << i << endl; 

編輯：性能明智的，應該是相當於您的解決方案或更快，因爲我在設置搜索使用0（日誌（N））的算法，當你有兩個循環完成。編輯2：你需要的東西比我想象的要複雜一些。一個開始的建議，雖然：你不能與迭代器循環，並修改你在迭代的容器在同一時間。你需要使用整數索引。

EDIT3：下面的解決方案提供了一種使用unordered_set的方法。您需要能夠區分屬於相同「組」的對象。

#include <unordered_set> 

// That's the objects we are going to "fuse" 
// In this example I suppose that all Points that have the same X must be fused 
struct Point 
{ 
    double x; 
    double y; 

    // We need a way to say that which points are equals 
    bool operator==(const Point& other) const 
    { 
     return other.x == x; 
    } 
}; 

// Then we need a unique identifier to place the points in a set 
namespace std { 
    template <> struct hash<Point> { 
     double operator()(const Point& point) const { 
      return point.x; 
     } 
    }; 
} 

// We will use an unordered_set to put our elements in 
unordered_set<Point> uniques; 

// Then we can proceed as before 
std::copy(myList.begin(), myList.end(), std::inserter(uniques, uniques.begin())); 
myList.clear(); 
std::copy(uniques.begin(), uniques.end(), std::back_inserter(myList)); 

Answer 3

我認爲修改（擦除）嵌套循環內的列表是一個壞主意。外循環迭代器（示例代碼中的mylistiterOutter）將無法正常工作。

你應該做兩個獨立的循環。第一個應該搜索要合併的項目，並以某種方式記住它們（沒有擦除）。第二個循環會擦除記憶的物品並創建新的物品。

Answer 4

​​

這應該工作，因爲插入和刪除元素不會使任何指針，引用和迭代器無效到任何其他元素。 [參考：C++ STL教程和參考，尼古拉Josuttis]