maps.h File Reference

Implementation of map containers. 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.

Detailed Description

Implementation of map containers.

Provides three map implementations with different underlying data structures:

1. hashMap - Hash table based implementation
2. treeMap - Red-Black Tree based implementation
3. JMap - Skip List based implementation

Common Features:

• Key-value pair storage with unique keys
• Full iterator support
• Customizable comparison/hash functions
• Customizable allocators
• Exception safety guarantees
• Polymorphic usage through map interface
• Both const and non-const element access

Performance Characteristics:

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

Usage Guidelines:

• Use hashMap for maximum performance when order doesn't matter
• Use treeMap for ordered traversal and consistent performance
• Use JMap for concurrent scenarios or when probabilistic balance is preferred

Additional Features:

• Operator[] for convenient element access
• Key existence checking
• Value updating

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