Associative array/Creation
In this task, the goal is to create an associative array.
You are encouraged to solve this task according to the task description, using any language you may know.
ActionScript
Because ActionScript does not have associative arrays in the normal sense, Object objects are used instead and keys are simply properties on those objects. <lang actionscript> var map:Object = {key1: "value1", key2: "value2"}; trace(map['key1']); // outputs "value1"
// Dot notation can also be used trace(map.key2); // outputs "value2"
// More keys and values can then be added map['key3'] = "value3"; trace(map['key3']); // outputs "value3" </lang>
Ada
<lang ada>
with Ada.Containers.Ordered_Maps;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO;
procedure Associative_Array is
-- Instantiate the generic package Ada.Containers.Ordered_Maps
package Associative_Int is new Ada.Containers.Ordered_Maps(Unbounded_String, Integer);
use Associative_Int;
Color_Map : Map;
Color_Cursor : Cursor;
Success : Boolean;
Value : Integer;
begin
-- Add values to the ordered map
Color_Map.Insert(To_Unbounded_String("Red"), 10, Color_Cursor, Success);
Color_Map.Insert(To_Unbounded_String("Blue"), 20, Color_Cursor, Success);
Color_Map.Insert(To_Unbounded_String("Yellow"), 5, Color_Cursor, Success);
-- retrieve values from the ordered map and print the value and key
-- to the screen
Value := Color_Map.Element(To_Unbounded_String("Red"));
Ada.Text_Io.Put_Line("Red:" & Integer'Image(Value));
Value := Color_Map.Element(To_Unbounded_String("Blue"));
Ada.Text_IO.Put_Line("Blue:" & Integer'Image(Value));
Value := Color_Map.Element(To_Unbounded_String("Yellow"));
Ada.Text_IO.Put_Line("Yellow:" & Integer'Image(Value));
end Associative_Array;
</lang>
ALGOL 68
main:(
MODE COLOR = BITS;
FORMAT color repr = $"16r"16r6d$;
# This is an associative array which maps strings to ints #
MODE ITEM = STRUCT(STRING key, COLOR value);
REF[]ITEM color map items := LOC[0]ITEM;
PROC color map find = (STRING color)REF COLOR:(
REF COLOR out;
# linear search! #
FOR index FROM LWB key OF color map items TO UPB key OF color map items DO
IF color = key OF color map items[index] THEN
out := value OF color map items[index]; GO TO found
FI
OD;
NIL EXIT
found:
out
);
PROC color map = (STRING color)REF COLOR:(
REF COLOR out = color map find(color);
IF out :=: REF COLOR(NIL) THEN # extend color map array #
HEAP[UPB key OF color map items + 1]ITEM color map append;
color map append[:UPB key OF color map items] := color map items;
color map items := color map append;
value OF (color map items[UPB value OF color map items] := (color, 16r000000)) # black #
ELSE
out
FI
);
# First, populate it with some values #
color map("red") := 16rff0000;
color map("green") := 16r00ff00;
color map("blue") := 16r0000ff;
color map("my favourite color") := 16r00ffff;
# then, get some values out #
COLOR color := color map("green"); # color gets 16r00ff00 #
color := color map("black"); # accessing unassigned values assigns them to 16r0 #
# get some value out without accidentally inserting new ones #
REF COLOR value = color map find("green");
IF value :=: REF COLOR(NIL) THEN
put(stand error, ("color not found!", new line))
ELSE
printf(($"green: "f(color repr)l$, value))
FI;
# Now I changed my mind about my favourite color, so change it #
color map("my favourite color") := 16r337733;
# print out all defined colors #
FOR index FROM LWB color map items TO UPB color map items DO
ITEM item = color map items[index];
putf(stand error, ($"color map("""g""") = "f(color repr)l$, item))
OD;
FORMAT fmt;
FORMAT comma sep = $"("n(UPB color map items-1)(f(fmt)", ")f(fmt)")"$;
fmt := $""""g""""$;
printf(($g$,"keys: ", comma sep, key OF color map items, $l$));
fmt := color repr;
printf(($g$,"values: ", comma sep, value OF color map items, $l$))
)
Output:
green: 16r00ff00
color map("red") = 16rff0000
color map("green") = 16r00ff00
color map("blue") = 16r0000ff
color map("my favourite color") = 16r337733
color map("black") = 16r000000
keys: ("red", "green", "blue", "my favourite color", "black")
values: (16rff0000, 16r00ff00, 16r0000ff, 16r337733, 16r000000)
APL
⍝ Create a namespace ("hash")
X←⎕NS ⍬
⍝ Assign some names
X.this←'that'
X.foo←88
⍝ Access the names
X.this
that
⍝ Or do it the array way
X.(foo this)
88 that
⍝ Namespaces are first class objects
sales ← ⎕NS ⍬
sales.(prices quantities) ← (100 98.4 103.4 110.16) (10 12 8 10)
sales.(revenue ← prices +.× quantities)
sales.revenue
4109.6
AWK
Arrays in AWK are indeed associative arrays. <lang awk>BEGIN {
a["red"] = 0xff0000
a["green"] = 0x00ff00
a["blue"] = 0x0000ff
for (i in a) {
printf "%8s %06x\n", i, a[i]
}
# deleting a key/value
delete a["red"]
for (i in a) {
print i
}
# check if a key exists
print ( "red" in a ) # print 0
print ( "blue" in a ) # print 1
}</lang>
C
Standard C libraries have not an associative array facility. So programmer must implement their own hashes, or use existing non standard libraries. I have not found de facto standard libraries (i.e. libraries so widespread and well-known that could be considered standard).
Here I have used Judy.
<lang c>#include <stdio.h>
- include <Judy.h>
int main() {
Pvoid_t assarray = (Pvoid_t) NULL; PWord_t value; int retval;
/* populating */ JSLI(value, assarray, "red"); *value = 0xff0000; JSLI(value, assarray, "green"); *value = 0x00ff00; JSLI(value, assarray, "blue"); *value = 0x0000ff;
/* retrieving existent */
JSLG(value, assarray, "blue");
printf("blue is #%06x\n", *value);
/* unknown key */
JSLG(value, assarray, "nonexistingkey");
if ( value == NULL ) { fprintf(stderr, "key 'nonexistingkey' does not exists\n"); }
/* deleting */
JSLD(retval, assarray, "red");
JSLG(value, assarray, "red");
if ( value == NULL ) { fprintf(stderr, "key red does not exist anymore\n"); }
return 0;
}</lang>
C++
The C++ standard defines std::map as a means of creating an association between a key of one arbitrary type and a value of another arbitrary type. This requires the inclusion of the standard header map.
<lang cpp>#include <map></lang>
Creation
To create a simple map whose key is of type A and whose value is of type B, one would define the variable like so: <lang cpp>std::map<A, B> exampleMap</lang>
If one wanted to us a key type of int and a value of double, you would define it like so:
<lang cpp>std::map<int, double> exampleMap</lang>
Insertion
Once we've created our map, we've got a couple different ways to insert the value. Let's use an example key of 7, and an exable value of 3.14.
Operator[]
The first method is using the [] operator. <lang cpp>exampleMap[7] = 3.14</lang>
Of course, you can use a variable (or any rvalue of the correct type) for the key or value parameters: <lang cpp>int myKey = 7; double myValue = 3.14; exampleMap[myKey] = myValue;</lang>
insert()
The second approach is a little more complicated. We have to use the pair<> template: <lang cpp>exampleMap.insert(std::pair<int, double>(7,3.14));</lang>
Lookup
As with insertion, there are a couple ways we can retrieve the value.
operator[]
We use it as an rvalue, supplying the correct key: <lang cpp>myValue = exampleMap[myKey]</lang> If the value doesn't already exist, a default-constructed object of the value's type will be inserted using the key you specified, and that default value will be returned.
find()
Alternatively, you can look up a value by using find(), storing its return value in an iterator, and comparing the iterator against the map's end() sentinal value: <lang cpp>double myValue = 0.0; std::map<int, double>::iterator myIterator = exampleMap.find(myKey); if(exampleMap.end() != myIterator) {
// Return the value for that key. myValue = myIterator->second;</lang cpp>
}</lang>
The need for the ->second code is because our iterator points to a pair<>(), and our value is the second member of that pair.
This code assigns a 0 to myValue if the map contained a value.
Example
This simple program creates a map, assigns a value to that map, retrieves a value from that map, and prints the value to STDOUT. <lang cpp>#include <map>
- include <iostreams>
int main() {
// Create the map. std::map<int, double> exampleMap;
// Choose our key int myKey = 7;
// Choose our value double myValue = 3.14;
// Assign a value to the map with the specified key. exampleMap[myKey] = myValue;
// Retrieve the value double myRetrievedValue = exampleMap[myKey];
// Display our retrieved value. std::cout << myRetrievedValue << std::endl;
// main() must return 0 on success. return 0;
}</lang>
C#
Platform: .NET 1.x
System.Collections.HashTable map = new System.Collections.HashTable(); map["key1"] = "foo";
Platform: .NET 2.0
Dictionary<string, string> map = new Dictionary<string,string>(); map[ "key1" ] = "foo";
<lang csharp>
var map = new Dictionary<string, string> Template:"key1", "foo";
</lang>
ColdFusion
<cfset myHash = structNew()>
<cfset myHash.key1 = "foo">
<cfset myHash["key2"] = "bar">
<cfset myHash.put("key3","java-style")>
In ColdFusion, a map is literally a java.util.HashMap, thus the above 3rd method is possible.
Common Lisp
;; default :test is #'eql, which is suitable for numbers only, ;; or for implementation identity for other types! ;; Use #'equalp if you want case-insensitive keying on strings.
(setf my-hash (make-hash-table :test #'equal)) (setf (gethash "H2O" my-hash) "Water") (setf (gethash "HCl" my-hash) "Hydrochloric Acid") (setf (gethash "CO" my-hash) "Carbon Monoxide")
;; That was actually a hash table, an associative array or ;; alist is written like this: (defparameter *legs* '((cow . 4) (flamingo . 2) (centipede . 100))) ;; you can use assoc to do lookups and cons new elements onto it to make it longer.
D
int[string] hash = ["foo"[]:42, "bar":100];
assert("foo" in hash);
E
[].asMap() # immutable, empty
["one" => 1, "two" => 2] # immutable, 2 mappings
[].asMap().diverge() # mutable, empty
["one" => 2].diverge(String, float64) # mutable, initial contents,
# typed (coerces to float)
Forth
The Forth dictionary is normally only used for function and symbol definitions, but you can also define separate wordlists for holding functions or data. There is no special syntax in the language for this, but you can define your own. All of Forth's defining words are available for adding things to the wordlist, but CREATE is most generic.
: get ( key len table -- data ) \ 0 if not present
search-wordlist if
>body @
else 0 then ;
: put ( data key len table -- )
>r 2dup r@ search-wordlist if
r> drop nip nip
>body !
else
r> get-current >r set-current \ switch definition word lists
nextname create ,
r> set-current
then ;
wordlist constant bar 5 s" alpha" bar put 9 s" beta" bar put 2 s" gamma" bar put s" alpha" bar get . \ 5 8 s" Alpha" bar put \ Forth dictionaries are normally case-insensitive s" alpha" bar get . \ 8
This is not necessarily a good option in all Forths, as the dictionary may be implemented as a simple linked list (normally not a problem because the dictionary is only used for compiling and interactive interpretation). GNU Forth and many other hosted Forths use hash tables for the dictionary, so this is a fine choice. If you need case-sensitive keys, GNU Forth has table and table-find, replacing wordlist and search-wordlist, respectively.
(The use of nextname ( str len -- ) is a GNU Forth extension to create; there is no means in the ANS standard to use a string on the stack to create a dictionary entry.)
Hashtable for mapping strings to integer
include ffl/hct.fs \ Create a hash table 'table' in the dictionary with a starting size of 10 10 hct-create htable \ Insert entries 5 s" foo" htable hct-insert 10 s" bar" htable hct-insert 15 s" baz" htable hct-insert \ Get entry from the table s" bar" htable hct-get [IF] .( Value:) . cr [ELSE] .( Entry not present.) cr [THEN]
Groovy
Create an empty map and add values
map = [:]
map[7] = 7
map['foo'] = 'foovalue'
map.put('bar', 'barvalue')
map.moo = 'moovalue'
assert 7 == map[7]
assert 'foovalue' == map.foo
assert 'barvalue' == map['bar']
assert 'moovalue' == map.get('moo')
Create a pre-populated map and verify values
map = [7:7, foo:'foovalue', bar:'barvalue', moo:'moovalue']
assert 7 == map[7]
assert 'foovalue' == map.foo
assert 'barvalue' == map['bar']
assert 'moovalue' == map.get('moo')
Haskell
import Data.Map
dict = fromList [("key1","val1"), ("key2","val2")]
Icon
procedure main() local t t := table() t["foo"] := "bar" write(t["foo"]) end
Java
Defining the Map:
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("foo", 5);
map.put("bar", 10);
map.put("baz", 15);
map.put("foo", 6)
"Putting" a value for a key that already exists ("map.put("foo", 6)" in this example) will replace and return the old value for the key.
Retrieving a value:
map.get("foo") // => 5
map.get("invalid") // => null
Iterate over keys:
for (String key: map.keySet())
System.out.println(key);
Iterate over values:
for (int value: map.values())
System.out.println(value);
Iterate over key, value pairs:
for (Map.Entry<String, Integer> entry: map.entrySet())
System.out.println(entry.getKey() + " => " + entry.getValue());
JavaScript
In Javascript we make an associative array from an empty object, otherwise if we make it from an array we'll get all the Array object's method and properties when we iterate over it
var assoc = {};
assoc['foo'] = 'bar';
assoc['another-key'] = 3;
assoc.thirdKey = 'we can also do this!';
for(key in assoc)
{
alert('key:"'+key+'", value:"'+assoc[key]+'"');
}
The above associative array can also be constructed using Javascript's object literal syntax
var assoc = {
'foo':'bar',
'another-key':3, //the key can either be enclosed by quotes or not
'thirdKey' = 'we can also do this!'
};
Notice the quotes on the names. When quoting the names you avoid potential collisions with reserved JavaScript key words. \\ http://www.quackit.com/javascript/javascript_reserved_words.cfm
Logo
UCB Logo has "property lists" which associate names with values. They have their own namespace.
pprop "animals "cat 5 pprop "animals "dog 4 pprop "animals "mouse 11 print gprop "animals "cat ; 5 remprop "animals "dog show plist "animals ; [mouse 11 cat 5]
Lua
Lua tables are Hashes
hash = {}
hash[ "key-1" ] = "val1"
hash[ "key-2" ] = 1
hash[ "key-3" ] = {}
Returns nil on unknown key.
Objective-C
You can use a NSDictionary to create an immutable hash. A dictionary can contain only objects; if you want store non objects like integer, you have to box it in NSNumber.
NSDictionary *dict = [NSDictionary dictionaryWithObjectsAndKeys:
@"Joe Doe", @"name",
[NSNumber numberWithUnsignedInt:42], @"age",
[NSNull null], @"extra",
nil];
To create a mutable dictionary, use NSMutableDictionary:
NSMutableDictionary *dict = [NSMutableDictionary dictionary]; [dict setObject:@"Joe Doe" forKey:@"name"]; [dict setObject:[NSNumber numberWithInt:42] forKey:@"age"];
You can access value with objectForKey:. If a key does not exists, nil is returned.
NSString *name = [dict objectForKey:@"name"]; unsigned age = [dict objectForKey:@"age"] unsignedIntValue]; id missing = [dict objectForKey:@"missing"];
OCaml
Hash table
A simple idiom to create a hash table mapping strings to integers:
let hash = Hashtbl.create 0;; List.iter (fun (key, value) -> Hashtbl.add hash key value) ["foo", 5; "bar", 10; "baz", 15];;
To retrieve a value:
let bar = Hashtbl.find hash "bar";; (* bar = 10 *)
To retrieve a value, returning a default if the key is not found:
let quux = try Hashtbl.find hash "quux" with Not_found -> some_value;;
Binary tree
A simple idiom to create a persistent binary tree mapping strings to integers:
module String = struct
type t = string
let compare = Pervasives.compare
end
module StringMap = Map.Make(String);;
let map = StringMap.empty;;
let map = List.fold_left (fun map (key, value) -> StringMap.add key value map) map
["foo", 5; "bar", 10; "baz", 15];;
To retrieve a value:
let bar = StringMap.find "bar" map;; (* bar = 10 *)
To retrieve a value, returning a default if the key is not found:
let quux = try StringMap.find "quux" map with Not_found -> some_value;;
Perl
Hash
Definition:
# using => key does not need to be quoted unless it contains special chars my %hash = ( key1 => 'val1', 'key-2' => 2, three => -238.83, 4 => 'val3', ); # using , both key and value need to be quoted if containing something non-numeric in nature my %hash = ( 'key1', 'val1', 'key-2', 2, 'three', -238.83, 4, 'val3', );
Use:
print $hash{'key1'};
$hash{'key1'} = 'val1';
@hash{'key1', 'three'} = ('val1', -238.83);
HashRef
Definition:
my $hashref = {
key1 => 'val1',
'key-2' => 2,
three => -238.83,
4 => 'val3',
}
Use:
print $hash->{'key1'};
$hash->{'key1'} = 'val1';
@hash->{'key1', 'three'} = ('val1', -238.83);
PHP
$array = array(); $array['foo'] = 'bar'; $array['bar'] = 'foo'; echo($array['foo']); // bar echo($array['moo']); // Undefined index
//alternative (inline) way
$array2 = array('fruit' => 'apple',
'price' => 12.96,
'colour' => 'green');
Iterate over key/value
foreach($array as $key => $value)
{
echo "Key: $key Value: $value";
}
Pop11
;;; Create expandable hash table of initial size 50 and with default
;;; value 0 (default value is returned when the item is absent).
vars ht = newmapping([], 50, 0, true);
;;; Set value corresponding to string 'foo'
12 -> ht('foo');
;;; print it
ht('foo') =>
;;; Set value corresponding to vector {1 2 3}
17 -> ht({1 2 3});
;;; print it
ht({1 2 3}) =>
;;; Set value corresponding to number 42 to vector {0 1}
{0 1} -> ht(42);
;;; print it
ht(42) =>
;;; Iterate over keys printing keys and values.
appproperty(ht,
procedure (key, value);
printf(value, '%p\t');
printf(key, '%p\n');
endprocedure);
Python
Hashes are a built-in type called dictionaries (or mappings) in Python.
<lang python>
hash = dict() # 'dict' is the dictionary type.
hash = dict(red="FF0000", green="00FF00", blue="0000FF")
hash = { 'key1':1, 'key2':2, }
value = hash[key]
</lang>
Numerous methods exist for the mapping type http://docs.python.org/lib/typesmapping.html
<lang python>
# empty dictionary
d = {}
d['spam'] = 1
d['eggs'] = 2
# dictionaries with two keys
d1 = {'spam': 1, 'eggs': 2}
d2 = dict(spam=1, eggs=2)
# dictionaries from tuple list
d1 = dict([('spam', 1), ('eggs', 2)])
d2 = dict(zip(['spam', 'eggs'], [1, 2]))
# iterating over keys for key in d: print key, d[key]
# iterating over (key, value) pairs for key, value in d.iteritems(): print key, value
</lang>
Note: Python dictionary keys can be of any arbitrary "hashable" type. The following contains several distinct key value pairs:
<lang python> myDict = { '1': 'a string', 1: 'an integer', 1.0: 'a floating point number', (1,): 'a tuple' } </lang>
(Some other languages such as awk and Perl evaluate all keys such that numerically or lexically equivalent expressions become identical entries in the hash or associative array).
User defined classes which implement the __hash__() special method can also be used as dictionary keys. It's the responsibility of the programmer to ensure the properties of the resultant hash value. The instance object's unique ID (accessible via the id() built-in function) is commonly used for this purpose.
Raven
{ 'a' 1 'b' 2 'c' 3.14 'd' 'xyz' } as a_hash
a_hash print
hash (4 items) a => 1 b => 2 c => 3.14 d => "xyz"
a_hash 'c' get # get key 'c' 6.28 a_hash 'c' set # set key 'c' a_hash.'c' # get key 'c' shorthand 6.28 a_hash:'c' # set key 'c' shorthand
Null is returned for unknown keys.
Ruby
A hash object that returns nil for unknown keys
hash={}
hash[666]='devil'
hash[777] # => nil
hash[666] # => 'devil'
A hash object that returns 'unknown key' for unknown keys
hash=Hash.new('unknown key')
hash[666]='devil'
hash[777] # => 'unknown key'
hash[666] # => 'devil'
A hash object that returns "unknown key #{key}" for unknown keys
hash=Hash.new{|h,k|h[k]="unknown key #{k}"}
hash[666]='devil'
hash[777] # => 'unknown key 777'
hash[666] # => 'devil'
Scala
// immutable maps var map = Map(1 -> 2, 3 -> 4, 5 -> 6) map(3) // 4 map = map + (44 -> 99) // maps are immutable, so we have to assign the result of adding elements map.isDefinedAt(33) // false map.isDefinedAt(44) // true
// mutable maps (HashSets) import scala.collection.mutable.HashMap val hash = new HashMap[int, int] hash(1) = 2 hash += (1 -> 2) // same as hash(1) = 2 hash += (3 -> 4, 5 -> 6, 44 -> 99) hash(44) // 99 hash.contains(33) // false hash.isDefinedAt(33) // same as contains hash.contains(44) // true
// iterate over key/value
hash.foreach {e => println("key "+e._1+" value "+e._2)} // e is a 2 element Tuple
// same with for syntax
for((k,v) <- hash) println("key " + k + " value " + v)
// items in map where the key is greater than 3
map.filter {k => k._1 > 3} // Map(5 -> 6, 44 -> 99)
// same with for syntax
for((k, v) <- map; if k > 3) yield (k,v)
Smalltalk
states := Dictionary new. states at: 'MI' put: 'Michigan'. states at: 'MN' put: 'Minnesota'.
Tcl
All arrays in Tcl are associative.
# Create one element at a time: set hash(foo) 5
# Create in bulk:
array set hash {
foo 5
bar 10
baz 15
}
# Access one element: set value $hash(foo)
# Output all values:
foreach key [array names hash] {
puts $hash($key)
}
Toka
Toka provides associative arrays via a library.
needs asarray
( create an associative array ) 1024 cells is-asarray foo
( store 100 as the "first" element in the array ) 100 " first" foo asarray.put
( store 200 as the "second" element in the array ) 200 " second" foo asarray.put
( obtain and print the values ) " first" foo asarray.get . " second" foo asarray.get .
UnixPipes
A sorted key value file can be considered as an associative array
cat <<EOF >p.map apple a boy b cat c dog d elephant e EOF
map='p.map'
put() {
k=$1; v=$2;
cat $map | (rm $map;cat) | sort |grep -v "$k$" | sort -m - <(echo $v $k) | uniq -n1 >$map
}
get() {
k=$1
cat $map | grep "$k$"
}
put c cow get c