3

整数を指すキーとしてベクトルを取るマップがあるプログラムで、c++ STL Map および Vector クラスを使用しています。通常、マップで値を検索する場合、値が見つからない場合、myMap.find() は myMap.end() を返します。

myVector.reserve(int) を使用してベクター内のスペースを事前に割り当てようとすると (使用するたびにサイズが変更されるのを防ぐため)、問題が発生します。何らかの理由で、存在しないことがわかっているベクトルをマップで検索しても、実際にベクトルを埋めるかどうかに関係なく、検索するベクトルにスペースが割り当てられている場合は myMap.end() が返されません (例 1)。

ただし、検索したいベクターにオブジェクトを挿入するだけで、ベクターがマップにない場合に適切な myMap.end() の場所が得られます (例 2)。

例 1:

#include <map>
#include <vector>
#include <iostream>

using namespace std;

int main(){

 vector<int> v, v1;
 v.reserve(1);
 v1.reserve(1);
 v[0] = 1;
 v1[0] = 2;
 map<vector <int>, int> m;

 m.insert(make_pair(v, 0));

 cout << int(m.find(v1) == m.end());
}

0 を返します

例 2:

#include <map>
#include <vector>
#include <iostream>

using namespace std;

int main(){

 vector<int> v, v1;
 v.reserve(1);
 v[0] = 1;
 v1.push_back(5);
 map<vector <int>, int> m;

 m.insert(make_pair(v, 0));

 cout << int(m.find(v1) == m.end());
}

1 を返します

ベクター内にある程度のスペースを確保したいのですが、マップを図のように機能させる唯一の方法は、その場で要素を挿入してベクターのサイズを動的に変更することです。これは正しいです？回避策はありますか? aberrantこの（明らかな）動作について説明できる人はいますか？

4

1 に答える 1

4

まず、このコードはあなたが思っていることをしません。reserve() は resize() しません。

vector<int> v;
v.reserve(100);
v[0] = 1;  //undefined
cout << v.size(); //prints 0

もう1つの編集:これは実際には「予想される」動作であることに気付きました。最初のケースでは、予約は==、<=などのセマンティクスに影響を与えないため、vとv1の両方が空のベクトルであるためです。予約が効果的であることを理解したらセグメンテーション違反を紛らわしい動作に変えるだけなら、これは理にかなっているはずです。パフォーマンスの違いが生じることが証明されるまで、予約を使用しないことをお勧めします (時期尚早の最適化)。

<= と => とマップの説明はおそらくここでは必要ありませんが、この問題の作業に影響を与える可能性があるため、参照用に残しておきます。

第二に、マップは == であるかどうかを気にしません。彼らは物事が両方向で <= であるかどうかを気にします - これの言葉は「同等」です。例えば

Foo foo1(1);
Foo foo2(2);

map<Foo, int> m;
m.insert(makepair(foo1, 1));
m.find(foo2) == m.end(); //will be true iff foo1 <= foo2 && foo2 <= foo1
//even if foo1 != foo2 or !(foo1 == foo2)

したがって、あるクラス Foo の場合、if(foo1 <= foo2 && foo2 <= foo1) then somemap.insert(makepair(foo1, 1)); somemap.find(foo2) は、foo1 != foo2 または !(foo1 == foo2) であっても foo1 を検索します。

第二に、ベクトルの <= 演算子は何ですか? 同じサイズであり、ポイントごとに == であることをテストしていません。すべてのベクトルは「同等」であり、空のベクトルに対して両方向で <= を意味すると思いますが、よくわかりません-いずれにせよ、これが問題がある場所であるため、この動作について考えてください。

于 2012-04-20T22:28:36.917 に答える