williamr@2: /* williamr@2: * williamr@2: * Copyright (c) 1994 williamr@2: * Hewlett-Packard Company williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1997 williamr@2: * Moscow Center for SPARC Technology williamr@2: * williamr@2: * Copyright (c) 1999 williamr@2: * Boris Fomitchev williamr@2: * williamr@2: * This material is provided "as is", with absolutely no warranty expressed williamr@2: * or implied. Any use is at your own risk. williamr@2: * williamr@2: * Permission to use or copy this software for any purpose is hereby granted williamr@2: * without fee, provided the above notices are retained on all copies. williamr@2: * Permission to modify the code and to distribute modified code is granted, williamr@2: * provided the above notices are retained, and a notice that the code was williamr@2: * modified is included with the above copyright notice. williamr@2: * williamr@2: */ williamr@2: williamr@2: /* NOTE: This is an internal header file, included by other STL headers. williamr@2: * You should not attempt to use it directly. williamr@2: */ williamr@2: williamr@2: #ifndef _STLP_INTERNAL_MAP_H williamr@2: #define _STLP_INTERNAL_MAP_H williamr@2: williamr@2: #ifndef _STLP_INTERNAL_TREE_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: #define map __WORKAROUND_RENAME(map) williamr@2: #define multimap __WORKAROUND_RENAME(multimap) williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@2: template ), williamr@2: _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) > williamr@2: class map williamr@2: { williamr@2: public: williamr@2: williamr@2: // typedefs: williamr@2: williamr@2: typedef _Key key_type; williamr@2: typedef _Tp data_type; williamr@2: typedef _Tp mapped_type; williamr@2: typedef pair value_type; williamr@2: typedef _Compare key_compare; williamr@2: williamr@2: class value_compare williamr@2: : public binary_function { williamr@2: friend class map<_Key,_Tp,_Compare,_Alloc>; williamr@2: protected : williamr@2: _Compare _M_comp; williamr@2: value_compare(_Compare __c) : _M_comp(__c) {} williamr@2: public: williamr@2: bool operator()(const value_type& __x, const value_type& __y) const { williamr@2: return _M_comp(__x.first, __y.first); williamr@2: } williamr@2: }; williamr@2: williamr@2: private: williamr@2: # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG williamr@2: typedef _Rb_tree, key_compare, _Alloc> _Rep_type; williamr@2: # else williamr@2: typedef _Rb_tree, key_compare, _Alloc> _Rep_type; williamr@2: # endif williamr@2: _Rep_type _M_t; // red-black tree representing map williamr@2: public: williamr@2: typedef typename _Rep_type::pointer pointer; williamr@2: typedef typename _Rep_type::const_pointer const_pointer; williamr@2: typedef typename _Rep_type::reference reference; williamr@2: typedef typename _Rep_type::const_reference const_reference; williamr@2: typedef typename _Rep_type::iterator iterator; williamr@2: typedef typename _Rep_type::const_iterator const_iterator; williamr@2: typedef typename _Rep_type::reverse_iterator reverse_iterator; williamr@2: typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; williamr@2: typedef typename _Rep_type::size_type size_type; williamr@2: typedef typename _Rep_type::difference_type difference_type; williamr@2: typedef typename _Rep_type::allocator_type allocator_type; williamr@2: typedef map<_Key,_Tp,_Compare,_Alloc> _Self; williamr@2: williamr@2: // allocation/deallocation williamr@2: williamr@2: map() : _M_t(_Compare(), allocator_type()) { williamr@2: _STLP_POP_IF_CHECK williamr@2: } williamr@2: williamr@2: explicit map(const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_POP_IF_CHECK williamr@2: } williamr@2: williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template williamr@2: map(_InputIterator __first, _InputIterator __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: template williamr@2: map(_InputIterator __first, _InputIterator __last, const _Compare& __comp, williamr@2: const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS williamr@2: template williamr@2: map(_InputIterator __first, _InputIterator __last, const _Compare& __comp) williamr@2: : _M_t(__comp, allocator_type()) williamr@2: { _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: # endif williamr@2: williamr@2: #else williamr@2: map(const value_type* __first, const value_type* __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: map(const value_type* __first, williamr@2: const value_type* __last, const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: map(const_iterator __first, const_iterator __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: map(const_iterator __first, const_iterator __last, const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_unique(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: # ifdef _STLP_USE_TRAP_LEAVE williamr@2: map(const map<_Key,_Tp,_Compare,_Alloc>& __x) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t =__x._M_t; williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: #else williamr@2: map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : williamr@2: _M_t(__x._M_t) { williamr@2: _STLP_POP_IF_CHECK williamr@2: } williamr@2: # endif williamr@2: map<_Key,_Tp,_Compare,_Alloc>& williamr@2: operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x) williamr@2: { williamr@2: _M_t = __x._M_t; williamr@2: return *this; williamr@2: } williamr@2: williamr@2: #ifdef _STLP_USE_TRAP_LEAVE williamr@2: public: williamr@2: static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper::_NewLC(__n); } williamr@2: static void* operator new (size_t __n) { return _STLP_StackHelper::_NewLC(__n); } williamr@2: #endif williamr@2: williamr@2: // accessors: williamr@2: williamr@2: key_compare key_comp() const { return _M_t.key_comp(); } williamr@2: value_compare value_comp() const { return value_compare(_M_t.key_comp()); } williamr@2: allocator_type get_allocator() const { return _M_t.get_allocator(); } williamr@2: williamr@2: iterator begin() { return _M_t.begin(); } williamr@2: const_iterator begin() const { return _M_t.begin(); } williamr@2: iterator end() { return _M_t.end(); } williamr@2: const_iterator end() const { return _M_t.end(); } williamr@2: reverse_iterator rbegin() { return _M_t.rbegin(); } williamr@2: const_reverse_iterator rbegin() const { return _M_t.rbegin(); } williamr@2: reverse_iterator rend() { return _M_t.rend(); } williamr@2: const_reverse_iterator rend() const { return _M_t.rend(); } williamr@2: bool empty() const { return _M_t.empty(); } williamr@2: size_type size() const { return _M_t.size(); } williamr@2: size_type max_size() const { return _M_t.max_size(); } williamr@2: _Tp& operator[](const key_type& __k) { williamr@2: iterator __i = lower_bound(__k); williamr@2: // __i->first is greater than or equivalent to __k. williamr@2: if (__i == end() || key_comp()(__k, (*__i).first)) { williamr@2: # ifdef _STLP_USE_TRAP_LEAVE williamr@2: value_type __tmp(__k, __false_type()); williamr@2: _STLP_PUSH_STACK_ITEM(value_type, &__tmp) williamr@2: __i = insert(__i, __tmp); williamr@2: williamr@2: # else williamr@2: __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp))); williamr@2: # endif williamr@2: } williamr@2: return (*__i).second; williamr@2: } williamr@2: void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } williamr@2: williamr@2: // insert/erase williamr@2: williamr@2: pair insert(const value_type& __x) williamr@2: { return _M_t.insert_unique(__x); } williamr@2: iterator insert(iterator position, const value_type& __x) williamr@2: { return _M_t.insert_unique(position, __x); } williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template williamr@2: void insert(_InputIterator __first, _InputIterator __last) { williamr@2: _M_t.insert_unique(__first, __last); williamr@2: } williamr@2: #else williamr@2: void insert(const value_type* __first, const value_type* __last) { williamr@2: _M_t.insert_unique(__first, __last); williamr@2: } williamr@2: void insert(const_iterator __first, const_iterator __last) { williamr@2: _M_t.insert_unique(__first, __last); williamr@2: } williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: void erase(iterator __position) { _M_t.erase(__position); } williamr@2: size_type erase(const key_type& __x) { return _M_t.erase(__x); } williamr@2: void erase(iterator __first, iterator __last) williamr@2: { _M_t.erase(__first, __last); } williamr@2: void clear() { _M_t.clear(); } williamr@2: williamr@2: // map operations: williamr@2: williamr@2: iterator find(const key_type& __x) { return _M_t.find(__x); } williamr@2: const_iterator find(const key_type& __x) const { return _M_t.find(__x); } williamr@2: size_type count(const key_type& __x) const { williamr@2: return _M_t.find(__x) == _M_t.end() ? 0 : 1; williamr@2: } williamr@2: iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } williamr@2: const_iterator lower_bound(const key_type& __x) const { williamr@2: return _M_t.lower_bound(__x); williamr@2: } williamr@2: iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } williamr@2: const_iterator upper_bound(const key_type& __x) const { williamr@2: return _M_t.upper_bound(__x); williamr@2: } williamr@2: williamr@2: pair equal_range(const key_type& __x) { williamr@2: return _M_t.equal_range(__x); williamr@2: } williamr@2: pair equal_range(const key_type& __x) const { williamr@2: return _M_t.equal_range(__x); williamr@2: } williamr@2: }; williamr@2: williamr@2: williamr@2: template ), williamr@2: _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) > williamr@2: class multimap williamr@2: { williamr@2: public: williamr@2: williamr@2: // typedefs: williamr@2: williamr@2: typedef _Key key_type; williamr@2: typedef _Tp data_type; williamr@2: typedef _Tp mapped_type; williamr@2: typedef pair value_type; williamr@2: typedef _Compare key_compare; williamr@2: williamr@2: class value_compare : public binary_function { williamr@2: friend class multimap<_Key,_Tp,_Compare,_Alloc>; williamr@2: protected: williamr@2: _Compare _M_comp; williamr@2: value_compare(_Compare __c) : _M_comp(__c) {} williamr@2: public: williamr@2: bool operator()(const value_type& __x, const value_type& __y) const { williamr@2: return _M_comp(__x.first, __y.first); williamr@2: } williamr@2: }; williamr@2: williamr@2: private: williamr@2: # ifdef _STLP_MULTI_CONST_TEMPLATE_ARG_BUG williamr@2: typedef _Rb_tree, key_compare, _Alloc> _Rep_type; williamr@2: # else williamr@2: typedef _Rb_tree, key_compare, _Alloc> _Rep_type; williamr@2: # endif williamr@2: _Rep_type _M_t; // red-black tree representing multimap williamr@2: public: williamr@2: typedef typename _Rep_type::pointer pointer; williamr@2: typedef typename _Rep_type::const_pointer const_pointer; williamr@2: typedef typename _Rep_type::reference reference; williamr@2: typedef typename _Rep_type::const_reference const_reference; williamr@2: typedef typename _Rep_type::iterator iterator; williamr@2: typedef typename _Rep_type::const_iterator const_iterator; williamr@2: typedef typename _Rep_type::reverse_iterator reverse_iterator; williamr@2: typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; williamr@2: typedef typename _Rep_type::size_type size_type; williamr@2: typedef typename _Rep_type::difference_type difference_type; williamr@2: typedef typename _Rep_type::allocator_type allocator_type; williamr@2: typedef multimap<_Key,_Tp,_Compare,_Alloc> _Self; williamr@2: williamr@2: // allocation/deallocation williamr@2: williamr@2: multimap() : _M_t(_Compare(), allocator_type()) { williamr@2: _STLP_POP_IF_CHECK williamr@2: } williamr@2: williamr@2: explicit multimap(const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_POP_IF_CHECK williamr@2: } williamr@2: williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template williamr@2: multimap(_InputIterator __first, _InputIterator __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS williamr@2: template williamr@2: multimap(_InputIterator __first, _InputIterator __last, williamr@2: const _Compare& __comp) williamr@2: : _M_t(__comp, allocator_type()) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: # endif williamr@2: template williamr@2: multimap(_InputIterator __first, _InputIterator __last, williamr@2: const _Compare& __comp, williamr@2: const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: #else williamr@2: multimap(const value_type* __first, const value_type* __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: multimap(const value_type* __first, const value_type* __last, williamr@2: const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: williamr@2: multimap(const_iterator __first, const_iterator __last) williamr@2: : _M_t(_Compare(), allocator_type()) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: multimap(const_iterator __first, const_iterator __last, williamr@2: const _Compare& __comp, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : _M_t(__comp, __a) { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t.insert_equal(__first, __last); williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: williamr@2: } williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: williamr@2: # ifdef _STLP_USE_TRAP_LEAVE williamr@2: multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) williamr@2: { williamr@2: _STLP_PUSH_CLEANUP_ITEM(_Self, this) williamr@2: _M_t =__x._M_t; williamr@2: _STLP_POP_CLEANUP_ITEM williamr@2: } williamr@2: # else williamr@2: multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { williamr@2: } williamr@2: # endif williamr@2: multimap<_Key,_Tp,_Compare,_Alloc>& williamr@2: operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) { williamr@2: _M_t = __x._M_t; williamr@2: return *this; williamr@2: } williamr@2: williamr@2: #ifdef _STLP_USE_TRAP_LEAVE williamr@2: public: williamr@2: static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper::_NewLC(__n); } williamr@2: static void* operator new (size_t __n) { return _STLP_StackHelper::_NewLC(__n); } williamr@2: #endif williamr@2: williamr@2: // accessors: williamr@2: williamr@2: key_compare key_comp() const { return _M_t.key_comp(); } williamr@2: value_compare value_comp() const { return value_compare(_M_t.key_comp()); } williamr@2: allocator_type get_allocator() const { return _M_t.get_allocator(); } williamr@2: williamr@2: iterator begin() { return _M_t.begin(); } williamr@2: const_iterator begin() const { return _M_t.begin(); } williamr@2: iterator end() { return _M_t.end(); } williamr@2: const_iterator end() const { return _M_t.end(); } williamr@2: reverse_iterator rbegin() { return _M_t.rbegin(); } williamr@2: const_reverse_iterator rbegin() const { return _M_t.rbegin(); } williamr@2: reverse_iterator rend() { return _M_t.rend(); } williamr@2: const_reverse_iterator rend() const { return _M_t.rend(); } williamr@2: bool empty() const { return _M_t.empty(); } williamr@2: size_type size() const { return _M_t.size(); } williamr@2: size_type max_size() const { return _M_t.max_size(); } williamr@2: void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } williamr@2: williamr@2: // insert/erase williamr@2: williamr@2: iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); } williamr@2: iterator insert(iterator __position, const value_type& __x) { williamr@2: return _M_t.insert_equal(__position, __x); williamr@2: } williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template williamr@2: void insert(_InputIterator __first, _InputIterator __last) { williamr@2: _M_t.insert_equal(__first, __last); williamr@2: } williamr@2: #else williamr@2: void insert(const value_type* __first, const value_type* __last) { williamr@2: _M_t.insert_equal(__first, __last); williamr@2: } williamr@2: void insert(const_iterator __first, const_iterator __last) { williamr@2: _M_t.insert_equal(__first, __last); williamr@2: } williamr@2: #endif /* _STLP_MEMBER_TEMPLATES */ williamr@2: void erase(iterator __position) { _M_t.erase(__position); } williamr@2: size_type erase(const key_type& __x) { return _M_t.erase(__x); } williamr@2: void erase(iterator __first, iterator __last) williamr@2: { _M_t.erase(__first, __last); } williamr@2: void clear() { _M_t.clear(); } williamr@2: williamr@2: // multimap operations: williamr@2: williamr@2: iterator find(const key_type& __x) { return _M_t.find(__x); } williamr@2: const_iterator find(const key_type& __x) const { return _M_t.find(__x); } williamr@2: size_type count(const key_type& __x) const { return _M_t.count(__x); } williamr@2: iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } williamr@2: const_iterator lower_bound(const key_type& __x) const { williamr@2: return _M_t.lower_bound(__x); williamr@2: } williamr@2: iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); } williamr@2: const_iterator upper_bound(const key_type& __x) const { williamr@2: return _M_t.upper_bound(__x); williamr@2: } williamr@2: pair equal_range(const key_type& __x) { williamr@2: return _M_t.equal_range(__x); williamr@2: } williamr@2: pair equal_range(const key_type& __x) const { williamr@2: return _M_t.equal_range(__x); williamr@2: } williamr@2: }; williamr@2: williamr@2: # define _STLP_TEMPLATE_HEADER template williamr@2: williamr@2: # define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc> williamr@2: williamr@2: // fbp : if this template header gets protected against your will, report it ! williamr@2: # include williamr@2: williamr@2: # undef _STLP_TEMPLATE_CONTAINER williamr@2: # define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc> williamr@2: williamr@2: // fbp : if this template header gets protected against your will, report it ! williamr@2: # include williamr@2: williamr@2: # undef _STLP_TEMPLATE_CONTAINER williamr@2: # undef _STLP_TEMPLATE_HEADER williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: // do a cleanup williamr@2: # undef map williamr@2: # undef multimap williamr@2: // provide a way to access full funclionality williamr@2: # define __map__ __FULL_NAME(map) williamr@2: # define __multimap__ __FULL_NAME(multimap) williamr@2: williamr@2: # ifdef _STLP_USE_WRAPPER_FOR_ALLOC_PARAM williamr@2: # include williamr@2: # endif williamr@2: williamr@2: #endif /* _STLP_INTERNAL_MAP_H */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: williamr@2: