抱歉，如果这很明显，我是 C++ 的新手。 stackoverflow 上似乎有相关的答案，只是我所理解的不足以适用于我的情况。

我有一个代表视觉补丁的类实例列表。 当特征之间的距离低于阈值时，我想合并这些项目，用合并后的输出替换 parent 。

像这样:

1. 使用嵌套 for 循环遍历所有项目(将每个项目与其他所有项目进行比较)

2. 当找到匹配项时(不是同一个实例):

   1. 从匹配对构造一个新的(子)实例，附加到新列表。

   2. 从列表中删除两个(父)项

3. 继续遍历列表以查找其他匹配项

4. 将新列表附加到原始列表。

我知道如何使用迭代器在单个 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 中合并(将两个项目融合在一起，用融合替换它们)项目的算法(即破坏性聚类)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9541961/