1

我最近决定为最近结束的 topcoder.com 比赛尝试 C++ 解决方案，作为学习语言的一种方式（对 C++ 不熟悉）。但是，当通过 std::set 对象的迭代没有成功到达集合中的所有元素（set.count > # 个遍历的元素）时，我感到很困惑。我徒劳地寻找在 StackExchange 和其他地方经历过这种情况的其他人。

细节

我已将代码发布到 pastebin：http://pastebin.com/U7xQzDQg。

我正在尝试做的是一种天真的聚类算法。我确信有更好的方法来实现我想做的事情；但这在这个阶段我并不感兴趣（因为我的重点是学习语言及其特性）。我用 Position 对象表示笛卡尔网格中的正方形，具有属性“x”和“y”。使用迭代方法，我扫描整个网格以寻找相同颜色的对象，并将它们分组为 Cluster 对象。当算法完成时，将有一组 Clusters，每个 Clusters 都包含一组 Position 对象，它们之间的距离不超过设定的距离。在算法过程中的某个时刻，有必要合并彼此靠近的簇；这就是我开始遇到问题的地方。

如果您编译并运行粘贴在 pastebin 上的代码，您将看到如下消息：

TO MERGE:
Cluster of size 1: [1,1], 
Cluster of size 2: [0,1], [0,2], 
MERGED: 0x7fffb5e9b970Cluster of size 3: [0,1], [1,1],

如果我的代码工作正常，最后一行应该显示的是：

MERGED: <Memory Address of Cluster>Cluster of size 3: [0,1], [1,1], [0,2],

每当尝试合并时都会生成这些行（参见第 54 行）；使用标准集迭代由运算符转换方法（参见第 97 行）生成的 Cluster 对象的字符串表示形式。

很清楚的是，尽管该集合声称拥有正确数量的元素，但遍历该集合并没有到达所有元素。我认为这可能是对象超出范围并被破坏的问题；但情况似乎并非如此，因为 std::set 对象在将元素插入数据结构之前复制元素（并且在其他情况下建议使用 Position 元素上的析构函数进行测试）。

我真的很茫然，不想绕开它......因为我认为我在这里遗漏了一些重要的东西。谁能帮我？

最好的，马修

4

2 回答 2

1

这

return output.c_str();

是未定义的行为，因为您的output字符串超出范围并且函数返回时删除了基础字符数组。

您的operator const char* () const功能可能应该是

friend std::ostream& operator<<(std::ostream&, Cluster const&)

直接写入的函数std::cout。

记住free你已经calloc编辑过的任何东西，或者如果你可以避免的话，最好还是不要在堆上分配东西。

于 2014-04-25T01:59:08.447 回答
1

您的程序表现出未定义的行为，因为您operator<不会为您的对象引入严格的弱排序。Position

bool operator< (Position other) const {
    return other.x - x + 100*(other.y - y);
}

您可以改用以下内容：

bool operator< (Position other) const {
    if (y < other.y) return true;
    if (y > other.y) return false;
    return x < other.x;
}
于 2014-04-25T02:03:00.847 回答