CHAPTER 51. C++ CHAPTER 51. C++
s.begin():
ptr=0x01D5D870 M_left=0x00000000 M_parent=0x01D5D890 M_right=0x00000000 M_color=0
key=11
s.end():
ptr=0x0028FE24 M_left=0x01D5D870 M_parent=0x007A1E80 M_right=0x01D5D8D0 M_color=0
GCC’s implementation is very similar^11. The only difference is the absence of theIsnilfield, so the structure occupies
slightly less space in memory than its implementation in MSVC. The dummy node is also used as a place to point the.end()
iterator also has no key and/or value.
Rebalancing demo (GCC)
Here is also a demo showing us how a tree is rebalanced after some insertions.
Listing 51.37: 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;
struct tree_node *M_right;
};
struct tree_struct
{
int M_key_compare;
struct tree_node M_header;
size_t M_node_count;
};
const char* ALOT_OF_TABS="\t\t\t\t\t\t\t\t\t\t\t";
void dump_as_tree (int tabs, struct tree_node n)
{
void point_after_struct=((char*)n)+sizeof(struct tree_node);
printf ("%d\n", *(int*)point_after_struct);if (n->M_left)
{
printf ("%.sL-------", tabs, ALOT_OF_TABS);
dump_as_tree (tabs+1, n->M_left);
};
if (n->M_right)
{
printf ("%.sR-------", tabs, ALOT_OF_TABS);
dump_as_tree (tabs+1, n->M_right);
};
};
void dump_map_and_set(struct tree_struct *m)
{
printf ("root----");
dump_as_tree (1, m->M_header.M_parent);