CHAPTER 51. C++ CHAPTER 51. C++
first=0 second=[zero]
m.end():
ptr=0x005BB3A0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB580 Color=1 Isnil=1
dumping s as set:
ptr=0x0020FDFC, Myhead=0x005BB5E0, Mysize=6
ptr=0x005BB5E0 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=1
ptr=0x005BB600 Left=0x005BB660 Parent=0x005BB5E0 Right=0x005BB620 Color=1 Isnil=0
first=123
ptr=0x005BB660 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB680 Color=1 Isnil=0
first=12
ptr=0x005BB640 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=11
ptr=0x005BB680 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=100
ptr=0x005BB620 Left=0x005BB5E0 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=0
first=456
ptr=0x005BB6A0 Left=0x005BB5E0 Parent=0x005BB620 Right=0x005BB5E0 Color=0 Isnil=0
first=1001
As a tree:
root----123
L-------12
L-------11
R-------100
R-------456
R-------1001
s.begin():
ptr=0x005BB640 Left=0x005BB5E0 Parent=0x005BB660 Right=0x005BB5E0 Color=0 Isnil=0
first=11
s.end():
ptr=0x005BB5E0 Left=0x005BB640 Parent=0x005BB600 Right=0x005BB6A0 Color=1 Isnil=1
The structure is not packed, so bothcharvalues occupy 4 bytes each.
As forstd::map,firstandsecondcan be viewed as a single value of typestd::pair.std::sethas only one value
at this address in the structure instead.
The current size of the tree is always present, as in the case of the implementation ofstd::listin MSVC (51.4.2 on
page 550).
As in the case ofstd::list, the iterators are just pointers to nodes. The.begin()iterator points to the minimal key.
That pointer is not stored anywhere (as in lists), the minimal key of the tree is looked up every time.operator--and
operator++ move the current node pointer to the predecessor or successor respectively, i.e., the nodes which have the
previous or next key. The algorithms for all these operations are explained in [Cor+09].
The.end()iterator points to the dummy node, it has 1 inIsnil, which implies that the node has no key and/or value. It
can be viewed as a “landing zone” inHDD^10. The “parent” field of the dummy node points to the root node, which serves as
a vertex of the tree and contains information.
GCC
#include <stdio.h>
#include
struct map_pair
{
int key;
const char *value;
};
struct tree_node
{
int M_color; // 0 - Red, 1 - Black
struct tree_node M_parent;
struct tree_node M_left;
(^10) Hard disk drive