1 _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 #define map __WORKAROUND_RENAME(map)

    38 #define multimap __WORKAROUND_RENAME(multimap)

    39 

    40 _STLP_BEGIN_NAMESPACE

    41 

    42 template <class _Key, class _Tp, __DFL_TMPL_PARAM(_Compare, less<_Key> ), 

    43           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >

    44 class map 

    45 {

    46 public:

    47 

    48 // typedefs:

    49 

    50   typedef _Key                  key_type;

    51   typedef _Tp                   data_type;

    52   typedef _Tp                   mapped_type;

    53   typedef pair<const _Key, _Tp> value_type;

    54   typedef _Compare              key_compare;

    55     

    56   class value_compare

    57     : public binary_function<value_type, value_type, bool> {

    58   friend class map<_Key,_Tp,_Compare,_Alloc>;

    59   protected :

    60     _Compare _M_comp;

    61     value_compare(_Compare __c) : _M_comp(__c) {}

    62   public:

    63     bool operator()(const value_type& __x, const value_type& __y) const {

    64       return _M_comp(__x.first, __y.first);

    65     }

    66   };

    67 

    68 private:

    69 # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG

    70   typedef _Rb_tree<key_type, value_type, 

    71                    _Select1st_hint<value_type, _Key>, key_compare, _Alloc> _Rep_type;

    72 # else

    73   typedef _Rb_tree<key_type, value_type, 

    74                    _Select1st<value_type>, key_compare, _Alloc> _Rep_type;

    75 # endif

    76   _Rep_type _M_t;  // red-black tree representing map

    77 public:

    78   typedef typename _Rep_type::pointer pointer;

    79   typedef typename _Rep_type::const_pointer const_pointer;

    80   typedef typename _Rep_type::reference reference;

    81   typedef typename _Rep_type::const_reference const_reference;

    82   typedef typename _Rep_type::iterator iterator;

    83   typedef typename _Rep_type::const_iterator const_iterator;

    84   typedef typename _Rep_type::reverse_iterator reverse_iterator;

    85   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

    86   typedef typename _Rep_type::size_type size_type;

    87   typedef typename _Rep_type::difference_type difference_type;

    88   typedef typename _Rep_type::allocator_type allocator_type;

    89   typedef map<_Key,_Tp,_Compare,_Alloc> _Self;

    90 

    91   // allocation/deallocation

    92 

    93   map() : _M_t(_Compare(), allocator_type()) {

    94     _STLP_POP_IF_CHECK

    95   }

    96 

    97   explicit map(const _Compare& __comp,

    98                const allocator_type& __a = allocator_type())

    99     : _M_t(__comp, __a) {

   100     _STLP_POP_IF_CHECK

   101   }

   102 

   103 #ifdef _STLP_MEMBER_TEMPLATES

   104   template <class _InputIterator>

   105   map(_InputIterator __first, _InputIterator __last)

   106     : _M_t(_Compare(), allocator_type())

   107     { 

   108       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   109       _M_t.insert_unique(__first, __last);

   110       _STLP_POP_CLEANUP_ITEM

   111     }

   112 

   113   template <class _InputIterator>

   114   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,

   115       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)

   116     : _M_t(__comp, __a) {

   117     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   118     _M_t.insert_unique(__first, __last); 

   119     _STLP_POP_CLEANUP_ITEM

   120   }

   121 

   122 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS

   123   template <class _InputIterator>

   124   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp)

   125     : _M_t(__comp, allocator_type()) 

   126   { _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   127     _M_t.insert_unique(__first, __last);

   128     _STLP_POP_CLEANUP_ITEM

   129   }

   130 # endif

   131 

   132 #else

   133   map(const value_type* __first, const value_type* __last)

   134     : _M_t(_Compare(), allocator_type())

   135     { _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   136       _M_t.insert_unique(__first, __last); 

   137       _STLP_POP_CLEANUP_ITEM

   138     }

   139 

   140   map(const value_type* __first,

   141       const value_type* __last, const _Compare& __comp,

   142       const allocator_type& __a = allocator_type())

   143     : _M_t(__comp, __a) { 

   144     _STLP_PUSH_CLEANUP_ITEM(_Self, this) 

   145     _M_t.insert_unique(__first, __last); 

   146     _STLP_POP_CLEANUP_ITEM

   147   }

   148 

   149   map(const_iterator __first, const_iterator __last)

   150     : _M_t(_Compare(), allocator_type()) 

   151   {

   152     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   153     _M_t.insert_unique(__first, __last);

   154     _STLP_POP_CLEANUP_ITEM

   155   }

   156 

   157   map(const_iterator __first, const_iterator __last, const _Compare& __comp,

   158       const allocator_type& __a = allocator_type())

   159     : _M_t(__comp, __a) {

   160     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   161     _M_t.insert_unique(__first, __last); 

   162     _STLP_POP_CLEANUP_ITEM

   163   }

   164 

   165 #endif /* _STLP_MEMBER_TEMPLATES */

   166 

   167 # ifdef _STLP_USE_TRAP_LEAVE

   168   map(const map<_Key,_Tp,_Compare,_Alloc>& __x)

   169   {

   170     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   171     _M_t =__x._M_t; 

   172     _STLP_POP_CLEANUP_ITEM

   173   }

   174 #else

   175   map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : 

   176     _M_t(__x._M_t) {

   177     _STLP_POP_IF_CHECK

   178   }

   179 # endif

   180   map<_Key,_Tp,_Compare,_Alloc>&

   181   operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)

   182   {

   183     _M_t = __x._M_t;

   184     return *this; 

   185   }

   186 

   187 #ifdef _STLP_USE_TRAP_LEAVE

   188 public:

   189   static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   190   static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   191 #endif

   192 

   193   // accessors:

   194 

   195   key_compare key_comp() const { return _M_t.key_comp(); }

   196   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }

   197   allocator_type get_allocator() const { return _M_t.get_allocator(); }

   198 

   199   iterator begin() { return _M_t.begin(); }

   200   const_iterator begin() const { return _M_t.begin(); }

   201   iterator end() { return _M_t.end(); }

   202   const_iterator end() const { return _M_t.end(); }

   203   reverse_iterator rbegin() { return _M_t.rbegin(); }

   204   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }

   205   reverse_iterator rend() { return _M_t.rend(); }

   206   const_reverse_iterator rend() const { return _M_t.rend(); }

   207   bool empty() const { return _M_t.empty(); }

   208   size_type size() const { return _M_t.size(); }

   209   size_type max_size() const { return _M_t.max_size(); }

   210   _Tp& operator[](const key_type& __k) {

   211     iterator __i = lower_bound(__k);

   212     // __i->first is greater than or equivalent to __k.

   213     if (__i == end() || key_comp()(__k, (*__i).first)) {

   214 # ifdef _STLP_USE_TRAP_LEAVE      

   215       value_type __tmp(__k, __false_type());

   216        _STLP_PUSH_STACK_ITEM(value_type, &__tmp)

   217       __i = insert(__i, __tmp);

   218       

   219 # else

   220       __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));

   221 # endif

   222     }

   223     return (*__i).second;

   224   }

   225   void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }

   226 

   227   // insert/erase

   228 

   229   pair<iterator,bool> insert(const value_type& __x) 

   230     { return _M_t.insert_unique(__x); }

   231   iterator insert(iterator position, const value_type& __x)

   232     { return _M_t.insert_unique(position, __x); }

   233 #ifdef _STLP_MEMBER_TEMPLATES

   234   template <class _InputIterator>

   235   void insert(_InputIterator __first, _InputIterator __last) {

   236     _M_t.insert_unique(__first, __last);

   237   }

   238 #else

   239   void insert(const value_type* __first, const value_type* __last) {

   240     _M_t.insert_unique(__first, __last);

   241   }

   242   void insert(const_iterator __first, const_iterator __last) {

   243     _M_t.insert_unique(__first, __last);

   244   }

   245 #endif /* _STLP_MEMBER_TEMPLATES */

   246 

   247   void erase(iterator __position) { _M_t.erase(__position); }

   248   size_type erase(const key_type& __x) { return _M_t.erase(__x); }

   249   void erase(iterator __first, iterator __last)

   250     { _M_t.erase(__first, __last); }

   251   void clear() { _M_t.clear(); }

   252 

   253   // map operations:

   254 

   255   iterator find(const key_type& __x) { return _M_t.find(__x); }

   256   const_iterator find(const key_type& __x) const { return _M_t.find(__x); }

   257   size_type count(const key_type& __x) const { 

   258     return _M_t.find(__x) == _M_t.end() ? 0 : 1;

   259   }

   260   iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }

   261   const_iterator lower_bound(const key_type& __x) const {

   262     return _M_t.lower_bound(__x); 

   263   }

   264   iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }

   265   const_iterator upper_bound(const key_type& __x) const {

   266     return _M_t.upper_bound(__x); 

   267   }

   268   

   269   pair<iterator,iterator> equal_range(const key_type& __x) {

   270     return _M_t.equal_range(__x);

   271   }

   272   pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {

   273     return _M_t.equal_range(__x);

   274   }

   275 };

   276 

   277 

   278 template <class _Key, class _Tp, __DFL_TMPL_PARAM(_Compare, less<_Key> ), 

   279           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >

   280 class multimap 

   281 {

   282 public:

   283 

   284 // typedefs:

   285 

   286   typedef _Key                  key_type;

   287   typedef _Tp                   data_type;

   288   typedef _Tp                   mapped_type;

   289   typedef pair<const _Key, _Tp> value_type;

   290   typedef _Compare              key_compare;

   291 

   292   class value_compare : public binary_function<value_type, value_type, bool> {

   293   friend class multimap<_Key,_Tp,_Compare,_Alloc>;

   294   protected:

   295     _Compare _M_comp;

   296     value_compare(_Compare __c) : _M_comp(__c) {}

   297   public:

   298     bool operator()(const value_type& __x, const value_type& __y) const {

   299       return _M_comp(__x.first, __y.first);

   300     }

   301   };

   302 

   303 private:

   304 # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG

   305   typedef _Rb_tree<key_type, value_type, 

   306                   _Select1st_hint<value_type, _Key>, key_compare, _Alloc> _Rep_type;

   307 # else

   308   typedef _Rb_tree<key_type, value_type, 

   309                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;

   310 # endif

   311   _Rep_type _M_t;  // red-black tree representing multimap

   312 public:

   313   typedef typename _Rep_type::pointer pointer;

   314   typedef typename _Rep_type::const_pointer const_pointer;

   315   typedef typename _Rep_type::reference reference;

   316   typedef typename _Rep_type::const_reference const_reference;

   317   typedef typename _Rep_type::iterator iterator;

   318   typedef typename _Rep_type::const_iterator const_iterator; 

   319   typedef typename _Rep_type::reverse_iterator reverse_iterator;

   320   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

   321   typedef typename _Rep_type::size_type size_type;

   322   typedef typename _Rep_type::difference_type difference_type;

   323   typedef typename _Rep_type::allocator_type allocator_type;

   324   typedef multimap<_Key,_Tp,_Compare,_Alloc> _Self;

   325 

   326 // allocation/deallocation

   327 

   328   multimap() : _M_t(_Compare(), allocator_type()) {

   329     _STLP_POP_IF_CHECK

   330   }

   331 

   332   explicit multimap(const _Compare& __comp,

   333                     const allocator_type& __a = allocator_type())

   334     : _M_t(__comp, __a) { 

   335     _STLP_POP_IF_CHECK

   336   }

   337 

   338 #ifdef _STLP_MEMBER_TEMPLATES  

   339   template <class _InputIterator>

   340   multimap(_InputIterator __first, _InputIterator __last)

   341     : _M_t(_Compare(), allocator_type())

   342     { 

   343       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   344       _M_t.insert_equal(__first, __last); 

   345       _STLP_POP_CLEANUP_ITEM

   346     }

   347 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS

   348   template <class _InputIterator>

   349   multimap(_InputIterator __first, _InputIterator __last,

   350            const _Compare& __comp)

   351     : _M_t(__comp, allocator_type()) { 

   352     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   353     _M_t.insert_equal(__first, __last); 

   354     _STLP_POP_CLEANUP_ITEM

   355   }

   356 #  endif

   357   template <class _InputIterator>

   358   multimap(_InputIterator __first, _InputIterator __last,

   359            const _Compare& __comp,

   360            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)

   361     : _M_t(__comp, __a) { 

   362     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   363     _M_t.insert_equal(__first, __last); 

   364     _STLP_POP_CLEANUP_ITEM

   365   }

   366 #else

   367   multimap(const value_type* __first, const value_type* __last)

   368     : _M_t(_Compare(), allocator_type())

   369     { 

   370       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   371       _M_t.insert_equal(__first, __last); 

   372       _STLP_POP_CLEANUP_ITEM

   373     }

   374   multimap(const value_type* __first, const value_type* __last,

   375            const _Compare& __comp,

   376            const allocator_type& __a = allocator_type())

   377     : _M_t(__comp, __a) { 

   378     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   379       _M_t.insert_equal(__first, __last); 

   380     _STLP_POP_CLEANUP_ITEM

   381       }

   382 

   383   multimap(const_iterator __first, const_iterator __last)

   384     : _M_t(_Compare(), allocator_type())

   385     { 

   386       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   387       _M_t.insert_equal(__first, __last); 

   388       _STLP_POP_CLEANUP_ITEM

   389     }

   390   multimap(const_iterator __first, const_iterator __last,

   391            const _Compare& __comp,

   392            const allocator_type& __a = allocator_type())

   393     : _M_t(__comp, __a) { 

   394     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   395       _M_t.insert_equal(__first, __last); 

   396     _STLP_POP_CLEANUP_ITEM

   397 

   398   }

   399 #endif /* _STLP_MEMBER_TEMPLATES */

   400 

   401 

   402 # ifdef _STLP_USE_TRAP_LEAVE

   403   multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x)

   404   {

   405     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   406     _M_t =__x._M_t; 

   407     _STLP_POP_CLEANUP_ITEM

   408   }

   409 # else

   410   multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { 

   411 }

   412 # endif

   413   multimap<_Key,_Tp,_Compare,_Alloc>&

   414   operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {

   415     _M_t = __x._M_t;

   416     return *this; 

   417   }

   418 

   419 #ifdef _STLP_USE_TRAP_LEAVE

   420 public:

   421   static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   422   static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   423 #endif

   424 

   425   // accessors:

   426 

   427   key_compare key_comp() const { return _M_t.key_comp(); }

   428   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }

   429   allocator_type get_allocator() const { return _M_t.get_allocator(); }

   430 

   431   iterator begin() { return _M_t.begin(); }

   432   const_iterator begin() const { return _M_t.begin(); }

   433   iterator end() { return _M_t.end(); }

   434   const_iterator end() const { return _M_t.end(); }

   435   reverse_iterator rbegin() { return _M_t.rbegin(); }

   436   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }

   437   reverse_iterator rend() { return _M_t.rend(); }

   438   const_reverse_iterator rend() const { return _M_t.rend(); }

   439   bool empty() const { return _M_t.empty(); }

   440   size_type size() const { return _M_t.size(); }

   441   size_type max_size() const { return _M_t.max_size(); }

   442   void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }

   443 

   444   // insert/erase

   445 

   446   iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }

   447   iterator insert(iterator __position, const value_type& __x) {

   448     return _M_t.insert_equal(__position, __x);

   449   }

   450 #ifdef _STLP_MEMBER_TEMPLATES  

   451   template <class _InputIterator>

   452   void insert(_InputIterator __first, _InputIterator __last) {

   453     _M_t.insert_equal(__first, __last);

   454   }

   455 #else

   456   void insert(const value_type* __first, const value_type* __last) {

   457     _M_t.insert_equal(__first, __last);

   458   }

   459   void insert(const_iterator __first, const_iterator __last) {

   460     _M_t.insert_equal(__first, __last);

   461   }

   462 #endif /* _STLP_MEMBER_TEMPLATES */

   463   void erase(iterator __position) { _M_t.erase(__position); }

   464   size_type erase(const key_type& __x) { return _M_t.erase(__x); }

   465   void erase(iterator __first, iterator __last)

   466     { _M_t.erase(__first, __last); }

   467   void clear() { _M_t.clear(); }

   468 

   469   // multimap operations:

   470 

   471   iterator find(const key_type& __x) { return _M_t.find(__x); }

   472   const_iterator find(const key_type& __x) const { return _M_t.find(__x); }

   473   size_type count(const key_type& __x) const { return _M_t.count(__x); }

   474   iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }

   475   const_iterator lower_bound(const key_type& __x) const {

   476     return _M_t.lower_bound(__x); 

   477   }

   478   iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }

   479   const_iterator upper_bound(const key_type& __x) const {

   480     return _M_t.upper_bound(__x); 

   481   }

   482    pair<iterator,iterator> equal_range(const key_type& __x) {

   483     return _M_t.equal_range(__x);

   484   }

   485   pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {

   486     return _M_t.equal_range(__x);

   487   }

   488 };

   489 

   490 # define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>

   491 

   492 # define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>

   493 

   494 // fbp : if this template header gets protected against your will, report it !

   495 # include <stl/_relops_cont.h>

   496 

   497 # undef  _STLP_TEMPLATE_CONTAINER

   498 # define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>

   499 

   500 // fbp : if this template header gets protected against your will, report it !

   501 # include <stl/_relops_cont.h>

   502 

   503 # undef  _STLP_TEMPLATE_CONTAINER

   504 # undef  _STLP_TEMPLATE_HEADER

   505 

   506 _STLP_END_NAMESPACE

   507 

   508 // do a cleanup

   509 #  undef map

   510 #  undef multimap

   511 // provide a way to access full funclionality 

   512 # define __map__  __FULL_NAME(map)

   513 # define __multimap__  __FULL_NAME(multimap)

   514 

   515 # ifdef _STLP_USE_WRAPPER_FOR_ALLOC_PARAM

   516 # include <stl/wrappers/_map.h>

   517 # endif

   518 

   519 #endif /* _STLP_INTERNAL_MAP_H */

   520 

   521 // Local Variables:

   522 // mode:C++

   523 // End:

   524