Relation: none

Note: most abstract data types do not have explicit different names for the object and associative containers; however, in this case, the object container is described by the Abstract Set and the associative container is described by the Abstract Map.

Note: most abstract data types do not differentiate between that container which can only store one of an object or key and that which can store multiple copies of one object or key; however, in this case, the corresponding containers are described by the Abstract Mulitset and the Abstract Multimap.

Critical Operations for Abstract Sets

• Accessing the number of objects in the container
  int size() const
• Determining if the container is empty
  bool empty() const
• Inserting a new object into the container
  void insert( Type )
• Determining if an object is in the container (membership)
  bool member( Type ) const
• Removing an object from the container
  void remove( Type )
• Removing all objects from (clearing) the container
  void clear()

Critical Operations for Abstract Maps (Abstract Associative Set)

• Accessing the number of objects in the container
  int size() const
• Determining if the container is empty
  bool empty() const
• Inserting a new key-object pair into the container
  void insert( key, Type )
• Determining if a key is in the container (membership)
  bool member( key ) const
• Access and/or modify the object associated with a key
  Type &access( key ) const
• Removing an object from the container
  void remove( key )
• Removing all objects from (clearing) the container
  void clear()

Example Data Structures

Under the correct conditions, the following hash-table-based data structures will execute all the above operations in O(1) time:

• Chained Hash Table with:
• Linked Lists
• Dynamic Arrays
• Chained Hash Table with Self-balancing Search Trees
• Scatter Table
• Open-addressed Hash Table with:
• Linear Probing
• Quadratic Probing
• Double Hashing
• Cuckoo Hashing
• Coalesced Hash Table

Implementations in the Standard Template Library (STL)

While the STL has the set, map, multiset, and multimap containers, these still require a strict weak ordering. The SGI STL implements the four containers hash_set, hash_map, hash_multiset, and hash_multimap which use hash values rather than a strict weak ordering.