|
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.
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, HashFn>& ndx, pick_ V& val)
This form of constructors creates AMap by picking Index of keys ndx and basic random access container of values. Both containers must have same number of elements val.
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.
T& Add(const K& k, const T& x)
T& Add(const K& k, T&& x)
T& Add(const K& k)
T& Add(K&& k, const T& x)
T& Add(K&& k, T&& x)
T& Add(K&& k)
Adds a key and value pair to the AMap. Returns a reference to the element. If value is not specified, it is default constructed.
Invalidates iterators to AIndex.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to AMap values.
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 FindNext(int i) 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, a negative number is returned. Unlinked elements are ignored.
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 FindPrev 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)
int FindAdd(const K& k, const T& init)
int FindAdd(const K& k, T&& x)
int FindAdd(K&& k)
int FindAdd(K&& k, const T& init)
int FindAdd(K&& k, 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, lowest position is retrieved. If the element does not exist in AMap, adds new element (if init is present, constructed form init otherwise default constructed) at the end of AMap and returns its position. Unlinked elements are ignored.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
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)
int Put(const K& k, T&& x)
int Put(K&& k, const T& x)
int Put(K&& k, T&& x)
If there are any unlinked elements in AMap, one of them is replaced by the specified key/value pair. If there is no unlinked element, the key/value pair is added to the end of AIndex using Add. Value is transfered using deep copy constructor. The return values is the index of replaced / added pair.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
T& Put(const K& k)
T& Put(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.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
int PutDefault(const K& k)
int PutDefault(K&& k)
Similar to Put, but value is default constructed.
Invalidates multi-key ordering.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
int FindPut(const K& k)
int FindPut(const K& k, const T& init)
int FindPut(const K& k, T&& init)
int FindPut(K&& k)
int FindPut(K&& k, const T& init)
int FindPut(K&& k, 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.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
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 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. 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)
T& GetAdd(const K& k, const T& x)
T& GetAdd(const K& k, T&& x)
T& GetAdd(K&& k)
T& GetAdd(K&& k, const T& x)
T& GetAdd(K&& k, 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 (x or default constructed) at the end of AMap and returns a reference to it.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
T& GetPut(const K& k)
T& GetPut(const K& k, const T& x)
T& GetPut(const K& k, T&& x)
T& GetPut(K&& k)
T& GetPut(K&& k, const T& x)
T& GetPut(K&& k, 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 (x or default constructed) into the AMap using Put and returns a reference to it.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
void SetKey(int i, const K& k)
void SetKey(int i, 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 the 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. |
T *FindLastPtr(const K& k)
const T *FindLastPtr(const K& k) const
Retrieves a constant pointer to value of the 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 AMap, the greatest position is retrieved. If the element does not exist in AMap, NULL pointer is returned. Unlinked elements are ignored..
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. |
void Sweep()
Removes all unlinked elements from the container.
bool HasUnlinked() const
Returns true if AMap has any unlinked elements.
T& Insert(int i, const K& k)
T& Insert(int i, const K& k, const T& x)
T& Insert(int i, const K& k, T&& x)
T& Insert(int i, K&& k)
T& Insert(int i, K&& k, const T& x)
T& Insert(int i, K&& k, T&& x)
Inserts an element with the specified key at the specified position, with value x or default constructed. Returns a reference to the new element.
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(int i, int count)
Removes count elements at i.
Invalidates iterators to AMap.
Invalidates references to keys.
Invalidates references to VectorMap values.
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. |
template <typename P> void RemoveIf(P p)
Removes all elements whose index satisfies predicate p.
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. |
unsigned GetHash(int i) const
Returns a hash of element i. This is perhaps only useful when making the exact copy of AMap, e.g. in the persistent storage.
void Drop(int n = 1)
Drops the specified number of elements at the end of the AMap.
T& Top()
const T& Top() const
Returns a 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. |
void Trim(int n)
Reduces the number of items in map to n. n must be lover than or equal to GetCount().
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.
void Swap(AMap& x)
Swap AMap content with another AMap (of the same type).
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()
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()
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.
V& GetValues()
Returns a (writable) reference to the basic random access container of values. Destroys AIndex by picking.
V PickValues()
Returns basic random access container of values. Destroys AIndex by picking.
|
Return value |
Basic random access container of values. |
MapKVRange<AMap<K, T, V>, K, T> operator~()
MapKVRange<AMap<const K, T, V>, K, const T> operator~() const
Returns a special range object that can be used in C++11 range for to iterate over key/value pairs. Unlinked objects are automatically skipped.
AMap& operator()(const K& k, const T& v)
Same as Add(k, v), returns *this. Syntax sugar for creating map.
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. |
|
