Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site













SourceForge.net Logo

AMap

 

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.

 

 

Constructor Detail

 

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.

s

Source AMap.


 

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.

ndx

Keys.

val

Values.

 

 

Public Method List

 

T& Add(const K& k, const T& x)

Adds a key and value pair to the AMap. Returns a reference to the element.

Invalidates iterators to AIndex.

T must have deep copy constructor.

Invalidates iterators to AMap.

Invalidates references to keys.

Invalidates references to VectorMap values.

k

Key.

x

Value.

 


 

T& AddPick(const K& k, 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. Returns a reference to the element.

 


 

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.

k

Key.

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.

x

Key to find.

h

Precomputed hash value.

Return value

Position of element or a negative value if element is not in AMap.

 


 

int Find(const K& kconst

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.

x

Key to find.

Return value

Position of element or a negative value if element is not in AMap.

 


 

int FindNext(int iconst

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 hconst

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.

i

Position of element.

Return value

Position of next element with same value.

 


 

int FindLast(const K& k, unsigned hconst

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.

x

Key to find.

h

Precomputed hash value.

Return value

Position of element or a negative value if element is not in AMap.

 


 

int FindLast(const K& kconst

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.

x

Element to find.

Return value

Position of element or a negative value if element is not in AMap.

 


 

int FindPrev(int iconst

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.

i

Position of element.

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.

k

Key to find.

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.

k

Key to find.

init

Value to add if key is not in AMap yet.

Return value

Position of element (either found or added).

 


 

int FindAddPick(const 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, 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.

 


 

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 no 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.

k

Key.

x

Value.

 


 

int PutDefault(const K& k)

Similar to Put, but value is default constructed.

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, 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 at the end of AIndex using Add. Value is transfered using pick constructor.

 


 

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.

k

Key.

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.

k

Key to find.

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.

k

Key to find.

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, 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& 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).

k

Key to find.

Return value

Reference to corresponding value.

 


 

const T& Get(const K& kconst

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).

k

Key to find.

Return value

Reference to corresponding value.

 


 

const T& Get(const K& k, const T& dconst

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.

k

Key to find.

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.

k

Key to find.

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.

k

Key to find.

x

Value to add if key is not in AMap.

Return value

Reference to corresponding value.

 


 

T& GetAddPick(const 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, pick constructed from x, at the end of AMap and returns a reference to it.

 


 

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.

k

Key to find.

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.

k

Key to find.

x

Value to add if key is not in AMap.

Return value

Reference to corresponding value.

 


 

T& GetPutPick(const 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, pick constructed from x, into the AMap using Put and returns a reference to it.

 


 

void SetKey(int i, const K& k)

Replaces key of element at the specified position.

i

Position of element.

k

New key value.

 


 

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.

k

Key to find.

Return value

Pointer to value or NULL pointer if element is not in AMap.

 


 

const T *FindPtr(const K& kconst

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.

k

Key to find.

Return value

Pointer to value or NULL pointer if element is not in AMap.

 


 

T *FindLastPtr(const K& k)

const T *FindLastPtr(const K& kconst

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.

k

Key to unlink.

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.

k

Key to unlink.

Return value

Number of elements unlinked.

 


 

bool IsUnlinked(int iconst

Tests whether element at the specified position is unlinked.

i

Position.

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)

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. Returns a reference to the element.

Requires T to have default constructor.

Invalidates iterators to AMap.

Invalidates references to keys.

Invalidates references to VectorMap values.

i

Insert position.

k

Key to insert.

 


 

T& 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. Returns a reference to the element.

Requires T to have deep copy constructor.

Invalidates iterators to AMap.

Invalidates references to keys.

Invalidates references to VectorMap values.

i

Insert position.

k

Key to insert.

x

Value to insert.

 


 

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.

 


 

int RemoveKey(const K& k)

Removes all elements with the specified value. This is a slow operation, especially when combined with any search operations.

k

Key to remove.

 


 

const T& operator[](int iconst

Returns a constant reference to the element at the specified position.

i

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.

i

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.

n

Required capacity.

 


 

int GetAlloc() const

Returns the current capacity of Array.

Return value

Capacity of Array.

 


 

unsigned GetHash(int iconst

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.

n

Number of elements.

 


 

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 iconst

Returns a constant reference to the key of element at the specified position.

i

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.

s

Target/source stream.

 


 

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, HashFnPickIndex()

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<KPickKeys()

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, Toperator~()

MapKVRange<AMap<const K, T, V>, K, const Toperator~() 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 posconst

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.

i

Required position.

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.

i

Required position.

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 posconst

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.

i

Required position.

Return value

Constant value iterator.

 

 

Do you want to contribute?