0

問題のstdmapでcharをキーとして使用する場合は、カスタム比較関数/ファンクターを使用することをお勧めします。

struct cmp_str
{
   bool operator()(char const *a, char const *b)
   {
      return std::strcmp(a, b) < 0;
   }
};

map<char *, int, cmp_str> BlahBlah;

これにより、マップはキーAがキーBより小さいかどうかを検出できます。ただし、たとえば、 map <> :: find（）は、要素が見つからない場合はendを返し、要素が見つかった場合はそれを繰り返します。したがって、マップは、未満だけでなく、同等性についても認識しています。どのように？

4

3 に答える 3

7

2つのキーの等式条件aとbはそれa<bでありb<a、両方とも偽です。マップ自体は通常、平衡二分木*として実装されるため、一致する要素が見つかるまで、ルートノードからマップをトラバースするために小なりの比較が使用されます。キーを検索する場合k、比較がfalseである最初の要素が見つかるまで、未満の比較が使用されます。逆比較も偽の場合、kが見つかりました。それ以外の場合kは、マップにありません。マップは、この目的に対する未満の比較のみを使用します。

std::setまた、まったく同じメカニズムを使用していることにも注意してください。唯一の違いは、各要素が独自のキーであるということです。

*厳密に言えば、C ++標準ではstd::map、バランスの取れたバイナリツリーであるとは指定されていませんが、挿入やルックアップなどの操作に課せられる複雑さの制約により、実装は赤黒木などの構造を選択します。

于 2012-09-08T14:43:31.760 に答える
3

同等性/operator==は次の関数として表すことができますoperator<：

bool operator==(T left, T right) {
  return !(left < right) && !(right < left);
}
于 2012-09-08T14:44:33.830 に答える
3

これは、マップのコンパレータが、などの厳密な弱順序を実装する必要があるため<です。

このような関係の数学的特性の1つは反対称関係です。これは、任意のxとy、の場合、not (x < y)およびをnot (y < x)意味することを示しx == yます。

したがって、検索しているキーよりも小さく比較されない最初の要素を見つけた後、実装はその要素がより大きく比較されるかどうかをチェックするだけであり、それが小さくも大きくもない場合は、等しくなければなりません。

于 2012-09-08T15:00:41.313 に答える