pblMap - Map Implementation

Documentation

The Map module provides two implementations of maps, an open source C hash map implementation equivalent to the Java HashMap class and a sorted open source C avl-tree-based balanced tree map implementation equivalent to the Java TreeMap class.

Hash maps make no guarantees as to the iteration order of the map; in particular, they do not guarantee that the order will remain constant over time. Hash maps offer constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over hash maps requires time proportional to the sum of the hash map instance's size (the number of elements) plus the "capacity" of the map (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Tree maps being sorted guarantee that the map can be iterated in ascending element order, according to the compare function specified for the map. The implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). Iterating over tree maps requires time proportional to the tree map instance's size.

The Map module provides an iterator, called a pblIterator, that allows bidirectional access in addition to the normal operations iterators provide.

All map functions described below work on hash maps as well as on tree maps, they of course will show different runtime and memory complexities depending on the type of map used.

Constructors and Destructors