mappings

---

ʹ��ӳ�� (mapping)�������� 1992 September 28 MudOS ӳ�����������ļ� -�� ׫��: Truilkan@TMI

---

MudOS 0.9 �ṩ����Ϊ��ӳ�䡹����������. ӳ�������������е��������� (associative arrays)�� һ�� (���� Perl). һ��������������ͨ����������, ���������������ʹ���κ��������� (�ַ��������������������ȵ�) ��Ϊ����(index) , ������ֻ��ʹ������. ����, �������������ɵ����� (sparse arrays), Ҳ����˵, ������ָֻ���� 1,000,000�� ��Ԫ�ص�����, ������ָ������Ԫ��.
ӳ��������ʵ�ʵ���;:

1)�� ���ݿ�
2)�� ���� C�� �ļ����������� struct. ֻ��Ҫ��ӳ���еĹؼ��� (key) ���� struct�� ����λ (field)�� ����.

��������һ��ӳ��:

mapping x;

һ��ӳ����������ַ�����ʼ�� (initialize):

x = ([�ؼ���һ : ����ֵһ, �ؼ��ֶ� : ����ֵ��, ...]);

���� (ע��: x = ([]); �������һ���յ�ӳ��)

��ע��һ��ӳ������ȳ�ʼ��, ����ָ�����е��κ�Ԫ��. �д���������Ϊ��Ϸ�����������еı�����ʼ��Ϊ 0 (���ܱ�����ʲô����).�� �����û�г�ʼ��һ��ӳ��, ��Ϊ������ָ��Ԫ��ʱ, �ͻῴ�� Indexing on illegal type�� (����ָ�����������Υ��) �Ĵ���.

�µ� (�ؼ���, ����ֵ) ���������µķ����ӽ�һ��ӳ��:

x[key] = value;

��������ʹ��������Ѱ����ӳ�� x�� �е��ض��ؼ��� (key). ���ӳ�� x�� �д˹ؼ���, ��ӳ�������������ֵ (value)�� �ͻ��ɵȺ��ұ�ָ����ֵ. ���ӳ�䲢û�а�������ؼ���, ����Զ���̬ (dynamically) ���� (allocate)�� ����Ŀռ�, �����µ� (�ؼ���, ����ֵ) ����ӳ����.

ӳ���е�һ��Ԫ�ؿ������еķ�ʽ��ȡ:

write(x[key] + "\n");

һ�������Ԫ�ؿ������еķ�ʽɾ��:

map_delete(x, key);

ɾ��֮��, �������������ʽΪ�� (1):

undefinedp(x[key])

����������׫д�����µ�Դ����:

if (undefinedp(value = x["MudOS"])) {
write("��MudOS��Ϊӳ�� x ��һ��Ԫ�ء�\n");
} else {
write("�ؼ�ֵ��MudOS����ֵ�ǣ�" + value + "��\n");
}

�ؼ��� (����) ���б������ keys() �ⲿ�����г�, ��������:

���� mixed *idx;
���� map x;

���� x = ([ "x" : 3, "y" : 4]);
���� idx = keys(x);�������������� /* idx == ({"x", "y"}) �� ({"y", "x"}) */

��ע��, ���������Ե�, keys()�� ����һ�������˳�� (random) �����������б� (���������˳��, ��ӳ�䴢�����ݵķ�ʽ�ĸ����� ---- �ڴ�, ����Ϊ������ʽ������Ѱ�� (extensible hash table)�� ˳��Ĺ�ϵ)

һ��ӳ�������ֵ (values) �б�, ���� values() �ⲿ�����г�:

idx = values(x);

ʹ idx ���� ({3, 4}) �� ({4, 3}). ע��, values() ���ص�����ֵ˳����� keys() ���ص�˳����ͬ.

��(�ؼ���, ����ֵ) ��һ��ӳ����, �������� each()�� �ⲿ����������Ѱ. each()�� ���ҵ�ӳ���β��ʱ, �ͷ���һ�������� (null vector).�� each() ���� (�ؼ���, ����ֵ) ��˳��, �� keys() �� values()�� ���ص�˳����ͬ. ����:

mixed *pair;

while ((pair = each(x)) != ({})) {

write("key���� = " + pair[0] + "\n");
write("value = " + pair[1] + "\n");
}

ӳ�����Ϊ��Ԫ (two-dimensional) (���Ǹ��ߴ�Ԫ��ӳ��),�� ������ LPC�� ������ͬ:
��

mapping x, y;

x = ([]);
y = ([]);

y["a"] = "c";
x["b"] = y;

�� x["b"]["a"]�� == "c"

ӳ��Ҳ������ *�� (�˷�) �������ϵõ� (��ѧ�ϵ����).

mapping r1, r2, a;

r1 = ([]);
r2 = ([]);

r1["driver"] = "mudlib";
r2["mudlib"] = "castle";

����:

a = r1 * r2

����� a["driver"] == "castle";

��Ҳ���Խ�����ӳ�����. ����ӳ����ܺͶ���Ϊ����ӳ������� (union).

a = r1 + r2

����� a["driver"] == "mudlib" �� a["mudlib"] == "castle"

��+=��Ҳ��ʹ��. ������������:

a += ([key : value]);

���Դ���:

a[key] = value;

����, �������� a[key] = value ����ʽҪ��ǰ��� a += ([key : value]) �ķ���Ҫ������Ч��. ��Ϊǰ��ķ�����Ҫ����һ���µ�ӳ����밴: ָ ([key : value]) ���ӳ���, �����߲���.

ӳ�䲻��ʹ�� - (����) �������Ҫʹ�� map_delete() ��.

sizeof() �ⲿ���������ж�һ��ӳ�����ж��ٶ� (�ؼ���, ����ֵ)�� ������.

write("ӳ�� x �ں� " + sizeof(x) + " ��Ԫ�ء�\n");

�ڲ������� (implementation):

MudOS ��ӳ��ʹ�ÿ�����ʽ��������Ѱ�� (extensible hash table). ������Ѱ��Ĵ�Сһ���� 2�� �ij��� (power of 2).�� ��������Ѱ�������װ��һ���ij̶�ʱ, ������Ѱ��ľ���Ϊ������ά��������Ѱ��Ч��.

---

����:

---

MudOS ��ӳ��ԭ���� Whiplash@TMI ��д. ���е�һ���ݺ����� Truilkan@TMI ��д��ʹ�ÿ�����ʽ��������Ѱ�����滻ԭ���Ķ�Ԫ�� (binary tree)��.

ӳ�����ݽṹ��һ�����ǻ��� Larry Wall д�� Perl �������Ե� hash.c ģ��. Perl�� �����׳��������� GNU Copyleft general public license.

---

����: Spock @ FF 97.Aug.11.

---

�ص���һҳ

---