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