mappings

使用映射 (mapping)　　　　 1992 September 28 MudOS 映射資料型態文件 -　撰稿: Truilkan@TMI

MudOS 0.9 提供了名為「映射」的資料型態. 映射與其他語言中的聯結陣列 (associative arrays)　一樣 (例如 Perl). 一個聯結陣列與普通的陣列類似, 但是聯結陣列可以使用任何資料型態 (字串、物件、整數、陣列等等) 作為索引(index) , 而陣列只能使用整數. 另外, 聯結陣列是疏鬆的陣列 (sparse arrays), 也就是說, 您可以只指定第 1,000,000　項元素的內容, 而不必指定其他元素.
映射有兩個實際的用途:

這樣宣告一個映射:

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　的乘冪 (power of 2).　當資料搜尋表的內容裝滿一定的程度時, 資料搜尋表的就增為兩倍以維持資料搜尋的效率.

作者:

MudOS 的映射原本由 Whiplash@TMI 所寫. 其中的一部份後來由 Truilkan@TMI 重寫﹝使用可擴充式的資料搜尋表以替換原來的二元樹 (binary tree)﹞.

映射資料結構的一部份是基於 Larry Wall 寫的 Perl 程式語言的 hash.c 模組. Perl　的整套程式適用於 GNU Copyleft general public license.

翻譯: Spock @ FF 97.Aug.11.

回到上一頁