// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009// Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 3, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// Under Section 7 of GPL version 3, you are granted additional// permissions described in the GCC Runtime Library Exception, version// 3.1, as published by the Free Software Foundation.// You should have received a copy of the GNU General Public License and// a copy of the GCC Runtime Library Exception along with this program;// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see// <http://www.gnu.org/licenses/>./** @file debug/unordered_map* This file is a GNU debug extension to the Standard C++ Library.*/#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP#define _GLIBCXX_DEBUG_UNORDERED_MAP 1#ifdef __GXX_EXPERIMENTAL_CXX0X__# include <unordered_map>#else# include <c++0x_warning.h>#endif#include <debug/safe_sequence.h>#include <debug/safe_iterator.h>#include <initializer_list>namespace std{namespace __debug{template<typename _Key, typename _Tp,typename _Hash = std::hash<_Key>,typename _Pred = std::equal_to<_Key>,typename _Alloc = std::allocator<_Key> >class unordered_map: public _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,_Pred, _Alloc> >{typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,_Pred, _Alloc> _Base;typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,unordered_map> iterator;typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,unordered_map> const_iterator;explicitunordered_map(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a) { }template<typename _InputIterator>unordered_map(_InputIterator __f, _InputIterator __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,__hf, __eql, __a), _Safe_base() { }unordered_map(const unordered_map& __x): _Base(__x), _Safe_base() { }unordered_map(const _Base& __x): _Base(__x), _Safe_base() { }unordered_map(unordered_map&& __x): _Base(std::forward<unordered_map>(__x)), _Safe_base() { }unordered_map(initializer_list<value_type> __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }unordered_map&operator=(const unordered_map& __x){*static_cast<_Base*>(this) = __x;this->_M_invalidate_all();return *this;}unordered_map&operator=(unordered_map&& __x){// NB: DR 675.clear();swap(__x);return *this;}unordered_map&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}voidswap(unordered_map&& __x){_Base::swap(__x);_Safe_base::_M_swap(__x);}voidclear(){_Base::clear();this->_M_invalidate_all();}iteratorbegin(){ return iterator(_Base::begin(), this); }const_iteratorbegin() const{ return const_iterator(_Base::begin(), this); }iteratorend(){ return iterator(_Base::end(), this); }const_iteratorend() const{ return const_iterator(_Base::end(), this); }const_iteratorcbegin() const{ return const_iterator(_Base::begin(), this); }const_iteratorcend() const{ return const_iterator(_Base::end(), this); }// local versionsusing _Base::begin;using _Base::end;using _Base::cbegin;using _Base::cend;std::pair<iterator, bool>insert(const value_type& __obj){typedef std::pair<typename _Base::iterator, bool> __pair_type;__pair_type __res = _Base::insert(__obj);return std::make_pair(iterator(__res.first, this), __res.second);}iteratorinsert(iterator, const value_type& __obj){typedef std::pair<typename _Base::iterator, bool> __pair_type;__pair_type __res = _Base::insert(__obj);return iterator(__res.first, this);}const_iteratorinsert(const_iterator, const value_type& __obj){typedef std::pair<typename _Base::iterator, bool> __pair_type;__pair_type __res = _Base::insert(__obj);return const_iterator(__res.first, this);}voidinsert(std::initializer_list<value_type> __l){ _Base::insert(__l); }template<typename _InputIterator>voidinsert(_InputIterator __first, _InputIterator __last){__glibcxx_check_valid_range(__first, __last);_Base::insert(__first, __last);}iteratorfind(const key_type& __key){ return iterator(_Base::find(__key), this); }const_iteratorfind(const key_type& __key) const{ return const_iterator(_Base::find(__key), this); }std::pair<iterator, iterator>equal_range(const key_type& __key){typedef typename _Base::iterator _Base_iterator;typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;__pair_type __res = _Base::equal_range(__key);return std::make_pair(iterator(__res.first, this),iterator(__res.second, this));}std::pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{typedef typename _Base::const_iterator _Base_iterator;typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;__pair_type __res = _Base::equal_range(__key);return std::make_pair(const_iterator(__res.first, this),const_iterator(__res.second, this));}size_typeerase(const key_type& __key){size_type __ret(0);iterator __victim(_Base::find(__key), this);if (__victim != end()){this->erase(__victim);__ret = 1;}return __ret;}iteratorerase(iterator __it){__glibcxx_check_erase(__it);__it._M_invalidate();return iterator(_Base::erase(__it.base()), this);}const_iteratorerase(const_iterator __it){__glibcxx_check_erase(__it);__it._M_invalidate();return const_iterator(_Base::erase(__it.base()), this);}iteratorerase(iterator __first, iterator __last){__glibcxx_check_erase_range(__first, __last);for (iterator __tmp = __first; __tmp != __last;){iterator __victim = __tmp++;__victim._M_invalidate();}return iterator(_Base::erase(__first.base(),__last.base()), this);}const_iteratorerase(const_iterator __first, const_iterator __last){__glibcxx_check_erase_range(__first, __last);for (const_iterator __tmp = __first; __tmp != __last;){const_iterator __victim = __tmp++;__victim._M_invalidate();}return const_iterator(_Base::erase(__first.base(),__last.base()), this);}_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }private:void_M_invalidate_all(){typedef typename _Base::const_iterator _Base_const_iterator;typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;this->_M_invalidate_if(_Not_equal(_M_base().end()));}};template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y){ __x.swap(__y); }template<typename _Key, typename _Tp,typename _Hash = std::hash<_Key>,typename _Pred = std::equal_to<_Key>,typename _Alloc = std::allocator<_Key> >class unordered_multimap: public _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc>,public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc> >{typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,_Pred, _Alloc> _Base;typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;public:typedef typename _Base::size_type size_type;typedef typename _Base::hasher hasher;typedef typename _Base::key_equal key_equal;typedef typename _Base::allocator_type allocator_type;typedef typename _Base::key_type key_type;typedef typename _Base::value_type value_type;typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,unordered_multimap> iterator;typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,unordered_multimap> const_iterator;explicitunordered_multimap(size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__n, __hf, __eql, __a) { }template<typename _InputIterator>unordered_multimap(_InputIterator __f, _InputIterator __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n,__hf, __eql, __a), _Safe_base() { }unordered_multimap(const unordered_multimap& __x): _Base(__x), _Safe_base() { }unordered_multimap(const _Base& __x): _Base(__x), _Safe_base() { }unordered_multimap(unordered_multimap&& __x): _Base(std::forward<unordered_multimap>(__x)), _Safe_base() { }unordered_multimap(initializer_list<value_type> __l,size_type __n = 10,const hasher& __hf = hasher(),const key_equal& __eql = key_equal(),const allocator_type& __a = allocator_type()): _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }unordered_multimap&operator=(const unordered_multimap& __x){*static_cast<_Base*>(this) = __x;this->_M_invalidate_all();return *this;}unordered_multimap&operator=(unordered_multimap&& __x){// NB: DR 675.clear();swap(__x);return *this;}unordered_multimap&operator=(initializer_list<value_type> __l){this->clear();this->insert(__l);return *this;}voidswap(unordered_multimap&& __x){_Base::swap(__x);_Safe_base::_M_swap(__x);}voidclear(){_Base::clear();this->_M_invalidate_all();}iteratorbegin(){ return iterator(_Base::begin(), this); }const_iteratorbegin() const{ return const_iterator(_Base::begin(), this); }iteratorend(){ return iterator(_Base::end(), this); }const_iteratorend() const{ return const_iterator(_Base::end(), this); }const_iteratorcbegin() const{ return const_iterator(_Base::begin(), this); }const_iteratorcend() const{ return const_iterator(_Base::end(), this); }// local versionsusing _Base::begin;using _Base::end;using _Base::cbegin;using _Base::cend;iteratorinsert(const value_type& __obj){ return iterator(_Base::insert(__obj), this); }iteratorinsert(iterator, const value_type& __obj){ return iterator(_Base::insert(__obj), this); }const_iteratorinsert(const_iterator, const value_type& __obj){ return const_iterator(_Base::insert(__obj), this); }voidinsert(std::initializer_list<value_type> __l){ _Base::insert(__l); }template<typename _InputIterator>voidinsert(_InputIterator __first, _InputIterator __last){__glibcxx_check_valid_range(__first, __last);_Base::insert(__first, __last);}iteratorfind(const key_type& __key){ return iterator(_Base::find(__key), this); }const_iteratorfind(const key_type& __key) const{ return const_iterator(_Base::find(__key), this); }std::pair<iterator, iterator>equal_range(const key_type& __key){typedef typename _Base::iterator _Base_iterator;typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;__pair_type __res = _Base::equal_range(__key);return std::make_pair(iterator(__res.first, this),iterator(__res.second, this));}std::pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{typedef typename _Base::const_iterator _Base_iterator;typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;__pair_type __res = _Base::equal_range(__key);return std::make_pair(const_iterator(__res.first, this),const_iterator(__res.second, this));}size_typeerase(const key_type& __key){size_type __ret(0);iterator __victim(_Base::find(__key), this);if (__victim != end()){this->erase(__victim);__ret = 1;}return __ret;}iteratorerase(iterator __it){__glibcxx_check_erase(__it);__it._M_invalidate();return iterator(_Base::erase(__it.base()), this);}const_iteratorerase(const_iterator __it){__glibcxx_check_erase(__it);__it._M_invalidate();return const_iterator(_Base::erase(__it.base()), this);}iteratorerase(iterator __first, iterator __last){__glibcxx_check_erase_range(__first, __last);for (iterator __tmp = __first; __tmp != __last;){iterator __victim = __tmp++;__victim._M_invalidate();}return iterator(_Base::erase(__first.base(),__last.base()), this);}const_iteratorerase(const_iterator __first, const_iterator __last){__glibcxx_check_erase_range(__first, __last);for (const_iterator __tmp = __first; __tmp != __last;){const_iterator __victim = __tmp++;__victim._M_invalidate();}return const_iterator(_Base::erase(__first.base(),__last.base()), this);}_Base&_M_base() { return *this; }const _Base&_M_base() const { return *this; }private:void_M_invalidate_all(){typedef typename _Base::const_iterator _Base_const_iterator;typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;this->_M_invalidate_if(_Not_equal(_M_base().end()));}};template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x,unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){ __x.swap(__y); }template<typename _Key, typename _Tp, typename _Hash,typename _Pred, typename _Alloc>inline voidswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y){ __x.swap(__y); }} // namespace __debug} // namespace std#endif