ACE
6.3.3
|
Light weight array-based map with fast iteration, but linear (i.e. O(n)) search times. More...
#include <Array_Map.h>
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 |
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_Map & | operator= (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... | |
data_type & | operator[] (key_type const &k) |
Convenience array index operator. More... | |
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 | |
size_type | size_ |
Number of elements in the map. More... | |
size_type | capacity_ |
Current size of underlying array. More... | |
value_type * | nodes_ |
Underlying array containing keys and data. More... | |
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.
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. std::map
-like interface is exposed by this class portability. Furthermore, this map's iterators are compatible with STL algorithms. typedef value_type const* ACE_Array_Map< Key, Value, EqualTo >::const_iterator |
typedef value_type const* ACE_Array_Map< Key, Value, EqualTo >::const_pointer |
typedef value_type const& ACE_Array_Map< Key, Value, EqualTo >::const_reference |
typedef Value ACE_Array_Map< Key, Value, EqualTo >::data_type |
typedef ptrdiff_t ACE_Array_Map< Key, Value, EqualTo >::difference_type |
typedef value_type* ACE_Array_Map< Key, Value, EqualTo >::iterator |
typedef Key ACE_Array_Map< Key, Value, EqualTo >::key_type |
typedef value_type* ACE_Array_Map< Key, Value, EqualTo >::pointer |
typedef value_type& ACE_Array_Map< Key, Value, EqualTo >::reference |
typedef size_t ACE_Array_Map< Key, Value, EqualTo >::size_type |
typedef std::pair<key_type, data_type> ACE_Array_Map< Key, Value, EqualTo >::value_type |
ACE_DECLARE_STL_REVERSE_ITERATORS 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.
ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map | ( | InputIterator | f, |
InputIterator | l | ||
) |
ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map | ( | ACE_Array_Map< Key, Value, EqualTo > const & | map | ) |
ACE_Array_Map< Key, Value, EqualTo >::~ACE_Array_Map | ( | void | ) |
Destructor.
|
inline |
|
inline |
void ACE_Array_Map< Key, Value, EqualTo >::clear | ( | void | ) |
Clear contents of map.
|
inline |
Count the number of elements corresponding to key k.
|
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.
|
inline |
|
inline |
void ACE_Array_Map< Key, Value, EqualTo >::erase | ( | iterator | pos | ) |
Remove element at position pos from the map.
size_type ACE_Array_Map< Key, Value, EqualTo >::erase | ( | key_type const & | k | ) |
Remove element corresponding to key k from the map.
void ACE_Array_Map< Key, Value, EqualTo >::erase | ( | iterator | first, |
iterator | last | ||
) |
Remove range of elements [first, last) from the map.
iterator ACE_Array_Map< Key, Value, EqualTo >::find | ( | key_type const & | k | ) |
end()
if data corresponding to key k is not in the map. const_iterator ACE_Array_Map< Key, Value, EqualTo >::find | ( | key_type const & | k | ) | const |
end()
if data corresponding to key k is not in the map.
|
private |
Increase size of underlying buffer by s.
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.
x | std::pair containing key and datum. |
std::pair::second
will be false
if the map already contains a value with the same key as x. void ACE_Array_Map< Key, Value, EqualTo >::insert | ( | InputIterator | f, |
InputIterator | l | ||
) |
Insert range of elements into map.
|
inline |
Return true
if the map is empty, else false
.
|
inline |
Maximum number of elements the map can hold.
|
inline |
|
inline |
Convenience array index operator.
Array index operator that allows insertion and retrieval of elements using an array index syntax, such as:
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Return current size of map.
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.
|
private |
Current size of underlying array.
capacity_
is always greater than or equal to size_
;
|
private |
Underlying array containing keys and data.
|
private |
Number of elements in the map.