Cara terbaik untuk menggabungkan beberapa wadah STL, menghapus elemen duplikat?

Saya memiliki dua wadah STL yang ingin saya gabungkan, menghapus elemen apa pun yang muncul lebih dari sekali. Misalnya:

typedef std::list<int> container;
container c1;
container c2;

c1.push_back(1);
c1.push_back(2);
c1.push_back(3);

c2.push_back(2);
c2.push_back(3);
c2.push_back(4);

container c3 = unique_merge(c1, c2);
// c3 now contains the following 4 elements:
//   1, 2, 3, 4

std::unique sepertinya hanya untuk elemen yang berdekatan, dan dalam kasus saya wadahnya bisa dalam urutan apa pun. Saya kira saya bisa melakukan beberapa tipu daya std::set:

container unique_merge(const container& c1, const container& c2)
{
    std::set<container::value_type> s;
    BOOST_FOREACH(const container::value_type& val, c1)
        s.insert(val);
    BOOST_FOREACH(const container::value_type& val, c2)
        s.insert(val);
    return container(s.begin(), s.end());
}

Apakah ada cara yang lebih baik atau apakah saya melewatkan sesuatu yang jelas terlihat?


c++ stl
person Rob    schedule 11.11.2008    source sumber
comment
Jika Anda meminta sesuatu yang jelas-jelas jelas, penerapan Anda cukup baik untuk sebagian besar kasus. Namun algoritma yang lebih baik memang ada, dengan biaya O(N * log(M)), dimana N adalah jumlah total elemen dalam semua container, dan M adalah jumlah container. Kodenya tidak sepele, nanti saya tulis kalau ada waktu.   -  person RnMss    schedule 01.04.2014
comment
@RnMss Benarkah? Bisakah Anda memposting jawaban? ...   -  person user202729    schedule 04.04.2018
comment
@ user202729 ya ampun Saat itu tahun 2014...   -  person RnMss    schedule 07.04.2018
comment
@ user202729 Sekarang saya tidak yakin tentang hal itu. Menurut saya..., dilihat dari apa yang saya tulis, bahwa... mungkin... saat itu saya mengira setiap container sudah tersortir, namun jumlah containernya bisa saja lebih banyak (misalnya 1000 atau lebih).   -  person RnMss    schedule 12.04.2018

Jawaban (3)


arrow_upward
7
arrow_downward

Untuk daftar yang tidak berurutan, trik set Anda mungkin adalah salah satu yang terbaik. Setiap sisipan harus berupa O(log n), dengan N sisipan diperlukan, dan lintasannya akan menjadi O(n), memberi Anda O(N*log n). Opsi lainnya adalah menjalankan std::sort pada setiap daftar satu per satu lalu menelusurinya secara paralel menggunakan std::set_union, yang menghapus duplikat untuk Anda. Ini juga akan menjadi O(n*log n), jadi jika Anda mengkhawatirkan kinerja, Anda harus membuat profil. Jika tidak, lakukan mana saja yang lebih masuk akal bagi Anda.

Sunting: set_union hanya akan berfungsi jika tidak ada duplikat dalam daftar asli, jika tidak, Anda harus menggunakan sort, merge, unique dan erase. Performa O besar masih sama, dengan peringatan yang sama tentang pembuatan profil.

template <typename container>
container unique_merge(container c1, container c2)
{
    std::sort(c1.begin(), c1.end());
    std::sort(c2.begin(), c2.end());
    container mergeTarget;
    std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(), 
        std::insert_iterator(mergeTarget, mergeTarget.end())
    );
    std::erase(
        std::unique(mergeTarget.begin(), mergeTarget.end()), 
        mergeTarget.end()
    );

    return mergeTarget;
}
person Eclipse    schedule 11.11.2008
comment
Menurut spesifikasi std::set_union: Jika ada elemen duplikat di dua rentang, R1 dan R2, katakanlah V muncul N kali di R1 dan M kali di R2, hasil std::set_union akan berisi max(N, M) contoh V. Jadi kecuali N‹=1 dan M‹=1 itu bukan solusi yang tepat. - person Andreas Magnusson; 12.11.2008
comment
Itulah yang saya dapatkan karena tidak menguji kompilasinya. - person Eclipse; 12.11.2008

arrow_upward
4
arrow_downward

Anda perlu mengurutkannya (baik secara eksplisit, atau implisit melalui wadah yang diurutkan seperti set).

Ada ungkapan umum yang menggunakan std::sort/std::unique/std::erase untuk mendapatkan elemen unik dalam sebuah wadah.

Jadi buatlah wadah dengan konten c1, tambahkan konten c2, lalu urutkan, pindahkan elemen unik ke akhir, dan hapus elemen tersebut. Sesuatu seperti ini:

container c(c1.begin(), c1.end());
c.insert(c.end(), c2.begin(), c2.end());
c.erase(std::unique(c.begin(), c.end()), c.end());
person Chris Morley    schedule 11.11.2008

arrow_upward
3
arrow_downward

Gunakan std::set_union algoritma dari STL. Anda harus mengurutkan daftar masukan Anda terlebih dahulu -- atau membuat salinan daftar masukan Anda, mengurutkannya, lalu menggunakan std::set_union.

person Uhall    schedule 11.11.2008