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:
- hashMap - Hash table based implementation
- treeMap - Red-Black Tree based implementation
- 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
