使用矢量的unordered_map和C++ 14中的erase-remove惯用法的奇怪行为

Question

所以我计算Biconnected Components (BCC)在undirected graph计算后,我的算法也包括一些BridgeBCC中的一些边缘,所以作为后处理步骤,我在每个BCC 上运行一个循环BCC(表示为a vector<pair<int, int>>,每个pair<int, int>代表一个edgeBCC中.)这是我的方式做到了:

auto pred = [&Bridges](pair<int, int>& edge) -> bool
{
    return Bridges.find(edge) != Bridges.end();
};

for (auto bcc = BCC.begin(); bcc != BCC.end(); bcc++)
{
    vector<pair<int, int>>& BCCList = (bcc->second);
    BCCList.erase(remove_if(
        BCCList.begin(), BCCList.end(), pred), BCCList.end());
}

Bridges是set的pair<int, int>又在发,包含所有桥边缘由我的算法中找到.

BCC是一个unordered_map<int, vector<pair<int, int>>>.

上面的代码按预期工作,删除之前可能已经在BCC向量中的任何Bridge边.但是,如果我稍作修改并执行此操作:

auto pred = [&Bridges](pair<int, int>& edge) -> bool
{
    return Bridges.find(edge) != Bridges.end();
};

for (auto bcc = BCC.begin(); bcc != BCC.end(); bcc++)
{
    vector<pair<int, int>> BCCList = (bcc->second);
    BCCList.erase(remove_if(
        BCCList.begin(), BCCList.end(), pred), BCCList.end());
}

我所做的就是删除&之前BCCList的第一行for-loop.这使代码不起作用,并产生一个结果,好像这for-loop从未执行过; 没有任何BCC中的桥边缘被移除,因此最终计算出错误的BCC.请告诉我为什么会这样？

我总是想,如果我有一个bcc上一个像迭代器unordered_map,然后bcc->first是key(这里bcc->first应该是一个int),并bcc->second是value(这里,bcc->second应该是vector<pair<int, int>>).这不正确吗？为什么我必须明确指定&(参考变量)代码才能工作？

这种行为可能与某些事情有关remove_if吗？

Answer 1

vector<pair<int, int>>& BCCList = (bcc->second);

这里BCCList是存储的向量的引用(替代名称)bcc->second.无论你做了什么改变,BCCList实际上都是这样做的bcc->second.

vector<pair<int, int>> BCCList = (bcc->second);

这里BCCList是存储的矢量的副本bcc->second.这是一个单独的对象.对它的更改根本不会影响bcc->second.

这是一个更简单的例子,它应该更明显地发生了什么:

int data = 42;
int *bcc = &data;

int &ref = *bcc;
ref = 314;

int cop = *bcc;
cop = -42;

我认为您不希望cop = -42;修改任务data.这与您的代码中的情况完全相同.