stl_map.h revision 97403
1163953Srrs// Map implementation -*- C++ -*-
2185694Srrs
3235828Stuexen// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
4235828Stuexen//
5163953Srrs// This file is part of the GNU ISO C++ Library.  This library is free
6163953Srrs// software; you can redistribute it and/or modify it under the
7163953Srrs// terms of the GNU General Public License as published by the
8163953Srrs// Free Software Foundation; either version 2, or (at your option)
9163953Srrs// any later version.
10228653Stuexen
11163953Srrs// This library is distributed in the hope that it will be useful,
12163953Srrs// but WITHOUT ANY WARRANTY; without even the implied warranty of
13163953Srrs// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14228653Stuexen// GNU General Public License for more details.
15163953Srrs
16163953Srrs// You should have received a copy of the GNU General Public License along
17163953Srrs// with this library; see the file COPYING.  If not, write to the Free
18163953Srrs// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19163953Srrs// USA.
20163953Srrs
21163953Srrs// As a special exception, you may use this file as part of a free software
22163953Srrs// library without restriction.  Specifically, if other files instantiate
23163953Srrs// templates or use macros or inline functions from this file, or you compile
24163953Srrs// this file and link it with other files to produce an executable, this
25163953Srrs// file does not by itself cause the resulting executable to be covered by
26163953Srrs// the GNU General Public License.  This exception does not however
27163953Srrs// invalidate any other reasons why the executable file might be covered by
28163953Srrs// the GNU General Public License.
29163953Srrs
30163953Srrs/*
31163953Srrs *
32163953Srrs * Copyright (c) 1994
33163953Srrs * Hewlett-Packard Company
34163953Srrs *
35163953Srrs * Permission to use, copy, modify, distribute and sell this software
36163953Srrs * and its documentation for any purpose is hereby granted without fee,
37163953Srrs * provided that the above copyright notice appear in all copies and
38167598Srrs * that both that copyright notice and this permission notice appear
39163953Srrs * in supporting documentation.  Hewlett-Packard Company makes no
40163953Srrs * representations about the suitability of this software for any
41163953Srrs * purpose.  It is provided "as is" without express or implied warranty.
42163953Srrs *
43163953Srrs *
44163953Srrs * Copyright (c) 1996,1997
45163953Srrs * Silicon Graphics Computer Systems, Inc.
46163953Srrs *
47170091Srrs * Permission to use, copy, modify, distribute and sell this software
48172091Srrs * and its documentation for any purpose is hereby granted without fee,
49188067Srrs * provided that the above copyright notice appear in all copies and
50179157Srrs * that both that copyright notice and this permission notice appear
51218211Srrs * in supporting documentation.  Silicon Graphics makes no
52163953Srrs * representations about the suitability of this software for any
53163953Srrs * purpose.  It is provided "as is" without express or implied warranty.
54163953Srrs */
55163953Srrs
56163953Srrs/** @file stl_map.h
57163953Srrs *  This is an internal header file, included by other library headers.
58163953Srrs *  You should not attempt to use it directly.
59163953Srrs */
60165220Srrs
61165220Srrs#ifndef _CPP_BITS_STL_MAP_H
62165220Srrs#define _CPP_BITS_STL_MAP_H 1
63165220Srrs
64165220Srrs#include <bits/concept_check.h>
65163953Srrs
66163953Srrsnamespace std
67165220Srrs{
68163953Srrs
69163953Srrs/**
70163953Srrs *  @brief A standard container made up of pairs (see std::pair in <utility>)
71165220Srrs *         which can be retrieved based on a key.
72165220Srrs *
73165220Srrs *  This is an associative container.  Values contained within it can be
74165220Srrs *  quickly retrieved through a key element.  Example:  MyMap["First"] would
75165220Srrs *  return the data associated with the key "First".
76165220Srrs*/
77163953Srrstemplate <class _Key, class _Tp, class _Compare = less<_Key>,
78163953Srrs          class _Alloc = allocator<pair<const _Key, _Tp> > >
79163953Srrsclass map
80163953Srrs{
81163953Srrs  // concept requirements
82163953Srrs  __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
83237715Stuexen  __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
84237715Stuexen
85237049Stuexenpublic:
86237049Stuexen  // typedefs:
87237049Stuexen  typedef _Key                 key_type;
88237049Stuexen  typedef _Tp                   data_type;
89163953Srrs  typedef _Tp                   mapped_type;
90163953Srrs  typedef pair<const _Key, _Tp> value_type;
91163953Srrs  typedef _Compare             key_compare;
92163953Srrs
93169420Srrs  class value_compare
94240148Stuexen    : public binary_function<value_type, value_type, bool> {
95172396Srrs  friend class map<_Key,_Tp,_Compare,_Alloc>;
96172396Srrs  protected :
97172396Srrs    _Compare comp;
98229774Stuexen    value_compare(_Compare __c) : comp(__c) {}
99163953Srrs  public:
100267723Stuexen    bool operator()(const value_type& __x, const value_type& __y) const {
101237715Stuexen      return comp(__x.first, __y.first);
102237049Stuexen    }
103179157Srrs  };
104168299Srrs
105168299Srrsprivate:
106172396Srrs  typedef _Rb_tree<key_type, value_type,
107163953Srrs                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
108163953Srrs  _Rep_type _M_t;  // red-black tree representing map
109229774Stuexenpublic:
110163953Srrs  typedef typename _Rep_type::pointer pointer;
111163953Srrs  typedef typename _Rep_type::const_pointer const_pointer;
112267723Stuexen  typedef typename _Rep_type::reference reference;
113237715Stuexen  typedef typename _Rep_type::const_reference const_reference;
114237049Stuexen  typedef typename _Rep_type::iterator iterator;
115179157Srrs  typedef typename _Rep_type::const_iterator const_iterator;
116168299Srrs  typedef typename _Rep_type::reverse_iterator reverse_iterator;
117168299Srrs  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
118172396Srrs  typedef typename _Rep_type::size_type size_type;
119163953Srrs  typedef typename _Rep_type::difference_type difference_type;
120163953Srrs  typedef typename _Rep_type::allocator_type allocator_type;
121163953Srrs
122267723Stuexen  // allocation/deallocation
123237715Stuexen
124237049Stuexen  map() : _M_t(_Compare(), allocator_type()) {}
125179157Srrs  explicit map(const _Compare& __comp,
126171440Srrs               const allocator_type& __a = allocator_type())
127171440Srrs    : _M_t(__comp, __a) {}
128172396Srrs
129163953Srrs  template <class _InputIterator>
130163953Srrs  map(_InputIterator __first, _InputIterator __last)
131163953Srrs    : _M_t(_Compare(), allocator_type())
132267723Stuexen    { _M_t.insert_unique(__first, __last); }
133237715Stuexen
134237049Stuexen  template <class _InputIterator>
135179157Srrs  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
136168299Srrs      const allocator_type& __a = allocator_type())
137168299Srrs    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
138172396Srrs  map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
139163953Srrs
140163953Srrs  map<_Key,_Tp,_Compare,_Alloc>&
141163953Srrs  operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
142267723Stuexen  {
143237715Stuexen    _M_t = __x._M_t;
144237049Stuexen    return *this;
145179157Srrs  }
146168299Srrs
147168299Srrs  // accessors:
148172396Srrs
149163953Srrs  key_compare key_comp() const { return _M_t.key_comp(); }
150163953Srrs  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
151229774Stuexen  allocator_type get_allocator() const { return _M_t.get_allocator(); }
152163953Srrs
153267723Stuexen  /**
154267723Stuexen   *  Returns a read/write iterator that points to the first pair in the map.
155267723Stuexen   *  Iteration is done in ascending order according to the keys.
156237049Stuexen  */
157237049Stuexen  iterator begin() { return _M_t.begin(); }
158168299Srrs
159168299Srrs  /**
160172396Srrs   *  Returns a read-only (constant) iterator that points to the first pair
161163953Srrs   *  in the map.  Iteration is done in ascending order according to the keys.
162229774Stuexen  */
163229774Stuexen  const_iterator begin() const { return _M_t.begin(); }
164229774Stuexen
165229774Stuexen  /**
166229774Stuexen   *  Returns a read/write iterator that points one past the last pair in the
167229774Stuexen   *  map.  Iteration is done in ascending order according to the keys.
168229774Stuexen  */
169229774Stuexen  iterator end() { return _M_t.end(); }
170229774Stuexen
171229774Stuexen  /**
172229774Stuexen   *  Returns a read-only (constant) iterator that points one past the last
173229774Stuexen   *  pair in the map.  Iteration is done in ascending order according to the
174229774Stuexen   *  keys.
175229774Stuexen  */
176229774Stuexen  const_iterator end() const { return _M_t.end(); }
177229774Stuexen
178229774Stuexen  /**
179229774Stuexen   *  Returns a read/write reverse iterator that points to the last pair in
180229774Stuexen   *  the map.  Iteration is done in descending order according to the keys.
181229774Stuexen  */
182229774Stuexen  reverse_iterator rbegin() { return _M_t.rbegin(); }
183229805Stuexen
184267723Stuexen  /**
185267723Stuexen   *  Returns a read-only (constant) reverse iterator that points to the last
186267723Stuexen   *  pair in the map.  Iteration is done in descending order according to
187237049Stuexen   *  the keys.
188237049Stuexen  */
189229805Stuexen  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
190229774Stuexen
191229774Stuexen  /**
192229774Stuexen   *  Returns a read/write reverse iterator that points to one before the
193229774Stuexen   *  first pair in the map.  Iteration is done in descending order according
194229774Stuexen   *  to the keys.
195229774Stuexen  */
196229774Stuexen  reverse_iterator rend() { return _M_t.rend(); }
197229774Stuexen
198229774Stuexen  /**
199237715Stuexen   *  Returns a read-only (constant) reverse iterator that points to one
200237715Stuexen   *  before the first pair in the map.  Iteration is done in descending order
201237049Stuexen   *  according to the keys.
202237049Stuexen  */
203229774Stuexen  const_reverse_iterator rend() const { return _M_t.rend(); }
204229774Stuexen
205172396Srrs  /** Returns true if the map is empty.  (Thus begin() would equal end().)  */
206172396Srrs  bool empty() const { return _M_t.empty(); }
207172396Srrs  /** Returns the size of the map.  */
208172396Srrs  size_type size() const { return _M_t.size(); }
209163953Srrs  /** Returns the maximum size of the map.  */
210163953Srrs  size_type max_size() const { return _M_t.max_size(); }
211163953Srrs
212163953Srrs  /**
213163953Srrs   *  @brief Subscript ( [] ) access to map data.
214171158Srrs   *  @param  k  The key for which data should be retrieved.
215171158Srrs   *
216221627Stuexen   *  Allows for easy lookup with the subscript ( [] ) operator.  Returns the
217221627Stuexen   *  data associated with the key specified in subscript.  If the key does
218221627Stuexen   *  not exist a pair with that key is created with a default value, which
219221627Stuexen   *  is then returned.
220221627Stuexen  */
221171158Srrs  _Tp& operator[](const key_type& __k) {
222171158Srrs    iterator __i = lower_bound(__k);
223217760Stuexen    // __i->first is greater than or equivalent to __k.
224217760Stuexen    if (__i == end() || key_comp()(__k, (*__i).first))
225171158Srrs      __i = insert(__i, value_type(__k, _Tp()));
226171158Srrs    return (*__i).second;
227171158Srrs  }
228171158Srrs
229171158Srrs  void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
230171158Srrs
231171158Srrs  // insert/erase
232171158Srrs  /**
233171158Srrs   *  @brief Attempts to insert a std::pair into the map.
234171158Srrs   *  @param  x  Pair to be inserted (see std::make_pair for easy creation of
235217760Stuexen   *             pairs).
236217760Stuexen   *  @return  A pair of which the first element is an iterator that points
237217760Stuexen   *           to the possibly inserted pair, a second element of type bool
238217760Stuexen   *           to show if the pair was actually inserted.
239217760Stuexen   *
240217760Stuexen   *  This function attempts to insert a (key, value) pair into the map.  A
241217760Stuexen   *  map relies on unique keys and thus a pair is only inserted if its first
242217760Stuexen   *  element (the key) is not already present in the map.
243171158Srrs  */
244171158Srrs  pair<iterator,bool> insert(const value_type& __x)
245171158Srrs    { return _M_t.insert_unique(__x); }
246171158Srrs
247171158Srrs  /**
248171158Srrs   *  @brief Attempts to insert a std::pair into the map.
249171158Srrs   *  @param  position  An iterator that serves as a hint as to where the
250171158Srrs   *                    pair should be inserted.
251171158Srrs   *  @param  x  Pair to be inserted (see std::make_pair for easy creation of
252171158Srrs   *             pairs).
253171158Srrs   *  @return  An iterator that points to the inserted (key,value) pair.
254171158Srrs   *
255171158Srrs   *  This function is not concerned about whether the insertion took place
256171158Srrs   *  or not and thus does not return a boolean like the single-argument
257171158Srrs   *  insert() does.  Note that the first parameter is only a hint and can
258171158Srrs   *  potentially improve the performance of the insertion process.  A bad
259217760Stuexen   *  hint would cause no gains in efficiency.
260217760Stuexen  */
261212712Stuexen  iterator insert(iterator position, const value_type& __x)
262212712Stuexen    { return _M_t.insert_unique(position, __x); }
263212712Stuexen
264212712Stuexen  /**
265171158Srrs   *  @brief A template function that attemps to insert elements from
266171158Srrs   *         another range (possibly another map).
267171158Srrs   *  @param  first  Iterator pointing to the start of the range to be inserted.
268171158Srrs   *  @param  last  Iterator pointing to the end of the range.
269221627Stuexen  */
270171158Srrs  template <class _InputIterator>
271171158Srrs  void insert(_InputIterator __first, _InputIterator __last) {
272216822Stuexen    _M_t.insert_unique(__first, __last);
273171158Srrs  }
274171158Srrs
275171158Srrs  /**
276171158Srrs   *  @brief Erases an element from a map.
277171158Srrs   *  @param  position  An iterator pointing to the element to be erased.
278171158Srrs   *
279171158Srrs   *  This function erases an element, pointed to by the given iterator, from
280163953Srrs   *  a map.  Note that this function only erases the element, and that if
281228653Stuexen   *  the element is itself a pointer, the pointed-to memory is not touched
282163953Srrs   *  in any way.  Managing the pointer is the user's responsibilty.
283163953Srrs  */
284163953Srrs  void erase(iterator __position) { _M_t.erase(__position); }
285163953Srrs
286163953Srrs  /**
287163953Srrs   *  @brief Erases an element according to the provided key.
288163953Srrs   *  @param  x  Key of element to be erased.
289163953Srrs   *  @return  Doc me! (Number of elements that match key? Only makes sense
290163953Srrs   *           with multimap)
291163953Srrs   *
292163953Srrs   *  This function erases an element, located by the given key, from a map.
293218129Srrs   *  Note that this function only erases the element, and that if
294218129Srrs   *  the element is itself a pointer, the pointed-to memory is not touched
295218129Srrs   *  in any way.  Managing the pointer is the user's responsibilty.
296212712Stuexen  */
297163953Srrs  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
298163953Srrs
299163953Srrs  /**
300179783Srrs   *  @brief Erases a [first,last) range of elements from a map.
301170744Srrs   *  @param  first  Iterator pointing to the start of the range to be erased.
302170744Srrs   *  @param  last  Iterator pointing to the end of the range to be erased.
303163953Srrs   *
304163953Srrs   *  This function erases a sequence of elements from a map.
305164181Srrs   *  Note that this function only erases the element, and that if
306163953Srrs   *  the element is itself a pointer, the pointed-to memory is not touched
307163953Srrs   *  in any way.  Managing the pointer is the user's responsibilty.
308163953Srrs  */
309216822Stuexen  void erase(iterator __first, iterator __last)
310216822Stuexen    { _M_t.erase(__first, __last); }
311163953Srrs
312196260Stuexen  /** Erases all elements in a map.  Note that this function only erases
313163953Srrs   *  the elements, and that if the elements themselves are pointers, the
314216822Stuexen   *  pointed-to memory is not touched in any way.  Managing the pointer is
315216822Stuexen   *  the user's responsibilty.
316216822Stuexen  */
317216822Stuexen  void clear() { _M_t.clear(); }
318242714Stuexen
319242714Stuexen  // map operations:
320242714Stuexen
321242714Stuexen  /**
322242714Stuexen   *  @brief Tries to locate an element in a map.
323242714Stuexen   *  @param  x  Key of (key, value) pair to be located.
324242714Stuexen   *  @return  Iterator pointing to sought-after element, or end() if not
325216822Stuexen   *           found.
326216822Stuexen   *
327235416Stuexen   *  This function takes a key and tries to locate the element with which
328235416Stuexen   *  the key matches.  If successful the function returns an iterator
329216822Stuexen   *  pointing to the sought after pair. If unsuccessful it returns the
330216822Stuexen   *  one past the end ( end() ) iterator.
331216822Stuexen  */
332196260Stuexen  iterator find(const key_type& __x) { return _M_t.find(__x); }
333196260Stuexen
334221627Stuexen  /**
335216822Stuexen   *  @brief Tries to locate an element in a map.
336196260Stuexen   *  @param  x  Key of (key, value) pair to be located.
337196260Stuexen   *  @return  Read-only (constant) iterator pointing to sought-after
338163953Srrs   *           element, or end() if not found.
339163953Srrs   *
340163953Srrs   *  This function takes a key and tries to locate the element with which
341216822Stuexen   *  the key matches.  If successful the function returns a constant iterator
342196260Stuexen   *  pointing to the sought after pair. If unsuccessful it returns the
343163953Srrs   *  one past the end ( end() ) iterator.
344163953Srrs  */
345235416Stuexen  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
346163953Srrs
347163953Srrs  /**
348163953Srrs   *  @brief Finds the number of elements with given key.
349163953Srrs   *  @param  x  Key of (key, value) pairs to be located.
350212712Stuexen   *  @return Number of elements with specified key.
351212712Stuexen   *
352212712Stuexen   *  This function only makes sense for multimaps.
353212712Stuexen  */
354163953Srrs  size_type count(const key_type& __x) const {
355221627Stuexen    return _M_t.find(__x) == _M_t.end() ? 0 : 1;
356169655Srrs  }
357163953Srrs
358163953Srrs  /**
359163953Srrs   *  @brief Finds the beginning of a subsequence matching given key.
360196260Stuexen   *  @param  x  Key of (key, value) pair to be located.
361163953Srrs   *  @return  Iterator pointing to first element matching given key, or
362163953Srrs   *           end() if not found.
363164181Srrs   *
364188854Srrs   *  This function is useful only with std::multimap.  It returns the first
365218129Srrs   *  element of a subsequence of elements that matches the given key.  If
366185694Srrs   *  unsuccessful it returns an iterator pointing to the first element that
367185694Srrs   *  has a greater value than given key or end() if no such element exists.
368179783Srrs  */
369170744Srrs  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
370170744Srrs
371163953Srrs  /**
372163953Srrs   *  @brief Finds the beginning of a subsequence matching given key.
373163953Srrs   *  @param  x  Key of (key, value) pair to be located.
374163953Srrs   *  @return  Read-only (constant) iterator pointing to first element
375180955Srrs   *           matching given key, or end() if not found.
376218129Srrs   *
377163953Srrs   *  This function is useful only with std::multimap.  It returns the first
378163953Srrs   *  element of a subsequence of elements that matches the given key.  If
379170091Srrs   *  unsuccessful the iterator will point to the next greatest element or,
380163953Srrs   *  if no such greater element exists, to end().
381163953Srrs  */
382216822Stuexen  const_iterator lower_bound(const key_type& __x) const {
383164181Srrs    return _M_t.lower_bound(__x);
384164181Srrs  }
385216822Stuexen
386164181Srrs  /**
387164181Srrs   *  @brief Finds the end of a subsequence matching given key.
388171158Srrs   *  @param  x  Key of (key, value) pair to be located.
389164181Srrs   *  @return Iterator pointing to last element matching given key.
390164181Srrs   *
391164181Srrs   *  This function only makes sense with multimaps.
392164181Srrs  */
393164181Srrs  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
394170091Srrs
395163953Srrs  /**
396252779Stuexen   *  @brief Finds the end of a subsequence matching given key.
397252779Stuexen   *  @param  x  Key of (key, value) pair to be located.
398252779Stuexen   *  @return  Read-only (constant) iterator pointing to last element matching
399252779Stuexen   *           given key.
400164181Srrs   *
401163953Srrs   *  This function only makes sense with multimaps.
402170091Srrs  */
403163953Srrs  const_iterator upper_bound(const key_type& __x) const {
404163953Srrs    return _M_t.upper_bound(__x);
405169420Srrs  }
406163953Srrs
407163953Srrs  /**
408163953Srrs   *  @brief Finds a subsequence matching given key.
409163953Srrs   *  @param  x  Key of (key, value) pairs to be located.
410163953Srrs   *  @return  Pair of iterators that possibly points to the subsequence
411163953Srrs   *           matching given key.
412168943Srrs   *
413163953Srrs   *  This function improves on lower_bound() and upper_bound() by giving a more
414163953Srrs   *  elegant and efficient solution.  It returns a pair of which the first
415163953Srrs   *  element possibly points to the first element matching the given key
416163953Srrs   *  and the second element possibly points to the last element matching the
417163953Srrs   *  given key.  If unsuccessful the first element of the returned pair will
418163953Srrs   *  contain an iterator pointing to the next greatest element or, if no such
419163953Srrs   *  greater element exists, to end().
420163953Srrs   *
421163953Srrs   *  This function only makes sense for multimaps.
422163953Srrs  */
423169655Srrs  pair<iterator,iterator> equal_range(const key_type& __x) {
424163953Srrs    return _M_t.equal_range(__x);
425163953Srrs  }
426163953Srrs
427163953Srrs  /**
428163953Srrs   *  @brief Finds a subsequence matching given key.
429163953Srrs   *  @param  x  Key of (key, value) pairs to be located.
430163953Srrs   *  @return  Pair of read-only (constant) iterators that possibly points to
431237715Stuexen   *           the subsequence matching given key.
432237715Stuexen   *
433237049Stuexen   *  This function improves on lower_bound() and upper_bound() by giving a more
434237049Stuexen   *  elegant and efficient solution.  It returns a pair of which the first
435237049Stuexen   *  element possibly points to the first element matching the given key
436237049Stuexen   *  and the second element possibly points to the last element matching the
437163953Srrs   *  given key.  If unsuccessful the first element of the returned pair will
438163953Srrs   *  contain an iterator pointing to the next greatest element or, if no such
439163953Srrs   *  a greater element exists, to end().
440163953Srrs   *
441163953Srrs   *  This function only makes sense for multimaps.
442185694Srrs  */
443163953Srrs  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
444163953Srrs    return _M_t.equal_range(__x);
445163953Srrs  }
446163953Srrs
447163953Srrs  template <class _K1, class _T1, class _C1, class _A1>
448163953Srrs  friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
449185694Srrs                          const map<_K1, _T1, _C1, _A1>&);
450163953Srrs  template <class _K1, class _T1, class _C1, class _A1>
451163953Srrs  friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
452235360Stuexen                         const map<_K1, _T1, _C1, _A1>&);
453170056Srrs};
454163953Srrs
455163953Srrstemplate <class _Key, class _Tp, class _Compare, class _Alloc>
456163953Srrsinline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
457185694Srrs                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
458163953Srrs  return __x._M_t == __y._M_t;
459228653Stuexen}
460163953Srrs
461163953Srrstemplate <class _Key, class _Tp, class _Compare, class _Alloc>
462163953Srrsinline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
463163953Srrs                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
464163953Srrs  return __x._M_t < __y._M_t;
465228653Stuexen}
466237715Stuexen
467237715Stuexentemplate <class _Key, class _Tp, class _Compare, class _Alloc>
468267723Stuexeninline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
469267723Stuexen                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
470169420Srrs  return !(__x == __y);
471169420Srrs}
472169420Srrs
473237715Stuexentemplate <class _Key, class _Tp, class _Compare, class _Alloc>
474267723Stuexeninline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
475237049Stuexen                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
476237049Stuexen  return __y < __x;
477168299Srrs}
478163953Srrs
479163953Srrstemplate <class _Key, class _Tp, class _Compare, class _Alloc>
480171477Srrsinline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
481171477Srrs                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
482216822Stuexen  return !(__y < __x);
483171477Srrs}
484216822Stuexen
485216822Stuexentemplate <class _Key, class _Tp, class _Compare, class _Alloc>
486216822Stuexeninline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
487171477Srrs                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
488171477Srrs  return !(__x < __y);
489163953Srrs}
490163953Srrs
491163953Srrstemplate <class _Key, class _Tp, class _Compare, class _Alloc>
492163953Srrsinline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
493163953Srrs                 map<_Key,_Tp,_Compare,_Alloc>& __y) {
494163953Srrs  __x.swap(__y);
495163953Srrs}
496163953Srrs
497179783Srrs} // namespace std
498171943Srrs
499171943Srrs#endif /* _CPP_BITS_STL_MAP_H */
500171943Srrs
501171943Srrs// Local Variables:
502171943Srrs// mode:C++
503171943Srrs// End:
504163953Srrs