std :: map insert atau std :: map find?

93

Dengan asumsi peta di mana Anda ingin menyimpan entri yang ada. 20% dari waktu, entri yang Anda masukkan adalah data baru. Apakah ada keuntungan melakukan std :: map :: find lalu std :: map :: insert menggunakan iterator yang dikembalikan? Atau lebih cepat untuk mencoba memasukkan dan kemudian bertindak berdasarkan apakah iterator menunjukkan rekaman itu atau tidak?

Superpolock
sumber
4
Saya telah dikoreksi dan bermaksud menggunakan std :: map :: lower_bound daripada std :: map :: find.
Superpolock

Jawaban:

148

Jawabannya adalah Anda tidak melakukan keduanya. Sebaliknya Anda ingin melakukan sesuatu yang disarankan oleh Item 24 dari STL Efektif oleh Scott Meyers :

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}
luke
sumber
2
Ini memang cara kerja find, triknya adalah menggabungkan pencarian yang dibutuhkan dengan menemukan dan menyisipkan. Tentu saja, begitu juga dengan hanya menggunakan penyisipan dan kemudian melihat nilai pengembalian kedua.
puetzk
1
Dua pertanyaan: 1) Apa perbedaan antara penggunaan lower_bound dengan penggunaan find untuk peta? 2) Untuk 'peta', bukankah ini kasus bahwa op di sebelah kanan && selalu benar ketika 'lb! = Mymap.end ()'?
Richard Corden
12
@Richard: find () mengembalikan end () jika kuncinya tidak ada, lower_bound mengembalikan posisi di mana item seharusnya (yang pada gilirannya dapat digunakan sebagai petunjuk penyisipan). @puetzek: Bukankah "masukkan saja" akan menimpa nilai referensi untuk kunci yang ada? Tidak yakin apakah OP menginginkan itu.
peterchen
2
ada yang tahu jika ada yang serupa untuk unordered_map?
Giovanni Funchal
3
@peterchen map :: insert tidak menimpa nilai yang ada jika ada, lihat cplusplus.com/reference/map/map/insert .
Chris Drew
11

Jawaban atas pertanyaan ini juga bergantung pada seberapa mahal untuk membuat tipe nilai yang Anda simpan di peta:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.first->second = v;
  }
}

Untuk tipe nilai seperti int, cara di atas akan lebih efisien daripada pencarian yang diikuti dengan penyisipan (jika tidak ada pengoptimalan compiler). Seperti yang dinyatakan di atas, ini karena pencarian melalui peta hanya dilakukan satu kali.

Namun, panggilan untuk menyisipkan mengharuskan Anda sudah memiliki "nilai" baru yang dibuat:

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.first->second = v;
  }
}

Untuk memanggil 'sisipkan' kami membayar untuk panggilan mahal untuk membangun tipe nilai kami - dan dari apa yang Anda katakan dalam pertanyaan Anda tidak akan menggunakan nilai baru ini 20% dari waktu. Dalam kasus di atas, jika mengubah tipe nilai peta bukanlah pilihan, maka lebih efisien untuk melakukan 'find' terlebih dahulu untuk memeriksa apakah kita perlu membangun elemen.

Alternatifnya, tipe nilai peta bisa diubah untuk menyimpan pegangan ke data menggunakan tipe penunjuk pintar favorit Anda. Panggilan untuk memasukkan menggunakan pointer nol (sangat murah untuk dibangun) dan hanya jika perlu tipe data baru dibangun.

Richard Corden
sumber
8

Hampir tidak akan ada perbedaan kecepatan antara 2, find akan mengembalikan iterator, insert melakukan hal yang sama dan tetap akan mencari peta untuk menentukan apakah entri tersebut sudah ada.

Jadi .. itu tergantung pada preferensi pribadi. Saya selalu mencoba memasukkan dan kemudian memperbarui jika perlu, tetapi beberapa orang tidak suka menangani pasangan yang dikembalikan.

gbjbaanb.dll
sumber
5

Saya akan berpikir jika Anda melakukan pencarian lalu memasukkan, biaya tambahannya adalah ketika Anda tidak menemukan kunci dan melakukan penyisipan setelahnya. Ini seperti melihat-lihat buku dalam urutan abjad dan tidak menemukan bukunya, lalu melihat-lihat buku lagi untuk melihat di mana harus memasukkannya. Itu intinya bagaimana Anda akan menangani kunci dan jika mereka terus berubah. Sekarang ada beberapa fleksibilitas jika Anda tidak menemukannya, Anda dapat masuk, pengecualian, melakukan apa pun yang Anda inginkan ...

PiNoYBoY82
sumber
1

Jika Anda mengkhawatirkan efisiensi, Anda mungkin ingin memeriksa hash_map <> .

Biasanya map <> diimplementasikan sebagai pohon biner. Bergantung pada kebutuhan Anda, hash_map mungkin lebih efisien.

Adam Tegen
sumber
Akan sangat senang. Tetapi tidak ada hash_map di pustaka standar C ++, dan PHB tidak mengizinkan kode di luar itu.
Superpolock
1
std :: tr1 :: unordered_map adalah peta hash yang diusulkan untuk ditambahkan ke standar berikutnya, dan harus tersedia di sebagian besar implementasi STL saat ini.
beldaz
1

Saya tampaknya tidak memiliki cukup poin untuk meninggalkan komentar, tetapi jawaban yang dicentang tampaknya panjang lebar bagi saya - ketika Anda menganggap sisipan itu mengembalikan iterator, mengapa mencari lower_bound, ketika Anda bisa menggunakan iterator yang dikembalikan. Aneh.

Stonky
sumber
1
Karena (tentu saja pra-C ++ 11) menggunakan sisipan berarti Anda masih harus membuat std::map::value_typeobjek, jawaban yang diterima bahkan menghindari itu.
KillianDS
-1

Setiap jawaban tentang efisiensi akan bergantung pada implementasi STL Anda secara tepat. Satu-satunya cara untuk mengetahui dengan pasti adalah dengan membandingkannya dengan dua cara. Saya kira perbedaannya tidak terlalu signifikan, jadi putuskan berdasarkan gaya yang Anda sukai.

Mark Ransom
sumber
1
Ini tidak sepenuhnya benar. STL tidak seperti kebanyakan pustaka lain yang menyediakan persyaratan big-O eksplisit untuk sebagian besar operasinya. Ada perbedaan yang dijamin antara 2 * O (log n) dan 1 * O (log n), terlepas dari implementasi apa yang digunakan fungsi untuk mencapai perilaku O (log n) tersebut. Apakah perbedaan itu signifikan atau tidak pada platform Anda adalah pertanyaan yang berbeda. Namun perbedaannya akan selalu ada.
srm
@srm yang mendefinisikan persyaratan big-O masih belum memberi tahu Anda berapa lama sebuah operasi akan berlangsung secara absolut. Perbedaan terjamin yang Anda bicarakan tidak ada.
Tandai Tebusan
-2

map [key] - biarkan stl memilahnya. Itu mengkomunikasikan niat Anda dengan paling efektif.

Ya, cukup adil.

Jika Anda melakukan pencarian dan kemudian memasukkan Anda melakukan 2 x O (log N) ketika Anda kehilangan karena pencarian hanya memberi tahu Anda jika Anda tidak perlu memasukkan ke tempat yang harus disisipkan (lower_bound mungkin membantu Anda di sana) . Hanya sisipan lurus dan kemudian memeriksa hasilnya adalah cara yang saya inginkan.


sumber
Tidak, jika entri tersebut ada, ia mengembalikan referensi ke entri yang sudah ada.
Kris Kumler
2
-1 untuk jawaban ini. Seperti yang dikatakan Kris K, menggunakan map [key] = value akan menimpa entri yang sudah ada, bukan "menyimpannya" seperti yang diminta dalam pertanyaan. Anda tidak dapat menguji keberadaan menggunakan map [key], karena itu akan mengembalikan objek bawaan yang dibangun jika kunci tidak ada, dan membuatnya sebagai entri untuk kunci
netjeff
Intinya adalah untuk menguji apakah peta sudah diisi dan hanya menambah / menimpa jika tidak ada. Menggunakan map [key] mengasumsikan nilainya sudah selalu ada.
srm