0

我编写了一个代码来解决以下问题：我们有一个map<double,double>（相对）大量的项目。我们希望合并相邻的项目以减小地图的大小，同时保持一定的“损失因子”尽可能低。

为此，我首先填充一个包含相邻迭代器和相关损失因子的列表（假设每个列表元素具有以下类型：

struct myPair {
    map<double,double>::iterator curr, next;
    double loss;
    myPair(map<double,double>::iterator c, map<double,double>::iterator n, 
        double l):  curr(c), next(n), loss(l) {}
};

）。这是按如下方式完成的：

for (map<double,double>::iterator it1 = myMap.begin(); it1 != --(myMap.end()); 
    it1++) {
    map<double,double>::iterator it2 = it1; it2++;
    double l = computeLoss(it1,it2); 
    List.push(myPair(it1,it2,l));
}

然后，我找到与最低损失因子相对应的列表元素，来自的erase对应元素map和. 因为这也会在我更新相应条目之后或之前更改与元素对应的列表元素，以及相关的损失因子。insertcurrnextmapnextcurr

（我没有详细介绍如何有效地实现上述内容，但基本上我将双链表和堆结合起来）。

虽然erase操作不应使程序的某些特定输入实例的剩余迭代器无效，但我double free or corruption在尝试从map.

我试图跟踪这一点，当两个地图元素的first和second条目非常接近时（更准确地说，当 和 的sfirst非常接近时）似乎会发生这种情况。currnext

奇怪的是，我放了一个assertwhile 填充列表，以确保在所有条目中curr和在删除元素的循环中next都不同且相同assert。第二个失败！

如果有人可以帮助我，我将不胜感激。

PS我很抱歉不是很精确，但我想尽可能地保持细节。

更新：这是（一个非常简化的版本）我如何从地图中删除元素：

while (myMap.size() > MAX_SIZE) {
    t = list.getMin();
    /* compute the merged version ... let's call the result as (a,b) */
    myMap.erase(t.curr);
    myMap.erase(t.next);
    myMap.insert(pair<double,double>(a,b));

    /* update the adjacent entries */
}
4

2 回答 2

0

容器修改后，存储的迭代器myPair保持无效。你应该避免这种技术。可能当您查看头文件时，您会为您的任务找到一些现成的草稿？

于 2013-09-09T22:14:18.620 回答
0

正如其他人已经提到的那样，事实证明，将其double用作 keymap是有问题的。特别是在计算值时。

因此，我的解决方案是使用std::multimap而不是map（然后在填充地图后将元素与相同的键合并）。有了这个，例如，即使a非常接近t.curr和t.next或任何其他元素的键，也可以肯定该insert操作会创建一个新元素，这样在 中不存在iterator将list指向该元素。

于 2013-09-10T16:06:20.903 回答