Implements |
DFA |
Class Specifications |
| name |
DFA_map |
| template parameters |
class _Sigma = Type_alphabet<char>,
class _Tag = empty_tag,
ifndef WIN32: class Allocator = default_allocator |
| constructor |
WIN32:
DFA_map(unsigned long n = 0)
else:
DFA_map(unsigned long n = 0, Allocator a = Allocator())
|
|
File |
dfa_map.h |
Structure |
Each state is a pair of tag and STL map storing couples in  *Q (key type is ). A map is implemented with a red-black tree. F is a bit vector.
 |
time |
Add/Remove state: O(1)
Add/Remove/Access transition: O(log2(c))
Iteration on edges:O(c) |
Space |
 |
Use Cases |
DFA_map constitutes a good tradeoff between speed and memory usage: transition accesses are relatively fast when state context is small and space complexity depends mainly on |Delta| and not on |Sigma|. Use it when the matrice is sparse and edge iteration frequent |
