home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / map.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  5KB  |  151 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef MAP_H
  17. #define MAP_H
  18.  
  19. #ifndef Allocator
  20. #define Allocator allocator
  21. #include <defalloc.h>
  22. #endif
  23.  
  24. #include <tree.h>
  25.  
  26. template <class Key, class T, class Compare>
  27. class map {
  28. public:
  29.  
  30. // typedefs:
  31.  
  32.     typedef Key key_type;
  33.     typedef pair<const Key, T> value_type;
  34.     typedef Compare key_compare;
  35.     
  36.     class value_compare
  37.         : public binary_function<value_type, value_type, bool> {
  38.     friend class map<Key, T, Compare>;
  39.     protected :
  40.         Compare comp;
  41.         value_compare(Compare c) : comp(c) {}
  42.     public:
  43.         bool operator()(const value_type& x, const value_type& y) const {
  44.             return comp(x.first, y.first);
  45.         }
  46.     };
  47.  
  48. private:
  49.     typedef rb_tree<key_type, value_type, 
  50.                     select1st<value_type, key_type>, key_compare> rep_type;
  51.     rep_type t;  // red-black tree representing map
  52. public:
  53.     typedef rep_type::pointer pointer;
  54.     typedef rep_type::reference reference;
  55.     typedef rep_type::const_reference const_reference;
  56.     typedef rep_type::iterator iterator;
  57.     typedef rep_type::const_iterator const_iterator;
  58.     typedef rep_type::reverse_iterator reverse_iterator;
  59.     typedef rep_type::const_reverse_iterator const_reverse_iterator;
  60.     typedef rep_type::size_type size_type;
  61.     typedef rep_type::difference_type difference_type;
  62.  
  63. // allocation/deallocation
  64.  
  65.     map(const Compare& comp = Compare()) : t(comp, false) {}
  66.     map(const value_type* first, const value_type* last, 
  67.         const Compare& comp = Compare()) : t(first, last, comp, false) {}
  68.     map(const map<Key, T, Compare>& x) : t(x.t, false) {}
  69.     map<Key, T, Compare>& operator=(const map<Key, T, Compare>& x) {
  70.         t = x.t;
  71.         return *this; 
  72.     }
  73.  
  74. // accessors:
  75.  
  76.     key_compare key_comp() const { return t.key_comp(); }
  77.     value_compare value_comp() const { return value_compare(t.key_comp()); }
  78.     iterator begin() { return t.begin(); }
  79.     const_iterator begin() const { return t.begin(); }
  80.     iterator end() { return t.end(); }
  81.     const_iterator end() const { return t.end(); }
  82.     reverse_iterator rbegin() { return t.rbegin(); }
  83.     const_reverse_iterator rbegin() const { return t.rbegin(); }
  84.     reverse_iterator rend() { return t.rend(); }
  85.     const_reverse_iterator rend() const { return t.rend(); }
  86.     bool empty() const { return t.empty(); }
  87.     size_type size() const { return t.size(); }
  88. #ifndef __GNUG__
  89.     size_type max_size() const { return t.max_size(); }
  90. #endif
  91.     Allocator<T>::reference operator[](const key_type& k) {
  92.         return (*((insert(value_type(k, T()))).first)).second;
  93.     }
  94.     void swap(map<Key, T, Compare>& x) { t.swap(x.t); }
  95.  
  96. // insert/erase
  97.  
  98.     typedef pair<iterator, bool> pair_iterator_bool; 
  99.     // typedef done to get around compiler bug
  100.     pair_iterator_bool insert(const value_type& x) { return t.insert(x); }
  101.     iterator insert(iterator position, const value_type& x) {
  102.         return t.insert(position, x);
  103.     }
  104.     void insert(const value_type* first, const value_type* last) {
  105.         t.insert(first, last);
  106.     }
  107.     void erase(iterator position) { t.erase(position); }
  108.     size_type erase(const key_type& x) { return t.erase(x); }
  109.     void erase(iterator first, iterator last) { t.erase(first, last); }
  110.  
  111. // map operations:
  112.  
  113.     iterator find(const key_type& x) { return t.find(x); }
  114.     const_iterator find(const key_type& x) const { return t.find(x); }
  115.     size_type count(const key_type& x) const { return t.count(x); }
  116.     iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
  117.     const_iterator lower_bound(const key_type& x) const {
  118.         return t.lower_bound(x); 
  119.     }
  120.     iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
  121.     const_iterator upper_bound(const key_type& x) const {
  122.         return t.upper_bound(x); 
  123.     }
  124.     typedef pair<iterator, iterator> pair_iterator_iterator; 
  125.     // typedef done to get around compiler bug
  126.     pair_iterator_iterator equal_range(const key_type& x) {
  127.         return t.equal_range(x);
  128.     }
  129.     typedef pair<const_iterator, const_iterator> pair_citerator_citerator; 
  130.     // typedef done to get around compiler bug
  131.     pair_citerator_citerator equal_range(const key_type& x) const {
  132.         return t.equal_range(x);
  133.     }
  134. };
  135.  
  136. template <class Key, class T, class Compare>
  137. inline bool operator==(const map<Key, T, Compare>& x, 
  138.                        const map<Key, T, Compare>& y) {
  139.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  140. }
  141.  
  142. template <class Key, class T, class Compare>
  143. inline bool operator<(const map<Key, T, Compare>& x, 
  144.                       const map<Key, T, Compare>& y) {
  145.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  146. }
  147.  
  148. #undef Allocator
  149.  
  150. #endif
  151.