#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. | |
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 | is_empty (void) const |
Return true if the map is empty, else false . | |
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. | |
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. |
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.
Definition at line 88 of file Array_Map.h.
|
Definition at line 97 of file Array_Map.h. |
|
Definition at line 101 of file Array_Map.h. |
|
Definition at line 99 of file Array_Map.h. |
|
Definition at line 94 of file Array_Map.h. |
|
Definition at line 102 of file Array_Map.h. |
|
Definition at line 96 of file Array_Map.h. |
|
Definition at line 93 of file Array_Map.h. |
|
Definition at line 100 of file Array_Map.h. |
|
Definition at line 98 of file Array_Map.h. |
|
Definition at line 103 of file Array_Map.h. Referenced by ACE_Array_Map< Key, Value, EqualTo >::max_size(). |
|
Definition at line 95 of file Array_Map.h. Referenced by ACE_Array_Map< Key, Value, EqualTo >::erase(). |
|
Default Constructor. Create an empty map with a preallocated buffer of size s. Definition at line 9 of file Array_Map.inl.
|
|
Definition at line 21 of file Array_Map.cpp. References ACE_make_checked_array_iterator(), and ACE_Array_Map< Key, Value, EqualTo >::size_.
00023 : size_ (l - f) 00024 , capacity_ (size_) 00025 , nodes_ (size_ == 0 ? 0 : new value_type[size_]) 00026 { 00027 (void) std::copy (f, 00028 l, 00029 ACE_make_checked_array_iterator (this->begin (), 00030 this->size_)); 00031 00032 // iterator n = this->begin (); 00033 00034 // for (InputIterator i = f; i != l; ++i, ++n) 00035 // *n = *i; 00036 } |
|
Definition at line 59 of file Array_Map.cpp. References ACE_make_checked_array_iterator(), ACE_Array_Map< Key, Value, EqualTo >::begin(), ACE_Array_Map< Key, Value, EqualTo >::end(), and ACE_Array_Map< Key, Value, EqualTo >::size_.
00061 : size_ (map.size_) 00062 , capacity_ (map.size_) 00063 , nodes_ (size_ == 0 ? 0 : new value_type[size_]) 00064 { 00065 std::copy (map.begin (), 00066 map.end (), 00067 ACE_make_checked_array_iterator (this->begin (), 00068 this->size_)); 00069 00070 // iterator f = map.begin (); 00071 // iterator l = map.end (); 00072 // iterator n = this->begin (); 00073 00074 // for (iterator i = f; i != l; ++i, ++n) 00075 // *n = *i; 00076 } |
|
Destructor.
Definition at line 79 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::nodes_.
00080 { 00081 delete[] this->nodes_; 00082 } |
|
Definition at line 45 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::nodes_.
00046 { 00047 return this->nodes_; 00048 } |
|
Definition at line 31 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::nodes_. Referenced by ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map(), ACE_Array_Map< Key, Value, EqualTo >::erase(), ACE_Array_Map< Key, Value, EqualTo >::grow(), and operator==().
00032 { 00033 return this->nodes_; 00034 } |
|
Clear contents of map.
Definition at line 205 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::size_.
00206 { 00207 this->size_ = 0; // No need to deallocate array nor destroy elements. 00208 } |
|
Count the number of elements corresponding to key k.
|
|
Return Definition at line 110 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::is_empty().
00111 { 00112 return this->is_empty (); 00113 } |
|
Definition at line 52 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::nodes_, and ACE_Array_Map< Key, Value, EqualTo >::size_.
|
|
Definition at line 38 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::nodes_, and ACE_Array_Map< Key, Value, EqualTo >::size_. Referenced by ACE_Array_Map< Key, Value, EqualTo >::ACE_Array_Map(), ACE_Array_Map< Key, Value, EqualTo >::erase(), ACE_Array_Map< Key, Value, EqualTo >::grow(), and operator==().
|
|
Remove range of elements [first, last) from the map.
Definition at line 194 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::begin(), ACE_Array_Map< Key, Value, EqualTo >::end(), and ACE_Array_Map< Key, Value, EqualTo >::erase().
|
|
Remove element corresponding to key k from the map.
|
|
Remove element at position pos from the map.
Definition at line 153 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::begin(), ACE_Array_Map< Key, Value, EqualTo >::end(), ACE_Array_Map< Key, Value, EqualTo >::size_, and ACE_Array_Map< Key, Value, EqualTo >::value_type. Referenced by ACE_Array_Map< Key, Value, EqualTo >::erase().
00155 { 00156 iterator const first = this->begin (); 00157 iterator const last = this->end (); 00158 00159 if (pos >= first && pos < last) 00160 { 00161 if (pos != last - 1) 00162 { 00163 // Relocate the tail element to the location of the erased 00164 // element to prevent introduction of "holes" in the 00165 // underlying array. 00166 *pos = *(last - 1); 00167 } 00168 00169 // Explicitly destroy the tail element by assigning a default 00170 // constructed instance to it. Note that this also works for 00171 // the case of a map of size 1. 00172 *(last - 1) = value_type (); 00173 00174 --this->size_; 00175 } 00176 } |
|
|
|
|
|
Increase size of underlying buffer by s.
Definition at line 244 of file Array_Map.cpp. References ACE_make_checked_array_iterator(), ACE_Array_Map< Key, Value, EqualTo >::begin(), ACE_Array_Map< Key, Value, EqualTo >::capacity_, ACE_Array_Map< Key, Value, EqualTo >::end(), ACE_Array_Map< Key, Value, EqualTo >::size(), ACE_Array_Map< Key, Value, EqualTo >::size_, and ACE_Array_Map< Key, Value, EqualTo >::swap(). Referenced by ACE_Array_Map< Key, Value, EqualTo >::insert().
00246 { 00247 if (this->size () + s > this->capacity_) 00248 { 00249 // This implementation focuses more on static footprint than 00250 // speed. 00251 00252 // Strongly exception safe. 00253 00254 ACE_Array_Map<Key, Value, EqualTo> temp (this->size () + s); 00255 00256 std::copy (this->begin (), 00257 this->end (), 00258 ACE_make_checked_array_iterator (temp.begin (), 00259 temp.capacity_)); 00260 00261 size_type const n = this->size (); // Do not swap out the size 00262 // since we bypassed the 00263 // temporary map's element 00264 // counting code. 00265 this->swap (temp); 00266 00267 this->size_ = n; 00268 } 00269 } |
|
Insert range of elements into map.
Definition at line 126 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::grow(), and ACE_Array_Map< Key, Value, EqualTo >::insert().
|
|
Insert the value x into the map. STL-style map insertion method.
Referenced by ACE_Array_Map< Key, Value, EqualTo >::insert(). |
|
Return
Definition at line 101 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::size_. Referenced by ACE_Array_Map< Key, Value, EqualTo >::empty().
00102 { 00103 return this->size_ == 0; 00104 } |
|
Maximum number of elements the map can hold.
Definition at line 94 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::size_type.
00095 { 00096 return size_type (-1) / sizeof (value_type); 00097 } |
|
Definition at line 19 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::swap().
00021 { 00022 // Strongly exception-safe assignment. 00023 00024 ACE_Array_Map<Key, Value, EqualTo> temp (map); 00025 this->swap (temp); 00026 return *this; 00027 } |
|
Convenience array index operator. Array index operator that allows insertion and retrieval of elements using an array index syntax, such as:
|
|
Definition at line 73 of file Array_Map.inl.
00074 {
00075 return const_reverse_iterator (this->end ());
00076 }
|
|
Definition at line 59 of file Array_Map.inl.
00060 {
00061 return reverse_iterator (this->end ());
00062 }
|
|
Definition at line 80 of file Array_Map.inl.
00081 {
00082 return const_reverse_iterator (this->begin ());
00083 }
|
|
Definition at line 66 of file Array_Map.inl.
00067 {
00068 return reverse_iterator (this->begin ());
00069 }
|
|
Return current size of map.
Definition at line 87 of file Array_Map.inl. References ACE_Array_Map< Key, Value, EqualTo >::size_. Referenced by ACE_Array_Map< Key, Value, EqualTo >::grow(), and operator==().
00088 { 00089 return this->size_; 00090 } |
|
Swap the contents of this map with the given map in an exception-safe manner. Definition at line 86 of file Array_Map.cpp. References ACE_Array_Map< Key, Value, EqualTo >::capacity_, ACE_Array_Map< Key, Value, EqualTo >::nodes_, and ACE_Array_Map< Key, Value, EqualTo >::size_. Referenced by ACE_Array_Map< Key, Value, EqualTo >::grow(), and ACE_Array_Map< Key, Value, EqualTo >::operator=().
|
|
Current size of underlying array.
Definition at line 263 of file Array_Map.h. Referenced by ACE_Array_Map< Key, Value, EqualTo >::grow(), and ACE_Array_Map< Key, Value, EqualTo >::swap(). |
|
Underlying array containing keys and data.
Definition at line 266 of file Array_Map.h. Referenced by ACE_Array_Map< Key, Value, EqualTo >::begin(), ACE_Array_Map< Key, Value, EqualTo >::end(), ACE_Array_Map< Key, Value, EqualTo >::swap(), and ACE_Array_Map< Key, Value, EqualTo >::~ACE_Array_Map(). |
|