ACE  6.4.2
Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
ACE_Array_Map< Key, Value, EqualTo, Alloc > Class Template Reference

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

#include <Array_Map.h>

Collaboration diagram for ACE_Array_Map< Key, Value, EqualTo, Alloc >:
Collaboration graph
[legend]

Public Types

typedef Key key_type
 
typedef Value mapped_type
 
typedef Value data_type
 
typedef std::pair< key_type, mapped_typevalue_type
 
typedef Alloc allocator_type
 
typedef value_typereference
 
typedef value_type const & const_reference
 
typedef value_typepointer
 
typedef value_type const * const_pointer
 
typedef value_typeiterator
 
typedef value_type const * const_iterator
 
typedef ptrdiff_t difference_type
 
typedef size_t size_type
 

Public Member Functions

ACE_DECLARE_STL_REVERSE_ITERATORS ACE_Array_Map (size_type s=0)
 Default Constructor. More...
 
template<typename InputIterator >
 ACE_Array_Map (InputIterator f, InputIterator l)
 
 ACE_Array_Map (ACE_Array_Map const &map)
 
ACE_Array_Mapoperator= (ACE_Array_Map const &map)
 
 ~ACE_Array_Map (void)
 Destructor. More...
 
size_type size (void) const
 Return current size of map. More...
 
size_type max_size (void) const
 Maximum number of elements the map can hold. More...
 
bool is_empty (void) const
 Return true if the map is empty, else false. More...
 
bool empty (void) const
 
void swap (ACE_Array_Map &map)
 
std::pair< iterator, bool > insert (value_type const &x)
 Insert the value x into the map. More...
 
template<typename InputIterator >
void insert (InputIterator f, InputIterator l)
 Insert range of elements into map. More...
 
void erase (iterator pos)
 Remove element at position pos from the map. More...
 
size_type erase (key_type const &k)
 Remove element corresponding to key k from the map. More...
 
void erase (iterator first, iterator last)
 Remove range of elements [first, last) from the map. More...
 
void clear (void)
 Clear contents of map. More...
 
size_type count (key_type const &k)
 Count the number of elements corresponding to key k. More...
 
mapped_typeoperator[] (key_type const &k)
 Convenience array index operator. More...
 
allocator_type get_allocator () const
 
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. More...
 

Private Attributes

allocator_type alloc_
 The allocator. More...
 
size_type size_
 Number of elements in the map. More...
 
size_type capacity_
 Current size of underlying array. More...
 
value_typenodes_
 Underlying array containing keys and data. More...
 

Detailed Description

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
class ACE_Array_Map< Key, Value, EqualTo, Alloc >

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>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef Alloc ACE_Array_Map< Key, Value, EqualTo, Alloc >::allocator_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type const* ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_iterator
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type const* ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_pointer
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type const& ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_reference
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef Value ACE_Array_Map< Key, Value, EqualTo, Alloc >::data_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef ptrdiff_t ACE_Array_Map< Key, Value, EqualTo, Alloc >::difference_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::iterator
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef Key ACE_Array_Map< Key, Value, EqualTo, Alloc >::key_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef Value ACE_Array_Map< Key, Value, EqualTo, Alloc >::mapped_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::pointer
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef value_type& ACE_Array_Map< Key, Value, EqualTo, Alloc >::reference
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef size_t ACE_Array_Map< Key, Value, EqualTo, Alloc >::size_type
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
typedef std::pair<key_type, mapped_type> ACE_Array_Map< Key, Value, EqualTo, Alloc >::value_type

Constructor & Destructor Documentation

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
ACE_DECLARE_STL_REVERSE_ITERATORS ACE_Array_Map< Key, Value, EqualTo, Alloc >::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 , class Alloc >
template<typename InputIterator >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::ACE_Array_Map ( InputIterator  f,
InputIterator  l 
)
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::ACE_Array_Map ( ACE_Array_Map< Key, Value, EqualTo, Alloc > const &  map)
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::~ACE_Array_Map ( void  )

Destructor.

Member Function Documentation

template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::begin ( void  )
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::begin ( void  ) const
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::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>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
ACE_Array_Map< Key, Value, EqualTo, Alloc >::size_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::count ( key_type const &  k)
inline

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 , class Alloc >
bool ACE_Array_Map< Key, Value, EqualTo, Alloc >::empty ( void  ) const
inline

Return true if the map is empty, else false. We recommend using is_empty() instead since it's more consistent with the ACE container naming conventions.

template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::end ( void  )
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::end ( void  ) const
inline
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::erase ( iterator  pos)

Remove element at position pos from the map.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
size_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::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 = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::erase ( iterator  first,
iterator  last 
)

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

Note
[first, last) must be valid range within the map.
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::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 = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
const_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::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>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
allocator_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::get_allocator ( ) const
inline
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::grow ( size_type  s)
private

Increase size of underlying buffer by s.

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

Insert the value x into the map.

STL-style map insertion method.

Parameters
xstd::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 , class Alloc >
template<typename InputIterator >
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::insert ( InputIterator  f,
InputIterator  l 
)

Insert range of elements into map.

template<typename Key , typename Value , class EqualTo , class Alloc >
bool ACE_Array_Map< Key, Value, EqualTo, Alloc >::is_empty ( void  ) const
inline

Return true if the map is empty, else false.

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

Maximum number of elements the map can hold.

template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc > & ACE_Array_Map< Key, Value, EqualTo, Alloc >::operator= ( ACE_Array_Map< Key, Value, EqualTo, Alloc > const &  map)
inline
template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
ACE_Array_Map< Key, Value, EqualTo, Alloc >::mapped_type & ACE_Array_Map< Key, Value, EqualTo, Alloc >::operator[] ( key_type const &  k)
inline

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 , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::reverse_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::rbegin ( void  )
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_reverse_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::rbegin ( void  ) const
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::reverse_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::rend ( void  )
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_reverse_iterator ACE_Array_Map< Key, Value, EqualTo, Alloc >::rend ( void  ) const
inline
template<typename Key , typename Value , class EqualTo , class Alloc >
ACE_Array_Map< Key, Value, EqualTo, Alloc >::size_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::size ( void  ) const
inline

Return current size of map.

Returns
The number of elements in the map.
template<typename Key , typename Value , class EqualTo , class Alloc >
void ACE_Array_Map< Key, Value, EqualTo, Alloc >::swap ( ACE_Array_Map< Key, Value, EqualTo, Alloc > &  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>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
allocator_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::alloc_
private

The allocator.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
size_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::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>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::nodes_
private

Underlying array containing keys and data.

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = ACE_ARRAY_MAP_DEFAULT_ALLOCATOR (Key, Value)>
size_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::size_
private

Number of elements in the map.


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