diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_map.h')
-rw-r--r-- | contrib/libstdc++/include/bits/stl_map.h | 214 |
1 files changed, 130 insertions, 84 deletions
diff --git a/contrib/libstdc++/include/bits/stl_map.h b/contrib/libstdc++/include/bits/stl_map.h index 8535ae5..13e62bc 100644 --- a/contrib/libstdc++/include/bits/stl_map.h +++ b/contrib/libstdc++/include/bits/stl_map.h @@ -1,6 +1,7 @@ // Map implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 +// 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 @@ -15,7 +16,7 @@ // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software @@ -61,10 +62,11 @@ #ifndef _MAP_H #define _MAP_H 1 +#include <bits/functexcept.h> #include <bits/concept_check.h> -namespace _GLIBCXX_STD -{ +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) + /** * @brief A standard container made up of (key,value) pairs, which can be * retrieved based on a key, in logarithmic time. @@ -86,25 +88,30 @@ namespace _GLIBCXX_STD * called (*_unique versus *_equal, same as the standard). * @endif */ - template <typename _Key, typename _Tp, typename _Compare = less<_Key>, - typename _Alloc = allocator<pair<const _Key, _Tp> > > + template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, + typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > class map { + public: + typedef _Key key_type; + typedef _Tp mapped_type; + typedef std::pair<const _Key, _Tp> value_type; + typedef _Compare key_compare; + typedef _Alloc allocator_type; + + private: // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) + __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) public: - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const _Key, _Tp> value_type; - typedef _Compare key_compare; - class value_compare - : public binary_function<value_type, value_type, bool> + : public std::binary_function<value_type, value_type, bool> { - friend class map<_Key,_Tp,_Compare,_Alloc>; + friend class map<_Key, _Tp, _Compare, _Alloc>; protected: _Compare comp; @@ -118,19 +125,22 @@ namespace _GLIBCXX_STD private: /// @if maint This turns a red-black tree into a [multi]map. @endif - typedef _Rb_tree<key_type, value_type, - _Select1st<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<value_type>::other + _Pair_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, + key_compare, _Pair_alloc_type> _Rep_type; + /// @if maint The actual tree structure. @endif _Rep_type _M_t; public: // many of these are specified differently in ISO, but the following are // "functionally equivalent" - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Rep_type::allocator_type allocator_type; + typedef typename _Pair_alloc_type::pointer pointer; + typedef typename _Pair_alloc_type::const_pointer const_pointer; + typedef typename _Pair_alloc_type::reference reference; + typedef typename _Pair_alloc_type::const_reference const_reference; typedef typename _Rep_type::iterator iterator; typedef typename _Rep_type::const_iterator const_iterator; typedef typename _Rep_type::size_type size_type; @@ -177,7 +187,7 @@ namespace _GLIBCXX_STD template <typename _InputIterator> map(_InputIterator __first, _InputIterator __last) : _M_t(_Compare(), allocator_type()) - { _M_t.insert_unique(__first, __last); } + { _M_t._M_insert_unique(__first, __last); } /** * @brief Builds a %map from a range. @@ -194,11 +204,11 @@ namespace _GLIBCXX_STD map(_InputIterator __first, _InputIterator __last, const _Compare& __comp, const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) - { _M_t.insert_unique(__first, __last); } + { _M_t._M_insert_unique(__first, __last); } - // FIXME There is no dtor declared, but we should have something generated - // by Doxygen. I don't know what tags to add to this paragraph to make - // that happen: + // FIXME There is no dtor declared, but we should have something + // generated by Doxygen. I don't know what tags to add to this + // paragraph to make that happen: /** * The dtor only erases the elements, and note that if the elements * themselves are pointers, the pointed-to memory is not touched in any @@ -244,8 +254,9 @@ namespace _GLIBCXX_STD { return _M_t.begin(); } /** - * Returns a read/write iterator that points one past the last pair in - * the %map. Iteration is done in ascending order according to the keys. + * Returns a read/write iterator that points one past the last + * pair in the %map. Iteration is done in ascending order + * according to the keys. */ iterator end() @@ -320,10 +331,10 @@ namespace _GLIBCXX_STD * @param k The key for which data should be retrieved. * @return A reference to the data of the (key,data) %pair. * - * Allows for easy lookup with the subscript ( @c [] ) operator. Returns - * data associated with the key specified in subscript. If the key does - * not exist, a pair with that key is created using default values, which - * is then returned. + * Allows for easy lookup with the subscript ( @c [] ) + * operator. Returns data associated with the key specified in + * subscript. If the key does not exist, a pair with that key + * is created using default values, which is then returned. * * Lookup requires logarithmic time. */ @@ -340,14 +351,43 @@ namespace _GLIBCXX_STD return (*__i).second; } + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 464. Suggestion for new member functions in standard containers. + /** + * @brief Access to %map data. + * @param k The key for which data should be retrieved. + * @return A reference to the data whose key is equivalent to @a k, if + * such a data is present in the %map. + * @throw std::out_of_range If no such data is present. + */ + mapped_type& + at(const key_type& __k) + { + iterator __i = lower_bound(__k); + if (__i == end() || key_comp()(__k, (*__i).first)) + __throw_out_of_range(__N("map::at")); + return (*__i).second; + } + + const mapped_type& + at(const key_type& __k) const + { + const_iterator __i = lower_bound(__k); + if (__i == end() || key_comp()(__k, (*__i).first)) + __throw_out_of_range(__N("map::at")); + return (*__i).second; + } + // modifiers /** * @brief Attempts to insert a std::pair into the %map. - * @param x Pair to be inserted (see std::make_pair for easy creation of - * pairs). - * @return A pair, of which the first element is an iterator that points - * to the possibly inserted pair, and the second is a bool that - * is true if the pair was actually inserted. + + * @param x Pair to be inserted (see std::make_pair for easy creation + * of pairs). + + * @return A pair, of which the first element is an iterator that + * points to the possibly inserted pair, and the second is + * a bool that is true if the pair was actually inserted. * * This function attempts to insert a (key, value) %pair into the %map. * A %map relies on unique keys and thus a %pair is only inserted if its @@ -355,36 +395,39 @@ namespace _GLIBCXX_STD * * Insertion requires logarithmic time. */ - pair<iterator,bool> + std::pair<iterator, bool> insert(const value_type& __x) - { return _M_t.insert_unique(__x); } + { return _M_t._M_insert_unique(__x); } /** * @brief Attempts to insert a std::pair into the %map. * @param position An iterator that serves as a hint as to where the * pair should be inserted. - * @param x Pair to be inserted (see std::make_pair for easy creation of - * pairs). + * @param x Pair to be inserted (see std::make_pair for easy creation + * of pairs). * @return An iterator that points to the element with key of @a x (may * or may not be the %pair passed in). * - * This function is not concerned about whether the insertion took place, - * and thus does not return a boolean like the single-argument - * insert() does. Note that the first parameter is only a hint and can - * potentially improve the performance of the insertion process. A bad - * hint would cause no gains in efficiency. + + * This function is not concerned about whether the insertion + * took place, and thus does not return a boolean like the + * single-argument insert() does. Note that the first + * parameter is only a hint and can potentially improve the + * performance of the insertion process. A bad hint would + * cause no gains in efficiency. * - * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 + * See + * http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 * for more on "hinting". * * Insertion requires logarithmic time (if the hint is not taken). */ iterator - insert(iterator position, const value_type& __x) - { return _M_t.insert_unique(position, __x); } + insert(iterator __position, const value_type& __x) + { return _M_t._M_insert_unique(__position, __x); } /** - * @brief A template function that attemps to insert a range of elements. + * @brief Template function that attemps to insert a range of elements. * @param first Iterator pointing to the start of the range to be * inserted. * @param last Iterator pointing to the end of the range. @@ -394,16 +437,17 @@ namespace _GLIBCXX_STD template <typename _InputIterator> void insert(_InputIterator __first, _InputIterator __last) - { _M_t.insert_unique(__first, __last); } + { _M_t._M_insert_unique(__first, __last); } /** * @brief Erases an element from a %map. * @param position An iterator pointing to the element to be erased. * - * This function erases an element, pointed to by the given iterator, - * from a %map. Note that this function only erases the element, and - * that if the element is itself a pointer, the pointed-to memory is not - * touched in any way. Managing the pointer is the user's responsibilty. + * This function erases an element, pointed to by the given + * iterator, from a %map. Note that this function only erases + * the element, and that if the element is itself a pointer, + * the pointed-to memory is not touched in any way. Managing + * the pointer is the user's responsibilty. */ void erase(iterator __position) @@ -443,22 +487,22 @@ namespace _GLIBCXX_STD * @brief Swaps data with another %map. * @param x A %map of the same element and allocator types. * - * This exchanges the elements between two maps in constant time. - * (It is only swapping a pointer, an integer, and an instance of - * the @c Compare type (which itself is often stateless and empty), so it - * should be quite fast.) - * Note that the global std::swap() function is specialized such that - * std::swap(m1,m2) will feed to this function. + * This exchanges the elements between two maps in constant + * time. (It is only swapping a pointer, an integer, and an + * instance of the @c Compare type (which itself is often + * stateless and empty), so it should be quite fast.) Note + * that the global std::swap() function is specialized such + * that std::swap(m1,m2) will feed to this function. */ void swap(map& __x) { _M_t.swap(__x._M_t); } /** - * Erases all elements in a %map. Note that this function only erases - * the elements, and that if the elements themselves are pointers, the - * pointed-to memory is not touched in any way. Managing the pointer is - * the user's responsibilty. + * Erases all elements in a %map. Note that this function only + * erases the elements, and that if the elements themselves are + * pointers, the pointed-to memory is not touched in any way. + * Managing the pointer is the user's responsibilty. */ void clear() @@ -589,7 +633,7 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multimaps. */ - pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } @@ -608,19 +652,19 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multimaps. */ - pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator== (const map<_K1,_T1,_C1,_A1>&, - const map<_K1,_T1,_C1,_A1>&); + operator== (const map<_K1, _T1, _C1, _A1>&, + const map<_K1, _T1, _C1, _A1>&); template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator< (const map<_K1,_T1,_C1,_A1>&, - const map<_K1,_T1,_C1,_A1>&); + operator< (const map<_K1, _T1, _C1, _A1>&, + const map<_K1, _T1, _C1, _A1>&); }; /** @@ -635,8 +679,8 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -652,43 +696,45 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Based on operator== template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __y < __x; } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::map::swap(). template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline void - swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y) + swap(map<_Key, _Tp, _Compare, _Alloc>& __x, + map<_Key, _Tp, _Compare, _Alloc>& __y) { __x.swap(__y); } -} // namespace std + +_GLIBCXX_END_NESTED_NAMESPACE #endif /* _MAP_H */ |