c++ - 无法遍历 STL 集

Question

我的程序中循环的配置方式有问题。在做了一些调试之后，我发现循环一直运行到最后一次迭代，就在 temp 与目标匹配之前。 EXC_BAD_ACCESS (code=1, address=0x0) 被抛出，程序退出。 (11)

bool isadjacent(string& a, string& b)
{
    int count = 0;
    int n = a.length();

    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[i]) count++;
        if (count > 1) return false;
    }
    return count == 1 ? true : false;
}    


int shortestChainLen(string& start, string& target, set<string> &D)
{
    queue<QItem> Q;
    QItem item = {start, 1};
    Q.push(item);
    while (!Q.empty())
    {
        QItem curr = Q.front();
        Q.pop();
        for (set<string>::iterator it = D.begin(); it != D.end(); it++)
        {
            string temp = *it;
            if (isadjacent(curr.word, temp))
            {
                item.word = temp;
                item.len = curr.len + 1;
                Q.push(item);
                D.erase(temp);
                if (temp == target)
                    return item.len;
            }
        }
    }
    return 0;
}

这是 XCode 调试器发现的，但我不确定如何解释它。

Answer 1

问题是你正在删除你的迭代器当前指向的集合中的元素

D.erase(temp);

发生这种情况时，迭代器将失效，任何对它的进一步使用都是未定义的行为。您希望将代码结构化为:

    for (set<string>::iterator it = D.begin(); it != D.end();) {
        if (isadjacent(curr.word, *it)) {
            item.word = *it;
            item.len = curr.len + 1;
            Q.push(item);
            it = D.erase(it);
            if (item.word == target)
                return item.len;
        } else {
            ++it;
        }
    }

使用 erase 方法接受一个迭代器并返回一个指向下一项的迭代器。