home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / lib270b.zip / emx / include / cpp / multimap.h < prev    next >
C/C++ Source or Header  |  1995-05-17  |  5KB  |  143 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 MULTIMAP_H
  17. #define MULTIMAP_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 multimap {
  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 multimap<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 multimap
  52. public:
  53.     typedef rep_type::reference reference;
  54.     typedef rep_type::const_reference const_reference;
  55.     typedef rep_type::iterator iterator;
  56.     typedef rep_type::const_iterator const_iterator; 
  57.     typedef rep_type::reverse_iterator reverse_iterator;
  58.     typedef rep_type::const_reverse_iterator const_reverse_iterator;
  59.     typedef rep_type::size_type size_type;
  60.     typedef rep_type::difference_type difference_type;
  61.  
  62. // allocation/deallocation
  63.  
  64.     multimap(const Compare& comp = Compare()) : t(comp, true) { }
  65.     multimap(const value_type* first, const value_type* last, 
  66.              const Compare& comp = Compare()) : t(first, last, comp, true) { }
  67.     multimap(const multimap<Key, T, Compare>& x) : t(x.t, true) { }
  68.     multimap<Key, T, Compare>& operator=(const multimap<Key, T, Compare>& x) {
  69.         t = x.t;
  70.         return *this; 
  71.     }
  72.  
  73. // accessors:
  74.  
  75.     key_compare key_comp() const { return t.key_comp(); }
  76.     value_compare value_comp() const { return value_compare(t.key_comp()); }
  77.     iterator begin() { return t.begin(); }
  78.     const_iterator begin() const { return t.begin(); }
  79.     iterator end() { return t.end(); }
  80.     const_iterator end() const { return t.end(); }
  81.     reverse_iterator rbegin() { return t.rbegin(); }
  82.     const_reverse_iterator rbegin() const { return t.rbegin(); }
  83.     reverse_iterator rend() { return t.rend(); }
  84.     const_reverse_iterator rend() const { return t.rend(); }
  85.     bool empty() const { return t.empty(); }
  86.     size_type size() const { return t.size(); }
  87.     size_type max_size() const { return t.max_size(); }
  88.     void swap(multimap<Key, T, Compare>& x) { t.swap(x.t); }
  89.  
  90. // insert/erase
  91.  
  92.     iterator insert(const value_type& x) { return t.insert(x).first; }
  93.     iterator insert(iterator position, const value_type& x) {
  94.         return t.insert(position, x);
  95.     }
  96.     void insert(const value_type* first, const value_type* last) {
  97.         t.insert(first, last);
  98.     }
  99.     void erase(iterator position) { t.erase(position); }
  100.     size_type erase(const key_type& x) { return t.erase(x); }
  101.     void erase(iterator first, iterator last) { t.erase(first, last); }
  102.  
  103. // multimap operations:
  104.  
  105.     iterator find(const key_type& x) { return t.find(x); }
  106.     const_iterator find(const key_type& x) const { return t.find(x); }
  107.     size_type count(const key_type& x) const { return t.count(x); }
  108.     iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
  109.     const_iterator lower_bound(const key_type& x) const {
  110.         return t.lower_bound(x); 
  111.     }
  112.     iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
  113.     const_iterator upper_bound(const key_type& x) const {
  114.         return t.upper_bound(x); 
  115.     }
  116.     typedef  pair<iterator, iterator> pair_iterator_iterator; 
  117.     // typedef done to get around compiler bug
  118.     pair_iterator_iterator equal_range(const key_type& x) {
  119.         return t.equal_range(x);
  120.     }
  121.     typedef  pair<const_iterator, const_iterator> pair_citerator_citerator; 
  122.     // typedef done to get around compiler bug
  123.     pair_citerator_citerator equal_range(const key_type& x) const {
  124.         return t.equal_range(x);
  125.     }
  126. };
  127.  
  128. template <class Key, class T, class Compare>
  129. inline bool operator==(const multimap<Key, T, Compare>& x, 
  130.                        const multimap<Key, T, Compare>& y) {
  131.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  132. }
  133.  
  134. template <class Key, class T, class Compare>
  135. inline bool operator<(const multimap<Key, T, Compare>& x, 
  136.                       const multimap<Key, T, Compare>& y) {
  137.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  138. }
  139.  
  140. #undef Allocator
  141.  
  142. #endif
  143.