stl_map.h revision 97403
197403Sobrien// Map implementation -*- C++ -*-
297403Sobrien
397403Sobrien// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
497403Sobrien//
597403Sobrien// This file is part of the GNU ISO C++ Library.  This library is free
697403Sobrien// software; you can redistribute it and/or modify it under the
797403Sobrien// terms of the GNU General Public License as published by the
897403Sobrien// Free Software Foundation; either version 2, or (at your option)
997403Sobrien// any later version.
1097403Sobrien
1197403Sobrien// This library is distributed in the hope that it will be useful,
1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of
1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1497403Sobrien// GNU General Public License for more details.
1597403Sobrien
1697403Sobrien// You should have received a copy of the GNU General Public License along
1797403Sobrien// with this library; see the file COPYING.  If not, write to the Free
1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
1997403Sobrien// USA.
2097403Sobrien
2197403Sobrien// As a special exception, you may use this file as part of a free software
2297403Sobrien// library without restriction.  Specifically, if other files instantiate
2397403Sobrien// templates or use macros or inline functions from this file, or you compile
2497403Sobrien// this file and link it with other files to produce an executable, this
2597403Sobrien// file does not by itself cause the resulting executable to be covered by
2697403Sobrien// the GNU General Public License.  This exception does not however
2797403Sobrien// invalidate any other reasons why the executable file might be covered by
2897403Sobrien// the GNU General Public License.
2997403Sobrien
3097403Sobrien/*
3197403Sobrien *
3297403Sobrien * Copyright (c) 1994
3397403Sobrien * Hewlett-Packard Company
3497403Sobrien *
3597403Sobrien * Permission to use, copy, modify, distribute and sell this software
3697403Sobrien * and its documentation for any purpose is hereby granted without fee,
3797403Sobrien * provided that the above copyright notice appear in all copies and
3897403Sobrien * that both that copyright notice and this permission notice appear
3997403Sobrien * in supporting documentation.  Hewlett-Packard Company makes no
4097403Sobrien * representations about the suitability of this software for any
4197403Sobrien * purpose.  It is provided "as is" without express or implied warranty.
4297403Sobrien *
4397403Sobrien *
4497403Sobrien * Copyright (c) 1996,1997
4597403Sobrien * Silicon Graphics Computer Systems, Inc.
4697403Sobrien *
4797403Sobrien * Permission to use, copy, modify, distribute and sell this software
4897403Sobrien * and its documentation for any purpose is hereby granted without fee,
4997403Sobrien * provided that the above copyright notice appear in all copies and
5097403Sobrien * that both that copyright notice and this permission notice appear
5197403Sobrien * in supporting documentation.  Silicon Graphics makes no
5297403Sobrien * representations about the suitability of this software for any
5397403Sobrien * purpose.  It is provided "as is" without express or implied warranty.
5497403Sobrien */
5597403Sobrien
5697403Sobrien/** @file stl_map.h
5797403Sobrien *  This is an internal header file, included by other library headers.
5897403Sobrien *  You should not attempt to use it directly.
5997403Sobrien */
6097403Sobrien
6197403Sobrien#ifndef _CPP_BITS_STL_MAP_H
6297403Sobrien#define _CPP_BITS_STL_MAP_H 1
6397403Sobrien
6497403Sobrien#include <bits/concept_check.h>
6597403Sobrien
6697403Sobriennamespace std
6797403Sobrien{
6897403Sobrien
6997403Sobrien/**
7097403Sobrien *  @brief A standard container made up of pairs (see std::pair in <utility>)
7197403Sobrien *         which can be retrieved based on a key.
7297403Sobrien *
7397403Sobrien *  This is an associative container.  Values contained within it can be
7497403Sobrien *  quickly retrieved through a key element.  Example:  MyMap["First"] would
7597403Sobrien *  return the data associated with the key "First".
7697403Sobrien*/
7797403Sobrientemplate <class _Key, class _Tp, class _Compare = less<_Key>,
7897403Sobrien          class _Alloc = allocator<pair<const _Key, _Tp> > >
7997403Sobrienclass map
8097403Sobrien{
8197403Sobrien  // concept requirements
8297403Sobrien  __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
8397403Sobrien  __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
8497403Sobrien
8597403Sobrienpublic:
8697403Sobrien  // typedefs:
8797403Sobrien  typedef _Key                 key_type;
8897403Sobrien  typedef _Tp                   data_type;
8997403Sobrien  typedef _Tp                   mapped_type;
9097403Sobrien  typedef pair<const _Key, _Tp> value_type;
9197403Sobrien  typedef _Compare             key_compare;
9297403Sobrien
9397403Sobrien  class value_compare
9497403Sobrien    : public binary_function<value_type, value_type, bool> {
9597403Sobrien  friend class map<_Key,_Tp,_Compare,_Alloc>;
9697403Sobrien  protected :
9797403Sobrien    _Compare comp;
9897403Sobrien    value_compare(_Compare __c) : comp(__c) {}
9997403Sobrien  public:
10097403Sobrien    bool operator()(const value_type& __x, const value_type& __y) const {
10197403Sobrien      return comp(__x.first, __y.first);
10297403Sobrien    }
10397403Sobrien  };
10497403Sobrien
10597403Sobrienprivate:
10697403Sobrien  typedef _Rb_tree<key_type, value_type,
10797403Sobrien                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
10897403Sobrien  _Rep_type _M_t;  // red-black tree representing map
10997403Sobrienpublic:
11097403Sobrien  typedef typename _Rep_type::pointer pointer;
11197403Sobrien  typedef typename _Rep_type::const_pointer const_pointer;
11297403Sobrien  typedef typename _Rep_type::reference reference;
11397403Sobrien  typedef typename _Rep_type::const_reference const_reference;
11497403Sobrien  typedef typename _Rep_type::iterator iterator;
11597403Sobrien  typedef typename _Rep_type::const_iterator const_iterator;
11697403Sobrien  typedef typename _Rep_type::reverse_iterator reverse_iterator;
11797403Sobrien  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
11897403Sobrien  typedef typename _Rep_type::size_type size_type;
11997403Sobrien  typedef typename _Rep_type::difference_type difference_type;
12097403Sobrien  typedef typename _Rep_type::allocator_type allocator_type;
12197403Sobrien
12297403Sobrien  // allocation/deallocation
12397403Sobrien
12497403Sobrien  map() : _M_t(_Compare(), allocator_type()) {}
12597403Sobrien  explicit map(const _Compare& __comp,
12697403Sobrien               const allocator_type& __a = allocator_type())
12797403Sobrien    : _M_t(__comp, __a) {}
12897403Sobrien
12997403Sobrien  template <class _InputIterator>
13097403Sobrien  map(_InputIterator __first, _InputIterator __last)
13197403Sobrien    : _M_t(_Compare(), allocator_type())
13297403Sobrien    { _M_t.insert_unique(__first, __last); }
13397403Sobrien
13497403Sobrien  template <class _InputIterator>
13597403Sobrien  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
13697403Sobrien      const allocator_type& __a = allocator_type())
13797403Sobrien    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
13897403Sobrien  map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
13997403Sobrien
14097403Sobrien  map<_Key,_Tp,_Compare,_Alloc>&
14197403Sobrien  operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
14297403Sobrien  {
14397403Sobrien    _M_t = __x._M_t;
14497403Sobrien    return *this;
14597403Sobrien  }
14697403Sobrien
14797403Sobrien  // accessors:
14897403Sobrien
14997403Sobrien  key_compare key_comp() const { return _M_t.key_comp(); }
15097403Sobrien  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
15197403Sobrien  allocator_type get_allocator() const { return _M_t.get_allocator(); }
15297403Sobrien
15397403Sobrien  /**
15497403Sobrien   *  Returns a read/write iterator that points to the first pair in the map.
15597403Sobrien   *  Iteration is done in ascending order according to the keys.
15697403Sobrien  */
15797403Sobrien  iterator begin() { return _M_t.begin(); }
15897403Sobrien
15997403Sobrien  /**
16097403Sobrien   *  Returns a read-only (constant) iterator that points to the first pair
16197403Sobrien   *  in the map.  Iteration is done in ascending order according to the keys.
16297403Sobrien  */
16397403Sobrien  const_iterator begin() const { return _M_t.begin(); }
16497403Sobrien
16597403Sobrien  /**
16697403Sobrien   *  Returns a read/write iterator that points one past the last pair in the
16797403Sobrien   *  map.  Iteration is done in ascending order according to the keys.
16897403Sobrien  */
16997403Sobrien  iterator end() { return _M_t.end(); }
17097403Sobrien
17197403Sobrien  /**
17297403Sobrien   *  Returns a read-only (constant) iterator that points one past the last
17397403Sobrien   *  pair in the map.  Iteration is done in ascending order according to the
17497403Sobrien   *  keys.
17597403Sobrien  */
17697403Sobrien  const_iterator end() const { return _M_t.end(); }
17797403Sobrien
17897403Sobrien  /**
17997403Sobrien   *  Returns a read/write reverse iterator that points to the last pair in
18097403Sobrien   *  the map.  Iteration is done in descending order according to the keys.
18197403Sobrien  */
18297403Sobrien  reverse_iterator rbegin() { return _M_t.rbegin(); }
18397403Sobrien
18497403Sobrien  /**
18597403Sobrien   *  Returns a read-only (constant) reverse iterator that points to the last
18697403Sobrien   *  pair in the map.  Iteration is done in descending order according to
18797403Sobrien   *  the keys.
18897403Sobrien  */
18997403Sobrien  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
19097403Sobrien
19197403Sobrien  /**
19297403Sobrien   *  Returns a read/write reverse iterator that points to one before the
19397403Sobrien   *  first pair in the map.  Iteration is done in descending order according
19497403Sobrien   *  to the keys.
19597403Sobrien  */
19697403Sobrien  reverse_iterator rend() { return _M_t.rend(); }
19797403Sobrien
19897403Sobrien  /**
19997403Sobrien   *  Returns a read-only (constant) reverse iterator that points to one
20097403Sobrien   *  before the first pair in the map.  Iteration is done in descending order
20197403Sobrien   *  according to the keys.
20297403Sobrien  */
20397403Sobrien  const_reverse_iterator rend() const { return _M_t.rend(); }
20497403Sobrien
20597403Sobrien  /** Returns true if the map is empty.  (Thus begin() would equal end().)  */
20697403Sobrien  bool empty() const { return _M_t.empty(); }
20797403Sobrien  /** Returns the size of the map.  */
20897403Sobrien  size_type size() const { return _M_t.size(); }
20997403Sobrien  /** Returns the maximum size of the map.  */
21097403Sobrien  size_type max_size() const { return _M_t.max_size(); }
21197403Sobrien
21297403Sobrien  /**
21397403Sobrien   *  @brief Subscript ( [] ) access to map data.
21497403Sobrien   *  @param  k  The key for which data should be retrieved.
21597403Sobrien   *
21697403Sobrien   *  Allows for easy lookup with the subscript ( [] ) operator.  Returns the
21797403Sobrien   *  data associated with the key specified in subscript.  If the key does
21897403Sobrien   *  not exist a pair with that key is created with a default value, which
21997403Sobrien   *  is then returned.
22097403Sobrien  */
22197403Sobrien  _Tp& operator[](const key_type& __k) {
22297403Sobrien    iterator __i = lower_bound(__k);
22397403Sobrien    // __i->first is greater than or equivalent to __k.
22497403Sobrien    if (__i == end() || key_comp()(__k, (*__i).first))
22597403Sobrien      __i = insert(__i, value_type(__k, _Tp()));
22697403Sobrien    return (*__i).second;
22797403Sobrien  }
22897403Sobrien
22997403Sobrien  void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
23097403Sobrien
23197403Sobrien  // insert/erase
23297403Sobrien  /**
23397403Sobrien   *  @brief Attempts to insert a std::pair into the map.
23497403Sobrien   *  @param  x  Pair to be inserted (see std::make_pair for easy creation of
23597403Sobrien   *             pairs).
23697403Sobrien   *  @return  A pair of which the first element is an iterator that points
23797403Sobrien   *           to the possibly inserted pair, a second element of type bool
23897403Sobrien   *           to show if the pair was actually inserted.
23997403Sobrien   *
24097403Sobrien   *  This function attempts to insert a (key, value) pair into the map.  A
24197403Sobrien   *  map relies on unique keys and thus a pair is only inserted if its first
24297403Sobrien   *  element (the key) is not already present in the map.
24397403Sobrien  */
24497403Sobrien  pair<iterator,bool> insert(const value_type& __x)
24597403Sobrien    { return _M_t.insert_unique(__x); }
24697403Sobrien
24797403Sobrien  /**
24897403Sobrien   *  @brief Attempts to insert a std::pair into the map.
24997403Sobrien   *  @param  position  An iterator that serves as a hint as to where the
25097403Sobrien   *                    pair should be inserted.
25197403Sobrien   *  @param  x  Pair to be inserted (see std::make_pair for easy creation of
25297403Sobrien   *             pairs).
25397403Sobrien   *  @return  An iterator that points to the inserted (key,value) pair.
25497403Sobrien   *
25597403Sobrien   *  This function is not concerned about whether the insertion took place
25697403Sobrien   *  or not and thus does not return a boolean like the single-argument
25797403Sobrien   *  insert() does.  Note that the first parameter is only a hint and can
25897403Sobrien   *  potentially improve the performance of the insertion process.  A bad
25997403Sobrien   *  hint would cause no gains in efficiency.
26097403Sobrien  */
26197403Sobrien  iterator insert(iterator position, const value_type& __x)
26297403Sobrien    { return _M_t.insert_unique(position, __x); }
26397403Sobrien
26497403Sobrien  /**
26597403Sobrien   *  @brief A template function that attemps to insert elements from
26697403Sobrien   *         another range (possibly another map).
26797403Sobrien   *  @param  first  Iterator pointing to the start of the range to be inserted.
26897403Sobrien   *  @param  last  Iterator pointing to the end of the range.
26997403Sobrien  */
27097403Sobrien  template <class _InputIterator>
27197403Sobrien  void insert(_InputIterator __first, _InputIterator __last) {
27297403Sobrien    _M_t.insert_unique(__first, __last);
27397403Sobrien  }
27497403Sobrien
27597403Sobrien  /**
27697403Sobrien   *  @brief Erases an element from a map.
27797403Sobrien   *  @param  position  An iterator pointing to the element to be erased.
27897403Sobrien   *
27997403Sobrien   *  This function erases an element, pointed to by the given iterator, from
28097403Sobrien   *  a map.  Note that this function only erases the element, and that if
28197403Sobrien   *  the element is itself a pointer, the pointed-to memory is not touched
28297403Sobrien   *  in any way.  Managing the pointer is the user's responsibilty.
28397403Sobrien  */
28497403Sobrien  void erase(iterator __position) { _M_t.erase(__position); }
28597403Sobrien
28697403Sobrien  /**
28797403Sobrien   *  @brief Erases an element according to the provided key.
28897403Sobrien   *  @param  x  Key of element to be erased.
28997403Sobrien   *  @return  Doc me! (Number of elements that match key? Only makes sense
29097403Sobrien   *           with multimap)
29197403Sobrien   *
29297403Sobrien   *  This function erases an element, located by the given key, from a map.
29397403Sobrien   *  Note that this function only erases the element, and that if
29497403Sobrien   *  the element is itself a pointer, the pointed-to memory is not touched
29597403Sobrien   *  in any way.  Managing the pointer is the user's responsibilty.
29697403Sobrien  */
29797403Sobrien  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
29897403Sobrien
29997403Sobrien  /**
30097403Sobrien   *  @brief Erases a [first,last) range of elements from a map.
30197403Sobrien   *  @param  first  Iterator pointing to the start of the range to be erased.
30297403Sobrien   *  @param  last  Iterator pointing to the end of the range to be erased.
30397403Sobrien   *
30497403Sobrien   *  This function erases a sequence of elements from a map.
30597403Sobrien   *  Note that this function only erases the element, and that if
30697403Sobrien   *  the element is itself a pointer, the pointed-to memory is not touched
30797403Sobrien   *  in any way.  Managing the pointer is the user's responsibilty.
30897403Sobrien  */
30997403Sobrien  void erase(iterator __first, iterator __last)
31097403Sobrien    { _M_t.erase(__first, __last); }
31197403Sobrien
31297403Sobrien  /** Erases all elements in a map.  Note that this function only erases
31397403Sobrien   *  the elements, and that if the elements themselves are pointers, the
31497403Sobrien   *  pointed-to memory is not touched in any way.  Managing the pointer is
31597403Sobrien   *  the user's responsibilty.
31697403Sobrien  */
31797403Sobrien  void clear() { _M_t.clear(); }
31897403Sobrien
31997403Sobrien  // map operations:
32097403Sobrien
32197403Sobrien  /**
32297403Sobrien   *  @brief Tries to locate an element in a map.
32397403Sobrien   *  @param  x  Key of (key, value) pair to be located.
32497403Sobrien   *  @return  Iterator pointing to sought-after element, or end() if not
32597403Sobrien   *           found.
32697403Sobrien   *
32797403Sobrien   *  This function takes a key and tries to locate the element with which
32897403Sobrien   *  the key matches.  If successful the function returns an iterator
32997403Sobrien   *  pointing to the sought after pair. If unsuccessful it returns the
33097403Sobrien   *  one past the end ( end() ) iterator.
33197403Sobrien  */
33297403Sobrien  iterator find(const key_type& __x) { return _M_t.find(__x); }
33397403Sobrien
33497403Sobrien  /**
33597403Sobrien   *  @brief Tries to locate an element in a map.
33697403Sobrien   *  @param  x  Key of (key, value) pair to be located.
33797403Sobrien   *  @return  Read-only (constant) iterator pointing to sought-after
33897403Sobrien   *           element, or end() if not found.
33997403Sobrien   *
34097403Sobrien   *  This function takes a key and tries to locate the element with which
34197403Sobrien   *  the key matches.  If successful the function returns a constant iterator
34297403Sobrien   *  pointing to the sought after pair. If unsuccessful it returns the
34397403Sobrien   *  one past the end ( end() ) iterator.
34497403Sobrien  */
34597403Sobrien  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
34697403Sobrien
34797403Sobrien  /**
34897403Sobrien   *  @brief Finds the number of elements with given key.
34997403Sobrien   *  @param  x  Key of (key, value) pairs to be located.
35097403Sobrien   *  @return Number of elements with specified key.
35197403Sobrien   *
35297403Sobrien   *  This function only makes sense for multimaps.
35397403Sobrien  */
35497403Sobrien  size_type count(const key_type& __x) const {
35597403Sobrien    return _M_t.find(__x) == _M_t.end() ? 0 : 1;
35697403Sobrien  }
35797403Sobrien
35897403Sobrien  /**
35997403Sobrien   *  @brief Finds the beginning of a subsequence matching given key.
36097403Sobrien   *  @param  x  Key of (key, value) pair to be located.
36197403Sobrien   *  @return  Iterator pointing to first element matching given key, or
36297403Sobrien   *           end() if not found.
36397403Sobrien   *
36497403Sobrien   *  This function is useful only with std::multimap.  It returns the first
36597403Sobrien   *  element of a subsequence of elements that matches the given key.  If
36697403Sobrien   *  unsuccessful it returns an iterator pointing to the first element that
36797403Sobrien   *  has a greater value than given key or end() if no such element exists.
36897403Sobrien  */
36997403Sobrien  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
37097403Sobrien
37197403Sobrien  /**
37297403Sobrien   *  @brief Finds the beginning of a subsequence matching given key.
37397403Sobrien   *  @param  x  Key of (key, value) pair to be located.
37497403Sobrien   *  @return  Read-only (constant) iterator pointing to first element
37597403Sobrien   *           matching given key, or end() if not found.
37697403Sobrien   *
37797403Sobrien   *  This function is useful only with std::multimap.  It returns the first
37897403Sobrien   *  element of a subsequence of elements that matches the given key.  If
37997403Sobrien   *  unsuccessful the iterator will point to the next greatest element or,
38097403Sobrien   *  if no such greater element exists, to end().
38197403Sobrien  */
38297403Sobrien  const_iterator lower_bound(const key_type& __x) const {
38397403Sobrien    return _M_t.lower_bound(__x);
38497403Sobrien  }
38597403Sobrien
38697403Sobrien  /**
38797403Sobrien   *  @brief Finds the end of a subsequence matching given key.
38897403Sobrien   *  @param  x  Key of (key, value) pair to be located.
38997403Sobrien   *  @return Iterator pointing to last element matching given key.
39097403Sobrien   *
39197403Sobrien   *  This function only makes sense with multimaps.
39297403Sobrien  */
39397403Sobrien  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
39497403Sobrien
39597403Sobrien  /**
39697403Sobrien   *  @brief Finds the end of a subsequence matching given key.
39797403Sobrien   *  @param  x  Key of (key, value) pair to be located.
39897403Sobrien   *  @return  Read-only (constant) iterator pointing to last element matching
39997403Sobrien   *           given key.
40097403Sobrien   *
40197403Sobrien   *  This function only makes sense with multimaps.
40297403Sobrien  */
40397403Sobrien  const_iterator upper_bound(const key_type& __x) const {
40497403Sobrien    return _M_t.upper_bound(__x);
40597403Sobrien  }
40697403Sobrien
40797403Sobrien  /**
40897403Sobrien   *  @brief Finds a subsequence matching given key.
40997403Sobrien   *  @param  x  Key of (key, value) pairs to be located.
41097403Sobrien   *  @return  Pair of iterators that possibly points to the subsequence
41197403Sobrien   *           matching given key.
41297403Sobrien   *
41397403Sobrien   *  This function improves on lower_bound() and upper_bound() by giving a more
41497403Sobrien   *  elegant and efficient solution.  It returns a pair of which the first
41597403Sobrien   *  element possibly points to the first element matching the given key
41697403Sobrien   *  and the second element possibly points to the last element matching the
41797403Sobrien   *  given key.  If unsuccessful the first element of the returned pair will
41897403Sobrien   *  contain an iterator pointing to the next greatest element or, if no such
41997403Sobrien   *  greater element exists, to end().
42097403Sobrien   *
42197403Sobrien   *  This function only makes sense for multimaps.
42297403Sobrien  */
42397403Sobrien  pair<iterator,iterator> equal_range(const key_type& __x) {
42497403Sobrien    return _M_t.equal_range(__x);
42597403Sobrien  }
42697403Sobrien
42797403Sobrien  /**
42897403Sobrien   *  @brief Finds a subsequence matching given key.
42997403Sobrien   *  @param  x  Key of (key, value) pairs to be located.
43097403Sobrien   *  @return  Pair of read-only (constant) iterators that possibly points to
43197403Sobrien   *           the subsequence matching given key.
43297403Sobrien   *
43397403Sobrien   *  This function improves on lower_bound() and upper_bound() by giving a more
43497403Sobrien   *  elegant and efficient solution.  It returns a pair of which the first
43597403Sobrien   *  element possibly points to the first element matching the given key
43697403Sobrien   *  and the second element possibly points to the last element matching the
43797403Sobrien   *  given key.  If unsuccessful the first element of the returned pair will
43897403Sobrien   *  contain an iterator pointing to the next greatest element or, if no such
43997403Sobrien   *  a greater element exists, to end().
44097403Sobrien   *
44197403Sobrien   *  This function only makes sense for multimaps.
44297403Sobrien  */
44397403Sobrien  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
44497403Sobrien    return _M_t.equal_range(__x);
44597403Sobrien  }
44697403Sobrien
44797403Sobrien  template <class _K1, class _T1, class _C1, class _A1>
44897403Sobrien  friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
44997403Sobrien                          const map<_K1, _T1, _C1, _A1>&);
45097403Sobrien  template <class _K1, class _T1, class _C1, class _A1>
45197403Sobrien  friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
45297403Sobrien                         const map<_K1, _T1, _C1, _A1>&);
45397403Sobrien};
45497403Sobrien
45597403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
45697403Sobrieninline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
45797403Sobrien                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
45897403Sobrien  return __x._M_t == __y._M_t;
45997403Sobrien}
46097403Sobrien
46197403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
46297403Sobrieninline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
46397403Sobrien                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
46497403Sobrien  return __x._M_t < __y._M_t;
46597403Sobrien}
46697403Sobrien
46797403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
46897403Sobrieninline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
46997403Sobrien                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
47097403Sobrien  return !(__x == __y);
47197403Sobrien}
47297403Sobrien
47397403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
47497403Sobrieninline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
47597403Sobrien                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
47697403Sobrien  return __y < __x;
47797403Sobrien}
47897403Sobrien
47997403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
48097403Sobrieninline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
48197403Sobrien                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
48297403Sobrien  return !(__y < __x);
48397403Sobrien}
48497403Sobrien
48597403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
48697403Sobrieninline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
48797403Sobrien                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
48897403Sobrien  return !(__x < __y);
48997403Sobrien}
49097403Sobrien
49197403Sobrientemplate <class _Key, class _Tp, class _Compare, class _Alloc>
49297403Sobrieninline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
49397403Sobrien                 map<_Key,_Tp,_Compare,_Alloc>& __y) {
49497403Sobrien  __x.swap(__y);
49597403Sobrien}
49697403Sobrien
49797403Sobrien} // namespace std
49897403Sobrien
49997403Sobrien#endif /* _CPP_BITS_STL_MAP_H */
50097403Sobrien
50197403Sobrien// Local Variables:
50297403Sobrien// mode:C++
50397403Sobrien// End:
504