dep/ACE_wrappers/ace/Array_Map.h

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