Associative Containers
From CS315
Contents |
Associative Containers
Associative Containers are used to store data based on a set of keys. They are variable-sized containers that efficiently retrieve data, but unlike Sequences they do not have a mechanism for inserting an element in a specific position.
There are different types of Associative Containers: Simple Associative Containers, Pair Associative Containers, Unique Associative Containers, and Multiple Associative Containers. The types are determined by the value type and the key type. Since the elements are sorted based on there keys, the keys associated with each elements must be immutable. The value type is not assignable causing Associative Containers to not have mutable iterators.
Types
Simple Associative Containers
Simple Associative Containers have the key type and the value type the same, meaning elements are used as their own keys. This causes the elements to also be immutable. Also, the nested types iterator and const_iterator are equivalent. The additional types of Associative Containers have mutable elements, providing iterators, which elements can be modified through.
Pair Associative Containers
In Pair Associative Containers, the elements are mutable, but the key part of the element is still immutable.
Unique Associative Containers
Unique Associative Containers demands that no elements share the same key.
Multiple Associative Containers
Multiple Associative Containers, inversely, allows elements to share keys.
Java Associated Containers
The library provides different kinds of Associative Containers: Set, MultiSet, HashSet, HashMultiSet, TreeSet, TreeMultiSet, Map, MultiMap, HashMap, HashMultiMap, TreeMap, and TreeMultiMap. Sets and Maps support unique keys, making them Unique Associative Containers; however, MultiSets and MultiMaps can share keys, making them Multiple Associative Containers.
Hashes
Hashes are based on Hash Tables which perform at constant time for their basic operations. (add, remove, contains, and size) operations for HashSet. (get and put) operations for HashMap. This only occurs if the hash function disperses the elements properly.
Trees
Trees are based on Red-black trees. Red-black trees guarantee the structure will be in ascending key order, sorted according to the natural order for the key’s class. The comparator can be provided at creation time, depending on which constructor is used. This provides guaranteed log(n) time cost for the basic operations. (add, remove and contains) operations for TreeSet. (containsKey, get, put and remove) operations for TreeMap.
Maps
Maps are instances of Sorted Associative Containers which associate objects of type Key with objects of type Data. Also Maps are Pair Associate Containers also, causing its value type to be pair <const Key, Data>.
Sets
Sets are also Sorted Containers, but they differ from Maps because they are Simple Associative Containers, meaning their key type and value type are type_Key.
Written by Michael Pecora
