std::map 是否将元素存储为 std::p air?遍历地图如下所示:
#include <map>
int main() {
std::map<int, char> m;
m[1] = 'A';
m[2] = 'B';
m[3] = 'C';
std::map<int, char>::iterator it;
for(it = m.begin(); it != m.end(); it++)
{
std::cout << "Key: " << it->first;
std::cout << " Value: " << it->second;
std::cout << std::endl;
}
}
不,std::map
不会将数据存储为对,它只是将其公开为成对。尽管不禁止在基础存储中使用std::pair
。
在典型的红黑树实现中,您需要在存储的键和值之上至少有两个指向子节点的指针(可能还有一个指向父节点的指针,我真的不记得 RB 树是如何工作的,抱歉(。基础存储类型为std::map::node_type
(自 C++17 以来添加(,在标准(也称为特定于实现(中未指定。
请注意,有以下子句(来自 cpp首选项(:
对于key_type为 K 且 mapped_type 为 T 的所有映射容器(std::map、std::multimap、std::unordered_map 和 std::unordered_multimap(,如果存在
std::pair<K, T>
或std::pair<const K, T>
的用户定义的 std::p air 专用化,则涉及节点句柄的操作的行为是未定义的。
它表明标准绝对允许将数据存储在节点句柄类型中作为std::pair
(并且实现可能假定std::pair
的行为完全符合预期(。
简单的答案是肯定的。
从[map.overview]
开始,map
的value_type
为:
using value_type = pair<const Key, T>;
[unord.map.overview]
也有相同的value_type
。
编辑:正如Yksisarviven所说,这些仍然需要存储在某种node_type
中,这在C++17标准中没有指定。
从 std::map::extract 我可以得出结论,它将其存储为 std::map::node_type。在实践中可能特定于实施。研究我的 GCC 9.3 实现结果:
template<typename _Val>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Val>* _Link_type;
#if __cplusplus < 201103L
_Val _M_value_field;
_Val*
_M_valptr()
{ return std::__addressof(_M_value_field); }
const _Val*
_M_valptr() const
{ return std::__addressof(_M_value_field); }
#else
__gnu_cxx::__aligned_membuf<_Val> _M_storage;
_Val*
_M_valptr()
{ return _M_storage._M_ptr(); }
const _Val*
_M_valptr() const
{ return _M_storage._M_ptr(); }
#endif
};
这意味着在我的实现中,节点中包含_Val = std::p air,即是的,它存储std::p air,但包装在一个节点中。