home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _map.h < prev    next >
C/C++ Source or Header  |  2002-01-18  |  15KB  |  412 lines
  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. public:
  46.  
  47. // typedefs:
  48.  
  49.   typedef _Key                  key_type;
  50.   typedef _Tp                   data_type;
  51.   typedef _Tp                   mapped_type;
  52.   typedef pair<const _Key, _Tp> value_type;
  53.   typedef _Compare              key_compare;
  54.     
  55.   class value_compare
  56.     : public binary_function<value_type, value_type, bool> {
  57.   friend class map<_Key,_Tp,_Compare,_Alloc>;
  58.   protected :
  59.     _Compare _M_comp;
  60.     value_compare(_Compare __c) : _M_comp(__c) {}
  61.   public:
  62.     bool operator()(const value_type& __x, const value_type& __y) const {
  63.       return _M_comp(__x.first, __y.first);
  64.     }
  65.   };
  66.  
  67. private:
  68. # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG
  69.   typedef _Rb_tree<key_type, value_type, 
  70.                    _Select1st_hint<value_type, _Key>, key_compare, _Alloc> _Rep_type;
  71. # else
  72.   typedef _Rb_tree<key_type, value_type, 
  73.                    _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  74. # endif
  75.   _Rep_type _M_t;  // red-black tree representing map
  76. public:
  77.   typedef typename _Rep_type::pointer pointer;
  78.   typedef typename _Rep_type::const_pointer const_pointer;
  79.   typedef typename _Rep_type::reference reference;
  80.   typedef typename _Rep_type::const_reference const_reference;
  81.   typedef typename _Rep_type::iterator iterator;
  82.   typedef typename _Rep_type::const_iterator const_iterator;
  83.   typedef typename _Rep_type::reverse_iterator reverse_iterator;
  84.   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  85.   typedef typename _Rep_type::size_type size_type;
  86.   typedef typename _Rep_type::difference_type difference_type;
  87.   typedef typename _Rep_type::allocator_type allocator_type;
  88.  
  89.   // allocation/deallocation
  90.  
  91.   map() : _M_t(_Compare(), allocator_type()) {}
  92.   explicit map(const _Compare& __comp,
  93.                const allocator_type& __a = allocator_type())
  94.     : _M_t(__comp, __a) {}
  95.  
  96. #ifdef _STLP_MEMBER_TEMPLATES
  97.   template <class _InputIterator>
  98.   map(_InputIterator __first, _InputIterator __last)
  99.     : _M_t(_Compare(), allocator_type())
  100.     { _M_t.insert_unique(__first, __last); }
  101.  
  102.   template <class _InputIterator>
  103.   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
  104.       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
  105.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  106.  
  107. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  108.   template <class _InputIterator>
  109.   map(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
  110.     : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
  111. # endif
  112.  
  113. #else
  114.   map(const value_type* __first, const value_type* __last)
  115.     : _M_t(_Compare(), allocator_type())
  116.     { _M_t.insert_unique(__first, __last); }
  117.  
  118.   map(const value_type* __first,
  119.       const value_type* __last, const _Compare& __comp,
  120.       const allocator_type& __a = allocator_type())
  121.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  122.  
  123.   map(const_iterator __first, const_iterator __last)
  124.     : _M_t(_Compare(), allocator_type()) 
  125.     { _M_t.insert_unique(__first, __last); }
  126.  
  127.   map(const_iterator __first, const_iterator __last, const _Compare& __comp,
  128.       const allocator_type& __a = allocator_type())
  129.     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  130.  
  131. #endif /* _STLP_MEMBER_TEMPLATES */
  132.  
  133.   map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
  134.   map<_Key,_Tp,_Compare,_Alloc>&
  135.   operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
  136.   {
  137.     _M_t = __x._M_t;
  138.     return *this; 
  139.   }
  140.  
  141.   // accessors:
  142.  
  143.   key_compare key_comp() const { return _M_t.key_comp(); }
  144.   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  145.   allocator_type get_allocator() const { return _M_t.get_allocator(); }
  146.  
  147.   iterator begin() { return _M_t.begin(); }
  148.   const_iterator begin() const { return _M_t.begin(); }
  149.   iterator end() { return _M_t.end(); }
  150.   const_iterator end() const { return _M_t.end(); }
  151.   reverse_iterator rbegin() { return _M_t.rbegin(); }
  152.   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
  153.   reverse_iterator rend() { return _M_t.rend(); }
  154.   const_reverse_iterator rend() const { return _M_t.rend(); }
  155.   bool empty() const { return _M_t.empty(); }
  156.   size_type size() const { return _M_t.size(); }
  157.   size_type max_size() const { return _M_t.max_size(); }
  158.   _Tp& operator[](const key_type& __k) {
  159.     iterator __i = lower_bound(__k);
  160.     // __i->first is greater than or equivalent to __k.
  161.     if (__i == end() || key_comp()(__k, (*__i).first))
  162.       __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));
  163.     return (*__i).second;
  164.   }
  165.   void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
  166.  
  167.   // insert/erase
  168.  
  169.   pair<iterator,bool> insert(const value_type& __x) 
  170.     { return _M_t.insert_unique(__x); }
  171.   iterator insert(iterator position, const value_type& __x)
  172.     { return _M_t.insert_unique(position, __x); }
  173. #ifdef _STLP_MEMBER_TEMPLATES
  174.   template <class _InputIterator>
  175.   void insert(_InputIterator __first, _InputIterator __last) {
  176.     _M_t.insert_unique(__first, __last);
  177.   }
  178. #else
  179.   void insert(const value_type* __first, const value_type* __last) {
  180.     _M_t.insert_unique(__first, __last);
  181.   }
  182.   void insert(const_iterator __first, const_iterator __last) {
  183.     _M_t.insert_unique(__first, __last);
  184.   }
  185. #endif /* _STLP_MEMBER_TEMPLATES */
  186.  
  187.   void erase(iterator __position) { _M_t.erase(__position); }
  188.   size_type erase(const key_type& __x) { return _M_t.erase(__x); }
  189.   void erase(iterator __first, iterator __last)
  190.     { _M_t.erase(__first, __last); }
  191.   void clear() { _M_t.clear(); }
  192.  
  193.   // map operations:
  194.  
  195.   iterator find(const key_type& __x) { return _M_t.find(__x); }
  196.   const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
  197.   size_type count(const key_type& __x) const { 
  198.     return _M_t.find(__x) == _M_t.end() ? 0 : 1;
  199.   }
  200.   iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
  201.   const_iterator lower_bound(const key_type& __x) const {
  202.     return _M_t.lower_bound(__x); 
  203.   }
  204.   iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
  205.   const_iterator upper_bound(const key_type& __x) const {
  206.     return _M_t.upper_bound(__x); 
  207.   }
  208.   
  209.   pair<iterator,iterator> equal_range(const key_type& __x) {
  210.     return _M_t.equal_range(__x);
  211.   }
  212.   pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
  213.     return _M_t.equal_range(__x);
  214.   }
  215. };
  216.  
  217.  
  218. template <class _Key, class _Tp, __DFL_TMPL_PARAM(_Compare, less<_Key> ), 
  219.           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
  220. class multimap {
  221. public:
  222.  
  223. // typedefs:
  224.  
  225.   typedef _Key                  key_type;
  226.   typedef _Tp                   data_type;
  227.   typedef _Tp                   mapped_type;
  228.   typedef pair<const _Key, _Tp> value_type;
  229.   typedef _Compare              key_compare;
  230.  
  231.   class value_compare : public binary_function<value_type, value_type, bool> {
  232.   friend class multimap<_Key,_Tp,_Compare,_Alloc>;
  233.   protected:
  234.     _Compare _M_comp;
  235.     value_compare(_Compare __c) : _M_comp(__c) {}
  236.   public:
  237.     bool operator()(const value_type& __x, const value_type& __y) const {
  238.       return _M_comp(__x.first, __y.first);
  239.     }
  240.   };
  241.  
  242. private:
  243. # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG
  244.   typedef _Rb_tree<key_type, value_type, 
  245.                   _Select1st_hint<value_type, _Key>, key_compare, _Alloc> _Rep_type;
  246. # else
  247.   typedef _Rb_tree<key_type, value_type, 
  248.                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  249. # endif
  250.   _Rep_type _M_t;  // red-black tree representing multimap
  251. public:
  252.   typedef typename _Rep_type::pointer pointer;
  253.   typedef typename _Rep_type::const_pointer const_pointer;
  254.   typedef typename _Rep_type::reference reference;
  255.   typedef typename _Rep_type::const_reference const_reference;
  256.   typedef typename _Rep_type::iterator iterator;
  257.   typedef typename _Rep_type::const_iterator const_iterator; 
  258.   typedef typename _Rep_type::reverse_iterator reverse_iterator;
  259.   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  260.   typedef typename _Rep_type::size_type size_type;
  261.   typedef typename _Rep_type::difference_type difference_type;
  262.   typedef typename _Rep_type::allocator_type allocator_type;
  263.  
  264. // allocation/deallocation
  265.  
  266.   multimap() : _M_t(_Compare(), allocator_type()) { }
  267.   explicit multimap(const _Compare& __comp,
  268.                     const allocator_type& __a = allocator_type())
  269.     : _M_t(__comp, __a) { }
  270.  
  271. #ifdef _STLP_MEMBER_TEMPLATES  
  272.   template <class _InputIterator>
  273.   multimap(_InputIterator __first, _InputIterator __last)
  274.     : _M_t(_Compare(), allocator_type())
  275.     { _M_t.insert_equal(__first, __last); }
  276. # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  277.   template <class _InputIterator>
  278.   multimap(_InputIterator __first, _InputIterator __last,
  279.            const _Compare& __comp)
  280.     : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
  281. #  endif
  282.   template <class _InputIterator>
  283.   multimap(_InputIterator __first, _InputIterator __last,
  284.            const _Compare& __comp,
  285.            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
  286.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  287. #else
  288.   multimap(const value_type* __first, const value_type* __last)
  289.     : _M_t(_Compare(), allocator_type())
  290.     { _M_t.insert_equal(__first, __last); }
  291.   multimap(const value_type* __first, const value_type* __last,
  292.            const _Compare& __comp,
  293.            const allocator_type& __a = allocator_type())
  294.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  295.  
  296.   multimap(const_iterator __first, const_iterator __last)
  297.     : _M_t(_Compare(), allocator_type())
  298.     { _M_t.insert_equal(__first, __last); }
  299.   multimap(const_iterator __first, const_iterator __last,
  300.            const _Compare& __comp,
  301.            const allocator_type& __a = allocator_type())
  302.     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  303. #endif /* _STLP_MEMBER_TEMPLATES */
  304.  
  305.   multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }
  306.   multimap<_Key,_Tp,_Compare,_Alloc>&
  307.   operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
  308.     _M_t = __x._M_t;
  309.     return *this; 
  310.   }
  311.  
  312.   // accessors:
  313.  
  314.   key_compare key_comp() const { return _M_t.key_comp(); }
  315.   value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  316.   allocator_type get_allocator() const { return _M_t.get_allocator(); }
  317.  
  318.   iterator begin() { return _M_t.begin(); }
  319.   const_iterator begin() const { return _M_t.begin(); }
  320.   iterator end() { return _M_t.end(); }
  321.   const_iterator end() const { return _M_t.end(); }
  322.   reverse_iterator rbegin() { return _M_t.rbegin(); }
  323.   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
  324.   reverse_iterator rend() { return _M_t.rend(); }
  325.   const_reverse_iterator rend() const { return _M_t.rend(); }
  326.   bool empty() const { return _M_t.empty(); }
  327.   size_type size() const { return _M_t.size(); }
  328.   size_type max_size() const { return _M_t.max_size(); }
  329.   void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
  330.  
  331.   // insert/erase
  332.  
  333.   iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
  334.   iterator insert(iterator __position, const value_type& __x) {
  335.     return _M_t.insert_equal(__position, __x);
  336.   }
  337. #ifdef _STLP_MEMBER_TEMPLATES  
  338.   template <class _InputIterator>
  339.   void insert(_InputIterator __first, _InputIterator __last) {
  340.     _M_t.insert_equal(__first, __last);
  341.   }
  342. #else
  343.   void insert(const value_type* __first, const value_type* __last) {
  344.     _M_t.insert_equal(__first, __last);
  345.   }
  346.   void insert(const_iterator __first, const_iterator __last) {
  347.     _M_t.insert_equal(__first, __last);
  348.   }
  349. #endif /* _STLP_MEMBER_TEMPLATES */
  350.   void erase(iterator __position) { _M_t.erase(__position); }
  351.   size_type erase(const key_type& __x) { return _M_t.erase(__x); }
  352.   void erase(iterator __first, iterator __last)
  353.     { _M_t.erase(__first, __last); }
  354.   void clear() { _M_t.clear(); }
  355.  
  356.   // multimap operations:
  357.  
  358.   iterator find(const key_type& __x) { return _M_t.find(__x); }
  359.   const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
  360.   size_type count(const key_type& __x) const { return _M_t.count(__x); }
  361.   iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
  362.   const_iterator lower_bound(const key_type& __x) const {
  363.     return _M_t.lower_bound(__x); 
  364.   }
  365.   iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
  366.   const_iterator upper_bound(const key_type& __x) const {
  367.     return _M_t.upper_bound(__x); 
  368.   }
  369.    pair<iterator,iterator> equal_range(const key_type& __x) {
  370.     return _M_t.equal_range(__x);
  371.   }
  372.   pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
  373.     return _M_t.equal_range(__x);
  374.   }
  375. };
  376.  
  377. # define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
  378.  
  379. # define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
  380.  
  381. // fbp : if this template header gets protected against your will, report it !
  382. # include <stl/_relops_cont.h>
  383.  
  384. # undef  _STLP_TEMPLATE_CONTAINER
  385. # define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
  386.  
  387. // fbp : if this template header gets protected against your will, report it !
  388. # include <stl/_relops_cont.h>
  389.  
  390. # undef  _STLP_TEMPLATE_CONTAINER
  391. # undef  _STLP_TEMPLATE_HEADER
  392.  
  393. _STLP_END_NAMESPACE
  394.  
  395. // do a cleanup
  396. #  undef map
  397. #  undef multimap
  398. // provide a way to access full funclionality 
  399. # define __map__  __FULL_NAME(map)
  400. # define __multimap__  __FULL_NAME(multimap)
  401.  
  402. # ifdef _STLP_USE_WRAPPER_FOR_ALLOC_PARAM
  403. # include <stl/wrappers/_map.h>
  404. # endif
  405.  
  406. #endif /* _STLP_INTERNAL_MAP_H */
  407.  
  408. // Local Variables:
  409. // mode:C++
  410. // End:
  411.  
  412.