home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / multiset.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-10-12  |  4.2 KB  |  130 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 MULTISET_H
  17. #define MULTISET_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 Compare>
  27. class multiset {
  28. public:
  29. // typedefs:
  30.  
  31.     typedef Key key_type;
  32.     typedef Key value_type;
  33.     typedef Compare key_compare;
  34.     typedef Compare value_compare;
  35. private:
  36.     typedef rb_tree<key_type, value_type, 
  37.                     ident<value_type, key_type>, key_compare> rep_type;
  38.     rep_type t;  // red-black tree representing multiset
  39. public:
  40.     typedef rep_type::const_reference reference;
  41.     typedef rep_type::const_reference const_reference;
  42.     typedef rep_type::const_iterator iterator;
  43.     typedef rep_type::const_iterator const_iterator;
  44.     typedef rep_type::const_reverse_iterator reverse_iterator;
  45.     typedef rep_type::const_reverse_iterator const_reverse_iterator;
  46.     typedef rep_type::size_type size_type;
  47.     typedef rep_type::difference_type difference_type;
  48.  
  49. // allocation/deallocation
  50.  
  51.     multiset(const Compare& comp = Compare()) : t(comp, true) {}
  52.     multiset(const value_type* first, const value_type* last, 
  53.         const Compare& comp = Compare()) : t(comp, true) {
  54.         for (const value_type* i = first; i != last; ++i)
  55.            t.insert(*i);
  56.     }
  57.     multiset(const multiset<Key, Compare>& x) : t(x.t, true) {}
  58.     multiset<Key, Compare>& operator=(const multiset<Key, Compare>& x) { 
  59.         t = x.t; 
  60.         return *this;
  61.     }
  62.  
  63. // accessors:
  64.  
  65.     key_compare key_comp() const { return t.key_comp(); }
  66.     value_compare value_comp() const { return t.key_comp(); }
  67.     iterator begin() const { return t.begin(); }
  68.     iterator end() const { return t.end(); }
  69.     reverse_iterator rbegin() const { return t.rbegin(); } 
  70.     reverse_iterator rend() const { return t.rend(); }
  71.     bool empty() const { return t.empty(); }
  72.     size_type size() const { return t.size(); }
  73.     size_type max_size() const { return t.max_size(); }
  74.     void swap(multiset<Key, Compare>& x) { t.swap(x.t); }
  75.  
  76. // insert/erase
  77.     iterator insert(const value_type& x) { 
  78.         return t.insert(x).first;
  79.     }
  80.     iterator insert(iterator position, const value_type& x) {
  81.         return t.insert((rep_type::iterator&)position, x);
  82.     }
  83.     void insert(const value_type* first, const value_type* last) {
  84.         for (const value_type* i = first; i != last; ++i)
  85.             t.insert(*i);
  86.     }
  87.     void erase(iterator position) { 
  88.         t.erase((rep_type::iterator&)position); 
  89.     }
  90.     size_type erase(const key_type& x) { 
  91.         return t.erase(x); 
  92.     }
  93.     void erase(iterator first, iterator last) { 
  94.         t.erase((rep_type::iterator&)first, 
  95.                 (rep_type::iterator&)last); 
  96.     }
  97.  
  98. // multiset operations:
  99.  
  100.     iterator find(const key_type& x) const { return t.find(x); }
  101.     size_type count(const key_type& x) const { return t.count(x); }
  102.     iterator lower_bound(const key_type& x) const {
  103.         return t.lower_bound(x);
  104.     }
  105.     iterator upper_bound(const key_type& x) const {
  106.         return t.upper_bound(x); 
  107.     }
  108.     typedef  pair<iterator, iterator> pair_iterator_iterator; 
  109.     // typedef done to get around compiler bug
  110.     pair_iterator_iterator equal_range(const key_type& x) const {
  111.         return t.equal_range(x);
  112.     }
  113. };
  114.  
  115. template <class Key, class Compare>
  116. inline bool operator==(const multiset<Key, Compare>& x, 
  117.                        const multiset<Key, Compare>& y) {
  118.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  119. }
  120.  
  121. template <class Key, class Compare>
  122. inline bool operator<(const multiset<Key, Compare>& x, 
  123.                       const multiset<Key, Compare>& y) {
  124.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  125. }
  126.  
  127. #undef Allocator
  128.  
  129. #endif
  130.