マップ内のキーを見つけ

Question

私は私のように宣言したマップは、次のしている、しかし

int x; cin>>x; 
index[x]=true; 

cout<<index[y]; // for any number y not inインデックスgives me 0

1. マップに存在しないキーをチェックするときに値0を取得すると、キーがマップに存在するかどうかをどのようにして確実に知ることができますか？
2. 2つのセットが互いに素であるかどうかを調べるためにマップを使用しています。同じものについては、マップを使用していて、入力を格納する2つのベクトルを使用しています。これはどんな形でも手荒れですか？私が使っているはずの他のデータ構造ですか？

Answer 1

if (index.find(key) == index.end())を使用して、キーが存在するかどうかを判断できます。 index[key]を使用してデフォルト・構築、新しい値を（このケースでは、あなたがbool()を呼び出し、それが0として印刷されます。）新たに構築された値は、マップに挿入されます（つまり、index[key]はindex.insert(std::make_pair(key, bool())にこの場合は同じである。）

同じデータに対して2つのデータ構造を使用することはOKです。しかし、マップを使用する必要はありますか？ユースケースでは十分なセットではないでしょうか？私。 keyがpresentの場合、値はtrueです。そうでない場合はfalseです。

Answer 2

map::findを使用してください。

Answer 3

1、index.count(y)を使用してください。それはindex.find(y) != index.end()よりも簡潔であり、それは整数1または0であることを除いて、もちろん!=はあなたにブールを与えます。

multimapの場合、countがmapよりも効率が悪い可能性があるという欠点は、複数のエントリを数えなければならない可能性があるためです。 multimapを使用していないため、問題はありません。

2、両方のベクトルをソートしてstd::set_intersectionを使用することもできますが、交差点が空であるかどうか気になる場合は完璧にフィットしません。入力がどこにあるかによって、両方のベクトルを取り除くことができ、入力の最初のロードから行くときにmapを作成し、2番目の入力のロードの各要素をそれに対してチェックすることができます。最後にmapの代わりにsetを使用してください。

Answer 4

1. あなたは（唯一の可能なインデックス項目のreasonnably小さな範囲のために理にかなって、ビットマップを使用してもいいかもしれませんindex.find(key) != index.end()または
2. index.count(key) > 0が索引項目の範囲に応じて、使用することができます。あることのためのチェックを行いますマップの代わりにセットを使用してください（マップは、実際には必要でない追加のブールを格納します）。セットはまた、（std::setとして与えられた）2セットが互いに素であるかどうかを確認するには方法count(key)とfind(key)

Answer 5

を提供しています、あなたは、単に彼らの交点を計算することができます。

std::set<T> X, Y; // populate 
std::set<T> I; 

std::set_difference(X.begin(), X.end(), y.begin(), y.end(), std::back_inserter(I)); 

const bool disjoint = I.empty(); 

あなたのコンテナはstd::setのない場合は、範囲が順序付けされていることを確認する必要があります。

あなたがより効率的になりたい場合は、あなたがset_intersectionためalgorithmを実装することができますし、共通の要素を持っていたら停止：

template <typename Iter1, typename Iter2> 
bool disjoint(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) 
{ 
    while (first1 != last1 && first2 != last2) 
    { 
    if (*first1 < *first2) ++first1; 
    else if (*first2 < *first1) ++first2; 
    else { return false; } 
    } 
    return true; 
}