c++ - 如何正确处理 upper_bound 的迭代器

Question

我有一个 C++ 映射，称为 tableMap，是一个 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，我们有:

Return iterator to upper bound Returns an iterator pointing to the first element in the container whose key is considered to go after k.

我显然没有处理极端情况，那段代码有问题。在其他情况下我应该怎么做才能涵盖角落案件？我应该更换 upper_bound() 吗？通过 find()或 lower_bound() ？

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

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)

Answer 1

比较这两个:

The goal is to to find the next element greater than key, so that's why I'm decreasing iter. The reason was some overlapping ranges in the map.

Returns an iterator pointing to the first element in the container whose key is considered to go after k

这意味着，upper_bound 已经满足了您的需求。所以不要递减迭代器。共有三种极端情况:

1. map为空，则只有一个迭代器，即end()/begin()。 iter 的递减、递增和解引用将给出 UB。
2. map 中没有任何值的键大于您的参数。 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...
  }
}