Mengapa ada orang yang menggunakan set alih-alih unordered_set?

C ++ 0x memperkenalkan unordered_setyang tersedia di boostdan banyak tempat lain. Apa yang saya mengerti adalah bahwa unordered_settabel hash dengan O(1)kompleksitas pencarian. Di sisi lain, settidak lain adalah pohon dengan log(n)kompleksitas pencarian. Mengapa di bumi ada orang yang menggunakan setbukan unordered_set? yaitu apakah ada kebutuhan untuk setlagi?

Ketika, untuk seseorang yang ingin mengulangi item set, urutan penting.

Set yang tidak dipesan harus membayar waktu akses rata-rata O (1) dalam beberapa cara:

• setmenggunakan lebih sedikit memori daripada unordered_setmenyimpan jumlah elemen yang sama.
• Untuk sejumlah kecil elemen , pencarian dalam setmungkin lebih cepat daripada pencarian dalam unordered_set.
• Meskipun banyak operasi lebih cepat dalam kasus rata-rata untuk unordered_set, mereka sering dijamin memiliki lebih baik kompleksitas kasus terburuk untuk set(misalnya insert).
• Itu set macam unsur-unsur berguna jika Anda ingin akses mereka dalam rangka.
• Anda dapat leksikografi membandingkan berbeda sets dengan <, <=, >dan >=. unordered_setTidak diperlukan untuk mendukung operasi ini.

Setiap kali Anda lebih suka pohon ke tabel hash.

Misalnya, tabel hash adalah "O (n)" di kasus terburuk. O (1) adalah kasus rata-rata. Pohon adalah "O ( log n)" paling buruk.

Gunakan setel saat:

1. Kami membutuhkan data yang dipesan (elemen yang berbeda).
2. Kami harus mencetak / mengakses data (dalam urutan terurut).
3. Kita membutuhkan pendahulu / penerus elemen.

Gunakan unordered_set saat:

1. Kita perlu menyimpan satu set elemen yang berbeda dan tidak diperlukan pemesanan.
2. Kami membutuhkan akses elemen tunggal yaitu tidak ada traversal.

Contoh:

set:

Input: 1, 8, 2, 5, 3, 9

Output: 1, 2, 3, 5, 8, 9

Unordered_set:

Input: 1, 8, 2, 5, 3, 9

Output: 9 3 1 8 2 5 (mungkin urutan ini, dipengaruhi oleh fungsi hash)

Terutama perbedaan:

Catatan: (dalam beberapa kasus setlebih mudah) misalnya menggunakan vectorsebagai kunci

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3 

Alasan mengapa vector<int>bisa menjadi kunci setkarena vectormenimpa operator<.

Tetapi jika Anda menggunakan unordered_set<vector<int>>Anda harus membuat fungsi hash vector<int>, karena vektor tidak memiliki fungsi hash, jadi Anda harus mendefinisikan satu seperti:

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

Anda dapat melihat bahwa dalam beberapa kasus unordered_setlebih rumit.

Dikutip dari: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

Karena std :: set adalah bagian dari Standard C ++ dan unordered_set tidak. C ++ 0x BUKAN standar, dan tidak juga Meningkatkan. Bagi banyak dari kita, portabilitas sangat penting, dan itu berarti berpegang teguh pada standar.

Pertimbangkan algoritma Sweepline. Algoritma ini akan gagal total dengan tabel hash, tetapi bekerja dengan indah dengan pohon seimbang. Untuk memberi Anda contoh konkret dari algoritma sweepline pertimbangkan algoritma fortune. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Satu hal lagi, selain apa yang sudah disebutkan orang lain. Sementara kompleksitas amortisasi yang diharapkan untuk memasukkan elemen ke unordered_set adalah O (1), setiap sekarang dan kemudian akan membutuhkan O (n) karena tabel hash perlu direstrukturisasi (jumlah ember perlu diubah) - bahkan dengan fungsi hash 'baik'. Sama seperti memasukkan elemen ke vektor membutuhkan O (n) setiap saat karena array yang mendasarinya perlu dialokasikan kembali.

Memasukkan dalam set selalu membutuhkan paling banyak O (log n). Ini mungkin lebih disukai di beberapa aplikasi.

Maafkan saya, satu hal lagi yang perlu diperhatikan tentang properti yang diurutkan:

Jika Anda ingin rentang data dalam wadah, misalnya: Anda menyimpan waktu dalam set , dan Anda ingin waktu dari 2013-01-01 hingga 2014-01-01.

Untuk unordered_set tidak mungkin.

Tentu saja, contoh ini akan lebih meyakinkan untuk kasus penggunaan antara peta dan unordered_map .

g++ 6.4 stdlibc ++ memerintahkan vs patokan set tidak teratur

Saya membandingkan penerapan Linux C ++ yang dominan ini untuk melihat perbedaannya:

Rincian dan analisis benchmark lengkap telah diberikan di: Apa struktur data yang mendasari set STL di C ++? dan saya tidak akan mengulanginya di sini.

"BST" berarti "diuji dengan std::setdan" peta hash "berarti" diuji dengan std::unordered_set. "Heap" untuk std::priority_queueyang saya analisis di: Heap vs Binary Search Tree (BST)

Sebagai ringkasan cepat:

• grafik dengan jelas menunjukkan bahwa dalam kondisi ini, penyisipan hashmap selalu jauh lebih cepat ketika ada lebih dari 100k item, dan perbedaannya bertambah ketika jumlah item meningkat

  Biaya peningkatan kecepatan ini adalah Anda tidak dapat melakukan traverse secara efisien.

• kurva jelas menunjukkan bahwa dipesan std::setadalah berbasis BST dan std::unordered_setberbasis hashmap. Dalam jawaban referensi, saya selanjutnya mengonfirmasi bahwa dengan langkah GDB men-debug kode.

Pertanyaan serupa untuk mapvs unordered_map: Apakah ada keuntungan menggunakan peta di atas unordered_map jika ada kunci sepele?

Tentu saja, saya akan mengatakan itu nyaman untuk memiliki sesuatu dalam suatu hubungan jika Anda ingin mengubahnya menjadi format yang berbeda.

Ada juga kemungkinan bahwa sementara satu lebih cepat diakses, waktu untuk membangun indeks atau memori yang digunakan saat membuat dan / atau mengaksesnya lebih besar.

Jika Anda ingin memiliki hal-hal yang diurutkan, maka Anda akan menggunakan set alih-alih unordered_set. unordered_set digunakan lebih dari set ketika memesan disimpan tidak masalah.

Meskipun jawaban ini mungkin terlambat 10 tahun, ada baiknya menunjukkan bahwa std::unordered_setjuga memiliki kelemahan keamanan.

Jika fungsi hash dapat diprediksi (hal ini biasanya terjadi kecuali jika menerapkan tindakan balasan seperti garam acak), penyerang dapat mengolah data yang menghasilkan tabrakan hash dan menyebabkan semua penyisipan dan pencarian membutuhkan waktu O (n) .

Ini dapat digunakan untuk serangan penolakan layanan yang sangat efisien dan elegan.

Banyak (kebanyakan?) Implementasi bahasa yang menggunakan peta hash secara internal telah mengalami hal ini:

• Javascript
• PHP
• Jawa