maps.h File Reference

Implementation of map containers with different underlying data structures. More...

#include "allocator.h"
#include "couple.h"
#include "hash.h"
#include "hashTable.h"
#include "map.h"
#include "ownerPtr.h"
#include "comparator.h"
#include "RBTree.h"
#include "skipList.h"

Include dependency graph for maps.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	original::hashMap< K_TYPE, V_TYPE, HASH, ALLOC >
	Hash table based implementation of the map interface. More...
class	original::hashMap< K_TYPE, V_TYPE, HASH, ALLOC >::Iterator
	Bidirectional iterator for hashMap. More...
class	original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >
	Red-Black Tree based implementation of the map interface. More...
class	original::treeMap< K_TYPE, V_TYPE, Compare, ALLOC >::Iterator
	Bidirectional iterator for treeMap. More...
class	original::JMap< K_TYPE, V_TYPE, Compare, ALLOC >
	Skip List based implementation of the map interface. More...
class	original::JMap< K_TYPE, V_TYPE, Compare, ALLOC >::Iterator
	Forward iterator for JMap. More...

Namespaces
namespace	original
	Main namespace for the project Original.
namespace	std
	Standard namespace extensions for original::alternative.

Functions
template<typename K_TYPE , typename V_TYPE , typename HASH , typename ALLOC >
void	std::swap (original::hashMap< K_TYPE, V_TYPE, HASH, ALLOC > &lhs, original::hashMap< K_TYPE, V_TYPE, HASH, ALLOC > &rhs) noexcept
	std::swap specialization for hashMap
template<typename K_TYPE , typename V_TYPE , typename COMPARE , typename ALLOC >
void	std::swap (original::treeMap< K_TYPE, V_TYPE, COMPARE, ALLOC > &lhs, original::treeMap< K_TYPE, V_TYPE, COMPARE, ALLOC > &rhs) noexcept
	std::swap specialization for treeMap
template<typename K_TYPE , typename V_TYPE , typename COMPARE , typename ALLOC >
void	std::swap (original::JMap< K_TYPE, V_TYPE, COMPARE, ALLOC > &lhs, original::JMap< K_TYPE, V_TYPE, COMPARE, ALLOC > &rhs) noexcept
	std::swap specialization for JMap

Detailed Description

Implementation of map containers with different underlying data structures.

Provides three map implementations with different performance characteristics and iteration capabilities:

1. hashMap - Hash table based implementation (unordered, fastest average case)
2. treeMap - Red-Black Tree based implementation (ordered, consistent performance)
3. JMap - Skip List based implementation (ordered, probabilistic balance)

Common Features:

• Key-value pair storage with unique keys
• Full iterator support with different capabilities
• Customizable comparison/hash functions
• Customizable allocators with propagation support
• Exception safety guarantees (basic guarantee for most operations)
• Polymorphic usage through map interface
• Both const and non-const element access
• Operator[] for convenient element access and insertion
• Key existence checking with contains() method
• Value updating with insert() or operator[]
• Integration with printable for string representation

Performance Characteristics:

Container	Insertion	Lookup	Deletion	Ordered	Memory Usage	Iterator Type
hashMap	O(1) avg	O(1)	O(1)	No	Medium-High	Forward-only
treeMap	O(log n)	O(log n)	O(log n)	Yes	Low	Bidirectional
JMap	O(log n) avg	O(log n)	O(log n)	Yes	Medium	Forward-only

Memory Characteristics:

Container	Node Structure	Overhead	Rehashing	Balance Operations
hashMap	Key-Value + Next	1 pointer	Yes	No
treeMap	Key-Value + Parent/Child/Color	3 pointers + color	No	Yes (Red-Black)
JMap	Key-Value + Multi-level links	~2 pointers avg	No	Probabilistic

Usage Guidelines:

• Use hashMap for maximum performance when key order doesn't matter and keys are hashable
• Use treeMap for ordered traversal, range queries, and consistent worst-case performance
• Use JMap for concurrent scenarios (external synchronization) or when probabilistic balance is preferred

Iterator Invalidation:

• hashMap: Iterators invalidate on rehash (insertion that causes capacity change)
• treeMap: Iterators invalidate on element removal that affects the current position
• JMap: Iterators invalidate on any structural modification

Key Requirements:

• hashMap: Keys must be hashable (provide std::hash specialization or custom HASH)
• treeMap/JMap: Keys must be comparable (provide operator< or custom Compare)
• All keys must be copyable and movable
• Values must be default constructible for operator[] usage

Exception Safety:

• Basic guarantee: Container remains valid but unspecified state on exception
• Strong guarantee for some operations (no-throw if element operations are noexcept)
• Allocator-aware exception handling

See also

map.h For the base interface definition

hashTable.h For hashMap implementation details

RBTree.h For treeMap implementation details

skipList.h For JMap implementation details

printable.h For string formatting support

couple.h For key-value pair implementation