Updated 2014-07-07 05:28:47 by RLE

dict is a built-in command for creating and manipulating dictionaries (dicts), which are lists with an even number of elements where every two elements are interpreted as a key/value pair.

Documentation  edit

official reference
Changes in Tcl/Tk 8.5
links to the exact TIPs that specify this command.
TIP 111

Reference  edit

Associative Array, Wikipedia
Comparison of programming languages (mapping), Wikipedia

See Also  edit

dict tips and tricks
dictutils
a collection of dict-related utilities: witharray, equal, apply, capture, nlappend, switch
forward-compatible dict
pure-Tcl 8.4 implementation of the [dict] command
dictn
an experimental wrapper over dict, focused on nested lists
dict in snit
dictionaries as arrays
dictionaries as arrays by Stubs
everything is a dict
dict probe
dict vs array speed
eDictor
a visual editor for nested Tcl dicts and lists saved as data files
dictree
another visual editor for nested Tcl dicts using ttk::treeview
dict lappend2
pdict
pretty-print a dict
shorthand dict set
merge dict set into set
Another Tcl dict operation: nested merge

Synopsis  edit

Value-oriented

dict create ?key value ...?
dict exists dictionaryValue key ?key ...?
dict filter dictionaryValue filterType arg ?arg ...?
dict for {keyVar valueVar} dictionaryValue body
dict get dictionaryValue ?key ...?
dict info dictionaryValue
dict keys dictionaryValue ?globPattern?
dict map {keyVar valueVar} dictionaryValue body
dict merge ?dictionaryValue ...?
dict remove dictionaryValue ?key ...?
dict replace dictionaryValue ?key value ...?
dict size dictionaryValue
dict values dictionaryValue ?globPattern?

Variable-oriented

dict append dictionaryVariable key ?string ...?
dict incr dictionaryVariable key ?increment?
dict lappend dictionaryVariable key ?value ...?
dict set dictionaryVariable key ?key ...? value
dict unset dictionaryVariable key ?key ...?
dict update dictionaryVariable key varName ?key varName ...? body
dict with dictionaryVariable ?key ...? body

Description  edit

a dict, or dictionary, is a list having an even number of elements. Each pair of elements, from left to right, represents a key-value pair.

The internal representation of a dict is quite different from the internal representation of a list, and has different performance characteristics. Where its important to avoid shimmering, use only dict commands on the value.

The conversion between internal dict and list representations is lossless. I.e., a round-trip conversion from dict to list and back again will result in the original value. Duplicate keys, for example, will be retained.

A dict orders its elements according to the order in which they were added. list operations on a dict value reflect this. With dict create, key-value pairs are added from left to right, as they occur in the command.

dict was introduced in Tcl 8.5.

Etymology  edit

LV 2007-12-21: Anyone have an explanation why the data structure managed by this command is called dictionary? What is the relationship between the name and the behavior? Just curious...

Lars H: This is what they're called in for example PostScript, so I suppose the usage is fairly old and wide-spread. Etymologically the origin is probably the word translation dictionary as shown below, but there is also the question of where that made it into the realm of computer science.

LV: Thanks. Knowing that it is the name used in other languages helps. When I hear people refer to a Tcl array as a hash, I wonder where the references come from and why.

Lars H: Perhaps Perl? Basically, a dictionary corresponds to the set-theoretic function concept: The domain is the set of keys, and to each key is assigned exactly one value, period. A hash is a data structure that can be used to efficiently implement dictionaries, but there are alternatives such as balanced trees and skiplists.

Simple example  edit

Example dictionary value (English-French):
% set e_f [dict create dog chien cat chat cow vache horse cheval]
dog chien cat chat cow vache horse cheval

The resulting value reflects the order of the arguments.

More examples  edit

pcm: Here is a useful example: an array of dicts.
array set U {
    tom  { Name "Tom Brown"  Sex M  Age 19  Class {4 5} }
    mary { Name "Mary Brown" Sex F  Age 16  Class {5}   }
    sam  { Name "Sam Spade"  Sex M  Age 19  Class {3 4} }
}

dict set     U(tom)  Sex F
dict append  U(sam)  Name " Jr"
dict lappend U(sam)  Class 5
dict incr    U(mary) Age
dict set     U(tom)  Sax Y;  # Creates a new key.
dict set     U(bill) Sax N;  # Creates a new entry.

parray U

AMW: Here is another example, storing filesystem information in a dict that reflects the hierarchy (taken from dictree):
proc dictdir { { dir .} } {
    set d ""
    foreach subdir [lsort [glob -directory $dir -nocomplain -types d "*"]] {
        dict set d [file tail $dir]/ [dictdir $subdir]
    }
    foreach fname [lsort [glob -directory $dir -nocomplain -types f "*"]] {
        file stat $fname fstat
        # unsorted but faster:
        # dict set d [file tail $dir]/ [file tail $fname] [array get fstat]
        # sorted:
        foreach item [lsort [array names fstat]] {
            dict set d [file tail $dir]/ [file tail $fname] $item $fstat($item)
        }
    }
    return $d
}

Implementation of ordered dict  edit

With revision 1.53 of tclDictObj.c (2007-11-20 20:43:11), dict was changed to preserve item order. The log entry by dkf says:
Changed the underlying implementation of the hash table used in dictionaries to additionally keep all entries in the hash table in a linked list, which is only ever added to at the end. This makes iteration over all entries in the dictionary in key insertion order a trivial operation, and so cleans up a great deal of complexity relating to dictionary representation and stability of iteration order.

This change makes the string representations of pure dicts more sensitive to the way the dictionary was created than they used to be, but the dependency was always there.

DKF: Technically, sort of. No more so than with lists. What it does do is eliminate the fact that certain sequences of operations previously could (without changing the final mapping from the initial mapping) cause the reordering of all elements in the dictionary. Basically, the sequence of operations was to add dummy mappings until the backing hash was rebuilt, causing the allocation of mapping entries differently to the hash table buckets. Strip out the dummy mappings then to get back the "original" dict, except now with the elements in a different order. Moreover the representation of a dict with a new mapping added to it would probably be different if you started with a dict that had gone through this process than if you had not.

To summarize, the old dict code's iteration order (which was the natural iteration order of the underlying Tcl_HashTable) was unstable and exposed far too much information about the history of the dictionary value. The new dict's stable iteration order depends only on the order in which new keys are inserted and old keys removed, and could be modeled (inefficiently) using lists or strings; its behaviour requires no understanding of the implementation to explain.

Dictionaries and arrays  edit

The result of array get and the argument expected by array set are in the same format as a dict, so you can naturally switch between them:
set myDict [array get myArray]
dict set myDict foo bar bob $newValue
array set myArray $myDict

RHS: was doing some coding for the Language Shootout, and implemented the nsieve test using both arrays and dicts. Results can be found on the Dict vs Array Speed page

AMG: Be aware that dict preserves key order but array does not.

Shimmering between dict and list  edit

AMG: I wonder if shimmering between dict and list can be minimized by unifying their Tcl_Obj internal data structures. Just add a Tcl_HashTable pointer to struct List, and get rid of struct Dict. If the Tcl_HashTable pointer is NULL, a dict representation doesn't currently exist for the list. If the pointer isn't NULL, it points to a hash table that indexes the list. Dict operations performed on a list Tcl_Obj will use the Tcl_HashTable, creating it if it doesn't already exist. Read-only list operations leave the Tcl_HashTable untouched. Destructive list operations set the Tcl_HashTable pointer to NULL. (Or maybe they only do this when changing an even-numbered, i.e. key, element.) struct List and struct Dict are Tcl internals, so (as far as I know) this change can be made without breaking compatibility.

This would be very useful to me in Wibble for creating dict-like objects with potential (but rare) key duplication. lappend is used to make the data structure. If duplicate elements need to be kept separate, ordinary list operations are used to extract the data. If duplicate elements don't exist or can be ignored (the common case), dict operations are used instead, and the first such operation automatically creates the hash table. Actually this mode of operation is currently available, but the hash table would be regenerated every time a dict operation is performed.

Hmm, would epoch and chain also need to be imported into struct List? If so, instead of directly putting a Tcl_HashTable pointer into struct List, I would instead use a struct Dict pointer, to avoid growing struct List more than necessary. struct Dict would have everything removed that's already present in struct List, so it would be reduced to table, epoch, and chain.

Invalid and Noncanonical Returned Values  edit

AMG: When given only one argument, dict merge, dict remove, and dict replace return that argument directly. Therefore, they can return non-dicts or noncanonical dicts, which is contrary to the documentation. See [1] for the bug writeup. A fix to this bug would introduce a potential incompatibility, in case any existing programs depend on this direct pass-through behavior even in the case of bad dicts.

AMG: This has now been fixed [2]. [dict merge] still doesn't force canonicalization, but "fixing" that would cost more than it's worth.

Anyone considered dict equal?  edit

LV: Has anyone considered either submitting a TIP for a dict equal command or at least writing up a first draft of the script for tcllib? It would have to have a 'callback-ish type feature, ala lsort, because you couldn't know, in general, whether two things are "equal" or not...

NEM: Such a command is not too hard to write, see dictutils for one implementation. Note that a general scheme for equality of arbitrary data structures is quite tricky to write. See unification for one approach.

Care needed when extracting a dict from a list  edit

LV 2007-10-17: RS wrote on comp.lang.tcl the following helpful advice:

Be careful with the argument "args" - that is a list. If you pass one dict in args, retrieve it with:
set dict [lindex $args 0]

Because dicts always need an even number of key value key value..

dict vs TclX's key list?  edit

LV: Has anyone compared TclX's key list commands to dict to see how much of the functionality of a key list is missing if one were to try to use a dict in place of a TclX key list?

Lars H: This might be a subject for the Complex data structures page.

dict for Tcl 8.4  edit

If you want dict support in Tcl 8.4, download and compile http://pascal.scheffers.net/software/tclDict-8.5.2.tar.gz (Windows binary [3]).

Version 8.5.3 of this extension is available from the Tcl Extension Archive (teapot) [4].

AMG: Does anyone have a pure-Tcl implementation of dict for Tcl 8.4.7?

RLE: What about forward-compatible dict?

AMG: That works, thanks!

Stubs version of dict for Tcl 8.4  edit

PS 2004-04-14: (updated 2004-05-12): After a bit of chatting on the chat between dgp, dkf and myself, I have created a stubs package version of dict for tcl-8.4. You can download it from

http://pascal.scheffers.net/software/tclDict-8.5.2.tar.gz also see [5]

Status:

  • Builds, installs, passes all tests on SuSE/Linux 9.0 and Windows (MingW)
  • Has an extension stubs table (untested), public C API exported.
  • Needs more testing

The package will only load in tcl-8.4.x, it uses features first introduced in Tcl-8.4. I have no idea what it would take to make it work in 8.3. It will gracefully not load in tcl-8.5+, and not raise an error.

Update 2005-11-18:

I have updated the tclDict code, by syncing it with Tcl8.5 CVS. The 8.5.2 Url above is the new version. This version behaves just like the real thing, except for bignum support by dict incr, which I regressed to wide int support from the previous version of tclDict.

A Microsoft Windows binary version can be downloaded from http://pascal.scheffers.net/stan/dict/dict-8.5.2-win32.zip.

The dict extension is being maintained in my subversion archive at http://svn.scheffers.net/misc

- Pascal.

I tried installing this ... but get the following error:
./configure --with-tcl=/usr/local/lib/tcl8.4 --with-tclinclude=/usr/local/include/tcl8.4
.................. skip some stuff ....................
checking for Tcl public headers... /usr/local/include/tcl8.4
checking for building with threads... no (default)
checking how to build libraries... shared
checking if 64bit support is enabled... no
checking if 64bit Sparc VIS support is requested... no
checking system version (for dynamic loading)... ./configure: line 9892: syntax error near unexpected token `('
./configure: line 9892: `    case `(ac_space=' '; set | grep ac_space) 2>&1` in'

(/tmp/tclDict-8.5.2)-> uname -sr
FreeBSD 5.4-RELEASE-p16

I'll keep checking here for any help. this is using tclDict-8.5.2.tar.gz (it says use that for tcl 8.4...)

NEM: Is this comment still in need of answering? See also comp.lang.tcl for general questions.

MJ: It seems it is. This is caused by tclDict using an outdated tcl.m4 which has a quoting issue with bash. The tcl.m4 (and generated configure) in the download should be fixed.

Original dict implementation  edit

 What: dict
 Where: http://home.earthlink.net/~m-patton/dict-0.01.tar.gz
        http://purl.org/tcl/tip/111.html
 Description: Tcl implementation of TIP 111 - a new Tcl data type called
        dictionary, which consists of an array of values and manipulators
        of those values.
        Currently at version 0.1 .
 Updated: 12/2002
 Contact: See web site

Archived discussion  edit

NEM 2007-02-12: Moved lots of discussion on the design of dict to dict discussion in an attempt to focus this page more on the actual uses and techniques for working with dicts. Apologies if I moved too much by mistake.