ACE/ace/Array_Map.h

   1 // -*- C++ -*-
   2
   3 //=============================================================================
   4 /**
   5  * @file    Array_Map.h
   6  *
   7  * Light weight array-based map with fast iteration but linear
   8  * (i.e. O(n)) search times.  STL-style interface is exposed.
   9  *
  10  * @note This class requires the STL generic algorithms and
  11  *       reverse_iterator adapter.
  12  *
  13  * @author  Ossama Othman
  14  */
  15 //=============================================================================
  16
  17
  18 #ifndef ACE_ARRAY_MAP_H
  19 #define ACE_ARRAY_MAP_H
  20
  21 #include /**/ "ace/pre.h"
  22
  23 #include /**/ "ace/config-lite.h"
  24
  25 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  26 # pragma once
  27 #endif /* ACE_LACKS_PRAGMA_ONCE */
  28
  29 #include <utility>
  30 #include <iterator>
  31 #include <functional>
  32 #include <memory>
  33
  34 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  35
  36 #define ACE_ARRAY_MAP_DEFAULT_ALLOCATOR(K, V) std::allocator<std::pair<K, V> >
  37
  38 /**
  39  * @class ACE_Array_Map
  40  *
  41  * @brief Light weight array-based map with fast iteration, but linear
  42  *        (i.e. O(n)) search times.
  43  *
  44  * Map implementation that focuses on small footprint and fast
  45  * iteration. Search times are, however, linear (O(n)) meaning that
  46  * this map isn't suitable for large data sets that will be searched
  47  * in performance critical areas of code.  Iteration over large data
  48  * sets, however, is faster than linked list-based maps, for example,
  49  * since spatial locality is maximized through the use of contiguous
  50  * arrays as the underlying storage.
  51  * @par
  52  * An @c ACE_Array_Map is a unique associative container, meaning that
  53  * duplicate values may not be added to the map.  It is also pair
  54  * associative (value_type is a std::pair<>).  It is not a sorted
  55  * container.
  56  * @par
  57  * An STL @c std::map -like interface is exposed by this class
  58  * portability.  Furthermore, this map's iterators are compatible with
  59  * STL algorithms.
  60  * @par
  61  * <b> Requirements and Performance Characteristics</b>
  62  *   - Internal Structure
  63  *       Array
  64  *   - Duplicates allowed?
  65  *       No
  66  *   - Random access allowed?
  67  *       Yes
  68  *   - Search speed
  69  *       O(n)
  70  *   - Insert/replace speed
  71  *       O(n), can be longer if the map has to resize
  72  *   - Iterator still valid after change to container?
  73  *       No
  74  *   - Frees memory for removed elements?
  75  *       Yes
  76  *   - Items inserted by
  77  *       Value
  78  *   - Requirements for key type
  79  *       -# Default constructor
  80  *       -# Copy constructor
  81  *       -# operator=
  82  *       -# operator==
  83  *   - Requirements for object type
  84  *       -# Default constructor
  85  *       -# Copy constructor
  86  *       -# operator=
  87  */
  88 template<typename Key, typename Value, class EqualTo = std::equal_to<Key>,
  89          class Alloc = std::allocator<std::pair<Key,Value>>>
  90 class ACE_Array_Map
  91 {
  92 public:
  93   // STL-style typedefs/traits.
  94   typedef Key                                    key_type;
  95   typedef Value                                  mapped_type;
  96   typedef Value                                  data_type;
  97   typedef std::pair<key_type, mapped_type>       value_type;
  98   typedef Alloc                                  allocator_type;
  99   typedef value_type &                           reference;
 100   typedef value_type const &                     const_reference;
 101   typedef value_type *                           pointer;
 102   typedef value_type const *                     const_pointer;
 103   typedef value_type *                           iterator;
 104   typedef value_type const *                     const_iterator;
 105   typedef ptrdiff_t                              difference_type;
 106   typedef size_t                                 size_type;
 107   typedef std::reverse_iterator<iterator>        reverse_iterator;
 108   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
 109
 110   /// Default Constructor.
 111   /**
 112    * Create an empty map with a preallocated buffer of size @a s.
 113    */
 114   ACE_Array_Map (size_type s = 0);
 115
 116   template<typename InputIterator>
 117   ACE_Array_Map (InputIterator f, InputIterator l);
 118
 119   ACE_Array_Map (ACE_Array_Map const & map);
 120   ACE_Array_Map & operator= (ACE_Array_Map const & map);
 121
 122   /// Destructor.
 123   ~ACE_Array_Map ();
 124
 125   /**
 126    * @name Forward Iterator Accessors
 127    *
 128    * Forward iterator accessors.
 129    */
 130   //@{
 131   iterator begin ();
 132   iterator end   ();
 133   const_iterator begin () const;
 134   const_iterator end   () const;
 135   //@}
 136
 137   /**
 138    * @name Reverse Iterator Accessors
 139    *
 140    * Reverse iterator accessors.
 141    */
 142   //@{
 143   reverse_iterator rbegin ();
 144   reverse_iterator rend   ();
 145   const_reverse_iterator rbegin () const;
 146   const_reverse_iterator rend   () const;
 147   //@}
 148
 149   /// Return current size of map.
 150   /**
 151    * @return The number of elements in the map.
 152    */
 153   size_type size () const;
 154
 155   /// Maximum number of elements the map can hold.
 156   size_type max_size () const;
 157
 158   /// Return @c true if the map is empty, else @c false.
 159   bool is_empty () const;  // ACE style
 160
 161   /**
 162    * Return @c true if the map is empty, else @c false.  We recommend
 163    * using @c is_empty() instead since it's more consistent with the
 164    * ACE container naming conventions.
 165    */
 166   bool empty () const;  // STL style
 167
 168   /// Swap the contents of this map with the given @a map in an
 169   /// exception-safe manner.
 170   void swap (ACE_Array_Map & map);
 171
 172   /// Insert the value @a x into the map.
 173   /**
 174    * STL-style map insertion method.
 175    *
 176    * @param x @c std::pair containing key and datum.
 177    *
 178    * @return @c std::pair::second will be @c false if the map already
 179    *         contains a value with the same key as @a x.
 180    */
 181   std::pair<iterator, bool> insert (value_type const & x);
 182
 183   /// Insert range of elements into map.
 184   template<typename InputIterator>
 185   void insert (InputIterator f, InputIterator l);
 186
 187   /// Remove element at position @a pos from the map.
 188   void erase (iterator pos);
 189
 190   /// Remove element corresponding to key @a k from the map.
 191   /**
 192    * @return Number of elements that were erased.
 193    */
 194   size_type erase (key_type const & k);
 195
 196   /// Remove range of elements [@a first, @a last) from the map.
 197   /**
 198    * @note [@a first, @a last) must be valid range within the map.
 199    */
 200   void erase (iterator first, iterator last);
 201
 202   /// Clear contents of map.
 203   /**
 204    * @note This a constant time (O(1)) operation.
 205    */
 206   void clear ();
 207
 208   /**
 209    * @name Search Operations
 210    *
 211    * Search the map for data corresponding to key @a k.
 212    */
 213   //@{
 214   /**
 215    * @return @c end() if data corresponding to key @a k is not in the
 216    *         map.
 217    */
 218   iterator find (key_type const & k);
 219
 220   /**
 221    * @return @c end() if data corresponding to key @a k is not in the
 222    *         map.
 223    */
 224   const_iterator find (key_type const & k) const;
 225   //@}
 226
 227   /// Count the number of elements corresponding to key @a k.
 228   /**
 229    * @return In the case of this map, the count will always be one if
 230    *         such exists in the map.
 231    */
 232   size_type count (key_type const & k);
 233
 234   /// Convenience array index operator.
 235   /**
 236    * Array index operator that allows insertion and retrieval of
 237    * elements using an array index syntax, such as:
 238    * @par
 239    * map["Foo"] = 12;
 240    */
 241   mapped_type & operator[] (key_type const & k);
 242
 243   allocator_type get_allocator() const { return alloc_; }
 244
 245 private:
 246   /// Increase size of underlying buffer by @a s.
 247   void grow (size_type s);
 248
 249   /// The allocator.
 250   allocator_type alloc_;
 251
 252   /// Number of elements in the map.
 253   size_type size_;
 254
 255   /// Current size of underlying array.
 256   /**
 257    * @note @c capacity_ is always greater than or equal to @c size_;
 258    */
 259   size_type capacity_;
 260
 261   /// Underlying array containing keys and data.
 262   value_type * nodes_;
 263 };
 264
 265 // --------------------------------------------------------------
 266
 267 /// @c ACE_Array_Map equality operator.
 268 template <typename Key, typename Value, class EqualTo, class Alloc>
 269 bool operator== (ACE_Array_Map<Key, Value, EqualTo, Alloc> const & lhs,
 270                  ACE_Array_Map<Key, Value, EqualTo, Alloc> const & rhs);
 271
 272 /// @c ACE_Array_Map lexicographical comparison operator.
 273 template <typename Key, typename Value, class EqualTo, class Alloc>
 274 bool operator<  (ACE_Array_Map<Key, Value, EqualTo, Alloc> const & lhs,
 275                  ACE_Array_Map<Key, Value, EqualTo, Alloc> const & rhs);
 276
 277 // --------------------------------------------------------------
 278
 279 ACE_END_VERSIONED_NAMESPACE_DECL
 280
 281 #ifdef __ACE_INLINE__
 282 # include "ace/Array_Map.inl"
 283 #endif /* __ACE_INLINE__ */
 284
 285 #include "ace/Array_Map.cpp"
 286
 287 #include /**/ "ace/post.h"
 288
 289 #endif  /* ACE_ARRAY_MAP_H */