stl_multimap.h

Go to the documentation of this file.
00001 // Multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996,1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00061 #ifndef __GLIBCPP_INTERNAL_MULTIMAP_H 00062 #define __GLIBCPP_INTERNAL_MULTIMAP_H 00063 00064 #include <bits/concept_check.h> 00065 00066 namespace std 00067 { 00068 // Forward declaration of operators < and ==, needed for friend declaration. 00069 template <class _Key, class _Tp, 00070 class _Compare = less<_Key>, 00071 class _Alloc = allocator<pair<const _Key, _Tp> > > 00072 class multimap; 00073 00074 template <class _Key, class _Tp, class _Compare, class _Alloc> 00075 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00076 const multimap<_Key,_Tp,_Compare,_Alloc>& __y); 00077 00078 template <class _Key, class _Tp, class _Compare, class _Alloc> 00079 inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00080 const multimap<_Key,_Tp,_Compare,_Alloc>& __y); 00081 00090 template <class _Key, class _Tp, class _Compare, class _Alloc> 00091 class multimap 00092 { 00093 // concept requirements 00094 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00095 __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept); 00096 00097 public: 00098 00099 // typedefs: 00100 00101 typedef _Key key_type; 00102 typedef _Tp data_type; 00103 typedef _Tp mapped_type; 00104 typedef pair<const _Key, _Tp> value_type; 00105 typedef _Compare key_compare; 00106 00107 class value_compare : public binary_function<value_type, value_type, bool> { 00108 friend class multimap<_Key,_Tp,_Compare,_Alloc>; 00109 protected: 00110 _Compare comp; 00111 value_compare(_Compare __c) : comp(__c) {} 00112 public: 00113 bool operator()(const value_type& __x, const value_type& __y) const { 00114 return comp(__x.first, __y.first); 00115 } 00116 }; 00117 00118 private: 00119 typedef _Rb_tree<key_type, value_type, 00120 _Select1st<value_type>, key_compare, _Alloc> _Rep_type; 00121 _Rep_type _M_t; // red-black tree representing multimap 00122 public: 00123 typedef typename _Rep_type::pointer pointer; 00124 typedef typename _Rep_type::const_pointer const_pointer; 00125 typedef typename _Rep_type::reference reference; 00126 typedef typename _Rep_type::const_reference const_reference; 00127 typedef typename _Rep_type::iterator iterator; 00128 typedef typename _Rep_type::const_iterator const_iterator; 00129 typedef typename _Rep_type::reverse_iterator reverse_iterator; 00130 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00131 typedef typename _Rep_type::size_type size_type; 00132 typedef typename _Rep_type::difference_type difference_type; 00133 typedef typename _Rep_type::allocator_type allocator_type; 00134 00135 // allocation/deallocation 00136 00137 multimap() : _M_t(_Compare(), allocator_type()) { } 00138 explicit multimap(const _Compare& __comp, 00139 const allocator_type& __a = allocator_type()) 00140 : _M_t(__comp, __a) { } 00141 00142 template <class _InputIterator> 00143 multimap(_InputIterator __first, _InputIterator __last) 00144 : _M_t(_Compare(), allocator_type()) 00145 { _M_t.insert_equal(__first, __last); } 00146 00147 template <class _InputIterator> 00148 multimap(_InputIterator __first, _InputIterator __last, 00149 const _Compare& __comp, 00150 const allocator_type& __a = allocator_type()) 00151 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 00152 multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { } 00153 00154 multimap<_Key,_Tp,_Compare,_Alloc>& 00155 operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) { 00156 _M_t = __x._M_t; 00157 return *this; 00158 } 00159 00160 // accessors: 00161 00162 key_compare key_comp() const { return _M_t.key_comp(); } 00163 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } 00164 allocator_type get_allocator() const { return _M_t.get_allocator(); } 00165 00170 iterator begin() { return _M_t.begin(); } 00171 00177 const_iterator begin() const { return _M_t.begin(); } 00178 00183 iterator end() { return _M_t.end(); } 00184 00190 const_iterator end() const { return _M_t.end(); } 00191 00197 reverse_iterator rbegin() { return _M_t.rbegin(); } 00198 00204 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 00205 00211 reverse_iterator rend() { return _M_t.rend(); } 00212 00218 const_reverse_iterator rend() const { return _M_t.rend(); } 00219 00221 bool empty() const { return _M_t.empty(); } 00222 00224 size_type size() const { return _M_t.size(); } 00225 00227 size_type max_size() const { return _M_t.max_size(); } 00228 00229 void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 00230 00231 // insert/erase 00242 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); } 00243 00259 iterator insert(iterator __position, const value_type& __x) { 00260 return _M_t.insert_equal(__position, __x); 00261 } 00262 00270 template <class _InputIterator> 00271 void insert(_InputIterator __first, _InputIterator __last) { 00272 _M_t.insert_equal(__first, __last); 00273 } 00274 00284 void erase(iterator __position) { _M_t.erase(__position); } 00285 00297 size_type erase(const key_type& __x) { return _M_t.erase(__x); } 00298 00309 void erase(iterator __first, iterator __last) 00310 { _M_t.erase(__first, __last); } 00311 00317 void clear() { _M_t.clear(); } 00318 00319 // multimap operations: 00320 00332 iterator find(const key_type& __x) { return _M_t.find(__x); } 00333 00345 const_iterator find(const key_type& __x) const { return _M_t.find(__x); } 00346 00352 size_type count(const key_type& __x) const { return _M_t.count(__x); } 00353 00365 iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } 00366 00378 const_iterator lower_bound(const key_type& __x) const { 00379 return _M_t.lower_bound(__x); 00380 } 00381 00387 iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } 00388 00395 const_iterator upper_bound(const key_type& __x) const { 00396 return _M_t.upper_bound(__x); 00397 } 00398 00413 pair<iterator,iterator> equal_range(const key_type& __x) { 00414 return _M_t.equal_range(__x); 00415 } 00416 00431 pair<const_iterator,const_iterator> equal_range(const key_type& __x) const { 00432 return _M_t.equal_range(__x); 00433 } 00434 00435 template <class _K1, class _T1, class _C1, class _A1> 00436 friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&, 00437 const multimap<_K1, _T1, _C1, _A1>&); 00438 template <class _K1, class _T1, class _C1, class _A1> 00439 friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&, 00440 const multimap<_K1, _T1, _C1, _A1>&); 00441 }; 00442 00443 template <class _Key, class _Tp, class _Compare, class _Alloc> 00444 inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00445 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00446 return __x._M_t == __y._M_t; 00447 } 00448 00449 template <class _Key, class _Tp, class _Compare, class _Alloc> 00450 inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00451 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00452 return __x._M_t < __y._M_t; 00453 } 00454 00455 template <class _Key, class _Tp, class _Compare, class _Alloc> 00456 inline bool operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00457 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00458 return !(__x == __y); 00459 } 00460 00461 template <class _Key, class _Tp, class _Compare, class _Alloc> 00462 inline bool operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00463 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00464 return __y < __x; 00465 } 00466 00467 template <class _Key, class _Tp, class _Compare, class _Alloc> 00468 inline bool operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00469 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00470 return !(__y < __x); 00471 } 00472 00473 template <class _Key, class _Tp, class _Compare, class _Alloc> 00474 inline bool operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00475 const multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00476 return !(__x < __y); 00477 } 00478 00479 template <class _Key, class _Tp, class _Compare, class _Alloc> 00480 inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x, 00481 multimap<_Key,_Tp,_Compare,_Alloc>& __y) { 00482 __x.swap(__y); 00483 } 00484 00485 } // namespace std 00486 00487 #endif /* __GLIBCPP_INTERNAL_MULTIMAP_H */ 00488 00489 // Local Variables: 00490 // mode:C++ 00491 // End:

Generated on Wed Sep 29 13:54:52 2004 for libstdc++-v3 Source by doxygen 1.3.7