CAtlMap Class

 

The new home for Visual Studio documentation is Visual Studio 2017 Documentation on docs.microsoft.com.

The latest version of this topic can be found at CAtlMap Class.

This class provides methods for creating and managing a map object.

template <typename K,
          typename V, 
          class KTraits = CElementTraits<K>, 
          class VTraits = CElementTraits<V>>
class CAtlMap

Parameters

K
The key element type.

V
The value element type.

KTraits
The code used to copy or move key elements. See CElementTraits Class for more details.

VTraits
The code used to copy or move value elements.

Public Typedefs

NameDescription
CAtlMap::KINARGTYPEType used when a key is passed as an input argument
CAtlMap::KOUTARGTYPEType used when a key is returned as an output argument.
CAtlMap::VINARGTYPEType used when a value is passed as an input argument.
CAtlMap::VOUTARGTYPEType used when a value is passed as an output argument.

Public Classes

NameDescription
CAtlMap::CPair ClassA class containing the key and value elements.

CPair Data Members

NameDescription
CPair::m_keyThe data member storing the key element.
CPair::m_valueThe data member storing the value element.

Public Constructors

NameDescription
CAtlMap::CAtlMapThe constructor.
CAtlMap::~CAtlMapThe destructor.

Public Methods

NameDescription
CAtlMap::AssertValidCall this method to cause an ASSERT if the CAtlMap is not valid.
CAtlMap::DisableAutoRehashCall this method to disable automatic rehashing of the CAtlMap object.
CAtlMap::EnableAutoRehashCall this method to enable automatic rehashing of the CAtlMap object.
CAtlMap::GetAtCall this method to return the element at a specified position in the map.
CAtlMap::GetCountCall this method to retrieve the number of elements in the map.
CAtlMap::GetHashTableSizeCall this method to determine the number of bins in the map's hash table.
CAtlMap::GetKeyAtCall this method to retrieve the key stored at the given position in the CAtlMap object.
CAtlMap::GetNextCall this method to obtain a pointer to the next element pair stored in the CAtlMap object.
CAtlMap::GetNextAssocGets the next element for iterating.
CAtlMap::GetNextKeyCall this method to retrieve the next key from the CAtlMap object.
CAtlMap::GetNextValueCall this method to get the next value from the CAtlMap object.
CAtlMap::GetStartPositionCall this method to start a map iteration.
CAtlMap::GetValueAtCall this method to retrieve the value stored at a given position in the CAtlMap object.
CAtlMap::InitHashTableCall this method to initialize the hash table.
CAtlMap::IsEmptyCall this method to test for an empty map object.
CAtlMap::LookupCall this method to look up keys or values in the CAtlMap object.
CAtlMap::RehashCall this method to rehash the CAtlMap object.
CAtlMap::RemoveAllCall this method to remove all elements from the CAtlMap object.
CAtlMap::RemoveAtPosCall this method to remove the element at the given position in the CAtlMap object.
CAtlMap::RemoveKeyCall this method to remove an element from the CAtlMap object, given the key.
CAtlMap::SetAtCall this method to insert an element pair into the map.
CAtlMap::SetOptimalLoadCall this method to set the optimal load of the CAtlMap object.
CAtlMap::SetValueAtCall this method to change the value stored at a given position in the CAtlMap object.

Public Operators

NameDescription
CAtlMap::operatorReplaces or adds a new element to the CAtlMap.

CAtlMap provides support for a mapping array of any given type, managing an unordered array of key elements and their associated values. Elements (consisting of a key and a value) are stored using a hashing algorithm, allowing a large amount of data to be efficiently stored and retrieved.

The KTraits and VTraits parameters are traits classes that contain any supplemental code needed to copy or move elements.

An alternative to CAtlMap is offered by the CRBMap class. CRBMap also stores key/value pairs, but exhibits different performance characteristics. The time taken to insert an item, look up a key, or delete a key from a CRBMap object is of order log(n), where n is the number of elements. For CAtlMap, all of these operations typically take a constant time, although worst-case scenarios might be of order n. Therefore, in a typical case, CAtlMap is faster.

The other difference between CRBMap and CAtlMap becomes apparent when iterating through the stored elements. In a CRBMap, the elements are visited in a sorted order. In a CAtlMap, the elements are not ordered, and no order can be inferred.

When a small number of elements need to be stored, consider using the CSimpleMap class instead.

For more information, see ATL Collection Classes.

Header: atlcoll.h

Call this method to cause an ASSERT if the CAtlMap object is not valid.

void AssertValid() const;

Remarks

In debug builds, this method will cause an ASSERT if the CAtlMap object is not valid.

Example

See the example for CAtlMap::CAtlMap.

The constructor.

CAtlMap(
    UINT nBins = 17,
    float fOptimalLoad = 0.75f,
    float fLoThreshold = 0.25f,
    float fHiThreshold = 2.25f,
    UINT nBlockSize = 10) throw ();

Parameters

nBins
The number of bins providing pointers to the stored elements. See Remarks later in this topic for an explanation of bins.

fOptimalLoad
The optimal load ratio.

fLoThreshold
The lower threshold for the load ratio.

fHiThreshold
The upper threshold for the load ratio.

nBlockSize
The block size.

Remarks

CAtlMap references all of its stored elements by first creating an index using a hashing algorithm on the key. This index references a "bin" which contains a pointer to the stored elements. If the bin is already in use, a linked-list is created to access the subsequent elements. Traversing a list is slower than directly accessing the correct element, and so the map structure needs to balance storage requirements against performance. The default parameters have been chosen to give good results in most cases.

The load ratio is the ratio of the number of bins to the number of elements stored in the map object. When the map structure is recalculated, the fOptimalLoad parameter value will be used to calculate the number of bins required. This value can be changed using the CAtlMap::SetOptimalLoad method.

The fLoThreshold parameter is the lower value that the load ratio can reach before CAtlMap will recalculate the optimal size of the map.

The fHiThreshold parameter is the upper value that the load ratio can reach before the CAtlMap object will recalculate the optimal size of the map.

This recalculation process (known as rehashing) is enabled by default. If you want to disable this process, perhaps when entering a lot of data at one time, call the CAtlMap::DisableAutoRehash method. Reactivate it with the CAtlMap::EnableAutoRehash method.

The nBlockSize parameter is a measure of the amount of memory allocated when a new element is required. Larger block sizes reduce calls to memory allocation routines, but use more resources.

Before any data can be stored, it is necessary to initialize the hash table with a call to CAtlMap::InitHashTable.

Example

   // Create a map which stores a double
   // value using an integer key

   CAtlMap<int, double> mySinTable;
   int i;

   // Initialize the Hash Table
   mySinTable.InitHashTable(257);

   // Add items to the map
   for (i = 0; i < 90; i++)
      mySinTable[i] = sin((double)i);

   // Confirm the map is valid
   mySinTable.AssertValid();

   // Confirm the number of elements in the map
   ATLASSERT(mySinTable.GetCount() == 90);

   // Remove elements with even key values
   for (i = 0; i < 90; i += 2)
      mySinTable.RemoveKey(i);

   // Confirm the number of elements in the map
   ATLASSERT(mySinTable.GetCount() == 45);

   // Walk through all the elements in the map.
   // First, get start position.
   POSITION pos;
   int key;
   double value;
   pos = mySinTable.GetStartPosition();

   // Now iterate the map, element by element
   while (pos != NULL) 
   {
      key = mySinTable.GetKeyAt(pos);
      value = mySinTable.GetNextValue(pos);
   }

The destructor.

~CAtlMap() throw();

Remarks

Frees any allocated resources.

A class containing the key and value elements.

class CPair : public __POSITION

Remarks

This class is used by the methods CAtlMap::GetNext and CAtlMap::Lookup to access the key and value elements stored in the mapping structure.

Call this method to disable automatic rehashing of the CAtlMap object.

void DisableAutoRehash() throw();

Remarks

When automatic rehashing is enabled (which it is by default), the number of bins in the hash table will automatically be recalculated if the load value (the ratio of the number of bins to the number of elements stored in the array) exceeds the maximum or minimum values specified at the time the map was created.

DisableAutoRehash is most useful when a large number of elements will be added to the map at once. Instead of triggering the rehashing process every time the limits are exceeded, it is more efficient to call DisableAutoRehash, add the elements, and finally call CAtlMap::EnableAutoRehash.

Call this method to enable automatic rehashing of the CAtlMap object.

void EnableAutoRehash() throw();

Remarks

When automatic rehashing is enabled (which it is by default), the number of bins in the hash table will automatically be recalculated if the load value (the ratio of the number of bins to the number of elements stored in the array) exceeds the maximum or minimum values specified at the time the map is created.

EnableAutoRefresh is most often used after a call to CAtlMap::DisableAutoRehash.

Call this method to return the element at a specified position in the map.

void GetAt(
    POSITION pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

CPair* GetAt(POSITION& pos) throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

key
Template parameter specifying the type of the map's key.

value
Template parameter specifying the type of the map's value.

Return Value

Returns a pointer to the current pair of key/value elements stored in the map.

Remarks

In debug builds, an assertion error will occur if pos is equal to NULL.

Call this method to retrieve the number of elements in the map.

size_t GetCount() const throw();

Return Value

Returns the number of elements in the map object. A single element is a key/value pair.

Example

See the example for CAtlMap::CAtlMap.

Call this method to determine the number of bins in the map's hash table.

UINT GetHashTableSize() const throw();

Return Value

Returns the number of bins in the hash table. See CAtlMap::CAtlMap for an explanation.

Call this method to retrieve the key stored at the given position in the CAtlMap object.

const K& GetKeyAt(POSITION pos) const throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Return Value

Returns a reference to the key stored at the given position in the CAtlMap object.

Example

See the example for CAtlMap::CAtlMap.

Call this method to obtain a pointer to the next element pair stored in the CAtlMap object.

CPair* GetNext(POSITION& pos) throw();
const CPair* GetNext(POSITION& pos) const throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Return Value

Returns a pointer to the next pair of key/value elements stored in the map. The pos position counter is updated after each call. If the retrieved element is the last in the map, pos is set to NULL.

Gets the next element for iterating.

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

key
Template parameter specifying the type of the map's key.

value
Template parameter specifying the type of the map's value.

Remarks

The pos position counter is updated after each call. If the retrieved element is the last in the map, pos is set to NULL.

Call this method to retrieve the next key from the CAtlMap object.

const K& GetNextKey(POSITION& pos) const throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Return Value

Returns a reference to the next key in the map.

Remarks

Updates the current position counter, pos. If there are no more entries in the map, the position counter is set to NULL.

Call this method to get the next value from the CAtlMap object.

V& GetNextValue(POSITION& pos) throw();
const V& GetNextValue(POSITION& pos) const throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Return Value

Returns a reference to the next value in the map.

Remarks

Updates the current position counter, pos. If there are no more entries in the map, the position counter is set to NULL.

Example

See the example for CAtlMap::CAtlMap.

Call this method to start a map iteration.

POSITION GetStartPosition() const throw();

Return Value

Returns the start position, or NULL is returned if the map is empty.

Remarks

Call this method to start a map iteration by returning a POSITION value that can be passed to the GetNextAssoc method.

System_CAPS_ICON_note.jpg Note

The iteration sequence is not predictable

Example

See the example for CAtlMap::CAtlMap.

Call this method to retrieve the value stored at a given position in the CAtlMap object.

V& GetValueAt(POSITION pos) throw();
const V& GetValueAt(POSITION pos) const throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Return Value

Returns a reference to the value stored at the given position in the CAtlMap object.

Call this method to initialize the hash table.

bool InitHashTable(
    UINT nBins,
    bool bAllocNow = true);

Parameters

nBins
The number of bins used by the hash table. See CAtlMap::CAtlMap for an explanation.

bAllocNow
A flag indication when memory should be allocated.

Return Value

Returns true on successful initialization, false on failure.

Remarks

InitHashTable must be called before any elements are stored in the hash table. If this method is not called explicitly, it will be called automatically the first time an element is added using the bin count specified by the CAtlMap constructor. Otherwise, the map will be initialized using the new bin count specified by the nBins parameter.

If the bAllocNow parameter is false, the memory required by the hash table will not be allocated until it is first required. This can be useful if it is uncertain if the map will be used.

Example

See the example for CAtlMap::CAtlMap.

Call this method to test for an empty map object.

bool IsEmpty() const throw();

Return Value

Returns true if the map is empty, false otherwise.

Type used when a key is passed as an input argument.

typedef KTraits::INARGTYPE KINARGTYPE;

Type used when a key is returned as an output argument.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

Call this method to look up keys or values in the CAtlMap object.

bool Lookup(KINARGTYPE key, VOUTARGTYPE value) const;
const CPair* Lookup(KINARGTYPE key) const throw();
CPair* Lookup(KINARGTYPE key) throw();

Parameters

key
Specifies the key that identifies the element to be looked up.

value
Variable that receives the looked-up value.

Return Value

The first form of the method returns true if the key is found, otherwise false. The second and third forms return a pointer to a CPair which can be used as a position for calls to CAtlMap::GetNext and so on.

Remarks

Lookup uses a hashing algorithm to quickly find the map element containing a key that exactly matches the given key parameter.

Replaces or adds a new element to the CAtlMap.

V& operator[](KINARGTYPE   key) throw();

Parameters

key
The key of the element to add or replace.

Return Value

Returns a reference to the value associated with the given key.

Example

If the key already exists, the element is replaced. If the key does not exist, a new element is added. See the example for CAtlMap::CAtlMap.

Call this method to rehash the CAtlMap object.

void Rehash(UINT nBins = 0);

Parameters

nBins
The new number of bins to use in the hash table. See CAtlMap::CAtlMap for an explanation.

Remarks

If nBins is 0, CAtlMap calculates a reasonable number based on the number of elements in the map and the optimal load setting. Normally the rehashing process is automatic, but if CAtlMap::DisableAutoRehash has been called, this method will perform the necessary resizing.

Call this method to remove all elements from the CAtlMap object.

void RemoveAll() throw();

Remarks

Clears out the CAtlMap object, freeing the memory used to store the elements.

Call this method to remove the element at the given position in the CAtlMap object.

void RemoveAtPos(POSITION pos) throw();

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

Remarks

Removes the key/value pair stored at the specified position. The memory used to store the element is freed. The POSITION referenced by pos becomes invalid, and while the POSITION of any other elements in the map remains valid, they do not necessarily retain the same order.

Call this method to remove an element from the CAtlMap object, given the key.

bool RemoveKey(KINARGTYPE key) throw();

Parameters

key
The key corresponding to the element pair you want to remove.

Return Value

Returns true if the key is found and removed, false on failure.

Example

See the example for CAtlMap::CAtlMap.

Call this method to insert an element pair into the map.

POSITION SetAt(
    KINARGTYPE key,
    VINARGTYPE value);

Parameters

key
The key value to add to the CAtlMap object.

value
The value to add to the CAtlMap object.

Return Value

Returns the position of the key/value element pair in the CAtlMap object.

Remarks

SetAt replaces an existing element if a matching key is found. If the key is not found, a new key/value pair is created.

Call this method to set the optimal load of the CAtlMap object.

void SetOptimalLoad(
    float fOptimalLoad,
    float fLoThreshold,
    float fHiThreshold,
    bool bRehashNow = false);

Parameters

fOptimalLoad
The optimal load ratio.

fLoThreshold
The lower threshold for the load ratio.

fHiThreshold
The upper threshold for the load ratio.

bRehashNow
Flag indicating if the hash table should be recalculated.

Remarks

This method redefines the optimal load value for the CAtlMap object. See CAtlMap::CAtlMap for a discussion of the various parameters. If bRehashNow is true, and the number of elements is outside the minimum and maximum values, the hash table is recalculated.

Call this method to change the value stored at a given position in the CAtlMap object.

void SetValueAt(
    POSITION pos,
    VINARGTYPE value);

Parameters

pos
The position counter, returned by a previous call to CAtlMap::GetNextAssoc or CAtlMap::GetStartPosition.

value
The value to add to the CAtlMap object.

Remarks

Changes the value element stored at the given position in the CAtlMap object.

Type used when a value is passed as an input argument.

typedef VTraits::INARGTYPE VINARGTYPE;

Type used when a value is passed as an output argument.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

The data member storing the key element.

const K m_key;

Parameters

K
The key element type.

The data member storing the value element.

V  m_value;

Parameters

V
The value element type.

Marquee Sample
UpdatePV Sample
Class Overview

Show: