- Characteristics
- Performance
- Supported Element Types
- Declaration
- Literal Syntax
- Access
- Iteration
- Sorting
- No Duplicates
- Weak Value Maps
- Further Information
The map generic data type contains key/value pairs and is useful for associating values with other values. Other names for this data type are associative array and dictionary. It is implemented with a hash table.
Characteristics
- Unordered
- No key duplicates (each key element value is only stored once)
Performance
- No indexing
- Fast append/put (constant time, O(1), except if resize is necessary)
- Fast lookup for key contains test (constant time, O(1))
- No insert (because there is no order, append/put is the only way to add elements)
- Fast remove
- Large memory footprint (compared to sequence)
All element access depends on the performance of the hash function. For objects, the default hashing is based on a pointer, which is very fast (but has the drawback that the map has to be rehashed if the garbage collector moves any of the referred elements). Hashing on strings is linear to the length of the string. Hashing on large values, such as point, can also be noticeable.
Supported Element Types
The supported value element types for maps are any types with 4 bytes or less, and all pointer types (Object, str, str8, cstr, symbol, class, Type, Enum, etc.)
You can test the size of a type by just printing the size of the type as such:
pln(int.size);
The supported key element types for maps are any 8 bytes or less basic type or value:
- int8, int16, int, int64
- byte, word, nat
- char, cchar
- str, str8, cstr, symbol
- Object, Rigid
- class, Type, Enum
- time, timespan, date, datetime
- rangeI, rangeF
- pointF (cm.geometry)
- pointF2D (cm.geometry2D)
- pointI (cm.geometry2D)
- any 8-byte basic type or value
Examples of types that cannot be used as keys:
- float
- colorF, range
- point (cm.geometry)
- point2D (cm.geometry2D)
Examples of types that cannot be used as values (without wrapping in a class):
- int64
- time, timespan, date, datetime
- colorF, range, rangeI, rangeF, distance, weight
- point, pointF, point2D, pointF2D, pointI, angle
Declaration
keyElementType->valueElementType identifier;
Example
Declare a map from str to Object initialized to null:
str->Object map;
Declare and create an empty map in two equivalent ways:
str->Object map(); str->Object map = new str->Object();
It's also possible to create the map using the init feature:
str->Object map; ... init map();
You can also specify an initial capacity (measured in the number of elements) for the collection:
str->Object map(64); map = new str->Object(64); init map(64);
Even though the map will grow incrementally (by doubling its size) as necessary when you append elements, increasing the initial size can improve performance if you know that you will append a large number of elements. Generally speaking, however, you should be conservative with the allocation size.
Literal Syntax
str->double string2Double = {"aaa"->1.0, "bbb"->4.5}; int->bool int2Bool = {1->false, 2->true}; double->str[] double2StrArr = {1.3->["haha", "bbbb"]};
Access
{ int->str map(); map.put(1, "aa"); map.put(2, "bb"); map.put(3, "cc"); pln(#map); pln(#map.count); pln(#map.capacity); pln(#map.get(1)); pln(#map.get(3)); pln(#map.get(42)); pln(#map.contains(1)); pln(#map.contains(3)); pln(#map.contains(42)); map.remove(1); pln(#map); }
Iteration
Built-in for iteration is supported, but index operations (such as start=n, end=n, or reverse) are not suitable because the map has no deterministic order. You can, however, use the index keyword for-loop index. Also, note that the order of the elements in the iteration is to be considered random.
for (k, v in map) pln(k, " -> ", v);
Sorting
Sorting a map is not possible. You may want to use an index instead.
No Duplicates
It is important to note that maps will only ever store one instance of an object at a time as a key. The exact behavior of this feature can be controlled by specifying an eq-function that defines if two elements are the same or not. You can specify the hash and eq function the same way as for a Set.
Weak Value Maps
Weak Value maps are maps where its values are weakly-held Objects. This means that the value in the map will be the target for the garbage collection to be cleared when the object contains no other references.
Weak value maps can be defined during map instantiation with the code snippet
int -> Int info(weakValue=true);
Below are some test cases to show how the garbage collector works on weak maps
{ int -> Int weak(weakValue=true); int -> Int weak2(weakValue=true); weak.put(1, 1); Int ref = 2; weak2.put(ref.v, ref); _gc(); for (k, v in weak) { pln("weak"; #k; #v); } for (k, v in weak2) { pln("weak2"; #k; #v); } }
Output:
Full garbage collect
DO NOT CALL THIS DURING NORMAL PROGRAM OPERATION
THIS IS ONLY FOR DEBUGGING MEMORY LEAKS IN CONJUCTION WITH printHeapSummary()
gc: 5188 ms
weak, k=1, v=null
weak2, k=2, v=2
Further Information
See file your workspace/base/cm/lang/map.cmz
Comments
0 comments
Please sign in to leave a comment.