# ACE_Array_Map< Key, Value, EqualTo > Class Template Reference

Light weight array-based map with fast iteration, but linear (i.e. O(n)) search times. More...

`#include <Array_Map.h>`

List of all members.

## Public Types

typedef Key | key_type
typedef Value | data_type
typedef std::pair< key_type, data_type > | value_type
typedef value_type * | iterator
typedef value_type const * | const_iterator
typedef value_type & | reference
typedef value_type const & | const_reference
typedef value_type * | pointer
typedef value_type const * | const_pointer
typedef ptrdiff_t | difference_type
typedef size_t | size_type
typedef std::reverse_iterator< iterator > | reverse_iterator
typedef std::reverse_iterator< const_iterator > | const_reverse_iterator

## Public Member Functions

| ACE_Array_Map (size_type s=0)
| Default Constructor.
template<typename InputIterator>
| ACE_Array_Map (InputIterator f, InputIterator l)
| ACE_Array_Map (ACE_Array_Map const &map)
ACE_Array_Map & | operator= (ACE_Array_Map const &map)
| ~ACE_Array_Map (void)
| Destructor.
size_type | size (void) const
| Return current size of map.
size_type | max_size (void) const
| Maximum number of elements the map can hold.
bool | empty (void) const
| Is the map empty?
void | swap (ACE_Array_Map &map)
std::pair< iterator, bool > | insert (value_type const &x)
| Insert the value x into the map.
template<typename InputIterator>
void | insert (InputIterator f, InputIterator l)
| Insert range of elements into map.
void | erase (iterator pos)
| Remove element at position pos from the map.
size_type | erase (key_type const &k)
| Remove element corresponding to key k from the map.
void | erase (iterator first, iterator last)
| Remove range of elements [first, last) from the map.
void | clear (void)
| Clear contents of map.
size_type | count (key_type const &k)
| Count the number of elements corresponding to key k.
data_type & | operator[] (key_type const &k)
| Convenience array index operator.
Forward Iterator Accessors
Forward iterator accessors.
iterator | begin (void)
iterator | end (void)
const_iterator | begin (void) const
const_iterator | end (void) const
Reverse Iterator Accessors
Reverse iterator accessors.
reverse_iterator | rbegin (void)
reverse_iterator | rend (void)
const_reverse_iterator | rbegin (void) const
const_reverse_iterator | rend (void) const
Search Operations
Search the map for data corresponding to key k.
iterator | find (key_type const &k)
const_iterator | find (key_type const &k) const

## Private Member Functions

void | grow (size_type s)
| Increase size of underlying buffer by s.

## Private Attributes

size_type | size_
| Number of elements in the map.
size_type | capacity_
| Current size of underlying array.
value_type * | nodes_
| Underlying array containing keys and data.

## Detailed Description

### template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
class ACE_Array_Map< Key, Value, EqualTo >

Light weight array-based map with fast iteration, but linear (i.e. O(n)) search times.

Map implementation that focuses on small footprint and fast iteration. Search times are, however, linear (O(n)) meaning that this map isn't suitable for large data sets that will be searched in performance critical areas of code. Iteration over large data sets, however, is faster than linked list-based maps, for example, since spatial locality is maximized through the use of contiguous arrays as the underlying storage.

  An `ACE_Array_Map` is a unique associative container, meaning that duplicate values may not be added to the map. It is also pair associative (value_type is a std::pair<>). It is not a sorted container.

  An STL `std::map` -like interface is exposed by this class portability. Furthermore, this map's iterators are compatible with STL algorithms.

  Requirements and Performance Characteristics
  - Internal Structure Array
  - Duplicates allowed? No
  - Random access allowed? Yes
  - Search speed O(n)
  - Insert/replace speed O(n), can be longer if the map has to resize
  - Iterator still valid after change to container? No
  - Frees memory for removed elements? Yes
  - Items inserted by Value
  - Requirements for key type
    1. Default constructor
    2. Copy constructor
    3. operator=
    4. operator==
  - Requirements for object type
    1. Default constructor
    2. Copy constructor
    3. operator=

## Member Typedef Documentation

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type const* ACE_Array_Map< Key, Value, EqualTo >::const_iterator

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type const* ACE_Array_Map< Key, Value, EqualTo >::const_pointer

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type const& ACE_Array_Map< Key, Value, EqualTo >::const_reference

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef std::reverse_iterator<const_iterator> ACE_Array_Map< Key, Value, EqualTo >::const_reverse_iterator

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef Value ACE_Array_Map< Key, Value, EqualTo >::data_type

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef ptrdiff_t ACE_Array_Map< Key, Value, EqualTo >::difference_type

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type* ACE_Array_Map< Key, Value, EqualTo >::iterator

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef Key ACE_Array_Map< Key, Value, EqualTo >::key_type

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type* ACE_Array_Map< Key, Value, EqualTo >::pointer

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef value_type& ACE_Array_Map< Key, Value, EqualTo >::reference

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef std::reverse_iterator<iterator> ACE_Array_Map< Key, Value, EqualTo >::reverse_iterator

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef size_t ACE_Array_Map< Key, Value, EqualTo >::size_type

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
typedef std::pair<key_type, data_type> ACE_Array_Map< Key, Value, EqualTo >::value_type

## Constructor & Destructor Documentation

template<typename Key, typename Value, class EqualTo>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map | ( | size_type | s = `0` | ) |

| Default Constructor. Create an empty map with a preallocated buffer of size s.

template<typename Key, typename Value, class EqualTo>
template<typename InputIterator>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map | ( | InputIterator | f,
|  | InputIterator | l
| ) |

template<typename Key, typename Value, class EqualTo>
ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map | ( | ACE_Array_Map< Key, Value, EqualTo > const & | map | ) |

template<typename Key, typename Value, class EqualTo>
ACE_Array_Map< Key, Value, EqualTo >::~ACE_Array_Map | ( | void |  | ) |

| Destructor.

## Member Function Documentation

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::const_iterator ACE_Array_Map< Key, Value, EqualTo >::begin | ( | void |  | ) | const

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::iterator ACE_Array_Map< Key, Value, EqualTo >::begin | ( | void |  | ) |

template<typename Key, typename Value, class EqualTo>
void ACE_Array_Map< Key, Value, EqualTo >::clear | ( | void |  | ) |

Clear contents of map.

Note:
  This a constant time (O(1)) operation.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
size_type ACE_Array_Map< Key, Value, EqualTo >::count | ( | key_type const & | k | ) |

Count the number of elements corresponding to key k.

Returns:
  In the case of this map, the count will always be one if such exists in the map.

template<typename Key, typename Value, class EqualTo>
ACE_INLINE bool ACE_Array_Map< Key, Value, EqualTo >::empty | ( | void |  | ) | const

| Is the map empty?

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::const_iterator ACE_Array_Map< Key, Value, EqualTo >::end | ( | void |  | ) | const

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::iterator ACE_Array_Map< Key, Value, EqualTo >::end | ( | void |  | ) |

template<typename Key, typename Value, class EqualTo>
void ACE_Array_Map< Key, Value, EqualTo >::erase | ( | iterator | first,
|  | iterator | last
| ) |

Remove range of elements [first, last) from the map.

Note:
  [first, ) must be valid range within the map.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
size_type ACE_Array_Map< Key, Value, EqualTo >::erase | ( | key_type const & | k | ) |

Remove element corresponding to key k from the map.

Returns:
  Number of elements that were erased.

template<typename Key, typename Value, class EqualTo>
void ACE_Array_Map< Key, Value, EqualTo >::erase | ( | iterator | pos | ) |

| Remove element at position pos from the map.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
const_iterator ACE_Array_Map< Key, Value, EqualTo >::find | ( | key_type const & | k | ) | const

Returns:
  `end()` if data corresponding to key k is not in the map.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
iterator ACE_Array_Map< Key, Value, EqualTo >::find | ( | key_type const & | k | ) |

Returns:
  `end()` if data corresponding to key k is not in the map.

template<typename Key, typename Value, class EqualTo>
void ACE_Array_Map< Key, Value, EqualTo >::grow | ( | size_type | s | ) | `[private]`

| Increase size of underlying buffer by s.

template<typename Key, typename Value, class EqualTo>
template<typename InputIterator>
void ACE_Array_Map< Key, Value, EqualTo >::insert | ( | InputIterator | f,
|  | InputIterator | l
| ) |

| Insert range of elements into map.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
std::pair<iterator, bool> ACE_Array_Map< Key, Value, EqualTo >::insert | ( | value_type const & | x | ) |

Insert the value x into the map.

STL-style map insertion method.

Parameters:

  | x | `std::pair` containing key and datum.

Returns:
  `std::pair::second` will be `false` if the map already contains a value with the same key as x.

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::size_type ACE_Array_Map< Key, Value, EqualTo >::max_size | ( | void |  | ) | const

| Maximum number of elements the map can hold.

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo > & ACE_Array_Map< Key, Value, EqualTo >::operator= | ( | ACE_Array_Map< Key, Value, EqualTo > const & | map | ) |

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
data_type& ACE_Array_Map< Key, Value, EqualTo >::operator[] | ( | key_type const & | k | ) |

Convenience array index operator.

Array index operator that allows insertion and retrieval of elements using an array index syntax, such as:

  map["Foo"] = 12;

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::const_reverse_iterator ACE_Array_Map< Key, Value, EqualTo >::rbegin | ( | void |  | ) | const

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::reverse_iterator ACE_Array_Map< Key, Value, EqualTo >::rbegin | ( | void |  | ) |

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::const_reverse_iterator ACE_Array_Map< Key, Value, EqualTo >::rend | ( | void |  | ) | const

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::reverse_iterator ACE_Array_Map< Key, Value, EqualTo >::rend | ( | void |  | ) |

template<typename Key, typename Value, class EqualTo>
ACE_INLINE ACE_Array_Map< Key, Value, EqualTo >::size_type ACE_Array_Map< Key, Value, EqualTo >::size | ( | void |  | ) | const

Return current size of map.

Returns:
  The number of elements in the map.

template<typename Key, typename Value, class EqualTo>
void ACE_Array_Map< Key, Value, EqualTo >::swap | ( | ACE_Array_Map< Key, Value, EqualTo > & | map | ) |

| Swap the contents of this map with the given map in an exception-safe manner.

## Member Data Documentation

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
size_type ACE_Array_Map< Key, Value, EqualTo >::capacity_`[private]`

Current size of underlying array.

Note:
  `capacity_` is always greater than or equal to `size_`;

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
value_type* ACE_Array_Map< Key, Value, EqualTo >::nodes_`[private]`

| Underlying array containing keys and data.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>>
size_type ACE_Array_Map< Key, Value, EqualTo >::size_`[private]`

| Number of elements in the map.

The documentation for this class was generated from the following files:

- Array_Map.h
- Array_Map.cpp
- Array_Map.inl