Apa cara yang disukai / idiomatik untuk dimasukkan ke dalam peta?

113

Saya telah mengidentifikasi empat cara berbeda untuk memasukkan elemen ke dalam std::map:

std::map<int, int> function;

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

Manakah dari itu yang lebih disukai / cara idiomatik? (Dan apakah ada cara lain yang belum saya pikirkan?)

fredoverflow
sumber
26
Peta Anda harus disebut "jawaban", bukan "fungsi"
Vincent Robert
2
@ Vincent: Hm? Fungsi pada dasarnya adalah peta antara dua set.
fredoverflow
7
@FredOverflow: sepertinya komentar Vincent agak bercanda tentang buku tertentu ...
Victor Sorokin
1
Tampaknya bertentangan dengan aslinya - 42 tidak bisa sekaligus menjadi jawaban untuk (a) kehidupan, alam semesta dan segalanya, dan (b) tidak ada. Tapi kemudian bagaimana Anda mengekspresikan kehidupan, alam semesta, dan segala sesuatu sebagai int?
Stuart Golodetz
19
@sgolodetz Anda dapat mengekspresikan semuanya dengan int yang cukup besar.
Yakov Galka

Jawaban:

90

Pertama-tama, operator[]dan insertfungsi anggota tidak setara secara fungsional:

  • Ini operator[]akan mencari kunci, memasukkan nilai bawaan yang dibangun jika tidak ditemukan, dan mengembalikan referensi yang Anda tetapkan nilai. Jelas, ini bisa menjadi tidak efisien jika mapped_typebisa mendapatkan keuntungan dari langsung diinisialisasi daripada default dibangun dan ditetapkan. Metode ini juga tidak memungkinkan untuk menentukan apakah penyisipan benar-benar terjadi atau jika Anda hanya menimpa nilai untuk kunci yang dimasukkan sebelumnya
  • Fungsi insertanggota tidak akan berpengaruh jika kunci sudah ada di peta dan, meskipun sering dilupakan, mengembalikan std::pair<iterator, bool>mana yang menarik (terutama untuk menentukan apakah penyisipan benar-benar telah dilakukan).

Dari semua kemungkinan yang terdaftar untuk menelepon insert, ketiganya hampir setara. Sebagai pengingat, mari kita lihat inserttanda tangan dalam standar:

typedef pair<const Key, T> value_type;

  /* ... */

pair<iterator, bool> insert(const value_type& x);

Jadi, bagaimana ketiga panggilan itu berbeda?

  • std::make_pairbergantung pada pengurangan argumen template dan dapat (dan dalam hal ini akan ) menghasilkan sesuatu dengan tipe yang berbeda dari yang sebenarnya value_typedari peta, yang akan membutuhkan panggilan tambahan ke std::pairkonstruktor template untuk mengonversi ke value_type(yaitu: menambahkan constke first_type)
  • std::pair<int, int>juga akan membutuhkan panggilan tambahan ke konstruktor template std::pairuntuk mengubah parameter menjadi value_type(yaitu: menambahkan constke first_type)
  • std::map<int, int>::value_typesama sekali tidak menyisakan tempat untuk keraguan karena secara langsung tipe parameter yang diharapkan oleh insertfungsi anggota.

Pada akhirnya, saya akan menghindari penggunaan operator[]jika tujuannya adalah untuk memasukkan, kecuali jika tidak ada biaya tambahan dalam membangun dan menetapkan secara default mapped_type, dan bahwa saya tidak peduli tentang menentukan apakah kunci baru telah dimasukkan secara efektif. Saat menggunakan insert, membuat a value_typemungkin adalah cara yang tepat.

icecrime.dll
sumber
apakah konversi dari Key ke const Key di make_pair () benar-benar meminta pemanggilan fungsi lain? Tampaknya cast implisit sudah mencukupi, compiler mana yang akan senang melakukannya.
galaktika
99

Mulai C ++ 11, Anda memiliki dua opsi tambahan utama. Pertama, Anda dapat menggunakan insert()sintaks inisialisasi dengan daftar:

function.insert({0, 42});

Ini secara fungsional setara dengan

function.insert(std::map<int, int>::value_type(0, 42));

tetapi jauh lebih ringkas dan mudah dibaca. Seperti jawaban lain telah dicatat, ini memiliki beberapa keunggulan dibandingkan bentuk lain:

  • The operator[]Pendekatan membutuhkan jenis dipetakan menjadi dialihkan, yang tidak selalu terjadi.
  • The operator[]pendekatan dapat menimpa elemen yang ada, dan memberikan Anda ada cara untuk mengetahui apakah hal ini terjadi.
  • Bentuk lain insertyang Anda daftarkan melibatkan jenis konversi implisit, yang dapat memperlambat kode Anda.

Kelemahan utama adalah bahwa formulir ini biasanya memerlukan kunci dan nilai agar dapat disalin, sehingga tidak akan berfungsi dengan misalnya peta dengan unique_ptrnilai. Itu telah diperbaiki dalam standar, tetapi perbaikannya mungkin belum mencapai implementasi perpustakaan standar Anda.

Kedua, Anda dapat menggunakan emplace()metode ini:

function.emplace(0, 42);

Ini lebih ringkas daripada bentuk apapun insert(), bekerja dengan baik dengan tipe yang hanya bergerak seperti unique_ptr, dan secara teoritis mungkin sedikit lebih efisien (walaupun kompiler yang layak harus mengoptimalkan perbedaannya). Satu-satunya kelemahan utama adalah ini mungkin sedikit mengejutkan pembaca Anda, karena emplacemetode biasanya tidak digunakan seperti itu.

Geoff Romer
sumber
8
ada juga insert_or_assign dan try_emplace baru
sp2danny
11

Versi pertama:

function[0] = 42; // version 1

mungkin atau mungkin tidak memasukkan nilai 42 ke dalam peta. Jika kunci tersebut 0ada, maka kunci tersebut akan menetapkan 42 ke kunci itu, menimpa nilai apa pun yang dimiliki kunci itu. Jika tidak, itu akan memasukkan pasangan kunci / nilai.

Fungsi sisipan:

function.insert(std::map<int, int>::value_type(0, 42));  // version 2
function.insert(std::pair<int, int>(0, 42));             // version 3
function.insert(std::make_pair(0, 42));                  // version 4

di sisi lain, jangan lakukan apa pun jika kunci 0sudah ada di peta. Jika kunci tidak ada, itu akan memasukkan pasangan kunci / nilai.

Ketiga fungsi sisipan hampir identik. std::map<int, int>::value_typeadalah typedefuntuk std::pair<const int, int>, dan std::make_pair()jelas menghasilkan std::pair<>sihir deduksi melalui template. Namun, hasil akhirnya harus sama untuk versi 2, 3, dan 4.

Yang mana yang akan saya gunakan? Saya pribadi lebih suka versi 1; itu ringkas dan "alami". Tentu saja, jika perilaku penimpaannya tidak diinginkan, maka saya lebih suka versi 4, karena ini membutuhkan lebih sedikit pengetikan daripada versi 2 dan 3. Saya tidak tahu apakah ada satu cara de facto untuk memasukkan pasangan kunci / nilai ke dalam std::map.

Cara lain untuk memasukkan nilai ke dalam peta melalui salah satu konstruktornya:

std::map<int, int> quadratic_func;

quadratic_func[0] = 0;
quadratic_func[1] = 1;
quadratic_func[2] = 4;
quadratic_func[3] = 9;

std::map<int, int> my_func(quadratic_func.begin(), quadratic_func.end());
In silico
sumber
5

Jika Anda ingin menimpa elemen dengan kunci 0

function[0] = 42;

Jika tidak:

function.insert(std::make_pair(0, 42));
Viktor Sehr
sumber
5

Karena C ++ 17 std::map menawarkan dua metode penyisipan baru: insert_or_assign()dan try_emplace(), seperti juga disebutkan dalam komentar oleh sp2danny .

insert_or_assign()

Pada dasarnya, insert_or_assign()ini adalah versi yang "ditingkatkan" dari operator[]. Berbeda dengan operator[], insert_or_assign()tidak mengharuskan tipe nilai peta menjadi dapat dibangun secara default. Misalnya, kode berikut tidak dapat dikompilasi, karena MyClasstidak memiliki konstruktor default:

class MyClass {
public:
    MyClass(int i) : m_i(i) {};
    int m_i;
};

int main() {
    std::map<int, MyClass> myMap;

    // VS2017: "C2512: 'MyClass::MyClass' : no appropriate default constructor available"
    // Coliru: "error: no matching function for call to 'MyClass::MyClass()"
    myMap[0] = MyClass(1);

    return 0;
}

Namun, jika Anda mengganti myMap[0] = MyClass(1);dengan baris berikut, maka kode akan terkompilasi dan penyisipan berlangsung seperti yang diinginkan:

myMap.insert_or_assign(0, MyClass(1));

Selain itu, mirip dengan insert(), insert_or_assign()mengembalikan a pair<iterator, bool>. Nilai Boolean adalah truejika penyisipan terjadi dan falsejika tugas telah selesai. Iterator menunjuk ke elemen yang disisipkan atau diperbarui.

try_emplace()

Mirip dengan di atas, try_emplace()merupakan "perbaikan" dari emplace(). Berbeda dengan emplace(), try_emplace()tidak mengubah argumennya jika penyisipan gagal karena kunci sudah ada di peta. Misalnya, kode berikut mencoba untuk menempatkan elemen dengan kunci yang sudah disimpan di peta (lihat *):

int main() {
    std::map<int, std::unique_ptr<MyClass>> myMap2;
    myMap2.emplace(0, std::make_unique<MyClass>(1));

    auto pMyObj = std::make_unique<MyClass>(2);    
    auto [it, b] = myMap2.emplace(0, std::move(pMyObj));  // *

    if (!b)
        std::cout << "pMyObj was not inserted" << std::endl;

    if (pMyObj == nullptr)
        std::cout << "pMyObj was modified anyway" << std::endl;
    else
        std::cout << "pMyObj.m_i = " << pMyObj->m_i <<  std::endl;

    return 0;
}

Output (setidaknya untuk VS2017 dan Coliru):

pMyObj tidak disisipkan
pMyObj tetap dimodifikasi

Seperti yang Anda lihat, pMyObjtidak lagi menunjuk ke objek aslinya. Namun, jika Anda mengganti auto [it, b] = myMap2.emplace(0, std::move(pMyObj));dengan kode berikut, maka keluarannya terlihat berbeda, karena pMyObjtetap tidak berubah:

auto [it, b] = myMap2.try_emplace(0, std::move(pMyObj));

Keluaran:

pMyObj tidak dimasukkan
pMyObj pMyObj.m_i = 2

Kode di Coliru

Harap diperhatikan: Saya mencoba membuat penjelasan saya sesingkat dan sesederhana mungkin agar sesuai dengan jawaban ini. Untuk penjelasan yang lebih tepat dan komprehensif, saya sarankan membaca artikel tentang Fluent C ++ ini .

membunyikan
sumber
3

Saya telah menjalankan beberapa perbandingan waktu antara versi yang disebutkan di atas:

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

Ternyata perbedaan waktu antara versi sisipan sangat kecil.

#include <map>
#include <vector>
#include <boost/date_time/posix_time/posix_time.hpp>
using namespace boost::posix_time;
class Widget {
public:
    Widget() {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = 1.0;
        }
    }
    Widget(double el)   {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = el;
        }
    }
private:
    std::vector<double> m_vec;
};


int main(int argc, char* argv[]) {



    std::map<int,Widget> map_W;
    ptime t1 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));
    }
    ptime t2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff = t2 - t1;
    std::cout << diff.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_2;
    ptime t1_2 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_2.insert(std::make_pair(it,Widget(2.0)));
    }
    ptime t2_2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_2 = t2_2 - t1_2;
    std::cout << diff_2.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_3;
    ptime t1_3 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_3[it] = Widget(2.0);
    }
    ptime t2_3 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_3 = t2_3 - t1_3;
    std::cout << diff_3.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_0;
    ptime t1_0 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));
    }
    ptime t2_0 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_0 = t2_0 - t1_0;
    std::cout << diff_0.total_milliseconds() << std::endl;

    system("pause");
}

Ini memberikan masing-masing untuk versi (saya menjalankan file 3 kali, maka 3 perbedaan waktu berturut-turut untuk masing-masing):

map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));

2198 md, 2078 md, 2072 md

map_W_2.insert(std::make_pair(it,Widget(2.0)));

2290 md, 2037 md, 2046 md

 map_W_3[it] = Widget(2.0);

2592 ms, 2278 ms, 2296 ms

 map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));

2234 md, 2031 md, 2027 md

Oleh karena itu, hasil antara versi sisipan yang berbeda dapat diabaikan (meskipun tidak melakukan uji hipotesis)!

The map_W_3[it] = Widget(2.0);Versi memakan waktu sekitar 10-15% lebih banyak waktu untuk contoh ini disebabkan oleh inisialisasi dengan konstruktor default untuk Widget.

pengguna3116431
sumber
2

Singkatnya, []operator lebih efisien untuk memperbarui nilai karena melibatkan pemanggilan konstruktor default dari tipe nilai dan kemudian menetapkan nilai baru, sementara insert()lebih efisien untuk menambahkan nilai.

Potongan kutipan dari STL Efektif: 50 Cara Khusus untuk Meningkatkan Penggunaan Anda dari Perpustakaan Templat Standar oleh Scott Meyers, Butir 24 mungkin membantu.

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator
insertKeyAndValue(MapType& m, const KeyArgType&k, const ValueArgType& v)
{
    typename MapType::iterator lb = m.lower_bound(k);

    if (lb != m.end() && !(m.key_comp()(k, lb->first))) {
        lb->second = v;
        return lb;
    } else {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k, v));
    }
}

Anda dapat memutuskan untuk memilih versi bebas-pemrograman-generik ini, tetapi intinya adalah saya menemukan paradigma ini (membedakan 'tambah' dan 'perbarui') sangat berguna.

galaktika
sumber
1

Jika Anda ingin menyisipkan elemen dalam fungsi std :: map - gunakan insert (), dan jika Anda ingin mencari elemen (dengan kunci) dan menetapkan beberapa ke dalamnya - gunakan operator [].

Untuk menyederhanakan penyisipan gunakan pustaka boost :: assign, seperti ini:

using namespace boost::assign;

// For inserting one element:

insert( function )( 0, 41 );

// For inserting several elements:

insert( function )( 0, 41 )( 0, 42 )( 0, 43 );
Denis Shevchenko
sumber
1

Saya hanya mengubah masalah sedikit (peta string) untuk menunjukkan minat lain untuk memasukkan:

std::map<int, std::string> rancking;

rancking[0] = 42;  // << some compilers [gcc] show no error

rancking.insert(std::pair<int, std::string>(0, 42));// always a compile error

fakta bahwa kompilator tidak menunjukkan kesalahan pada "rancking [1] = 42;" dapat memiliki dampak yang menghancurkan!

jo_
sumber
Kompiler tidak menampilkan kesalahan untuk yang pertama karena std::string::operator=(char)ada, tetapi mereka menunjukkan kesalahan untuk yang terakhir karena konstruktornya std::string::string(char)tidak ada. Ini seharusnya tidak menghasilkan kesalahan karena C ++ selalu bebas menafsirkan setiap bilangan bulat-gaya literal sebagai char, jadi ini bukan bug compiler, tetapi merupakan kesalahan programmer. Pada dasarnya, saya hanya mengatakan bahwa apakah itu memperkenalkan bug dalam kode Anda atau tidak adalah sesuatu yang harus Anda perhatikan sendiri. BTW, Anda dapat mencetak rancking[0]dan kompiler menggunakan ASCII akan mengeluarkan *, yaitu (char)(42).
Keith M