c++ - gcc 的 std::unordered_map 中的 SEGV

Question

我在 gcc 4.7.2 的 unordered_map 中遇到了 SEGV

在 find() 中它调用 _M_find_node，后者又调用 _M_find_before_node，传入 bucket number ，我们正在搜索的 key ，以及哈希码。

在 _M_find_before_node 中，它查找相关桶中的第一个节点:

_BaseNode* __prev_p = _M_buckets[__n];

然后获取以下节点:

_Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);

问题是__prev_p->_M_nxt为空；并且 _M_equals 尝试取消引用它并导致段错误。

我不是 100% 了解 unordered_map 的内部工作原理 - 是否要求桶的 _M_nxt 中的第一个节点是非空的，或者这是一个错误吗？

有问题的代码在这里:

  // Find the node whose key compares equal to k in the bucket n. Return nullptr
  // if no node is found.
  template<typename _Key, typename _Value,
       typename _Allocator, typename _ExtractKey, typename _Equal,
       typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
       bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
            _Equal, _H1, _H2, _Hash, _RehashPolicy,
            __chc, __cit, __uk>::_BaseNode*
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
           _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_find_before_node(size_type __n, const key_type& __k,
            typename _Hashtable::_Hash_code_type __code) const
    {
      _BaseNode* __prev_p = _M_buckets[__n];
      if (!__prev_p)
    return nullptr;
      _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); // __p is null here!!
      for (;; __p = __p->_M_next())
    {
      if (this->_M_equals(__k, __code, __p))
        return __prev_p;
      if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
        break;
      __prev_p = __p;
    }
      return nullptr;
    }

Answer 1

I'm not 100% clued up on the inner workings of unordered_map - is it a requirement that the first node in a bucket's _M_nxt be non-null, or is this a bug?

这个问题显然特定于 GCC 的实现，但我很确定如果 _M_buckets[__n] 是非空的，那么 _M_buckets[__n]->_M_nxt也应该是非空的。

即如果桶为空则 _M_buckets[__n]==nullptr，如果桶非空则 _M_buckets[__n]->_M_nxt 是桶中的第一个节点.

尝试使用 -D_GLIBCXX_DEBUG 构建并查看它是否识别出您的代码存在问题，可能存在错误，但更有可能是您以某种方式损坏了容器或使用错误。