0

私は、tableMap と呼ばれる C++ マップを持っていstd::map<int, std::string>ます。

void processMap(int key) {
  std::map<int, std::string>::const_iterator iter;
  while (true) {
     // key is an argument to the function
     iter = tableMap.upper_bound(key);
     --iter;
     std::string value = iter->second;
     // do something else  
     ...
  }
}

ポイントは、upper_bound関数呼び出しを正しく処理していないことです。また、私はそれを確認することはできません

if (iter != tableMap.end())

キーが最後の要素にある場合、upper_boundが返されるためend()です。C++APIから、次の情報が得られます。

反復子を上限に戻す コンテナ内でキーが k の後にあると見なされる最初の要素を指す反復子を返します。

私は明らかにコーナーケースを扱っていません。そのコードにはバグがあります。コーナーケースをカバーするために他に何をすべきですか? またはに置き換える必要がありupper_bound()ますfind()かlower_bound()？

目標は、 より大きい次の要素を見つけることです。keyそのため、 を減らしてiterいます。その理由は、マップ内の一部の範囲が重複していたためです。

Program received signal SIGSEGV, Segmentation fault.
0x0000003d3ba69eea in std::_Rb_tree_decrement(std::_Rb_tree_node_base*) () from /usr/lib64/libstdc++.so.6
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.47.el6_2.5.x86_64 keyutils-libs-1.4-4.el6.x86_64 krb5-libs-1.8.2-3.el6_0.3.x86_64 libcom_err-1.41.12-3.el6.x86_64 libgcc-4.4.6-3.el6.x86_64 libibverbs-1.1.5mlnx1-1.32.gc42bcbf.x86_64 libselinux-2.0.94-2.el6.x86_64 libstdc++-4.4.6-3.el6.x86_64 openssl-1.0.0-4.el6_0.2.x86_64 pcre-7.8-3.1.el6.x86_64 zlib-1.2.3-27.el6.x86_64
(gdb) bt
#0  0x0000003d3ba69eea in std::_Rb_tree_decrement(std::_Rb_tree_node_base*) () from /usr/lib64/libstdc++.so.6
#1  0x0000000000da8a41 in std::_Rb_tree_const_iterator<int, std::string >::operator-- (this=0x7fffffffb8b0)
    at /usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/bits/stl_tree.h:274
#2  0x0000000000de18db in processMap (
    this=0x17107b8,key=0)
4

1 に答える 1

3

次の 2 つを比較してください。

目標は、 key より大きい次の要素を見つけることです。そのため、 iter を減らしています。その理由は、マップ内の一部の範囲が重複していたためです。

キーが k の後にあると見なされるコンテナー内の最初の要素を指す反復子を返します。

つまり、upper_boundすでに必要なことを行っています。したがって、イテレータをデクリメントしないでください。3 つのコーナー ケースがあります。

  1. マップは空で、イテレータは 1 つだけ、つまりend()/begin()です。iter のデクリメント、インクリメント、逆参照は UB を与えます。
  2. マップには、引数より大きいキーを持つ値が含まれていません。upper_boundを返すend()ので、逆参照しないでください。
  3. マップには、引数より大きいキーを持つ値のみが含まれます。upper_bound戻りbegin()ます。あなたのデクリメントはUBですが、とにかく間違っているので、それを使用して逆参照することができます。

したがって、最初の 2 つのケースのみを処理する必要がありupper_boundますend()。

void processMap(int key) {
  while (true) {
     auto iter = tableMap.upper_bound(key);
     if (iter == tableMap.end())
       break; //there is no entry with a greater key

     // use iter...
  }
}
于 2013-06-10T07:23:27.630 に答える