template <class K, class T, class V, class HashFn>
class AMap
K Type of keys. K must have deep copy constructor, be moveable and must have operator== defined.
T Type of values. T must satisfy requirements for container flavor identified by parameter V.
V Type of basic random access container.
HashFn Hashing class. Must have defined unsigned operator()(const K& x) method returning hash value for elements.
AMap is a class that combines Index of keys with basic random access container of values, forming map flavors. It is used as base class for concrete map flavors, VectorMap, ArrayMap and SegtorMap.
Like any other NTL container, AMap is moveable type with pick and optional deep copy transfer semantics, although these features are more important in derived concrete index flavors.
Members
void Add(const K& k, const T& x)
Adds a key and value pair to the AMap.
Invalidates iterators to AIndex.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
void AddPick(const K& k, pick_ T& x)
Adds a key and value pair to the AMap. Value is transfered by pick constructor in low constant time, but the source value is destroyed.
T must have pick constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
T& Add(const K& k)
Adds a key to the AMap and returns a reference to the corresponding default constructed value.
T must have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Reference to value. |
int FindAdd(const K& k)
Retrieves the position of first element with the specified key in AMap, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. If the element does not exist in AMap, a negative number is returned. Unlinked elements are ignored.
|
h |
Precomputed hash value. |
|
Return value |
Position of element or a negative value if element is not in AMap. |
int Find(const K& k) const
Retrieves the position of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. If the element does not exist in AMap, a negative number is returned. Unlinked elements are ignored.
|
Return value |
Position of element or a negative value if element is not in AMap. |
int Find(const K& k, unsigned h) const
Retrieves the position of next element with the same key as element at the specified position. If multi-key ordering is not broken and more than one element with that value exists in AMap, the lowest position greater than specified one is retrieved (so that positions got by subsequent calls to FindNext are in ascending order). When there are no more elements with required key, negative number is returned. Unlinked elements are ignored.
|
Return value |
Position of next element with same value. |
int FindLast(const K& k, unsigned h) const
Retrieves position of last element with the specified key in AMap, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the greatest position is retrieved. If element does not exist in AMap, a negative number is returned. Unlinked elements are ignored.
|
h |
Precomputed hash value. |
|
Return value |
Position of element or a negative value if element is not in AMap. |
int FindLast(const K& k) const
Retrieves the position of last element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, the greatest position is retrieved. If element does not exist in AMap, a negative number is returned. Unlinked elements are ignored.
|
Return value |
Position of element or a negative value if element is not in AMap. |
int FindPrev(int i) const
Retrieves the position of previous element with the same key as element at the specified position. If multi-key ordering is not broken and more than one element with that value exists in AMap, the greatest position lower than specified one is retrieved (so that positions got by subsequent calls to FindNext are in descending order). When there are no more elements with required key, a negative number is returned. Unlinked elements are ignored.
|
Return value |
Position of previous element with same value. |
int FindAdd(const K& k)
Retrieves the position of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, lowest position is retrieved. If the element does not exist in AMap, adds new default constructed element at the end of AMap and returns its position. Unlinked elements are ignored.
T must have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Position of element (either found or added). |
int FindAdd(const K& k, const T& init)
Retrieves the position of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. Unlinked elements are ignored. If the element does not exist in AMap, adds new element, deep copy constructed from init, at the end of AMap and returns its position.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
init |
Value to add if key is not in AMap yet. |
|
Return value |
Position of element (either found or added). |
int FindPutPick(const K& k, pick_ T& init)
Retrieves the position of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. Unlinked elements are ignored. If the element does not exist in AMap, adds new element, pick constructed from init, at the end of AMap and returns its position.
T must have pick constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
init |
Value to add if key is not in AMap yet. |
|
Return value |
Position of element (either found or added). |
void Unlink(int i)
Unlinks element at the specified position. Unlinked item stays in AMap but is ignored by any Find operation.
|
i |
Position of element to unlink. |
int Put(const K& k, const T& x)
If there are any unlinked elements in AMap, one of them is replaced by the specified key/value pair. If there is are unlinked elements, the key/value pair is added to the end of AIndex using Add. Value is transfered using deep copy constructor.
T must have deep copy constructor.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
int PutPick(const K& k, pick_ T& x)
If there are any unlinked elements in AMap, one of them is replaced by the specified key/value pair. If there is none unlinked element, the key/value pair is added at the end of AIndex using Add. Value is transfered using pick constructor.
T must have pick constructor.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
T& Put(const K& k)
If there is any unlinked element in AMap, it is replaced by the specified key and reference to the value is returned. If there is none unlinked element, key is added at the end of AIndex using Add and a reference to corresponding default constructed Value is returned.
T must have default constructor.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Reference to the corresponding value. |
int FindPut(const K& k)
Retrieves the position of first element with the specified key in AMap. Unlinked elements are ignored. If the element does not exist in AMap, puts new default constructed element into AMap using Put and returns its position.
T must have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Position of element (either found or added). |
int FindPut(const K& k, const T& init)
Retrieves the position of first element with the specified key in AMap. Unlinked elements are ignored. If the element does not exist in AMap, puts new element, deep copy constructed from init, using Put and returns its position.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
init |
Value to add if key is not in AMap yet. |
|
Return value |
Position of element (either found or added). |
int FindPutPick(const K& k, pick_ T& init)
Retrieves the position of first element with the specified key in AMap. Unlinked elements are ignored. If the element does not exist in AMap, puts new element, pick constructed from init, using Put and returns its position.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
init |
Value to add if key is not in AMap yet. |
|
Return value |
Position of element (either found or added). |
T& Get(const K& k)
Retrieves a reference to the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. Required key must be in AMap, otherwise it is logic error (asserted in debug mode).
|
Return value |
Reference to corresponding value. |
const T& Get(const K& k) const
Retrieves a constant reference the the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. Required key must be in AMap, otherwise it is logic error (asserted in debug mode).
|
Return value |
Reference to corresponding value. |
const T& Get(const K& k, const T& d) const
Retrieves a constant reference value of the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. If the required key is not in the AMap, constant reference to the specified value is returned instead.
|
d |
Value to be returned if key is not found. |
|
Return value |
Reference to found element or supplied value. |
T& GetAdd(const K& k)
Retrieves a constant reference value of the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, adds new default constructed element at the end of AMap and returns a reference to it.
T must have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Reference to corresponding value. |
T& GetAdd(const K& k, const T& x)
Retrieves a constant reference to the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, adds new element, deep copy constructed from x, at the end of AMap and returns a reference to it.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
x |
Value to add if key is not in AMap. |
|
Return value |
Reference to corresponding value. |
T& GetAddPick(const K& k, pick_ T& x)
Retrieves a constant reference to the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, adds new element, pick constructed from x, at the end of AMap and returns a reference to it.
T must have pick constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
x |
Value to add if key is not in AMap. |
|
Return value |
Reference to corresponding value. |
T& GetPut(const K& k)
Retrieves a constant reference value of the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, puts new default constructed element into the AMap using Put and returns a reference to it.
T must have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
Return value |
Reference to corresponding value. |
T& GetPut(const K& k, const T& x)
Retrieves a constant reference value of the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, puts new element, deep copy constructed from x, into the AMap using Put and returns a reference to it.
T must have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
x |
Value to add if key is not in AMap. |
|
Return value |
Reference to corresponding value. |
T& GetPutPick(const K& k, pick_ T& x)
Retrieves a constant reference value of the first element with the specified key. If multi-key ordering is not broken and more than one element with the same value exists in AMap, lowest position element is retrieved. Unlinked elements are ignored. If required key is not in the AMap, puts new element, pick constructed from x, into the AMap using Put and returns a reference to it.
T must have pick constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
x |
Value to add if key is not in AMap. |
|
Return value |
Reference to corresponding value. |
void SetKey(int i, const K& k)
Replaces key of element at the specified position.
T *FindPtr(const K& k)
Retrieves a pointer to value of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. If the element does not exist in AMap, NULL pointer is returned. Unlinked elements are ignored.
|
Return value |
Pointer to value or NULL pointer if element is not in AMap. |
const T *FindPtr(const K& k) const
Retrieves a constant pointer to value of first element with the specified key in AMap. If multi-key ordering is not broken and more than one element with the same value exists in AMap, the lowest position is retrieved. If the element does not exist in AMap, NULL pointer is returned. Unlinked elements are ignored.
|
Return value |
Pointer to value or NULL pointer if element is not in AMap. |
int UnlinkKey(const K& k, unsigned h)
Unlinks all elements with the specified key using precomputed hash-value. Unlinked elements stay in AIndex but are ignored by any Find operations. The precomputed hash value must be the same as the hash value that would be the result of HashFn.
|
h |
Precomputed hash value. |
|
Return value |
Number of elements unlinked. |
int UnlinkKey(const K& k)
Unlinks all elements with the specified key. Unlinked elements stay in AIndex but are ignored by any Find operations.
|
Return value |
Number of elements unlinked. |
bool IsUnlinked(int i) const
Tests whether element at the specified position is unlinked.
|
Return value |
true if element is unlinked. |
T& Insert(int i, const K& k)
Inserts an element with the specified key and default constructed value at the specified position. This is a slow operation, especially when combined with any search operations.
Requires T to have default constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
void Insert(int i, const K& k, const T& x)
Inserts an element with the specified key and value copy constructed from x at the specified position. This is a slow operation, especially when combined with any search operations.
Requires T to have deep copy constructor.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
void Remove(int i)
Removes the element at the specified position. This is a slow operation, especially when combined with any search operations.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
i |
Position of element to remove. |
void Remove(const int *sl, int n)
Removes number of elements from AMap. Time of operation only slightly depends on the number of removed elements. This is a slow operation, especially when combined with any search operations.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
i |
Position of element to remove. |
|
sl |
Pointer to array of the positions to remove, in ascending order. |
|
n |
Number of elements to remove. |
void Remove(const Vector<int>& sl)
Removes number of elements from AMap. Same as Remove(sorted_list, sorted_list.GetCount()).
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
|
sl |
Sorted Vector of positions to remove. |
int RemoveKey(const K& k)
Removes all elements with the specified value. This is a slow operation, especially when combined with any search operations.
const T& operator[](int i) const
Returns a constant reference to the element at the specified position.
|
Return value |
Constant reference to the element at the specified position. |
T& operator[](int i)
Returns a reference to the element at the specified position.
|
Return value |
Constant reference to the element at the specified position. |
int GetCount() const
Returns the number of elements in AMap.
|
Return value |
Actual number of elements. |
bool IsEmpty() const
Tests whether AMap is empty. Same as GetCount() == 0.
|
Return value |
true if AMap is empty, false otherwise. |
void Clear()
Removes all elements from AMap.
void Shrink()
Minimizes memory consumption of AMap by decreasing the capacity to the number of elements.
void Reserve(int xtra)
Reserves capacity. If the required capacity is greater than current capacity, capacity is increased to the required value.
int GetAlloc() const
Returns the current capacity of Array.
|
Return value |
Capacity of Array. |
void Drop(int n = 1)
Drops the specified number of elements at the end of the AMap.
T& Top()
Returns a reference to the value of the last element of AMap.
|
Return value |
Reference to the value of the last element. |
T& Top()
Returns a constant reference to the value of the last element of AMap.
|
Return value |
Reference to the value of the last element. |
const K& TopKey() const
Returns a constant reference to the key of the last element of AMap.
|
Return value |
Reference to the key of the last element. |
K PopKey()
Drops the last element of AMap and returns the key of the dropped element.
|
Return value |
Key of the element dropped at the end of AMap. |
const K& GetKey(int i) const
Returns a constant reference to the key of element at the specified position.
|
Return value |
Constant reference to the key. |
void Serialize(Stream& s)
Serializes the content of AMap to/from Stream. Works only if NTL is used as part of UPP.
Requires T to have serialization operator defined.
const Index<K, HashFn>& GetIndex() const
Returns a constant reference to the internal Index of keys.
|
Return value |
Constant reference to the Index of keys. |
Index<K, HashFn> PickIndex() pick_
Returns Index of keys. Destroys AMap by picking.
|
Return value |
Index of keys. |
const Vector<K>& GetKeys() const
Returns a constant reference to the Vector of keys.
|
Return value |
Constant reference to the Vector of keys. |
Vector<K> PickKeys() pick_
Returns Vector of keys. Destroys AMap by picking.
|
Return value |
Vector of keys. |
const V& GetValues() const
Returns a constant reference to the basic random access container of values. Destroys AIndex by picking.
|
Return value |
Constant reference to the basic random access container of values. |
V PickValues() pick_
Returns basic random access container of values. Destroys AIndex by picking.
|
Return value |
Basic random access container of values. |
AMap()
Constructor. Constructs an empty AMap.
AMap(const AMap& s, int)
Optional deep copy constructor.
Requires T to have deep copy constructor or optional deep copy constructor.
AMap(pick_ Index<K>& ndx, pick_ V& val)
This form of constructors creates AMap by picking Index of keys and basic random access container of values. Both containers must have same number of elements.
AMap(pick_ Vector<K>& ndx, pick_ V& val)
This form of constructors creates AMap by picking Vector of keys and basic random access container of values. Both containers must have same number of elements.
typedef K KeyType
Typedef of K for use in templated algorithms.
typedef typename Index<K, HashFn>::ConstIterator KeyConstIterator
Key iterator type.
KeyConstIterator KeyBegin() const
Returns a constant iterator to the first key in AMap.
|
Return value |
Constant key iterator. |
KeyConstIterator KeyEnd() const
Returns a constant iterator to the key just beyond the last key in AMap.
|
Return value |
Constant key iterator. |
KeyConstIterator KeyGetIter(int pos) const
Returns a constant iterator to the key at the specified position. Same as KeyBegin() + i. The benefit of this method is that pos is range checked in debug mode.
|
Return value |
Constant key iterator. |
Iterator Begin()
Returns an iterator to the first value in AMap.
|
Return value |
Value iterator. |
Iterator End()
Returns a constant iterator to the value just beyond the last key in AMap.
|
Return value |
Value iterator. |
Iterator GetIter(int pos)
Returns an iterator to the value at the specified position. Same as Begin() + i. The benefit of this method is that pos is range checked in debug mode.
|
Return value |
Value iterator. |
ConstIterator Begin() const
Returns a constant iterator to the first value in AMap.
|
Return value |
Constant value iterator. |
ConstIterator End() const
Returns a constant iterator to the value just beyond the last value in AMap.
|
Return value |
Constant value iterator. |
ConstIterator GetIter(int pos) const
Returns a constant iterator to the value at the specified position. Same as Begin() + i. Benefit of this methods is that in debug mode pos is range checked.
|
Return value |
Constant value iterator. |
|
