101

既存のエントリを保持したいマップを想定しています。20% の確率で、挿入するエントリは新しいデータです。返されたイテレータを使用して std::map::find を実行してから std::map::insert を実行する利点はありますか? それとも、挿入を試みてから、反復子がレコードが挿入されたかどうかを示しているかどうかに基づいて処理するほうが速いですか?

4

8 に答える 8

154

答えは、どちらもしないということです。代わりに、 Scott Meyersによる効果的な STLの項目 24 で提案されていることを実行したいと考えています。

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
}
于 2008-09-19T13:52:25.413 に答える
13

この質問への答えは、マップに格納している値型を作成するのにどれだけの費用がかかるかにも依存します。

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;
  }
}

intなどの値型の場合、上記は、検索の後に挿入を行うよりも効率的です（コンパイラーの最適化がない場合）。前述のように、これはマップの検索が1回だけ行われるためです。

ただし、insertを呼び出すには、新しい「値」がすでに作成されている必要があります。

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;
  }
}

'insert'を呼び出すために、値型を構築するための高額な呼び出しにお金を払っています。質問で言ったことから、この新しい値を20％使用することはありません。上記の場合、マップ値タイプを変更するオプションがない場合は、最初に「検索」を実行して、要素を作成する必要があるかどうかを確認する方が効率的です。

または、マップの値タイプを変更して、お気に入りのスマートポインタータイプを使用してデータへのハンドルを格納することもできます。insertの呼び出しでは、nullポインター（作成が非常に安価）が使用され、必要な場合にのみ新しいデータ型が作成されます。

于 2008-09-19T11:09:50.743 に答える
8

2 つの間に速度の違いはほとんどありません。find はイテレータを返し、insert は同じことを行い、とにかくマップを検索して、エントリが既に存在するかどうかを判断します。

だから..それは個人的な好みにかかっています。私は常に挿入してから必要に応じて更新しようとしますが、返されたペアの処理を好まない人もいます。

于 2008-09-18T21:17:26.610 に答える
5

検索してから挿入すると、キーが見つからず、後で挿入を実行すると、追加のコストがかかると思います。それは、本をアルファベット順に見て、本が見つからず、次に本をもう一度見て、どこに挿入するかを確認するようなものです. 要するに、キーをどのように処理するか、およびキーが常に変化しているかどうかにかかっています。見つからない場合は、ログに記録したり、例外を作成したり、好きなことをしたりできるという点で、ある程度の柔軟性があります...

于 2008-09-18T21:24:42.227 に答える
1

コメントを残すのに十分なポイントがないようですが、チェックされた答えは私には長い間巻き込まれているようです-とにかく挿入がイテレータを返すことを考えると、返されたイテレータを使用できるのに、なぜlower_boundを検索するのですか？変。

于 2011-07-28T06:47:05.877 に答える
1

効率が気になる場合は、hash_map<>を確認してください。

通常、map<> はバイナリ ツリーとして実装されます。必要に応じて、hash_map の方が効率的です。

于 2008-09-18T21:26:30.957 に答える
-1

効率に関する答えは、STL の正確な実装によって異なります。確実に知る唯一の方法は、両方の方法でベンチマークすることです。違いはそれほど大きくないと思いますので、好みのスタイルに基づいて決定してください。

于 2008-09-18T21:21:27.287 に答える
-2

map[ key ] - stl で整理します。それがあなたの意図を最も効果的に伝えることです。

ええ、十分に公平です。

検索を行ってから挿入を行うと、ミスが発生したときに 2 x O(log N) を実行していることになります。 . まっすぐに挿入してから結果を調べるのが私のやり方です。

于 2008-09-18T21:19:43.563 に答える