freepascal.compiler/packages/fcl-stl/doc/map.tex

\chapter{TMap}

Implements container for ordered associative array with unique keys.
Takes 3 arguments for specialization, first one is type of keys, second one is type of values, third
one is comparator class for keys.
Usage example:

\lstinputlisting[language=Pascal]{mapexample.pp}

Memory complexity:
Size of stored base + constant overhead for each stored element (3 pointers + one boolean).

Members list:

\begin{longtable}{|m{10cm}|m{5cm}|}
\hline
Method & Complexity guarantees \\ \hline
\multicolumn{2}{|m{15cm}|}{Description} \\ \hline\hline

\verb!Create! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Constructor. Creates empty map.} \\ \hline\hline

\verb!function Size(): SizeUInt! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Returns number of elements in map.} \\\hline\hline

\verb!procedure Insert(key: TKey; value: TValue)! &
O(lg N), N is number of elements in map \\ \hline
\multicolumn{2}{|m{15cm}|}{Inserts key value pair into map. If key was already there, it will have
new value assigned.} \\\hline\hline

\verb!function InsertAndGetIterator! & $O(\lg N)$\\
\verb!(key:TKey; value: TValue):TIterator! & \\ \hline
\multicolumn{2}{|m{15cm}|}{Same as Insert but also returns iterator poiting to inserted element.} \\\hline\hline

\verb!procedure Delete(key: TKey)! &
O(lg N) \\ \hline
\multicolumn{2}{|m{15cm}|}{Deletes key (and associated value) from map. If element is not in map, nothing happens.} \\\hline\hline

\verb!function Find(key: T):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for key in map. If value is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from map.} \\\hline\hline

\verb!function FindLess(key: T):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for greatest element less than key in map. If such element is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from map.} \\\hline\hline

\verb!function FindLessEqual(key: T):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for greatest element less or equal than key in map. If such element is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from map.} \\\hline\hline

\verb!function FindGreater(key: T):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater than key in map. If such element is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from map.} \\\hline\hline

\verb!function FindGreaterEqual(key: T):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater or equal than key in map. If such element is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from map.} \\\hline\hline

\verb!function Min:TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns iterator pointing to smallest key of map. If map is empty returns
nil.} \\\hline\hline

\verb!function Max:TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns iterator pointing to largest key of map. If map is empty returns
nil.} \\\hline\hline

\verb!function IsEmpty(): boolean! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Returns true when map is empty.} \\\hline

\verb!property item[i: Key]: TValue; default;! & O(ln N) \\\hline
\multicolumn{2}{|m{15cm}|}{Property for accessing key i in map. Can be used just by square
brackets (its default property).} \\\hline\hline


\end{longtable}

Some methods return type TIterator, which has following methods:
\begin{longtable}{|m{10cm}|m{5cm}|}                                                             
\hline
Method & Complexity guarantees \\ \hline                                                  
\multicolumn{2}{|m{15cm}|}{Description} \\ \hline\hline                                               
\verb!function Next:boolean! & O(lg N) worst case, but traversal from smallest element to
largest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Moves iterator to element with smallest larger key. Returns true on
success. If the iterator is already pointing on element with largest key returns false.} \\\hline\hline

\verb!function Prev:boolean! & O(lg N) worst case, but traversal from largest element to
smallest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Moves iterator to element with largest smaller key. Returns true on
success. If the iterator is already pointing on element with smallest key returns false.} \\\hline\hline

\verb!property Key:TKey! & $O(1)$ \\\hline
\multicolumn{2}{|m{15cm}|}{Property, which allows reading the key.} \\\hline

\verb!property Value:TValue! & $O(1)$ \\\hline
\multicolumn{2}{|m{15cm}|}{Property, which allows reading and writing of the value.} \\\hline
\verb!property MutableValue:PValue! & $O(1)$ \\\hline
\multicolumn{2}{|m{15cm}|}{Returns pointer on stored value. Usefull for accessing records and
objects.} \\\hline


\end{longtable}