Компаратор приоритетной очереди C++ STL не работает

Я писал почти аналогичный код в прошлом, и он работал (я смутно помню). Похоже компаратор тут не работает?? Любые подсказки?

#include<iostream>
#include<vector>
#include<queue>
#include<iterator>
#include<algorithm>
using namespace std;

    typedef pair<vector<int>::iterator,vector<int>::iterator> PR;
    struct CompareFn{
        bool operator()(const PR& a, const PR& b){
            //cout<<"a and b first: "<<*(a.first)<<" "<< *(b.first)<<endl;
            return *a.first > *b.first;
        }
    };

vector<int> mergeKSortedArrays(vector<vector<int>> &A) {  
vector<int> result;
    
    priority_queue<PR, vector<PR>, CompareFn> PQ;
    for(auto e:A){  
        if(e.size()>0) PQ.push({e.begin(),e.end()});
    }

    while(PQ.size()>0) {
        PR tmp = PQ.top(); PQ.pop();
        auto cur=tmp.first;
        auto lst=tmp.second;
        result.emplace_back (*cur);
        if((++cur)!=lst) PQ.push({cur,lst});
    }
return result;
}


int main() { 
vector<vector<int>> v= {{2,3,8,10},{1,4,12},{4,5,8}};
 vector<int> result = mergeKSortedArrays(v);
 copy(result.begin(),result.end(), ostream_iterator<int>(cout," "));
 return 0;
}

Я ожидал, что он будет работать для пары итераторов почти так же, как и для целых чисел. но это не так.


person Alan Turing    schedule 12.08.2020    source источник
comment
Как проявляется не работает?   -  person Ted Lyngmo    schedule 12.08.2020
comment
Я ожидаю, что приоритетная очередь даст мне номера. Она даст мне несколько адресов. Похоже, что компаратор клиентов работает неправильно. Я пытался напечатать a.first и b.first, но оба раза печатает a.first.   -  person Alan Turing    schedule 12.08.2020
comment
Смутное воспоминание о том, что что-то почти похожее работало в прошлом, не является очень убедительным признаком либо работы, либо сходства.   -  person molbdnilo    schedule 12.08.2020
comment
Вам может понадобиться std::merge.   -  person Kenny Ostrom    schedule 12.08.2020


Ответы (1)


Итераторы begin() и end(), полученные из копии vector в for(auto e : A), станут недействительными после завершения итерации и уничтожения временного vector e.

Вместо этого используйте ссылку на внутренний vector:

for(auto& e : A) { // "auto& e" makes "e" a reference to the existing vector
    if(e.size()>0) PQ.emplace(e.begin(), e.end());
}

демонстрация

Вот еще одна демонстрация, где я применил соответствующие квалификаторы const.

person Ted Lyngmo    schedule 12.08.2020
comment
@Const Действительно! Я исправлю это! Спасибо! (и, кстати, красивое имя) Редактировать: исправлено! - person Ted Lyngmo; 12.08.2020
comment
Да,... мне нравится const. ;) - person Const; 12.08.2020
comment
Спасибо @TedLyngmo, использование e по ссылке устранило проблему !! - person Alan Turing; 14.08.2020
comment
@AlanTuring Рад, что это произошло! Ваше здоровье! - person Ted Lyngmo; 14.08.2020