18

マップの挿入には2つの方法があります。

m[key] = val;

または

m.insert(make_pair(key, val));

私の質問は、どちらの操作が速いかということです。STL標準では、最初に「キー」がマップに存在しない場合はデフォルト要素を「挿入」し、次に「val」をデフォルト要素に割り当てるため、通常、最初の要素は遅いと言われます。

しかし、「make_pair」があるため、2番目の方法の方が優れているとは思いません。make_pairは、実際には、と比較して「ペア」を作成するための便利な方法pair<T1, T2>(key, val)です。とにかく、どちらも2つの割り当てを行います。1つは「key」を「pair.first」に割り当て、2つは「val」を「pair.second」に割り当てます。ペアが作成された後、mapは「pair.second」で初期化された要素を挿入します。

したがって、最初の方法は1です。' default construct of typeof(val)'2.割り当て2番目の方法は1です。割り当て2.' copy construct of typeof(val)'

4

6 に答える 6

20

どちらも異なることを達成します。 

m[key] = val;

がまだ存在しない場合は新しいキーと値のペアを挿入しますkey。または、がすでに存在する場合は、マップされた古い値を上書きしますkey。 

m.insert(make_pair(key, val));

ペアkeyがまだ存在しない場合にのみ挿入され、古い値が上書きされることはありません。だから、あなたが達成したいことに応じて選択してください。
より効率的な質問については、プロファイル。：Pおそらく私が言う最初の方法です。割り当て（別名コピー）は両方の方法に当てはまるため、唯一の違いは構造にあります。誰もが知っているように、実装する必要がありますが、デフォルトの構造は基本的にノーオペレーションである必要があり、したがって非常に効率的です。コピーはまさにそれです-コピー。つまり、方法1では「no-op」とコピーを取得し、方法2では2つのコピーを取得します。
編集：最後に、プロファイリングの内容を信頼してください。@Matthieuが彼のコメントで述べているように私の分析はずれていましたが、それは私の推測でした。:)

次に、C ++ 0xが登場し、ペアを簡単に移動できるようになったため、2番目の方法でのダブルコピーは不要になります。結局のところ、それは私の最初のポイントに戻っていると思います。あなたがやりたいことを達成するために正しい方法を使用してください。

于 2011-04-17T07:39:50.920 に答える
7

十分なメモリを備えた負荷の少ないシステムでは、次のコードを使用します。

#include <map>
#include <iostream>
#include <ctime>
#include <string>

using namespace std;

typedef map <unsigned int,string> MapType;
const unsigned int NINSERTS = 1000000;

int main() {
    MapType m1;
    string s = "foobar";
    clock_t t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m1[i] = s;
    }
    cout << clock() - t << endl;
    MapType m2;
    t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m2.insert( make_pair( i, s ) );
    }
    cout << clock() - t << endl;
}

生成：

1547
1453

または繰り返し実行の同様の値。したがって、挿入は（この場合）わずかに高速です。

于 2011-04-17T09:48:46.117 に答える
2

パフォーマンスに関しては、一般的にほとんど同じだと思います。大きなオブジェクトを含むマップにはいくつかの例外がある場合があります。その場合は、[]を使用するか、「挿入」よりも少ない一時オブジェクトを作成するemplaceを使用する必要があります。詳細については、こちらの説明を参照してください。

ただし、挿入演算子で「ヒント」関数を使用すると、特別な場合にパフォーマンスが向上する可能性があります。だから、ここからオプション2を見てください：

iterator insert (const_iterator position, const value_type& val);

適切なヒントを提供すれば、「挿入」操作を（log（n）から）一定時間に短縮できます（マップの後ろに何かを追加していることがわかっている場合によくあります）。

于 2015-04-22T18:37:48.437 に答える
0

相対的なパフォーマンスは、コピーされるオブジェクトのタイプ（サイズ）にも依存することを指摘して、分析を改善する必要があります。

（int-> set）のマップを使用して（nbtに対して）同様の実験を行いました。私はそれがひどいことであることを知っていますが、このシナリオの実例です。「値」（この場合はintのセット）には、20個の要素が含まれています。

[]=Vsを100万回繰り返します。操作を挿入し、RDTSC/iter-countを実行します。

[]=セット| 10731サイクル

insert（make_pair <>）| 26100サイクル

コピーによって追加されたペナルティの大きさを示しています。もちろん、CPP11（move ctor's）は状況を変えます。

于 2014-11-20T21:33:19.307 に答える
0

私の見解：マップはバランスの取れた二分木であり、ほとんどの変更とチェックはO（logN）を使用することを思い出してください。

あなたが解決しようとしている問題に本当に依存します。

1）まだ存在しないことを認識して値を挿入するだけの場合、[]は2つのことを行います。a）アイテムが存在するかどうかを確認します。b）存在しない場合はペアを作成し、挿入する処理を実行します。 （O（logN）のdouble work）なので、insertを使用します。

2）そこにあるかどうかわからない場合は、a）上記の数行のif（map.find（item）== mp.end（））のようにして、アイテムがそこにあるかどうかを確認した場合どこかで、挿入を使用します。二重の作業のために[]が実行されますb）チェックしなかった場合は、依存します。挿入が存在する場合は値を変更しません。

于 2017-03-15T01:24:39.833 に答える
0

私の答えは、効率ではなく、挿入アルゴリズムの選択に関連する安全性に関するものです。

[]and呼び出しは、要素のinsert()デストラクタをトリガーします。たとえば、デストラクタが内部で重大な動作をしている場合、これは危険な副作用をもたらす可能性があります。

そのような危険の後で、私はSTLの暗黙のレイジー挿入機能に依存するのをやめ、オブジェクトがctors/dtorsで動作するかどうかを常に明示的にチェックします。

この質問を参照してください： オブジェクトをstd::listに追加するときにデストラクタがオブジェクトを呼び出しました

于 2019-09-19T07:45:32.543 に答える