Di STL maps, apakah lebih baik menggunakan map :: insert daripada []?

201

Beberapa waktu yang lalu, saya berdiskusi dengan seorang kolega tentang cara memasukkan nilai dalam peta STL . Saya lebih suka map[key] = value; karena rasanya alami dan jelas untuk membaca sedangkan dia lebih suka map.insert(std::make_pair(key, value))

Saya hanya bertanya kepadanya dan kami berdua tidak dapat mengingat alasan mengapa memasukkan lebih baik, tetapi saya yakin itu bukan hanya preferensi gaya melainkan ada alasan teknis seperti efisiensi. The referensi SGI STL hanya mengatakan "Sebenarnya, fungsi anggota ini tidak diperlukan. Itu ada hanya untuk kenyamanan"

Adakah yang bisa memberi tahu saya alasan itu, atau saya hanya bermimpi ada satu?

danio
sumber
2
Terima kasih atas semua tanggapan luar biasa - semuanya sangat membantu. Ini adalah demo tumpukan overflow yang terbaik. Saya bingung tentang jawaban mana yang harus diterima: netjeff lebih eksplisit tentang perilaku yang berbeda, Greg Rogers menyebutkan masalah kinerja. Seandainya aku bisa menandai keduanya.
danio
6
Sebenarnya, dengan C ++ 11, Anda mungkin lebih baik menggunakan map :: emplace yang menghindari konstruksi ganda
einpoklum
@einpoklum: Sebenarnya, Scott Meyers menyarankan sebaliknya dalam pembicaraannya "Pencarian yang berkembang untuk C ++ yang efektif".
Thomas Eding
3
@einpoklum: Itu adalah kasus ketika memasukkan ke dalam memori yang baru dibangun. Tetapi karena beberapa persyaratan standar untuk peta, ada alasan teknis mengapa emplace bisa lebih lambat daripada memasukkan. Pembicaraan tersedia secara bebas di youtube, seperti tautan ini youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 tandai min. Untuk tautan SO, inilah stackoverflow.com/questions/26446352/…
Thomas Eding
1
Saya sebenarnya akan berdebat dengan apa yang disajikan Meyers, tapi itu di luar cakupan utas komentar ini dan bagaimanapun, saya kira saya harus menarik kembali komentar saya sebelumnya.
einpoklum

Jawaban:

240

Ketika Anda menulis

map[key] = value;

tidak ada cara untuk mengetahui apakah Anda diganti yang valueuntuk key, atau jika Anda dibuat baru keydengan value.

map::insert() hanya akan membuat:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

Untuk sebagian besar aplikasi saya, saya biasanya tidak peduli apakah saya membuat atau mengganti, jadi saya menggunakan yang lebih mudah dibaca map[key] = value.

netjeff
sumber
16
Harus dicatat bahwa peta :: insert tidak pernah menggantikan nilai. Dan dalam kasus umum saya akan mengatakan bahwa lebih baik menggunakan (res.first)->seconddaripada valuejuga dalam kasus kedua.
dalle
1
Saya memperbarui agar lebih jelas bahwa map :: insert tidak pernah diganti. Saya meninggalkan elsekarena saya pikir menggunakan valuelebih jelas daripada iterator. Hanya jika tipe nilai memiliki copy ctor atau op == yang tidak biasa itu akan berbeda, dan tipe itu akan menyebabkan masalah lain menggunakan wadah STL seperti peta.
netjeff
1
map.insert(std::make_pair(key,value))seharusnya map.insert(MyMap::value_type(key,value)). Jenis yang dikembalikan dari make_pairtidak cocok dengan jenis yang diambil oleh insertdan solusi saat ini membutuhkan konversi
David Rodríguez - dribeas
1
ada cara untuk mengetahui apakah Anda memasukkan atau hanya ditugaskan operator[], cukup membandingkan ukuran sebelum dan sesudahnya. Saya hanya bisa memanggil map::operator[]untuk jenis konstruktif default jauh lebih penting.
idclev 463035818
@ DavidRodríguez-dribeas: Saran bagus, saya memperbarui kode dalam jawaban saya.
netjeff
53

Keduanya memiliki semantik yang berbeda ketika datang ke kunci yang sudah ada di peta. Jadi mereka tidak bisa dibandingkan secara langsung.

Tetapi versi operator [] memerlukan nilai konstruk default, dan kemudian menetapkan, jadi jika ini lebih mahal daripada menyalin konstruksi, maka itu akan lebih mahal. Terkadang konstruksi default tidak masuk akal, dan kemudian tidak mungkin menggunakan versi operator [].

Greg Rogers
sumber
1
make_pair mungkin memerlukan copy constructor - itu akan lebih buruk daripada yang standar. Tetap memberi +1.
1
Masalah utamanya adalah, seperti yang Anda katakan, mereka memiliki semantik yang berbeda. Jadi tidak ada yang lebih baik dari yang lain, gunakan saja yang melakukan apa yang Anda butuhkan.
jalf
Mengapa konstruktor salinan lebih buruk daripada konstruktor default diikuti oleh penugasan? Jika ya, maka orang yang menulis kelas telah melewatkan sesuatu, karena apa pun yang dilakukan operator =, mereka seharusnya melakukan hal yang sama dalam copy constructor.
Steve Jessop
1
Kadang-kadang pembuatan standar sama mahalnya dengan tugas itu sendiri. Secara alami penugasan dan pembuatan salinan akan setara.
Greg Rogers
@Arkadiy Dalam build yang dioptimalkan, kompiler akan sering menghapus banyak panggilan copy constructor yang tidak perlu.
antred
35

Hal lain yang perlu diperhatikan std::map:

myMap[nonExistingKey];akan membuat entri baru di peta, dikunci untuk nonExistingKeydiinisialisasi ke nilai default.

Ini membuatku takut saat pertama kali aku melihatnya (sambil membenturkan kepalaku ke bug warisan yang mengerikan). Tidak akan diharapkan itu. Bagi saya, itu terlihat seperti operasi, dan saya tidak mengharapkan "efek samping." Lebih suka map.find()saat mendapatkan dari peta Anda.

Hawkeye Parker
sumber
3
Itu adalah pandangan yang layak, meskipun peta hash cukup universal untuk format ini. Mungkin salah satu dari "keanehan yang tak seorang pun anggap aneh" hanya karena seberapa luas mereka menggunakan konvensi yang sama
Stephen J
19

Jika hit kinerja dari konstruktor default tidak menjadi masalah, silakan, untuk cinta tuhan, pergi dengan versi yang lebih mudah dibaca.

:)

Torlack
sumber
5
Kedua! Harus menandai ini. Terlalu banyak orang menukar kesesuaian untuk speedup nano-detik. Kasihanilah kami jiwa-jiwa miskin yang harus mempertahankan kekejaman seperti itu!
Mr.Ree
6
Seperti yang ditulis Greg Rogers: "Keduanya memiliki semantik yang berbeda dalam hal kunci yang sudah ada di peta. Jadi mereka tidak benar-benar sebanding secara langsung."
dalle
Ini adalah pertanyaan dan jawaban lama. Tetapi "versi yang lebih mudah dibaca" adalah alasan yang bodoh. Karena yang paling mudah dibaca tergantung pada orangnya.
vallentin
14

insert lebih baik dari sudut keamanan pengecualian.

Ekspresi map[key] = valuesebenarnya adalah dua operasi:

  1. map[key] - membuat elemen peta dengan nilai default.
  2. = value - menyalin nilai ke elemen itu.

Pengecualian dapat terjadi pada langkah kedua. Akibatnya operasi hanya akan dilakukan sebagian (elemen baru ditambahkan ke peta, tetapi elemen itu tidak diinisialisasi dengan value). Situasi ketika suatu operasi tidak lengkap, tetapi keadaan sistem dimodifikasi, disebut operasi dengan "efek samping".

insertoperasi memberikan jaminan yang kuat, berarti tidak memiliki efek samping ( https://en.wikipedia.org/wiki/Exception_safety ). insertbaik dilakukan sepenuhnya atau meninggalkan peta dalam keadaan tidak dimodifikasi.

http://www.cplusplus.com/reference/map/map/insert/ :

Jika satu elemen dimasukkan, tidak ada perubahan dalam wadah jika terkecuali (jaminan kuat).

anton_rh
sumber
1
lebih penting, masukkan tidak memerlukan nilai untuk dapat dibangun secara default.
UmNyobe
13

Jika aplikasi Anda sangat kritis, saya akan menyarankan menggunakan operator [] karena itu membuat total 3 salinan dari objek asli yang 2 di antaranya adalah objek sementara dan cepat atau lambat dihancurkan sebagai.

Namun dalam sisipan (), 4 salinan dari objek asli dibuat dari mana 3 adalah objek sementara (tidak harus "temporer") dan dihancurkan.

Yang berarti waktu tambahan untuk: 1. Alokasi memori satu objek 2. Satu panggilan konstruktor ekstra 3. Satu panggilan destruktor tambahan 4. Satu objek memori deallokasi

Jika objek Anda besar, konstruktor adalah tipikal, destruktor melakukan banyak pembebasan sumber daya, poin di atas bahkan lebih diperhitungkan. Mengenai keterbacaan, saya pikir keduanya cukup adil.

Pertanyaan yang sama muncul di benak saya tetapi tidak terlalu mudah dibaca tetapi kecepatan. Berikut adalah contoh kode yang saya gunakan untuk mengetahui poin yang saya sebutkan.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Output saat insert () digunakan Keluaran saat operator [] digunakan

Rampal Chaudhary
sumber
4
Sekarang jalankan pengujian itu lagi dengan optimalisasi penuh diaktifkan.
antred
2
Juga, pertimbangkan apa yang sebenarnya dilakukan operator []. Pertama mencari peta untuk entri yang cocok dengan kunci yang ditentukan. Jika menemukan satu, maka ia menimpa nilai entri itu dengan yang ditentukan. Jika tidak, ia memasukkan entri baru dengan kunci dan nilai yang ditentukan. Semakin besar peta Anda, semakin lama operator [] perlu mencari peta. Pada titik tertentu, ini akan lebih dari sekadar mengganti panggilan copy c'tor tambahan (jika itu bahkan tetap dalam program akhir setelah kompiler melakukan keajaiban pengoptimalan).
antred
1
@antred, insertharus melakukan pencarian yang sama, jadi tidak ada perbedaan dari itu [](karena kunci peta unik).
Sz.
Ilustrasi yang bagus tentang apa yang terjadi dengan hasil cetak - tetapi apa yang sebenarnya dilakukan oleh 2 bit kode ini? Mengapa 3 salinan dari objek asli sama sekali diperlukan?
rbennett485
1. harus mengimplementasikan operator penugasan, atau Anda akan mendapatkan nomor yang salah di destructor 2. menggunakan std :: move ketika membangun pasangan untuk menghindari kelebihan pembuatan salinan "map.insert (std :: make_pair <int, Sample> (1, std: : move (sample)))); "
Fl0
10

Sekarang di c ++ 11 saya berpikir bahwa cara terbaik untuk memasukkan pasangan dalam peta STL adalah:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

The Hasilnya akan menjadi pasangan dengan:

  • Elemen pertama (result.first), menunjuk ke pasangan yang dimasukkan atau menunjuk ke pasangan dengan kunci ini jika kunci sudah ada.

  • Elemen kedua (result.second), benar jika penyisipan itu benar atau salah itu ada sesuatu yang salah.

PS: Jika Anda tidak perlu memesan, Anda dapat menggunakan std :: unordered_map;)

Terima kasih!

GutiMac
sumber
9

Gotcha dengan map :: insert () adalah tidak akan mengganti nilai jika kunci sudah ada di peta. Saya telah melihat kode C ++ yang ditulis oleh programmer Java di mana mereka mengharapkan insert () untuk berperilaku seperti Map.put () di Java di mana nilainya diganti.

Anthony Cramp
sumber
2

Satu catatan adalah bahwa Anda juga dapat menggunakan Boost. Tugas :

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rbbond
sumber
1

Berikut adalah contoh lain, menunjukkan bahwa operator[] menimpa nilai untuk kunci jika ada, tetapi .insert tidak menimpa nilai jika ada.

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
bobobobo
sumber
1

Ini adalah kasus yang agak terbatas, tetapi menilai dari komentar yang saya terima saya pikir itu perlu diperhatikan.

Saya pernah melihat orang di masa lalu menggunakan peta dalam bentuk

map< const key, const val> Map;

untuk menghindari kasus penimpaan nilai yang tidak disengaja, tetapi kemudian lanjutkan menulis dalam beberapa bit kode lainnya:

const_cast< T >Map[]=val;

Alasan mereka untuk melakukan ini seingat saya adalah karena mereka yakin bahwa dalam bit kode tertentu mereka tidak akan menimpa nilai peta; karenanya, maju dengan metode yang lebih 'mudah dibaca' [].

Saya tidak pernah benar-benar mengalami masalah langsung dari kode yang ditulis oleh orang-orang ini, tetapi saya sangat merasa sampai hari ini bahwa risiko - betapapun kecilnya - tidak boleh diambil ketika mereka dapat dengan mudah dihindari.

Dalam kasus di mana Anda berurusan dengan nilai peta yang benar - benar tidak boleh ditimpa, gunakan insert. Jangan membuat pengecualian hanya untuk keterbacaan.

dk123
sumber
Banyak orang yang berbeda telah menulisnya? Tentu saja menggunakan insert(bukan input), karena const_castakan menyebabkan nilai sebelumnya ditimpa, yang sangat non-const. Atau, jangan tandai tipe nilai sebagai const. (Hal semacam itu biasanya merupakan hasil akhir const_cast, jadi hampir selalu ada bendera merah yang menunjukkan kesalahan di tempat lain.)
Potatoswatter
@Potatoswatter Anda benar. Saya hanya melihat bahwa const_cast [] digunakan dengan nilai peta const oleh beberapa orang ketika mereka yakin bahwa mereka tidak akan mengganti nilai lama dalam bit kode tertentu; karena [] itu sendiri lebih mudah dibaca. Seperti yang telah saya sebutkan di bagian terakhir dari jawaban saya, saya akan merekomendasikan menggunakan insertdalam kasus di mana Anda ingin mencegah nilai ditimpa. (Baru saja mengubah inputke insert- terima kasih)
dk123
@Potatoswatter Jika saya ingat dengan benar, alasan utama yang tampaknya orang gunakan const_cast<T>(map[key])adalah 1. [] lebih mudah dibaca, 2. mereka percaya pada bit kode tertentu mereka tidak akan menimpa nilai, dan 3. mereka tidak ingin bit lain dari kode yang tidak diketahui menimpa nilai - nilai mereka - karenanya const value.
dk123
2
Saya belum pernah mendengar hal ini dilakukan; dimana anda melihat ini? Menulis const_casttampaknya lebih dari meniadakan "keterbacaan" tambahan [], dan kepercayaan semacam itu hampir cukup untuk memecat seorang pengembang. Kondisi runtime yang rumit diselesaikan dengan desain antipeluru, bukan firasat.
Potatoswatter
@Potatoswatter Saya ingat itu selama salah satu pekerjaan saya di masa lalu dalam mengembangkan game edukasi. Saya tidak pernah bisa membuat orang menulis kode untuk mengubah kebiasaan mereka. Anda benar sekali dan saya sangat setuju dengan Anda. Dari komentar Anda, saya telah memutuskan bahwa ini mungkin lebih berharga daripada jawaban asli saya dan karenanya saya memperbaruinya untuk mencerminkan hal ini. Terima kasih!
dk123
1

Fakta bahwa insert()fungsi std :: map tidak menimpa nilai yang terkait dengan kunci memungkinkan kita untuk menulis kode enumerasi objek seperti ini:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

Ini adalah masalah yang cukup umum ketika kita perlu memetakan objek non-unik yang berbeda ke beberapa id dalam rentang 0..N. Id tersebut dapat digunakan nanti, misalnya, dalam algoritma grafik. Alternatif dengan operator[]akan terlihat kurang mudah dibaca menurut saya:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
mekatroner
sumber