Pembanding pelanggan antrian prioritas C++ STL tidak berfungsi

Saya telah menulis kode yang hampir serupa di masa lalu dan berhasil (saya ingat samar-samar). Tampaknya komparator tidak berfungsi di sini?? Ada petunjuk?

#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;
}

Saya berharap ini berfungsi untuk sepasang iterator hampir seperti berfungsi untuk bilangan bulat. tapi ternyata tidak.


person Alan Turing    schedule 12.08.2020    source sumber
comment
Bagaimana tidak berfungsi muncul?   -  person Ted Lyngmo    schedule 12.08.2020
comment
Saya mengharapkan antrian prioritas untuk memberi saya nomor.. Ini memberi saya beberapa alamat. Sepertinya pembanding pelanggan tidak berfungsi dengan benar. Saya mencoba mencetak a.first dan b.first tetapi mencetak a.first kedua kali.   -  person Alan Turing    schedule 12.08.2020
comment
Mengingat secara samar-samar bahwa sesuatu yang hampir serupa berhasil di masa lalu bukanlah indikasi kuat apakah ada yang berhasil atau serupa.   -  person molbdnilo    schedule 12.08.2020
comment
Anda mungkin ingin std::merge.   -  person Kenny Ostrom    schedule 12.08.2020


Jawaban (1)


Iterator begin() dan end() yang Anda dapatkan dari salinan vector di for(auto e : A) akan menjadi tidak valid setelah iterasi berakhir dan vector e sementara dimusnahkan.

Gunakan referensi ke bagian dalam vector sebagai gantinya:

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

demo

Berikut demo lainnya di mana saya telah menerapkan kualifikasi const yang sesuai.

person Ted Lyngmo    schedule 12.08.2020
comment
@Const Memang! Saya akan memperbaikinya! Terima kasih! (dan, nama bagus btw) Edit: Diperbaiki! - person Ted Lyngmo; 12.08.2020
comment
Ya,... Saya suka const. ;) - person Const; 12.08.2020
comment
Terima kasih @TedLyngmo, menggunakan e dengan referensi telah memperbaiki masalahnya !! - person Alan Turing; 14.08.2020
comment
@AlanTuring Senang melakukannya! Bersulang! - person Ted Lyngmo; 14.08.2020