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()orlower_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

比较这两个：

目标是找到下一个大于 key 的元素，这就是我减少 iter 的原因。原因是地图中有一些重叠的范围。

返回一个迭代器，该迭代器指向容器中的第一个元素，其键被认为在 k 之后

这意味着，upper_bound已经做了你需要的。所以不要减少迭代器。有三种极端情况：

  1. map 为空，则只有一个迭代器，即end()/ begin()。iter 的递减、递增和取消引用将给出 UB。
  2. 该映射不包含键大于您的参数的值。upper_bound将返回end()，所以不要取消引用它。
  3. 该映射仅包含键大于您的参数的值。upper_bound将返回begin()。那时你的减量是 UB，但既然它是错误的，你可以使用它并取消引用它。

所以你只需要处理前两种情况，其中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 回答