33.5 std::map and std::set

二叉树是另一个基本的数据结构。它是一个树，但是每个节点最多包含两个指向其他节点的指针。每个节点包含键和/或值。 二叉树在键值字典的实现中是常用数据结构。 二叉树至少包含三个重要的属性： 所有的键的存储是排序的。 任何类型的键都容易存储。二叉树并不知道键的类型，因此需要键比较算法。 查找键的速度相比于链表和数组要快。 下面是一个非常简单的例子，我们在二叉树中存储下面这些数据0，1，2，3，5，6，9，10，11，12，20，99，100，101，107，1001，1010.

所有小于根节点键的键存储在树的左侧，所有大于根节点键的键存储在树的右侧。 因此，查找算法就很直接，当要查找的值小于当前节点的键的值，则查找左侧；如果大于当前节点的键的值，则查找右侧；当值相等时，则停止查找。这就是为什么通过键比较函数，算法可以查找数值、文本串等。 所有键的值都是唯一的。 如果这样，为了在n个键的平衡二叉树中查找一个键将需要log2 n步。1000个键需要10步，10000个键需要13步。但是这要求树总是平衡的，即键应该均匀的分布在树的不同层里。插入和删除操作需要保持树的平衡状态。 有一些流行的平衡算法可用，包括AVL树和红黑树。红黑树通过给节点增加一个color值来简化平衡过程，因此每个节点可能是红或者黑。 GCC和MSVC中的std::map和std::set模板的实现均采用了红黑树。 std::set只包含键。std::map是set的扩展，它在每个节点中包含一个值。

** MSVC **

#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，即这个节点没有键和值。

GCC

#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <iostream>
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;
};
void dump_tree_node (struct tree_node *n, bool is_set, bool traverse, bool dump_keys_and_values)
{
    printf ("ptr=0x%p M_left=0x%p M_parent=0x%p M_right=0x%p M_color=%d\n", n, n->M_left, n->M_parent, n->M_right, n->M_color);
    void *point_after_struct=((char*)n)+sizeof(struct tree_node);
    if (dump_keys_and_values)
    {
        if (is_set)
            printf ("key=%d\n", *(int*)point_after_struct);
        else
        {
            struct map_pair *p=(struct map_pair *)point_after_struct;
            printf ("key=%d value=[%s]\n", p->key, p->value);
        };
    };
    if (traverse==false)
        return;
    if (n->M_left)
        dump_tree_node (n->M_left, is_set, traverse, dump_keys_and_values);
    if (n->M_right)
        dump_tree_node (n->M_right, is_set, traverse, dump_keys_and_values);
};
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)
{
    void *point_after_struct=((char*)n)+sizeof(struct tree_node);
    if (is_set)
        printf ("%d\n", *(int*)point_after_struct);
    else
    {
        struct map_pair *p=(struct map_pair *)point_after_struct;
        printf ("%d [%s]\n", p->key, p->value);
    }
    if (n->M_left)
    {
        printf ("%.*sL-------", tabs, ALOT_OF_TABS);
        dump_as_tree (tabs+1, n->M_left, is_set);
    };
    if (n->M_right)
    {
        printf ("%.*sR-------", tabs, ALOT_OF_TABS);
        dump_as_tree (tabs+1, n->M_right, is_set);
    };
};
void dump_map_and_set(struct tree_struct *m, bool is_set)
{
    printf ("ptr=0x%p, M_key_compare=0x%x, M_header=0x%p, M_node_count=%d\n", m, m->M_key_compare, &m->M_header, m->M_node_count);
    dump_tree_node (m->M_header.M_parent, is_set, true, true);
    printf ("As a tree:\n");
    printf ("root----");
    dump_as_tree (1, m->M_header.M_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, true);
    it1=m.end();
    printf ("m.end():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it1, false, 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, true);
    it2=s.end();
    printf ("s.end():\n");
    dump_tree_node ((struct tree_node *)*(void**)&it2, true, false, false);
};

dumping m as map:

ptr=0x0028FE3C, M_key_compare=0x402b70, M_header=0x0028FE40, M_node_count=17
ptr=0x007A4988 M_left=0x007A4C00 M_parent=0x0028FE40 M_right=0x007A4B80 M_color=1
key=10 value=[ten]
ptr=0x007A4C00 M_left=0x007A4BE0 M_parent=0x007A4988 M_right=0x007A4C60 M_color=1
key=1 value=[one]
ptr=0x007A4BE0 M_left=0x00000000 M_parent=0x007A4C00 M_right=0x00000000 M_color=1
key=0 value=[zero]
ptr=0x007A4C60 M_left=0x007A4B40 M_parent=0x007A4C00 M_right=0x007A4C20 M_color=0
key=5 value=[five]
ptr=0x007A4B40 M_left=0x007A4CE0 M_parent=0x007A4C60 M_right=0x00000000 M_color=1
key=3 value=[three]
ptr=0x007A4CE0 M_left=0x00000000 M_parent=0x007A4B40 M_right=0x00000000 M_color=0
key=2 value=[two]
ptr=0x007A4C20 M_left=0x00000000 M_parent=0x007A4C60 M_right=0x007A4D00 M_color=1
key=6 value=[six]
ptr=0x007A4D00 M_left=0x00000000 M_parent=0x007A4C20 M_right=0x00000000 M_color=0
key=9 value=[nine]
ptr=0x007A4B80 M_left=0x007A49A8 M_parent=0x007A4988 M_right=0x007A4BC0 M_color=1
key=100 value=[one hundred]
ptr=0x007A49A8 M_left=0x007A4BA0 M_parent=0x007A4B80 M_right=0x007A4C40 M_color=0
key=20 value=[twenty]
ptr=0x007A4BA0 M_left=0x007A4C80 M_parent=0x007A49A8 M_right=0x00000000 M_color=1
key=12 value=[twelve]
ptr=0x007A4C80 M_left=0x00000000 M_parent=0x007A4BA0 M_right=0x00000000 M_color=0
key=11 value=[eleven]
ptr=0x007A4C40 M_left=0x00000000 M_parent=0x007A49A8 M_right=0x00000000 M_color=1
key=99 value=[ninety-nine]
ptr=0x007A4BC0 M_left=0x007A4B60 M_parent=0x007A4B80 M_right=0x007A4CA0 M_color=0
key=107 value=[one hundred seven]
ptr=0x007A4B60 M_left=0x00000000 M_parent=0x007A4BC0 M_right=0x00000000 M_color=1
key=101 value=[one hundred one]
ptr=0x007A4CA0 M_left=0x00000000 M_parent=0x007A4BC0 M_right=0x007A4CC0 M_color=1
key=1001 value=[one thousand one]
ptr=0x007A4CC0 M_left=0x00000000 M_parent=0x007A4CA0 M_right=0x00000000 M_color=0
key=1010 value=[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=0x007A4BE0 M_left=0x00000000 M_parent=0x007A4C00 M_right=0x00000000 M_color=1
key=0 value=[zero]
m.end():
ptr=0x0028FE40 M_left=0x007A4BE0 M_parent=0x007A4988 M_right=0x007A4CC0 M_color=0
dumping s as set:
ptr=0x0028FE20, M_key_compare=0x8, M_header=0x0028FE24, M_node_count=6
ptr=0x007A1E80 M_left=0x01D5D890 M_parent=0x0028FE24 M_right=0x01D5D850 M_color=1
key=123
ptr=0x01D5D890 M_left=0x01D5D870 M_parent=0x007A1E80 M_right=0x01D5D8B0 M_color=1
key=12
ptr=0x01D5D870 M_left=0x00000000 M_parent=0x01D5D890 M_right=0x00000000 M_color=0
key=11
ptr=0x01D5D8B0 M_left=0x00000000 M_parent=0x01D5D890 M_right=0x00000000 M_color=0
key=100
ptr=0x01D5D850 M_left=0x00000000 M_parent=0x007A1E80 M_right=0x01D5D8D0 M_color=1
key=456
ptr=0x01D5D8D0 M_left=0x00000000 M_parent=0x01D5D850 M_right=0x00000000 M_color=0
key=1001
As a tree:
root----123
L-------12
L-------11
R-------100
R-------456
R-------1001
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的实现也很类似。唯一一的不同点就是没有Isnil元素，因此占用的空间要小于MSVC的实现。跟节点也是作为.end()迭代器指向的位置，同时也不包含键和值。

重新平衡的演示

下面的例子将向我们展示插入节点后，树如何重新平衡。

#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <iostream>
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);
};
int main()
{
    std::set<int> s;
    s.insert(123);
    s.insert(456);
    printf ("123, 456 are inserted\n");
    dump_map_and_set ((struct tree_struct *)(void*)&s);
    s.insert(11);
    s.insert(12);
    printf ("\n");
    printf ("11, 12 are inserted\n");
    dump_map_and_set ((struct tree_struct *)(void*)&s);
    s.insert(100);
    s.insert(1001);
    printf ("\n");
    printf ("100, 1001 are inserted\n");
    dump_map_and_set ((struct tree_struct *)(void*)&s);
    s.insert(667);
    s.insert(1);
    s.insert(4);
    s.insert(7);
    printf ("\n");
    printf ("667, 1, 4, 7 are inserted\n");
    dump_map_and_set ((struct tree_struct *)(void*)&s);
    printf ("\n");
};

123, 456 are inserted
root----123
R-------456
11, 12 are inserted
root----123
L-------11
R-------12
R-------456
100, 1001 are inserted
root----123
L-------12
L-------11
R-------100
R-------456
R-------1001
667, 1, 4, 7 are inserted
root----12
L-------4
L-------1
R-------11
L-------7
R-------123
L-------100
R-------667
L-------456
R-------1001

54.10位。

所有位操作工作，与其他的一些ISA（指令集架构）类似：

public static int set (int a, int b)
{
return a | 1<<b;
}
public static int clear (int a, int b)
{
return a & (~(1<<b));
}
public static int set(int, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=3, locals=2, args_size=2
0: iload_0
1: iconst_1
2: iload_1
3: ishl
4: ior
5: ireturn
public static int clear(int, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=3, locals=2, args_size=2
0: iload_0
1: iconst_1
2: iload_1
3: ishl
4: iconst_m1
5: ixor
6: iand
7: ireturn

926 iconst_m1将-1入栈，这数其实就是16进制的0xFFFFFFFF，将0xFFFFFFFF作为XOR-ing指令执行的操作数。起到的效果就是把所有bits位反向，（A.6.2在1406页）

我将所有数据类型，扩展成64为长整型。

public static long lset (long a, int b)
{
return a | 1<<b;
}
public static long lclear (long a, int b)
{
return a & (~(1<<b));
}
public static long lset(long, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=4, locals=3, args_size=2
0: lload_0
1: iconst_1
2: iload_2
3: ishl
4: i2l
5: lor
6: lreturn
public static long lclear(long, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=4, locals=3, args_size=2
0: lload_0
1: iconst_1
2: iload_2
3: ishl
4: iconst_m1
5: ixor
6: i2l
7: land
8: lreturn

代码是相同的，但是指令前面使用了前缀L，操作64位值，并且第二个函数参数还是int类型，并且32值需要升级为64位值，值被i21指令使用，本质上 就是把整型，扩展成64位长整型.

927页

54.12 switch()函数

switch（）语句的实现是用tableswitch指令，

public static void f(int a)
{
    switch (a)
    {
        case 0: System.out.println("zero"); break;
        case 1: System.out.println("one\n"); break;
        case 2: System.out.println("two\n"); break;
        case 3: System.out.println("three\n"); break;
        case 4: System.out.println("four\n"); break;
        default: System.out.println("something unknown\n"); break;
    };
}

尽可能简单的例子

public static void f(int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: iload_0
1: tableswitch { // 0 to 4
0: 36
1: 47
2: 58
3: 69
4: 80
default: 91
}
36: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
39: ldc #3 // String zero
41: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
44: goto 99
47: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
50: ldc #5 // String one\n
52: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
55: goto 99
58: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
61: ldc #6 // String two\n
63: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
66: goto 99
69: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
72: ldc #7 // String three\n
74: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
77: goto 99
80: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
83: ldc #8 // String four\n
85: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
88: goto 99
91: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
94: ldc #9 // String ⤦
Ç something unknown\n
931
CHAPTER 54. JAVA 54.13. ARRAYS
96: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
99: return

930

931

54.14 字符串 54.14.1 第一个例子

字符串也是对象，和其他对象的构造方式相同。（还有数组）

public static void main(String[] args)
{
System.out.println("What is your name?");
String input = System.console().readLine();
System.out.println("Hello, "+input);
}
public static void main(java.lang.String[]);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=3, locals=2, args_size=1
0: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
3: ldc #3 // String What is⤦
Ç your name?
5: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
8: invokestatic #5 // Method java/⤦
Ç lang/System.console:()Ljava/io/Console;
11: invokevirtual #6 // Method java/io⤦
Ç /Console.readLine:()Ljava/lang/String;
14: astore_1
15: getstatic #2 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
18: new #7 // class java/⤦
Ç lang/StringBuilder
21: dup
22: invokespecial #8 // Method java/⤦
Ç lang/StringBuilder."<init>":()V
25: ldc #9 // String Hello,
27: invokevirtual #10 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
30: aload_1
31: invokevirtual #10 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
34: invokevirtual #11 // Method java/⤦
Ç lang/StringBuilder.toString:()Ljava/lang/String;
37: invokevirtual #4 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
40: return

944 在11行偏移调用了readline()方法，字符串引用（由用户提供）被存储在栈顶，在14行偏移,字符串引用被存储在LVA的1号槽中。

用户输入的字符串在30行偏移处重新加载并和 “hello”字符进行了链接，使用的是StringBulder类，在17行偏移,构造的字符串被pirntln方法打印。

54.14.2 第二个例子 另外一个例子

public class strings
{
public static char test (String a)
{
return a.charAt(3);
};
public static String concat (String a, String b)
{
return a+b;
}
}
public static char test(java.lang.String);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: aload_0
1: iconst_3
2: invokevirtual #2 // Method java/⤦
Ç lang/String.charAt:(I)C
5: ireturn

945

字符串的链接使用用StringBuilder类完成。

public static java.lang.String concat(java.lang.String, java.⤦
Ç lang.String);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=2
0: new #3 // class java/⤦
Ç lang/StringBuilder
3: dup
4: invokespecial #4 // Method java/⤦
Ç lang/StringBuilder."<init>":()V
7: aload_0
8: invokevirtual #5 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
11: aload_1
12: invokevirtual #5 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
15: invokevirtual #6 // Method java/⤦
Ç lang/StringBuilder.toString:()Ljava/lang/String;
18: areturn

另外一个例子

public static void main(String[] args)
{
String s="Hello!";
int n=123;
System.out.println("s=" + s + " n=" + n);
}

字符串构造用StringBuilder类，和它的添加方法，被构造的字符串被传递给println方法。

public static void main(java.lang.String[]);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=3, locals=3, args_size=1
0: ldc #2 // String Hello!
2: astore_1
3: bipush 123
5: istore_2
6: getstatic #3 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
9: new #4 // class java/⤦
Ç lang/StringBuilder
12: dup
13: invokespecial #5 // Method java/⤦
Ç lang/StringBuilder."<init>":()V
16: ldc #6 // String s=
18: invokevirtual #7 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
21: aload_1
22: invokevirtual #7 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
25: ldc #8 // String n=
27: invokevirtual #7 // Method java/⤦
Ç lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/⤦
Ç StringBuilder;
30: iload_2
31: invokevirtual #9 // Method java/⤦
Ç lang/StringBuilder.append:(I)Ljava/lang/StringBuilder;
34: invokevirtual #10 // Method java/⤦
Ç lang/StringBuilder.toString:()Ljava/lang/String;
37: invokevirtual #11 // Method java/io⤦
Ç /PrintStream.println:(Ljava/lang/String;)V
40: return

946

54.16 类 简单类

清单 54.15: test.java

public class test
{
public static int a;
private static int b;
public test()
{
a=0;
b=0;
}
public static void set_a (int input)
{
a=input;
}
public static int get_a ()
{
return a;
}
public static void set_b (int input)
{
b=input;
}
public static int get_b ()
{
return b;
}
}

952

构造函数，只是把两个之段设置成0.

public test();
flags: ACC_PUBLIC
Code:
stack=1, locals=1, args_size=1
0: aload_0
1: invokespecial #1 // Method java/⤦
Ç lang/Object."<init>":()V
4: iconst_0
5: putstatic #2 // Field a:I
8: iconst_0
9: putstatic #3 // Field b:I
12: return

a的设定器

public static void set_a(int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=1, locals=1, args_size=1
0: iload_0
1: putstatic #2 // Field a:I
4: return

a的取得器

public static int get_a();
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=1, locals=0, args_size=0
0: getstatic #2 // Field a:I
3: ireturn

b的设定器

public static void set_b(int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=1, locals=1, args_size=1
0: iload_0
1: putstatic #3 // Field b:I
4: return

b的取得器

public static int get_b();
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=1, locals=0, args_size=0
0: getstatic #3 // Field b:I
3: ireturn

953 类中的公有和私有字段代码没什么区别。 但是类型信息会在in.class 文件中表示，并且，无论如何私有变量是不可以被访问的。

让我们创建对象并调用方法： 清单 54.16: ex1.java

954 新指令创建对象，但不调用构造函数（它在4行偏移被调用）set_a()方法被在16行偏移被调用，字段访问使用的getstatic指令,在行偏移21。

Listing 54.16: ex1.java
public class ex1
{
public static void main(String[] args)
{
test obj=new test();
obj.set_a (1234);
System.out.println(obj.a);
}
}
public static void main(java.lang.String[]);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=1
0: new #2 // class test
3: dup
4: invokespecial #3 // Method test."<⤦
Ç init>":()V
7: astore_1
8: aload_1
9: pop
10: sipush 1234
13: invokestatic #4 // Method test.⤦
Ç set_a:(I)V
16: getstatic #5 // Field java/⤦
Ç lang/System.out:Ljava/io/PrintStream;
19: aload_1
20: pop
21: getstatic #6 // Field test.a:I
24: invokevirtual #7 // Method java/io⤦
Ç /PrintStream.println:(I)V
27: return

5.4 章

54.1介绍 大家都知道，java有很多的反编译器（或是产生JVM字节码） 原因是JVM字节码比其他的X86低级代码更容易进行反编译。

a).多很多相关数据类型的信息。 b).JVM（java虚拟机）内存模型更严格和概括。 c).java编译器没有做任何的优化工作（JVM JIT不是实时），所以，类文件中的字节代码的通常更清晰易读。

JVM字节码知识什么时候有用呢？

a).文件的快速粗糙的打补丁任务，类文件不需要重新编译反编译的结果。 b).分析混淆代码 c).创建你自己的混淆器。 d).创建编译器代码生成器（后端）目标。

我们从一段简短的代码开始，除非特殊声明，我们用的都是JDK1.7

反编译类文件使用的命令，随处可见：javap -c -verbase.

在这本书中提供的很多的例子，都用到了这个。

54.3 简单的计算函数

让我们继续看简单的计算函数。

public class calc
{
public static int half(int a)
{
return a/2;
}
}

这种情况使用icont_2会被使用。

public static int half(int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: iload_0
1: iconst_2
2: idiv
3: ireturn

iload_0 将零给函数做参数，然后将其入栈。iconst_2将2入栈，这两个指令执行后，栈看上去是这个样子的。

+---+
TOS ->| 2 |
+---+
| a |
+---+

idiv携带两个值在栈顶， divides 只有一个值，返回结果在栈顶。

+--------+
TOS ->| result |
+--------+

ireturn取得比返回。 让我们处理双精度浮点整数。

public class calc
{
public static double half_double(double a)
{
return a/2.0;
}
}

清单54.7 常量区

...
#2 = Double 2.0d
...
public static double half_double(double);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=4, locals=2, args_size=1
0: dload_0
1: ldc2_w #2 // double 2.0d
4: ddiv
5: dreturn

类似，只是ldc2_w指令是从常量区装载2.0，另外，所有其他三条指令有d前缀，意思是他们工作在double数据类型下。

我们现在使用两个参数的函数。

public class calc
{
public static int sum(int a, int b)
{
return a+b;
}
}
public static int sum(int, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=2, args_size=2
0: iload_0
1: iload_1
2: iadd
3: ireturn

iload_0加载第一个函数参数（a)，iload_2 第二个参数(b)下面两条指令执行后，栈的情况如下：

+---+
TOS ->| b |
+---+
| a |
+---+

iadds 增加两个值，返回结果在栈顶。 +——–+ TOS ->| result | +——–+

让我们把这个例子扩展成长整型数据类型。

public static long lsum(long a, long b)
{
return a+b;
}

我们得到的是：

public static long lsum(long, long);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=4, locals=4, args_size=2
0: lload_0
1: lload_2
2: ladd
3: lreturn

第二个（load指令从第二参数槽中，取得第二参数。这是因为64位长整型的值占用来位，用了另外的话2位参数槽。）

稍微复杂的例子

public class calc
{
public static int mult_add(int a, int b, int c)
{
return a*b+c;
}
}
public static int mult_add(int, int, int);
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=3, args_size=3
0: iload_0
1: iload_1
2: imul
3: iload_2
4: iadd
5: ireturn