lib/3rdparty/stlport/stlport/stl/_map.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_MAP_H
  31 #define _STLP_INTERNAL_MAP_H
  32
  33 #ifndef _STLP_INTERNAL_TREE_H
  34 #  include <stl/_tree.h>
  35 #endif
  36
  37 _STLP_BEGIN_NAMESPACE
  38
  39 //Specific iterator traits creation
  40 _STLP_CREATE_ITERATOR_TRAITS(MapTraitsT, traits)
  41
  42 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
  43           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
  44 class map
  45 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  46           : public __stlport_class<map<_Key, _Tp, _Compare, _Alloc> >
  47 #endif
  48 {
  49   typedef map<_Key, _Tp, _Compare, _Alloc> _Self;
  50 public:
  51
  52 // typedefs:
  53
  54   typedef _Key                  key_type;
  55   typedef _Tp                   data_type;
  56   typedef _Tp                   mapped_type;
  57   typedef pair<_STLP_CONST _Key, _Tp> value_type;
  58   typedef _Compare              key_compare;
  59
  60   class value_compare
  61     : public binary_function<value_type, value_type, bool> {
  62   friend class map<_Key,_Tp,_Compare,_Alloc>;
  63   protected :
  64     //c is a Standard name (23.3.1), do no make it STLport naming convention compliant.
  65     _Compare comp;
  66     value_compare(_Compare __c) : comp(__c) {}
  67   public:
  68     bool operator()(const value_type& __x, const value_type& __y) const
  69     { return comp(__x.first, __y.first); }
  70   };
  71
  72 protected:
  73   typedef _STLP_PRIV _MapTraitsT<value_type> _MapTraits;
  74
  75 public:
  76   //Following typedef have to be public for __move_traits specialization.
  77   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
  78                               value_type, _STLP_SELECT1ST(value_type, _Key),
  79                               _MapTraits, _Alloc> _Rep_type;
  80
  81   typedef typename _Rep_type::pointer pointer;
  82   typedef typename _Rep_type::const_pointer const_pointer;
  83   typedef typename _Rep_type::reference reference;
  84   typedef typename _Rep_type::const_reference const_reference;
  85   typedef typename _Rep_type::iterator iterator;
  86   typedef typename _Rep_type::const_iterator const_iterator;
  87   typedef typename _Rep_type::reverse_iterator reverse_iterator;
  88   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  89   typedef typename _Rep_type::size_type size_type;
  90   typedef typename _Rep_type::difference_type difference_type;
  91   typedef typename _Rep_type::allocator_type allocator_type;
  92
  93 private:
  94   _Rep_type _M_t;  // red-black tree representing map
  95   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  96
  97 public:
  98   // allocation/deallocation
  99   map() : _M_t(_Compare(), allocator_type()) {}
 100 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 101   explicit map(const _Compare& __comp,
 102                const allocator_type& __a = allocator_type())
 103 #else
 104   explicit map(const _Compare& __comp)
 105     : _M_t(__comp, allocator_type()) {}
 106   explicit map(const _Compare& __comp, const allocator_type& __a)
 107 #endif
 108     : _M_t(__comp, __a) {}
 109
 110 #if defined (_STLP_MEMBER_TEMPLATES)
 111   template <class _InputIterator>
 112   map(_InputIterator __first, _InputIterator __last)
 113     : _M_t(_Compare(), allocator_type())
 114     { _M_t.insert_unique(__first, __last); }
 115
 116   template <class _InputIterator>
 117   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
 118       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 119     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 120
 121 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 122   template <class _InputIterator>
 123   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
 124     : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
 125 #  endif
 126
 127 #else
 128   map(const value_type* __first, const value_type* __last)
 129     : _M_t(_Compare(), allocator_type())
 130     { _M_t.insert_unique(__first, __last); }
 131
 132   map(const value_type* __first,
 133       const value_type* __last, const _Compare& __comp,
 134       const allocator_type& __a = allocator_type())
 135     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 136
 137   map(const_iterator __first, const_iterator __last)
 138     : _M_t(_Compare(), allocator_type())
 139     { _M_t.insert_unique(__first, __last); }
 140
 141   map(const_iterator __first, const_iterator __last, const _Compare& __comp,
 142       const allocator_type& __a = allocator_type())
 143     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 144 #endif /* _STLP_MEMBER_TEMPLATES */
 145
 146   map(const _Self& __x) : _M_t(__x._M_t) {}
 147
 148 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 149   map(__move_source<_Self> src)
 150     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 151 #endif
 152
 153   _Self& operator=(const _Self& __x) {
 154     _M_t = __x._M_t;
 155     return *this;
 156   }
 157
 158   // accessors:
 159   key_compare key_comp() const { return _M_t.key_comp(); }
 160   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
 161   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 162
 163   iterator begin() { return _M_t.begin(); }
 164   const_iterator begin() const { return _M_t.begin(); }
 165   iterator end() { return _M_t.end(); }
 166   const_iterator end() const { return _M_t.end(); }
 167   reverse_iterator rbegin() { return _M_t.rbegin(); }
 168   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 169   reverse_iterator rend() { return _M_t.rend(); }
 170   const_reverse_iterator rend() const { return _M_t.rend(); }
 171   bool empty() const { return _M_t.empty(); }
 172   size_type size() const { return _M_t.size(); }
 173   size_type max_size() const { return _M_t.max_size(); }
 174   _STLP_TEMPLATE_FOR_CONT_EXT
 175   _Tp& operator[](const _KT& __k) {
 176     iterator __i = lower_bound(__k);
 177     // __i->first is greater than or equivalent to __k.
 178     if (__i == end() || key_comp()(__k, (*__i).first))
 179       __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));
 180     return (*__i).second;
 181   }
 182   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 183 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 184   void _M_swap_workaround(_Self& __x) { swap(__x); }
 185 #endif
 186
 187   // insert/erase
 188   pair<iterator,bool> insert(const value_type& __x)
 189   { return _M_t.insert_unique(__x); }
 190   iterator insert(iterator __pos, const value_type& __x)
 191   { return _M_t.insert_unique(__pos, __x); }
 192 #ifdef _STLP_MEMBER_TEMPLATES
 193   template <class _InputIterator>
 194   void insert(_InputIterator __first, _InputIterator __last)
 195   { _M_t.insert_unique(__first, __last); }
 196 #else
 197   void insert(const value_type* __first, const value_type* __last)
 198   { _M_t.insert_unique(__first, __last); }
 199   void insert(const_iterator __first, const_iterator __last)
 200   { _M_t.insert_unique(__first, __last); }
 201 #endif /* _STLP_MEMBER_TEMPLATES */
 202
 203   void erase(iterator __pos) { _M_t.erase(__pos); }
 204   size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
 205   void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
 206   void clear() { _M_t.clear(); }
 207
 208   // map operations:
 209   _STLP_TEMPLATE_FOR_CONT_EXT
 210   iterator find(const _KT& __x) { return _M_t.find(__x); }
 211   _STLP_TEMPLATE_FOR_CONT_EXT
 212   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 213   _STLP_TEMPLATE_FOR_CONT_EXT
 214   size_type count(const _KT& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
 215   _STLP_TEMPLATE_FOR_CONT_EXT
 216   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 217   _STLP_TEMPLATE_FOR_CONT_EXT
 218   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 219   _STLP_TEMPLATE_FOR_CONT_EXT
 220   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 221   _STLP_TEMPLATE_FOR_CONT_EXT
 222   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 223
 224   _STLP_TEMPLATE_FOR_CONT_EXT
 225   pair<iterator,iterator> equal_range(const _KT& __x)
 226   { return _M_t.equal_range_unique(__x); }
 227   _STLP_TEMPLATE_FOR_CONT_EXT
 228   pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
 229   { return _M_t.equal_range_unique(__x); }
 230 };
 231
 232 //Specific iterator traits creation
 233 _STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits)
 234
 235 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
 236           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
 237 class multimap
 238 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 239                : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> >
 240 #endif
 241 {
 242   typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self;
 243 public:
 244
 245 // typedefs:
 246
 247   typedef _Key                  key_type;
 248   typedef _Tp                   data_type;
 249   typedef _Tp                   mapped_type;
 250   typedef pair<_STLP_CONST _Key, _Tp> value_type;
 251   typedef _Compare              key_compare;
 252
 253   class value_compare : public binary_function<value_type, value_type, bool> {
 254     friend class multimap<_Key,_Tp,_Compare,_Alloc>;
 255   protected:
 256     //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant.
 257     _Compare comp;
 258     value_compare(_Compare __c) : comp(__c) {}
 259   public:
 260     bool operator()(const value_type& __x, const value_type& __y) const
 261     { return comp(__x.first, __y.first); }
 262   };
 263
 264 protected:
 265   //Specific iterator traits creation
 266   typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits;
 267
 268 public:
 269   //Following typedef have to be public for __move_traits specialization.
 270   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
 271                               value_type, _STLP_SELECT1ST(value_type, _Key),
 272                               _MultimapTraits, _Alloc> _Rep_type;
 273
 274   typedef typename _Rep_type::pointer pointer;
 275   typedef typename _Rep_type::const_pointer const_pointer;
 276   typedef typename _Rep_type::reference reference;
 277   typedef typename _Rep_type::const_reference const_reference;
 278   typedef typename _Rep_type::iterator iterator;
 279   typedef typename _Rep_type::const_iterator const_iterator;
 280   typedef typename _Rep_type::reverse_iterator reverse_iterator;
 281   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
 282   typedef typename _Rep_type::size_type size_type;
 283   typedef typename _Rep_type::difference_type difference_type;
 284   typedef typename _Rep_type::allocator_type allocator_type;
 285
 286 private:
 287   _Rep_type _M_t;  // red-black tree representing multimap
 288   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 289
 290 public:
 291   // allocation/deallocation
 292   multimap() : _M_t(_Compare(), allocator_type()) { }
 293   explicit multimap(const _Compare& __comp,
 294                     const allocator_type& __a = allocator_type())
 295     : _M_t(__comp, __a) { }
 296
 297 #ifdef _STLP_MEMBER_TEMPLATES
 298   template <class _InputIterator>
 299   multimap(_InputIterator __first, _InputIterator __last)
 300     : _M_t(_Compare(), allocator_type())
 301     { _M_t.insert_equal(__first, __last); }
 302 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
 303   template <class _InputIterator>
 304   multimap(_InputIterator __first, _InputIterator __last,
 305            const _Compare& __comp)
 306     : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
 307 #  endif
 308   template <class _InputIterator>
 309   multimap(_InputIterator __first, _InputIterator __last,
 310            const _Compare& __comp,
 311            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 312     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 313 #else
 314   multimap(const value_type* __first, const value_type* __last)
 315     : _M_t(_Compare(), allocator_type())
 316     { _M_t.insert_equal(__first, __last); }
 317   multimap(const value_type* __first, const value_type* __last,
 318            const _Compare& __comp,
 319            const allocator_type& __a = allocator_type())
 320     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 321
 322   multimap(const_iterator __first, const_iterator __last)
 323     : _M_t(_Compare(), allocator_type())
 324     { _M_t.insert_equal(__first, __last); }
 325   multimap(const_iterator __first, const_iterator __last,
 326            const _Compare& __comp,
 327            const allocator_type& __a = allocator_type())
 328     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 329 #endif /* _STLP_MEMBER_TEMPLATES */
 330
 331   multimap(const _Self& __x) : _M_t(__x._M_t) {}
 332
 333 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 334   multimap(__move_source<_Self> src)
 335     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 336 #endif
 337
 338   _Self& operator=(const _Self& __x) {
 339     _M_t = __x._M_t;
 340     return *this;
 341   }
 342
 343   // accessors:
 344
 345   key_compare key_comp() const { return _M_t.key_comp(); }
 346   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
 347   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 348
 349   iterator begin() { return _M_t.begin(); }
 350   const_iterator begin() const { return _M_t.begin(); }
 351   iterator end() { return _M_t.end(); }
 352   const_iterator end() const { return _M_t.end(); }
 353   reverse_iterator rbegin() { return _M_t.rbegin(); }
 354   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 355   reverse_iterator rend() { return _M_t.rend(); }
 356   const_reverse_iterator rend() const { return _M_t.rend(); }
 357   bool empty() const { return _M_t.empty(); }
 358   size_type size() const { return _M_t.size(); }
 359   size_type max_size() const { return _M_t.max_size(); }
 360   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 361 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
 362   void _M_swap_workaround(_Self& __x) { swap(__x); }
 363 #endif
 364
 365   // insert/erase
 366   iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
 367   iterator insert(iterator __pos, const value_type& __x) { return _M_t.insert_equal(__pos, __x); }
 368 #if defined (_STLP_MEMBER_TEMPLATES)
 369   template <class _InputIterator>
 370   void insert(_InputIterator __first, _InputIterator __last)
 371   { _M_t.insert_equal(__first, __last); }
 372 #else
 373   void insert(const value_type* __first, const value_type* __last)
 374   { _M_t.insert_equal(__first, __last); }
 375   void insert(const_iterator __first, const_iterator __last)
 376   { _M_t.insert_equal(__first, __last); }
 377 #endif /* _STLP_MEMBER_TEMPLATES */
 378   void erase(iterator __pos) { _M_t.erase(__pos); }
 379   size_type erase(const key_type& __x) { return _M_t.erase(__x); }
 380   void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
 381   void clear() { _M_t.clear(); }
 382
 383   // multimap operations:
 384
 385   _STLP_TEMPLATE_FOR_CONT_EXT
 386   iterator find(const _KT& __x) { return _M_t.find(__x); }
 387   _STLP_TEMPLATE_FOR_CONT_EXT
 388   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 389   _STLP_TEMPLATE_FOR_CONT_EXT
 390   size_type count(const _KT& __x) const { return _M_t.count(__x); }
 391   _STLP_TEMPLATE_FOR_CONT_EXT
 392   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 393   _STLP_TEMPLATE_FOR_CONT_EXT
 394   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 395   _STLP_TEMPLATE_FOR_CONT_EXT
 396   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 397   _STLP_TEMPLATE_FOR_CONT_EXT
 398   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 399   _STLP_TEMPLATE_FOR_CONT_EXT
 400   pair<iterator,iterator> equal_range(const _KT& __x)
 401   { return _M_t.equal_range(__x); }
 402   _STLP_TEMPLATE_FOR_CONT_EXT
 403   pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
 404   { return _M_t.equal_range(__x); }
 405 };
 406
 407 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
 408 #define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
 409 #include <stl/_relops_cont.h>
 410 #undef  _STLP_TEMPLATE_CONTAINER
 411 #define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
 412 #include <stl/_relops_cont.h>
 413 #undef  _STLP_TEMPLATE_CONTAINER
 414 #undef  _STLP_TEMPLATE_HEADER
 415
 416 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
 417 template <class _Key, class _Tp, class _Compare, class _Alloc>
 418 struct __move_traits<map<_Key,_Tp,_Compare,_Alloc> > :
 419   _STLP_PRIV __move_traits_aux<typename map<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
 420 {};
 421
 422 template <class _Key, class _Tp, class _Compare, class _Alloc>
 423 struct __move_traits<multimap<_Key,_Tp,_Compare,_Alloc> > :
 424   _STLP_PRIV __move_traits_aux<typename multimap<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
 425 {};
 426 #endif
 427
 428 _STLP_END_NAMESPACE
 429
 430 #endif /* _STLP_INTERNAL_MAP_H */
 431
 432 // Local Variables:
 433 // mode:C++
 434 // End:
 435