Странное поведение с unordered_map векторов и идиома erase-remove в C ++ 14 - PullRequest
Новая
       13

Странное поведение с unordered_map векторов и идиома erase-remove в C ++ 14

0 голосов
/ 12 октября 2018

Итак, я вычисляю Biconnected Components (BCC) в undirected graph, после вычисления мой алгоритм также включает в себя некоторые Bridge ребра в некоторых BCC, поэтому в качестве шага постобработки я запускаю цикл для каждого BCC (представлен как vector<pair<int, int>>, каждый pair<int, int> представляет edge в этом BCC.) Вот как я это сделал: 

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 ранее.НО, если я сделаю небольшое изменение и сделаю следующее: 

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?

Ответы [ 2 ]

0 голосов
/ 12 октября 2018

В вашем исходном коде BCCList является ссылкой на элемент в BCC.Все, что вы делаете на BCCList, вы делаете это в реальности с оригинальным элементом.

При удалении & BCCList является независимым значением, которое инициализируется копией оригинала.Все, что вы делаете с ним, сохраняется локально для этого значения и теряется на следующей итерации (или при выходе из цикла).

0 голосов
/ 12 октября 2018 
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.Это точно такая же ситуация в вашем коде.

...