Pertanyaan Memahami Peta di C ++ sebagai pengembang Java [duplikat]


Pertanyaan ini sudah memiliki jawaban di sini:

di Java, kami memiliki metode seperti hashCode () dan equals () yang digunakan oleh peta untuk mengidentifikasi setiap objek. C ++ tidak memiliki metode dasar seperti itu, setiap objek mengimplementasikan secara default.

Bagaimana bisa peta sekarang menggunakan objek kustom sebagai nilai kunci?

Edit: Tidak ada duplikat karena itu terutama bertujuan terhadap metode-metode antarmuka khusus java, seseorang yang tidak memiliki apa pun yang dilakukan sebelumnya dengan C ++ akan mencari


5
2018-01-14 17:33


asal


Jawaban:


Pertama, a std::map di C ++ umumnya merupakan pohon merah-hitam, bukan tabel hash. Ada juga peta hash dalam C ++ 11 yang disebut std::unordered_map. Secara default menggunakan operator< untuk membandingkan elemen. Anda juga dapat memasang pembanding khusus yang dapat membandingkan menggunakan apa pun yang Anda inginkan. Ini dilakukan dengan menggunakan argumen 3 template opsional untuk std::map.


6
2018-01-14 17:38



C ++ std::map adalah peta yang diperintahkan, dengan persyaratan yang berarti bahwa itu diimplementasikan sebagai pohon pencarian biner yang menyeimbangkan diri (biasanya pohon merah-hitam). Ini berarti bahwa jenis kunci harus memiliki semacam pemesanan lemah yang ketat, yang bisa datang dalam bentuk a less-than operator, atau sebagai pengguna yang menentukan fungsi perbandingan.

Ada banyak posting SO tentang cara menggunakan std::map dengan jenis yang ditentukan pengguna sebagai tombol (lihat satu contoh di sini).

C ++ 11 punya std::unordered_map, yang merupakan tabel hash dengan persyaratan yang berbeda pada jenis kunci (khusus, fungsi hashing dan perbandingan persamaan diperlukan)


5
2018-01-14 17:37



Peta di C ++ bukan HashMap, melainkan peta yang diurutkan (biasanya diterapkan sebagai pohon merah-hitam). Entri diurutkan berdasarkan kunci menggunakan fungsi komparator. Dalam implementasi standar, kunci harus memiliki operator< kelebihan beban, tetapi Anda dapat menentukan fungsi komparator Anda sendiri.

Lihat di sini untuk info peta C ++: http://en.cppreference.com/w/cpp/container/map


2
2018-01-14 17:37



Peta Hash Java memiliki kompleksitas waktu O (1). Di C ++, peta berbasis pohon merah-hitam memiliki kompleksitas waktu O (logN).

CSLM adalah hread-safe ,concurrent dan TreeMap tidak . CSLM ditambahkan dalam JDK 1.6

Lihat Dokumen:Java setara dengan C ++ std :: map?


2
2018-01-14 17:40



C ++ map adalah peta yang diperintahkan, bukan peta hash, templated untuk menggunakan comp ekspresi boolean (a, b) untuk membandingkan nilai kunci. Standarnya lebih sedikit yang melakukan perbandingan (A B), yang dalam C ++ dapat diisi berlebih oleh kelas. Peta alternatif dapat menggunakan ekspresi berbeda.


1
2018-01-14 17:41



std :: map adalah kelas templated. Kuncinya harus sesuai dengan konsep tertentu yang disebut pemesanan lemah ketat yang menjamin:

  • Kunci tidak dapat dibandingkan (operator kelebihan beban) atau memberikan peta pembanding kustom
  • Jika elemen A lebih kecil dari B, B tidak boleh kurang dari A
  • Jika elemen A kurang dari B dan B kurang dari C, maka A kurang dari C

Berikut ini contoh dengan kunci jenis kustom sebagai:

#include <map>
#include <iostream>
struct Custom{ Custom(int c): c(c){} int c; };
bool operator< (Custom const &a, Custom const &b){ return a.c< b.c; }
int main(){ std::map<Custom, int> m; m[Custom(42)]= 42; std::cout<< m[Custom(42)]; }

Yang mengatakan, std :: map bukanlah ekuivalen yang tepat dari peta hash Java. C ++ 11 punya std::unordered_mapuntuk itu. Dengan unordered_map, Anda dapat menentukan sendiri std :: hash template untuk tipe Anda sendiri untuk mempertahankan jenis kustom Anda sebagai kunci hash.


1
2018-01-14 17:42