Question

#include <map>
#include <set>
#include <string>
#include <iostream>
// struct is not packed!
struct tree_node
{
struct tree_node *Left;
struct tree_node *Parent;
struct tree_node *Right;
char Color; // 0 - Red, 1 - Black
char Isnil;
//std::pair Myval;
unsigned int first; // called Myval in std::set
const char *second; // not present in std::set
};
struct tree_struct
{
struct tree_node *Myhead;
size_t Mysize;
};
void dump_tree_node (struct tree_node *n, bool is_set, bool traverse)
{
printf ("ptr=0x%p Left=0x%p Parent=0x%p Right=0x%p Color=%d Isnil=%d\n",
n, n->Left, n->Parent, n->Right, n->Color, n->Isnil);
if (n->Isnil==0)
{
if (is_set)
printf ("first=%d\n", n->first);
else
printf ("first=%d second=[%s]\n", n->first, n->second);
}
if (traverse)
{
if (n->Isnil==1)
dump_tree_node (n->Parent, is_set, true);
else
{
if (n->Left->Isnil==0)
dump_tree_node (n->Left, is_set, true);
if (n->Right->Isnil==0)
dump_tree_node (n->Right, is_set, true);
};
};
};
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, bool is_set)
{
if (is_set)
printf ("%d\n", n->first);
else
printf ("%d [%s]\n", n->first, n->second);
if (n->Left->Isnil==0)
{
printf ("%.*sL-------", tabs, ALOT_OF_TABS);
dump_as_tree (tabs+1, n->Left, is_set);
};
if (n->Right->Isnil==0)
{
printf ("%.*sR-------", tabs, ALOT_OF_TABS);
dump_as_tree (tabs+1, n->Right, is_set);
};
};
void dump_map_and_set(struct tree_struct *m, bool is_set)
{
printf ("ptr=0x%p, Myhead=0x%p, Mysize=%d\n", m, m->Myhead, m->Mysize);
dump_tree_node (m->Myhead, is_set, true);
printf ("As a tree:\n");
printf ("root----");
dump_as_tree (1, m->Myhead->Parent, is_set);
};
int main()
{
// map
std::map<int, const char*> m;
m[10]="ten";
m[20]="twenty";
m[3]="three";
m[101]="one hundred one";
m[100]="one hundred";
m[12]="twelve";
m[107]="one hundred seven";
m[0]="zero";
m[1]="one";
m[6]="six";
m[99]="ninety-nine";
m[5]="five";
m[11]="eleven";
m[1001]="one thousand one";
m[1010]="one thousand ten";
m[2]="two";
m[9]="nine";
printf ("dumping m as map:\n");
dump_map_and_set ((struct tree_struct *)(void*)&m, false);
std::map<int, const char*>::iterator it1=m.begin();
printf ("m.begin():\n");
dump_tree_node ((struct tree_node *)*(void**)&it1, false, false);
it1=m.end();
printf ("m.end():\n");
dump_tree_node ((struct tree_node *)*(void**)&it1, false, false);
// set
std::set<int> s;
s.insert(123);
s.insert(456);
s.insert(11);
s.insert(12);
s.insert(100);
s.insert(1001);
printf ("dumping s as set:\n");
dump_map_and_set ((struct tree_struct *)(void*)&s, true);
std::set<int>::iterator it2=s.begin();
printf ("s.begin():\n");
dump_tree_node ((struct tree_node *)*(void**)&it2, true, false);
it2=s.end();
printf ("s.end():\n");
dump_tree_node ((struct tree_node *)*(void**)&it2, true, false);
};
Listing 34.13: MSVC 2012
dumping m as map:
ptr=0x0020FE04, Myhead=0x005BB3A0, Mysize=17
ptr=0x005BB3A0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB580 Color=1 Isnil=1
ptr=0x005BB3C0 Left=0x005BB4C0 Parent=0x005BB3A0 Right=0x005BB440 Color=1 Isnil=0
first=10 second=[ten]
ptr=0x005BB4C0 Left=0x005BB4A0 Parent=0x005BB3C0 Right=0x005BB520 Color=1 Isnil=0
first=1 second=[one]
ptr=0x005BB4A0 Left=0x005BB3A0 Parent=0x005BB4C0 Right=0x005BB3A0 Color=1 Isnil=0
first=0 second=[zero]
ptr=0x005BB520 Left=0x005BB400 Parent=0x005BB4C0 Right=0x005BB4E0 Color=0 Isnil=0
first=5 second=[five]
ptr=0x005BB400 Left=0x005BB5A0 Parent=0x005BB520 Right=0x005BB3A0 Color=1 Isnil=0
first=3 second=[three]
ptr=0x005BB5A0 Left=0x005BB3A0 Parent=0x005BB400 Right=0x005BB3A0 Color=0 Isnil=0
first=2 second=[two]
ptr=0x005BB4E0 Left=0x005BB3A0 Parent=0x005BB520 Right=0x005BB5C0 Color=1 Isnil=0
first=6 second=[six]
ptr=0x005BB5C0 Left=0x005BB3A0 Parent=0x005BB4E0 Right=0x005BB3A0 Color=0 Isnil=0
first=9 second=[nine]
ptr=0x005BB440 Left=0x005BB3E0 Parent=0x005BB3C0 Right=0x005BB480 Color=1 Isnil=0
first=100 second=[one hundred]
ptr=0x005BB3E0 Left=0x005BB460 Parent=0x005BB440 Right=0x005BB500 Color=0 Isnil=0
first=20 second=[twenty]
ptr=0x005BB460 Left=0x005BB540 Parent=0x005BB3E0 Right=0x005BB3A0 Color=1 Isnil=0
first=12 second=[twelve]
ptr=0x005BB540 Left=0x005BB3A0 Parent=0x005BB460 Right=0x005BB3A0 Color=0 Isnil=0
first=11 second=[eleven]
ptr=0x005BB500 Left=0x005BB3A0 Parent=0x005BB3E0 Right=0x005BB3A0 Color=1 Isnil=0
first=99 second=[ninety-nine]
ptr=0x005BB480 Left=0x005BB420 Parent=0x005BB440 Right=0x005BB560 Color=0 Isnil=0
first=107 second=[one hundred seven]
ptr=0x005BB420 Left=0x005BB3A0 Parent=0x005BB480 Right=0x005BB3A0 Color=1 Isnil=0
first=101 second=[one hundred one]
ptr=0x005BB560 Left=0x005BB3A0 Parent=0x005BB480 Right=0x005BB580 Color=1 Isnil=0
first=1001 second=[one thousand one]
ptr=0x005BB580 Left=0x005BB3A0 Parent=0x005BB560 Right=0x005BB3A0 Color=0 Isnil=0
first=1010 second=[one thousand ten]
As a tree:
root----10 [ten]
L-------1 [one]
L-------0 [zero]
R-------5 [five]
L-------3 [three]
L-------2 [two]
R-------6 [six]
R-------9 [nine]
R-------100 [one hundred]
L-------20 [twenty]
L-------12 [twelve]
L-------11 [eleven]
R-------99 [ninety-nine]
R-------107 [one hundred seven]
L-------101 [one hundred one]
R-------1001 [one thousand one]
R-------1010 [one thousand ten]
m.begin():
ptr=0x005BB4A0 Left=0x005BB3A0 Parent=0x005BB4C0 Right=0x005BB3A0 Color=1 Isnil=0
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

结构体没有打包，因此所有的 char 类型都占用 4 个字节。 对于 std::map，first 和 second 变量可以看做是一个 std::pair 型变量。而在 std::set 中，std::pair 只有一个变量。 当前树的节点个数总被保存着，这与 MSVC 中的 std::list 实现方式一样。 和 std::list 一样，迭代器只是指向节点的指针。.begin() 迭代器指向最小的键。.begin() 指针没有存储在某个位置（和 list 一样），树中最小的 key 总是可以找到。当节点有前一个和后一个节点时，- -和++操作会将迭代器移动到前一个或者后一个节点。关于这些操作的算法在文献七中进行了描述。 .end() 迭代器指向根节点，它的 Isnil 的值为 1，即这个节点没有键和值。