10SN/A// Debugging multimap implementation -*- C++ -*- 22362SN/A 30SN/A// Copyright (C) 2003, 2004, 2005 40SN/A// Free Software Foundation, Inc. 50SN/A// 60SN/A// This file is part of the GNU ISO C++ Library. This library is free 72362SN/A// software; you can redistribute it and/or modify it under the 80SN/A// terms of the GNU General Public License as published by the 92362SN/A// Free Software Foundation; either version 2, or (at your option) 100SN/A// any later version. 110SN/A 120SN/A// This library is distributed in the hope that it will be useful, 130SN/A// but WITHOUT ANY WARRANTY; without even the implied warranty of 140SN/A// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 150SN/A// GNU General Public License for more details. 160SN/A 170SN/A// You should have received a copy of the GNU General Public License along 180SN/A// with this library; see the file COPYING. If not, write to the Free 190SN/A// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 200SN/A// USA. 212362SN/A 222362SN/A// As a special exception, you may use this file as part of a free software 232362SN/A// library without restriction. Specifically, if other files instantiate 240SN/A// templates or use macros or inline functions from this file, or you compile 250SN/A// this file and link it with other files to produce an executable, this 260SN/A// file does not by itself cause the resulting executable to be covered by 270SN/A// the GNU General Public License. This exception does not however 280SN/A// invalidate any other reasons why the executable file might be covered by 290SN/A// the GNU General Public License. 300SN/A 310SN/A/** @file debug/multimap.h 320SN/A * This file is a GNU debug extension to the Standard C++ Library. 330SN/A */ 340SN/A 350SN/A#ifndef _GLIBCXX_DEBUG_MULTIMAP_H 360SN/A#define _GLIBCXX_DEBUG_MULTIMAP_H 1 370SN/A 380SN/A#include <debug/safe_sequence.h> 390SN/A#include <debug/safe_iterator.h> 400SN/A#include <utility> 410SN/A 420SN/Anamespace std 430SN/A{ 440SN/Anamespace __debug 450SN/A{ 460SN/A template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 470SN/A typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 480SN/A class multimap 490SN/A : public _GLIBCXX_STD::multimap<_Key, _Tp, _Compare, _Allocator>, 500SN/A public __gnu_debug::_Safe_sequence<multimap<_Key,_Tp,_Compare,_Allocator> > 510SN/A { 520SN/A typedef _GLIBCXX_STD::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 530SN/A typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base; 540SN/A 550SN/A public: 560SN/A // types: 570SN/A typedef _Key key_type; 580SN/A typedef _Tp mapped_type; 590SN/A typedef std::pair<const _Key, _Tp> value_type; 600SN/A typedef _Compare key_compare; 610SN/A typedef _Allocator allocator_type; 620SN/A typedef typename _Base::reference reference; 630SN/A typedef typename _Base::const_reference const_reference; 640SN/A 650SN/A typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap> 660SN/A iterator; 670SN/A typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 680SN/A multimap> const_iterator; 690SN/A 700SN/A typedef typename _Base::size_type size_type; 710SN/A typedef typename _Base::difference_type difference_type; 720SN/A typedef typename _Base::pointer pointer; 730SN/A typedef typename _Base::const_pointer const_pointer; 740SN/A typedef std::reverse_iterator<iterator> reverse_iterator; 750SN/A typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 760SN/A 770SN/A // 23.3.1.1 construct/copy/destroy: 780SN/A explicit multimap(const _Compare& __comp = _Compare(), 790SN/A const _Allocator& __a = _Allocator()) 800SN/A : _Base(__comp, __a) { } 810SN/A 820SN/A template<typename _InputIterator> 830SN/A multimap(_InputIterator __first, _InputIterator __last, 840SN/A const _Compare& __comp = _Compare(), 850SN/A const _Allocator& __a = _Allocator()) 860SN/A : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, 870SN/A __comp, __a) { } 880SN/A 890SN/A multimap(const multimap<_Key,_Tp,_Compare,_Allocator>& __x) 900SN/A : _Base(__x), _Safe_base() { } 910SN/A 920SN/A multimap(const _Base& __x) : _Base(__x), _Safe_base() { } 930SN/A 940SN/A ~multimap() { } 950SN/A 960SN/A multimap<_Key,_Tp,_Compare,_Allocator>& 970SN/A operator=(const multimap<_Key,_Tp,_Compare,_Allocator>& __x) 980SN/A { 990SN/A *static_cast<_Base*>(this) = __x; 1000SN/A this->_M_invalidate_all(); 1010SN/A return *this; 1020SN/A } 1030SN/A 1040SN/A using _Base::get_allocator; 1050SN/A 1060SN/A // iterators: 1070SN/A iterator 1080SN/A begin() 1090SN/A { return iterator(_Base::begin(), this); } 1100SN/A 1110SN/A const_iterator 1120SN/A begin() const 1130SN/A { return const_iterator(_Base::begin(), this); } 1140SN/A 1150SN/A iterator 1160SN/A end() 1170SN/A { return iterator(_Base::end(), this); } 1180SN/A 1190SN/A const_iterator 1200SN/A end() const 1210SN/A { return const_iterator(_Base::end(), this); } 1220SN/A 1230SN/A reverse_iterator 1240SN/A rbegin() 1250SN/A { return reverse_iterator(end()); } 1260SN/A 1270SN/A const_reverse_iterator 1280SN/A rbegin() const 1290SN/A { return const_reverse_iterator(end()); } 1300SN/A 1310SN/A reverse_iterator 1320SN/A rend() 1330SN/A { return reverse_iterator(begin()); } 1340SN/A 1350SN/A const_reverse_iterator 1360SN/A rend() const 1370SN/A { return const_reverse_iterator(begin()); } 1380SN/A 1390SN/A // capacity: 1400SN/A using _Base::empty; 1410SN/A using _Base::size; 1420SN/A using _Base::max_size; 1430SN/A 1440SN/A // modifiers: 1450SN/A iterator 1460SN/A insert(const value_type& __x) 1470SN/A { return iterator(_Base::insert(__x), this); } 1480SN/A 1490SN/A iterator 1500SN/A insert(iterator __position, const value_type& __x) 1510SN/A { 1520SN/A __glibcxx_check_insert(__position); 1530SN/A return iterator(_Base::insert(__position.base(), __x), this); 1540SN/A } 1550SN/A 1560SN/A template<typename _InputIterator> 1570SN/A void 1580SN/A insert(_InputIterator __first, _InputIterator __last) 1590SN/A { 1600SN/A __glibcxx_check_valid_range(__first, __last); 1610SN/A _Base::insert(__first, __last); 1620SN/A } 1630SN/A 1640SN/A void 1650SN/A erase(iterator __position) 1660SN/A { 1670SN/A __glibcxx_check_erase(__position); 1680SN/A __position._M_invalidate(); 1690SN/A _Base::erase(__position.base()); 1700SN/A } 1710SN/A 1720SN/A size_type 1730SN/A erase(const key_type& __x) 1740SN/A { 1750SN/A std::pair<iterator, iterator> __victims = this->equal_range(__x); 1760SN/A size_type __count = 0; 1770SN/A while (__victims.first != __victims.second) 1780SN/A { 1790SN/A iterator __victim = __victims.first++; 1800SN/A __victim._M_invalidate(); 1810SN/A _Base::erase(__victim.base()); 1820SN/A ++__count; 1830SN/A } 1840SN/A return __count; 1850SN/A } 1860SN/A 1870SN/A void 1880SN/A erase(iterator __first, iterator __last) 1890SN/A { 1900SN/A // _GLIBCXX_RESOLVE_LIB_DEFECTS 1910SN/A // 151. can't currently clear() empty container 1920SN/A __glibcxx_check_erase_range(__first, __last); 1930SN/A while (__first != __last) 1940SN/A this->erase(__first++); 1950SN/A } 1960SN/A 1970SN/A void 1980SN/A swap(multimap<_Key,_Tp,_Compare,_Allocator>& __x) 1990SN/A { 2000SN/A _Base::swap(__x); 2010SN/A this->_M_swap(__x); 2020SN/A } 2030SN/A 2040SN/A void 2050SN/A clear() 2060SN/A { this->erase(begin(), end()); } 2070SN/A 2080SN/A // observers: 2090SN/A using _Base::key_comp; 2100SN/A using _Base::value_comp; 2110SN/A 2120SN/A // 23.3.1.3 multimap operations: 2130SN/A iterator 2140SN/A find(const key_type& __x) 2150SN/A { return iterator(_Base::find(__x), this); } 2160SN/A 2170SN/A const_iterator 2180SN/A find(const key_type& __x) const 2190SN/A { return const_iterator(_Base::find(__x), this); } 2200SN/A 2210SN/A using _Base::count; 2220SN/A 2230SN/A iterator 2240SN/A lower_bound(const key_type& __x) 2250SN/A { return iterator(_Base::lower_bound(__x), this); } 2260SN/A 2270SN/A const_iterator 2280SN/A lower_bound(const key_type& __x) const 2290SN/A { return const_iterator(_Base::lower_bound(__x), this); } 2300SN/A 2310SN/A iterator 2320SN/A upper_bound(const key_type& __x) 2330SN/A { return iterator(_Base::upper_bound(__x), this); } 2340SN/A 2350SN/A const_iterator 2360SN/A upper_bound(const key_type& __x) const 2370SN/A { return const_iterator(_Base::upper_bound(__x), this); } 2380SN/A 2390SN/A std::pair<iterator,iterator> 2400SN/A equal_range(const key_type& __x) 2410SN/A { 2420SN/A typedef typename _Base::iterator _Base_iterator; 2430SN/A std::pair<_Base_iterator, _Base_iterator> __res = 2440SN/A _Base::equal_range(__x); 2450SN/A return std::make_pair(iterator(__res.first, this), 2460SN/A iterator(__res.second, this)); 2470SN/A } 2480SN/A 2490SN/A std::pair<const_iterator,const_iterator> 2500SN/A equal_range(const key_type& __x) const 2510SN/A { 2520SN/A typedef typename _Base::const_iterator _Base_const_iterator; 2530SN/A std::pair<_Base_const_iterator, _Base_const_iterator> __res = 2540SN/A _Base::equal_range(__x); 2550SN/A return std::make_pair(const_iterator(__res.first, this), 2560SN/A const_iterator(__res.second, this)); 2570SN/A } 2580SN/A 2590SN/A _Base& 2600SN/A _M_base() { return *this; } 2610SN/A 2620SN/A const _Base& 2630SN/A _M_base() const { return *this; } 2640SN/A 2650SN/A private: 2660SN/A void 2670SN/A _M_invalidate_all() 2680SN/A { 2690SN/A typedef typename _Base::const_iterator _Base_const_iterator; 2700SN/A typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 2710SN/A this->_M_invalidate_if(_Not_equal(_M_base().end())); 2720SN/A } 2730SN/A }; 2740SN/A 2750SN/A template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 2760SN/A inline bool 2770SN/A operator==(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 2780SN/A const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 2790SN/A { return __lhs._M_base() == __rhs._M_base(); } 2800SN/A 2810SN/A template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 2820SN/A inline bool 2830SN/A operator!=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 2840SN/A const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 2850SN/A { return __lhs._M_base() != __rhs._M_base(); } 2860SN/A 287 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 288 inline bool 289 operator<(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 290 const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 291 { return __lhs._M_base() < __rhs._M_base(); } 292 293 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 294 inline bool 295 operator<=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 296 const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 297 { return __lhs._M_base() <= __rhs._M_base(); } 298 299 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 300 inline bool 301 operator>=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 302 const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 303 { return __lhs._M_base() >= __rhs._M_base(); } 304 305 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 306 inline bool 307 operator>(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 308 const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 309 { return __lhs._M_base() > __rhs._M_base(); } 310 311 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 312 inline void 313 swap(multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 314 multimap<_Key,_Tp,_Compare,_Allocator>& __rhs) 315 { __lhs.swap(__rhs); } 316} // namespace __debug 317} // namespace std 318 319#endif 320