c – 在std :: list中合并(将两个项目融合在一起,用融合替换它们)的算法(即破坏性聚类)

概述如果这是显而易见的道歉,我是C的新手. stackoverflow似乎有相关的答案,而不是那些我理解得足以应用于我的情况. 我有一个表示可视补丁的类实例列表. 当要素之间的距离低于阈值时,我想合并这些项目,用合并的输出替换父项. 像这样的东西： >使用嵌套for循环遍历所有项目(将每个项目与每个其他项目进行比较) >找到匹配项时(不是同一个实例)： >从匹配对构造一个新的(子)实例,追加到新列表. 如果这是显而易见的道歉,我是C的新手. stackoverflow似乎有相关的答案,而不是那些我理解得足以应用于我的情况.

我有一个表示可视补丁的类实例列表.
当要素之间的距离低于阈值时,我想合并这些项目,用合并的输出替换父项.

像这样的东西：

>使用嵌套for循环遍历所有项目(将每个项目与每个其他项目进行比较)
>找到匹配项时(不是同一个实例)：

>从匹配对构造一个新的(子)实例,追加到新列表.
>从列表中删除(父)项目

>继续遍历列表查找其他匹配项
>将新列表附加到原始列表.

我知道如何使用迭代器在单个for循环中擦除列表中的项目,但是我不清楚它是如何在嵌套循环中起作用的,因为erase()递增到下一个项目.

我可能还需要使这个函数递归,因为最终合并应该通过合并合并将列表减少为一组代表性实例.

建议将不胜感激.

以下是我的尝试,它不起作用(嵌套循环干扰一个和另一个).在列表中对元素进行这种成对比较的正确方法是什么？

#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

仍然没有运气.我认为问题可能是上面的代码不测试两个迭代器是否指向列表中的同一项,因此会混淆迭代器(当它们不应该递增或不递增时).

如何测试两个迭代器是否指向同一个项目？ (没有比较所有类成员的蛮力？,但是同一个实例的两个副本不是同一个实例.)

解决方法

voID mergeObjects(std::List<T>& List){    std::List<T> new_List;    typedef std::List<T>::iterator Itr;    for (Itr i=List.begin(); i != List.end();)    {        Itr j=i;        bool is_merged = false;        for (++j; j != List.end();)        {            if (isMergeable(*i,*j))            {                T merged = mergeObj(*i,*j);                new_List.push_back(merged);                List.erase(j);                is_merged = true;                break;            }            else            {                ++j;            }        }        if (is_merged)        {            i = List.erase(i);         }        else        {            ++i;        }    }    List.splice(List.end(),new_List);}

这应该工作,因为插入和删除元素不会使任何指针,引用和任何其他元素的迭代器无效. [参考：C STL教程和参考,nikolai Josuttis]

总结

以上是内存溢出为你收集整理的c – 在std :: list中合并(将两个项目融合在一起,用融合替换它们)的算法(即破坏性聚类)全部内容，希望文章能够帮你解决c – 在std :: list中合并(将两个项目融合在一起,用融合替换它们)的算法(即破坏性聚类)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。