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 >:

[legend]

Public Types
typedef Key	key_type

typedef Value	mapped_type

typedef Value	data_type

typedef std::pair< key_type, mapped_type >	value_type

typedef Alloc	allocator_type

typedef value_type &	reference

typedef value_type const &	const_reference

typedef value_type *	pointer

typedef value_type const *	const_pointer

typedef value_type *	iterator

typedef value_type const *	const_iterator

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

Forward Iterator Accessors
Forward iterator accessors.
iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

Reverse Iterator Accessors
Reverse iterator accessors.
reverse_iterator	rbegin ()
	Return current size of map.

reverse_iterator	rend ()
	Return current size of map.

const_reverse_iterator	rbegin () const
	Return current size of map.

const_reverse_iterator	rend () const
	Return current size of map.

size_type	size () const
	Return current size of map.

size_type	max_size () const
	Maximum number of elements the map can hold.

bool	is_empty () const
	Return `true` if the map is empty, else `false`.

bool	empty () const

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 ()
	Clear contents of map.

Search Operations
Search the map for data corresponding to key k.
allocator_type	alloc_
	The allocator.

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.

iterator	find (key_type const &k)

const_iterator	find (key_type const &k) const

size_type	count (key_type const &k)
	Count the number of elements corresponding to key k.

mapped_type &	operator[] (key_type const &k)
	Convenience array index operator.

allocator_type	get_allocator () const
	The allocator.

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

Detailed Description

template<typename Key, typename Value, class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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

◆ allocator_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef Alloc ACE_Array_Map< Key, Value, EqualTo, Alloc >::allocator_type

◆ const_iterator

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type const* ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_iterator

◆ const_pointer

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type const* ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_pointer

◆ const_reference

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type const& ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_reference

◆ const_reverse_iterator

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef std::reverse_iterator<const_iterator> ACE_Array_Map< Key, Value, EqualTo, Alloc >::const_reverse_iterator

◆ data_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef Value ACE_Array_Map< Key, Value, EqualTo, Alloc >::data_type

◆ difference_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef ptrdiff_t ACE_Array_Map< Key, Value, EqualTo, Alloc >::difference_type

◆ iterator

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::iterator

◆ key_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef Key ACE_Array_Map< Key, Value, EqualTo, Alloc >::key_type

◆ mapped_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef Value ACE_Array_Map< Key, Value, EqualTo, Alloc >::mapped_type

◆ pointer

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::pointer

◆ reference

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef value_type& ACE_Array_Map< Key, Value, EqualTo, Alloc >::reference

◆ reverse_iterator

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef std::reverse_iterator<iterator> ACE_Array_Map< Key, Value, EqualTo, Alloc >::reverse_iterator

◆ size_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef size_t ACE_Array_Map< Key, Value, EqualTo, Alloc >::size_type

◆ value_type

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

typedef std::pair<key_type, mapped_type> ACE_Array_Map< Key, Value, EqualTo, Alloc >::value_type

Constructor & Destructor Documentation

◆ ACE_Array_Map() [1/3]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

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.

◆ ACE_Array_Map() [2/3]

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 )

◆ ACE_Array_Map() [3/3]

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 )

◆ ~ACE_Array_Map()

template<typename Key , typename Value , class EqualTo , class Alloc >

ACE_Array_Map< Key, Value, EqualTo, Alloc >::~ACE_Array_Map ( )

Destructor.

Member Function Documentation

◆ begin() [1/2]

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

inline

◆ begin() [2/2]

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

inline

◆ clear()

template<typename Key , typename Value , class EqualTo , class Alloc >

void ACE_Array_Map< Key, Value, EqualTo, Alloc >::clear ( )

Clear contents of map.

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

◆ count()

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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.

◆ empty()

template<typename Key , typename Value , class EqualTo , class Alloc >

bool ACE_Array_Map< Key, Value, EqualTo, Alloc >::empty ( ) 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.

◆ end() [1/2]

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

inline

◆ end() [2/2]

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

inline

◆ erase() [1/3]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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.

◆ erase() [2/3]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

void ACE_Array_Map< Key, Value, EqualTo, Alloc >::erase ( iterator pos )

Remove element at position pos from the map.

◆ erase() [3/3]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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.

◆ find() [1/2]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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.

◆ find() [2/2]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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.

◆ get_allocator()

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

allocator_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::get_allocator ( ) const

inline

The allocator.

◆ grow()

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

void ACE_Array_Map< Key, Value, EqualTo, Alloc >::grow ( size_type s )

private

Increase size of underlying buffer by s.

◆ insert() [1/2]

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.

◆ insert() [2/2]

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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

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.

◆ is_empty()

template<typename Key , typename Value , class EqualTo , class Alloc >

bool ACE_Array_Map< Key, Value, EqualTo, Alloc >::is_empty ( ) const

inline

Return true if the map is empty, else false.

◆ max_size()

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

inline

Maximum number of elements the map can hold.

◆ operator=()

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

◆ operator[]()

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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;

◆ rbegin() [1/2]

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

inline

Return current size of map.

Returns: The number of elements in the map.

◆ rbegin() [2/2]

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

inline

Return current size of map.

Returns: The number of elements in the map.

◆ rend() [1/2]

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

inline

Return current size of map.

Returns: The number of elements in the map.

◆ rend() [2/2]

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

inline

Return current size of map.

Returns: The number of elements in the map.

◆ size()

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

inline

Return current size of map.

Returns: The number of elements in the map.

◆ swap()

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

◆ alloc_

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

allocator_type ACE_Array_Map< Key, Value, EqualTo, Alloc >::alloc_

private

The allocator.

◆ capacity_

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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_;

◆ nodes_

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<Key,Value>>>

value_type* ACE_Array_Map< Key, Value, EqualTo, Alloc >::nodes_

private

Underlying array containing keys and data.

◆ size_

template<typename Key , typename Value , class EqualTo = std::equal_to<Key>, class Alloc = std::allocator<std::pair<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:

Public Types

Public Member Functions

Search Operations

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ data_type

◆ difference_type

◆ iterator

◆ key_type

◆ mapped_type

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ ACE_Array_Map() [1/3]

◆ ACE_Array_Map() [2/3]

◆ ACE_Array_Map() [3/3]

◆ ~ACE_Array_Map()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ get_allocator()

◆ grow()

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_empty()

◆ max_size()

◆ operator=()

◆ operator[]()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ swap()

Member Data Documentation

◆ alloc_

◆ capacity_

◆ nodes_

◆ size_