{"id":108562,"date":"2023-08-07T07:00:00","date_gmt":"2023-08-07T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108562"},"modified":"2023-08-07T07:35:37","modified_gmt":"2023-08-07T14:35:37","slug":"20230807-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230807-00\/?p=108562","title":{"rendered":"Inside STL: The map, set, multimap, and multiset"},"content":{"rendered":"

The complexity requirements of the C+ standard library map<\/code>, set<\/code>, multimap<\/code>, and multiset<\/code> basically narrow the possible implementation options to AVL trees and red-black trees.<\/p>\n

In practice, everybody seems to choose a red-black tree, with an explicit sentinel node. The sentinel node also doubles as a header. The structure of the tree is as follows:<\/p>\n

struct tree\r\n{\r\n    node_base header; \/\/ or \"node_base* header;\"\r\n    size_t size;\r\n};\r\n\r\nstruct node_base\r\n{\r\n    node_base* parent;\r\n    node_base* left;\r\n    node_base* right;\r\n};\r\n\r\nstruct node : node_base\r\n{\r\n    bool color; \/\/ red or black\r\n    payload data;\r\n};\r\n<\/pre>\n
The tree remembers the number of elements it holds (because size()<\/code> is required to be O<\/var>(1)) and has a sentinel node, called the “header”. The sentinel node is either embedded in the tree object or is a separately-allocated node, depending on the implementation.<\/p>\n
The sentinel node uses its pointers in an unusual manner.<\/p>\n
    \n
  • parent<\/code> points to the root of the tree.<\/li>\n
  • left<\/code> points to the smallest item in the tree.<\/li>\n
  • right<\/code> points to the largest item in the tree.<\/li>\n<\/ul>\n
    If you follow the header.parent<\/code> to the root of the tree, then what you find is a standard red-black binary tree, with the left<\/code> node pointing to the subtree of smaller elements, the right<\/code> node pointing to the subtree of larger elements, and the parent<\/code> node pointing to the parent element.<\/p>\n
    The header node is used to represent end()<\/code>, the one-past-the-end iterator.<\/p>\n
    For a map<\/code> or multimap<\/code>, the payload is a std::pair<Key, T><\/code>. For a set<\/code> or multiset<\/code>, the payload is a Key<\/code>.<\/p>\n
    Here’s an example of how a map<\/code> is laid out in memory:<\/p>\n
    std::map<int, std::string> m = {\r\n    { 42, \"forty-two\" },\r\n    { 99, \"ninety-nine\" },\r\n};\r\n<\/pre>\n
    First, with an internal header node:<\/p>\n\n\n\n\n\n\n\n\n\n\n
    m<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    header.parent<\/td>\nA<\/td>\n\u2194<\/td>\nparent<\/td>\nm.header<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    header.left<\/td>\nA<\/td>\n <\/td>\nleft<\/td>\nnull<\/td>\n <\/td>\nB<\/td>\n<\/tr>\n
    header.right<\/td>\nB<\/td>\n <\/td>\nright<\/td>\nB<\/td>\n\u2194<\/td>\nparent<\/td>\nA<\/td>\n<\/tr>\n
    size<\/td>\n2<\/td>\n <\/td>\ncolor<\/td>\nblack<\/td>\n <\/td>\nleft<\/td>\nnull<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\ndata<\/td>\n42, \"forty-two\"<\/code><\/td>\n <\/td>\nright<\/td>\nnull<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ncolor<\/td>\nred<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ndata<\/td>\n99, \"ninety-nine\"<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    And again with an external header node:<\/p>\n\n\n\n\n\n\n\n\n\n\n
    m<\/td>\n <\/td>\nH<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    header<\/td>\nH<\/td>\n\u2192<\/td>\nparent<\/td>\nA<\/td>\n\u2194<\/td>\nparent<\/td>\nH<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    size<\/td>\n2<\/td>\n <\/td>\nleft<\/td>\nA<\/td>\n <\/td>\nleft<\/td>\nnull<\/td>\n <\/td>\nB<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\nright<\/td>\nB<\/td>\n <\/td>\nright<\/td>\nB<\/td>\n\u2194<\/td>\nparent<\/td>\nA<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ncolor<\/td>\nblack<\/td>\n <\/td>\nleft<\/td>\nnull<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ndata<\/td>\n42, \"forty-two\"<\/code><\/td>\n <\/td>\nright<\/td>\nnull<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ncolor<\/td>\nred<\/td>\n<\/tr>\n
     <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\ndata<\/td>\n99, \"ninety-nine\"<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    The map object itself has two members: The header<\/code> is (or points to) our sentinel\/header node H<\/code>, and the size<\/code> is 2, remembering that we have two nodes in our tree.<\/p>\n
    The header node’s parent<\/code> points to the root of the tree A<\/code>. This is confusing at first, because the member named “parent” actually points to the “child”, if you think of the header node as the “super-parent” of the entire tree. The header node’s left<\/code> and right<\/code> members point to the smallest and largest nodes of the tree, respectively. In our case, the smallest node is A<\/code> (42) and the largest node is B<\/code> (99). Finally, the color<\/code> and data<\/code> of the header node are not used.<\/p>\n
    The root of our tree is the node A<\/code>. It remembers that its parent is the header node H<\/code>, but the interesting parts are the left<\/code> and right<\/code> pointers. There is no left subtree, so the left<\/code> is null; the right subtree is rooted at B<\/code>. Finally, the node also has a color<\/code> (black in this case), and its data<\/code> holds the payload.<\/p>\n
    The last node in the tree is B<\/code>, representing the single-node right subtree of A<\/code>. Its parent is A<\/code>, and its left<\/code> and right<\/code> nodes are null because it is a leaf node. Node B<\/code> also has a color<\/code> (red in this case), and its data<\/code> holds the payload.<\/p>\n
    The tree also needs a comparer and allocator. Those classes are typically empty, so the tree saves them as compressed pairs with the rest of the data. (Since there are two usually-empty things, you have a compressed pair inside a compressed pair.)<\/p>\n
    The Microsoft implementation uses an external header sentinel node, whereas clang and gcc use an internal header sentinel node. The Microsoft implementation also has these extra quirks:<\/p>\n
      \n
    • There is an additional member of each node called _Isnil<\/code> that is true<\/code> for the header node and that is false<\/code> for everybody else.<\/li>\n
    • Everywhere you see null in the above diagram, the Microsoft implementation substitutes a pointer to the header node.<\/li>\n<\/ul>\n
      The _Isnil<\/code> member is technically redundant: You can detect that you have the header node by comparing it to the map’s header. However, the Visual C++ compiler uses a raw node pointer as its iterator, which means that it doesn’t have access to the containing tree to compare against the header. The information has to be internal to the node.<\/p>\n
      The Visual Studio debugger contains a visualizer to view the contents of a tree-based container more conveniently, but if you need to dig out the contents manually, here’s how you can do it with the Microsoft implementation of the standard library. I’ve left in the template explosion to make it look more like what you’re likely to encounter in the debugger.<\/p>\n
      0:000> ?? m\r\nclass std::map<int,std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::less<int>,std::allocator<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::less<int>,std::_Compressed_pair<std::allocator<std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> >,std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >,1>,1>\r\n<\/pre>\n
      The full name for the std::map<int, std::string><\/code> is this horrible monstrosity because std::string<\/code> is an alias for std::basic_string<char><\/code>, which is in turn a shorthand for std::basic_string<char, std::char_traits<char>, std::allocator<char>><\/code>. So everywhere you see the huge type std::basic_string<char, std::char_traits<char>, std::allocator<char>><\/code>, remember that’s just a std::string<\/code>.<\/p>\n
      On top of that, the std::map<\/code> itself comes with a default comparer of std::less<int><\/code> and a default allocator of std::allocator<std::pair<int, std::string>><\/code>. But wait, std::string<\/code> is itself an alias for that huge type name, so the default allocator’s full name is std::allocator<std::pair<int, std::basic_string<char, std::char_traits<char>, std::allocator<char>>>><\/code>. And that’s why when you declare a std::map<int, std::string><\/code>, you get this ridiculous type name in the debugger. That’s the name the compiler has to deal with.<\/p>\n
      Okay, so we have the map. We need to dig through the compressed pairs to find the header pointer and size.<\/p>\n
      0:000> ?? m._Mypair\r\nclass std::_Compressed_pair<std::less<int>,std::_Compressed_pair<std::allocator<std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> >,std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >,1>,1>\r\n   +0x000 _Myval2          : std::_Compressed_pair<std::allocator<std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> >,std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >,1>\r\n0:000> ?? m._Mypair._Myval2\r\nclass std::_Compressed_pair<std::allocator<std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> >,std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >,1>\r\n   +0x000 _Myval2          : std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >\r\n0:000> ?? m._Mypair._Myval2._Myval2\r\nclass std::_Tree_val<std::_Tree_simple_types<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > > > >\r\n   +0x000 _Myhead          : 0x0000019a`d09cc720 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x008 _Mysize          : 2\r\n<\/pre>\n
      We follow the header pointer to find the header node.<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead\r\nstruct std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> * 0x0000019a`d09cc720\r\n   +0x000 _Left            : 0x0000019a`d09c91f0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x008 _Parent          : 0x0000019a`d09c91f0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x010 _Right           : 0x0000019a`d09c9270 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x018 _Color           : 1 ''\r\n   +0x019 _Isnil           : 1 ''\r\n   +0x020 _Myval           : std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >\r\n<\/pre>\n
      We can confirm that we’re on the right track because the _Isnil<\/code> is true<\/code>, which is the case only for the header node. Follow the _Parent<\/code> to get to the root of the tree.<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent\r\nstruct std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> * 0x0000019a`d09c91f0\r\n   +0x000 _Left            : 0x0000019a`d09cc720 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x008 _Parent          : 0x0000019a`d09cc720 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x010 _Right           : 0x0000019a`d09c9270 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x018 _Color           : 1 ''\r\n   +0x019 _Isnil           : 0 ''\r\n   +0x020 _Myval           : std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >\r\n<\/pre>\n
      The payload of the root node is hiding inside the _Myval<\/code> pair, so we’ll have to expand it out:<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval\r\nstruct std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >\r\n   +0x000 first            : 0n42\r\n   +0x008 second           : std::basic_string<char,std::char_traits<char>,std::allocator<char> >\r\n<\/pre>\n
      We see immediately that the key of the root node is 42. We’re lucky that our map is keyed by int<\/code>, which is a simple type. If not, we’d have had to dig into the members of the first<\/code> to figure out what it is.<\/p>\n
      Let’s demonstrate that by digging into the second<\/code> of the pair, which holds the mapped value.<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second\r\nclass std::basic_string<char,std::char_traits<char>,std::allocator<char> >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::allocator<char>,std::_String_val<std::_Simple_types<char> >,1>\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair\r\nclass std::_Compressed_pair<std::allocator<char>,std::_String_val<std::_Simple_types<char> >,1>\r\n   +0x000 _Myval2          : std::_String_val<std::_Simple_types<char> >\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair._Myval2\r\nclass std::_String_val<std::_Simple_types<char> >\r\n   +0x000 _Bx              : std::_String_val<std::_Simple_types<char> >::_Bxty\r\n   +0x010 _Mysize          : 9\r\n   +0x018 _Myres           : 0xf\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair._Myval2._Bx\r\nunion std::_String_val<std::_Simple_types<char> >::_Bxty\r\n   +0x000 _Buf             : [16]  \"forty-two\"\r\n   +0x000 _Ptr             : 0x77742d79`74726f66  \"--- memory read error at address 0x77742d79`74726f66 ---\"\r\n   +0x000 _Alias           : [16]  \"forty-two\"\r\n<\/pre>\n
      In this case, the mapped type is a std::string<\/code>, so we use the string-dumping technique we learned about some time ago.<\/p>\n
      So we’ve found that the root of the tree is { 42, \"forty-two\" }<\/code>. The _Left<\/code> member points back to the header, so there is no left subtree. The _Right<\/code> member holds some other pointer value, so we have a right subtree. Let’s explore it.<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Right\r\nstruct std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *> * 0x0000019a`d09c9270\r\n   +0x000 _Left            : 0x0000019a`d09cc720 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x008 _Parent          : 0x0000019a`d09c91f0 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x010 _Right           : 0x0000019a`d09cc720 std::_Tree_node<std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >,void *>\r\n   +0x018 _Color           : 0 ''\r\n   +0x019 _Isnil           : 0 ''\r\n   +0x020 _Myval           : std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >\r\n0:000> ?? t._Mypair._Myval2._Myval2._Myhead->_Parent->_Right->_Myval\r\nstruct std::pair<int const ,std::basic_string<char,std::char_traits<char>,std::allocator<char> > >\r\n   +0x000 first            : 0n99\r\n   +0x008 second           : std::basic_string<char,std::char_traits<char>,std::allocator<char> >\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Right->_Myval.second._Mypair._Myval2._Bx\r\nunion std::_String_val<std::_Simple_types<char> >::_Bxty\r\n   +0x000 _Buf             : [16]  \"ninety-nine\"\r\n   +0x000 _Ptr             : 0x6e2d7974`656e696e  \"--- memory read error at address 0x6e2d7974`656e696e ---\"\r\n   +0x000 _Alias           : [16]  \"ninety-nine\"\r\n0:000>\r\n<\/pre>\n
      When I’m dumping tree structures in the debugger at this low level, I generally ignore all the type information because it’s so voluminous. I rely on the member variable names to tell me what I’m looking at. Here’s what the above debug session looks like to me:<\/p>\n
      0:000> ?? m\r\nclass std::map<int,std::basic_string<char, \u27e6 ... \u27e7 > >\r\n   +0x000 _Mypair       : \u27e6 ... \u27e7 \u27ea ugh, a wrapper \u27eb\r\n0:000> ?? m._Mypair\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Myval2       : \u27e6 ... \u27e7 \u27ea ugh, another wrapper \u27eb\r\n0:000> ?? m._Mypair._Myval2\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Myval2       : \u27e6 ... \u27e7 \u27ea ugh, another wrapper \u27eb\r\n0:000> ?? m._Mypair._Myval2._Myval2\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Myhead       : 0x0000019a`d09cc720 \u27e6 ... \u27e7 \u27ea yay, the header, end in c720 \u27eb\r\n   +0x008 _Mysize       : 2\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead\r\nstruct \u27e6 ... \u27e7* 0x0000019a`d09cc720 \u27ea yup, c720, this is the header \u27eb\r\n   \u27e6 ... \u27e7\r\n   +0x008 _Parent       : 0x0000019a`d09c91f0 \u27e6 ... \u27e7 \u27ea here is the root node \u27eb\r\n   \u27e6 ... \u27e7\r\n<\/pre>\n
      And then we inspect the root node:<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent\r\nstruct \u27e6 ... \u27e7 * 0x0000019a`d09c91f0\r\n   +0x000 _Left         : 0x0000019a`d09cc720 \u27e6 ... \u27e7 \u27ea this is c720, so no left subtree \u27eb\r\n   \u27e6 ... \u27e7\r\n   +0x010 _Right        : 0x0000019a`d09c9270 \u27e6 ... \u27e7 \u27ea there is a right subtree \u27eb\r\n   \u27e6 ... \u27e7\r\n   +0x020 _Myval        : \u27e6 ... \u27e7\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval\r\nstruct \u27e6 ... \u27e7\r\n   +0x000 first         : 0n42 \u27ea the key is 42 \u27eb\r\n   +0x008 second        : \u27e6 ... \u27e7 \u27ea the mapped value is hiding here \u27eb\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Mypair       : \u27e6 ... \u27e7 \u27ea ugh, a wrapper \u27eb\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Myval2       : \u27e6 ... \u27e7 \u27ea ugh, another wrapper \u27eb\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair._Myval2\r\nclass \u27e6 ... \u27e7\r\n   +0x000 _Bx           : \u27e6 ... \u27e7 \u27ea okay, the string data is in here \u27eb\r\n   \u27e6 ... \u27e7\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Myval.second._Mypair._Myval2._Bx\r\nunion std::_String_val<std::_Simple_types<char> >::_Bxty\r\n   +0x000 _Buf          : [16]  \"forty-two\"\r\n   +0x000 _Ptr          : 0x77742d79`74726f66  \u27ea garbage, ignore \u27eb\r\n    \u27e6 ... \u27e7\r\n<\/pre>\n
      Next we follow the right subtree.<\/p>\n
      0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Right\r\nstruct \u27e6 ... \u27e7 * 0x0000019a`d09c9270\r\n   +0x000 _Left         : 0x0000019a`d09cc720 \u27e6 ... \u27e7 \u27ea this is c720, so no left subtree \u27eb\r\n   \u27e6 ... \u27e7\r\n   +0x010 _Right        : 0x0000019a`d09cc720 \u27e6 ... \u27e7 \u27ea this is c720, so no right subtree \u27eb\r\n   \u27e6 ... \u27e7\r\n   +0x020 _Myval        : \u27e6 ... \u27e7\r\n0:000> ?? t._Mypair._Myval2._Myval2._Myhead->_Parent->_Right->_Myval\r\nstruct \u27e6 ... \u27e7\r\n   +0x000 first         : 0n99 \u27ea the key is 99 \u27eb\r\n   +0x008 second        : \u27e6 ... \u27e7 \u27ea I learned the path to the _Bx from last time \u27eb\r\n0:000> ?? m._Mypair._Myval2._Myval2._Myhead->_Parent->_Right->_Myval.second._Mypair._Myval2._Bx\r\nunion \u27e6 ... \u27e7\r\n   +0x000 _Buf          : [16]  \"ninety-nine\"\r\n   +0x000 _Ptr          : 0x6e2d7974`656e696e  \u27e6 ... \u27e7 \u27ea garbage, ignore \u27eb\r\n   \u27e6 ... \u27e7\r\n<\/pre>\n
      There, we walked the complete contents of a std::map<\/code> in the low-level debugger. It’s quite a hassle.<\/p>\n
      Bonus chatter<\/b>: Iterating through the tree can be done by performing an  incremental inorder walk of a binary tree<\/a>. Observe that this means that the operator++<\/code> on a tree iterator is not constant-time. However, it is amortized<\/i> constant time, because each edge in the tree is traversed twice (once outgoing and once returning), and the number of edges is equal to the number of nodes minus one. Therefore, the number of steps to traverse the entire tree is 2n<\/var> \u2212 2, which is O<\/var>(n<\/var>), and therefore each individual operator++<\/code> has amortized constant cost,  as required by the standard<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
      A red-black tree.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-108562","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
      A red-black tree.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108562","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108562"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108562\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108562"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108562"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108562"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}