contrib/gcc-5.0/libstdc++-v3/include/bits/stl_map.h

   1 // Map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/stl_map.h
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{map}
  54  */
  55
  56 #ifndef _STL_MAP_H
  57 #define _STL_MAP_H 1
  58
  59 #include <bits/functexcept.h>
  60 #include <bits/concept_check.h>
  61 #if __cplusplus >= 201103L
  62 #include <initializer_list>
  63 #include <tuple>
  64 #endif
  65
  66 namespace std _GLIBCXX_VISIBILITY(default)
  67 {
  68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  69
  70   /**
  71    *  @brief A standard container made up of (key,value) pairs, which can be
  72    *  retrieved based on a key, in logarithmic time.
  73    *
  74    *  @ingroup associative_containers
  75    *
  76    *  @tparam _Key  Type of key objects.
  77    *  @tparam  _Tp  Type of mapped objects.
  78    *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
  79    *  @tparam _Alloc  Allocator type, defaults to
  80    *                  allocator<pair<const _Key, _Tp>.
  81    *
  82    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
  83    *  <a href="tables.html#66">reversible container</a>, and an
  84    *  <a href="tables.html#69">associative container</a> (using unique keys).
  85    *  For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
  86    *  value_type is std::pair<const Key,T>.
  87    *
  88    *  Maps support bidirectional iterators.
  89    *
  90    *  The private tree data is declared exactly the same way for map and
  91    *  multimap; the distinction is made entirely in how the tree functions are
  92    *  called (*_unique versus *_equal, same as the standard).
  93   */
  94   template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  95             typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  96     class map
  97     {
  98     public:
  99       typedef _Key                                          key_type;
 100       typedef _Tp                                           mapped_type;
 101       typedef std::pair<const _Key, _Tp>                    value_type;
 102       typedef _Compare                                      key_compare;
 103       typedef _Alloc                                        allocator_type;
 104
 105     private:
 106       // concept requirements
 107       typedef typename _Alloc::value_type                   _Alloc_value_type;
 108       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 109       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
 110                                 _BinaryFunctionConcept)
 111       __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
 112
 113     public:
 114       class value_compare
 115       : public std::binary_function<value_type, value_type, bool>
 116       {
 117         friend class map<_Key, _Tp, _Compare, _Alloc>;
 118       protected:
 119         _Compare comp;
 120
 121         value_compare(_Compare __c)
 122         : comp(__c) { }
 123
 124       public:
 125         bool operator()(const value_type& __x, const value_type& __y) const
 126         { return comp(__x.first, __y.first); }
 127       };
 128
 129     private:
 130       /// This turns a red-black tree into a [multi]map.
 131       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
 132         rebind<value_type>::other _Pair_alloc_type;
 133
 134       typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
 135                        key_compare, _Pair_alloc_type> _Rep_type;
 136
 137       /// The actual tree structure.
 138       _Rep_type _M_t;
 139
 140       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
 141
 142     public:
 143       // many of these are specified differently in ISO, but the following are
 144       // "functionally equivalent"
 145       typedef typename _Alloc_traits::pointer            pointer;
 146       typedef typename _Alloc_traits::const_pointer      const_pointer;
 147       typedef typename _Alloc_traits::reference          reference;
 148       typedef typename _Alloc_traits::const_reference    const_reference;
 149       typedef typename _Rep_type::iterator               iterator;
 150       typedef typename _Rep_type::const_iterator         const_iterator;
 151       typedef typename _Rep_type::size_type              size_type;
 152       typedef typename _Rep_type::difference_type        difference_type;
 153       typedef typename _Rep_type::reverse_iterator       reverse_iterator;
 154       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
 155
 156       // [23.3.1.1] construct/copy/destroy
 157       // (get_allocator() is also listed in this section)
 158
 159       /**
 160        *  @brief  Default constructor creates no elements.
 161        */
 162       map()
 163 #if __cplusplus >= 201103L
 164       noexcept(is_nothrow_default_constructible<allocator_type>::value)
 165 #endif
 166       : _M_t() { }
 167
 168       /**
 169        *  @brief  Creates a %map with no elements.
 170        *  @param  __comp  A comparison object.
 171        *  @param  __a  An allocator object.
 172        */
 173       explicit
 174       map(const _Compare& __comp,
 175           const allocator_type& __a = allocator_type())
 176       : _M_t(__comp, _Pair_alloc_type(__a)) { }
 177
 178       /**
 179        *  @brief  %Map copy constructor.
 180        *  @param  __x  A %map of identical element and allocator types.
 181        *
 182        *  The newly-created %map uses a copy of the allocation object
 183        *  used by @a __x.
 184        */
 185       map(const map& __x)
 186       : _M_t(__x._M_t) { }
 187
 188 #if __cplusplus >= 201103L
 189       /**
 190        *  @brief  %Map move constructor.
 191        *  @param  __x  A %map of identical element and allocator types.
 192        *
 193        *  The newly-created %map contains the exact contents of @a __x.
 194        *  The contents of @a __x are a valid, but unspecified %map.
 195        */
 196       map(map&& __x)
 197       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 198       : _M_t(std::move(__x._M_t)) { }
 199
 200       /**
 201        *  @brief  Builds a %map from an initializer_list.
 202        *  @param  __l  An initializer_list.
 203        *  @param  __comp  A comparison object.
 204        *  @param  __a  An allocator object.
 205        *
 206        *  Create a %map consisting of copies of the elements in the
 207        *  initializer_list @a __l.
 208        *  This is linear in N if the range is already sorted, and NlogN
 209        *  otherwise (where N is @a __l.size()).
 210        */
 211       map(initializer_list<value_type> __l,
 212           const _Compare& __comp = _Compare(),
 213           const allocator_type& __a = allocator_type())
 214       : _M_t(__comp, _Pair_alloc_type(__a))
 215       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
 216
 217       /// Allocator-extended default constructor.
 218       explicit
 219       map(const allocator_type& __a)
 220       : _M_t(_Compare(), _Pair_alloc_type(__a)) { }
 221
 222       /// Allocator-extended copy constructor.
 223       map(const map& __m, const allocator_type& __a)
 224       : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }
 225
 226       /// Allocator-extended move constructor.
 227       map(map&& __m, const allocator_type& __a)
 228       noexcept(is_nothrow_copy_constructible<_Compare>::value
 229                && _Alloc_traits::_S_always_equal())
 230       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 231
 232       /// Allocator-extended initialier-list constructor.
 233       map(initializer_list<value_type> __l, const allocator_type& __a)
 234       : _M_t(_Compare(), _Pair_alloc_type(__a))
 235       { _M_t._M_insert_unique(__l.begin(), __l.end()); }
 236
 237       /// Allocator-extended range constructor.
 238       template<typename _InputIterator>
 239         map(_InputIterator __first, _InputIterator __last,
 240             const allocator_type& __a)
 241         : _M_t(_Compare(), _Pair_alloc_type(__a))
 242         { _M_t._M_insert_unique(__first, __last); }
 243 #endif
 244
 245       /**
 246        *  @brief  Builds a %map from a range.
 247        *  @param  __first  An input iterator.
 248        *  @param  __last  An input iterator.
 249        *
 250        *  Create a %map consisting of copies of the elements from
 251        *  [__first,__last).  This is linear in N if the range is
 252        *  already sorted, and NlogN otherwise (where N is
 253        *  distance(__first,__last)).
 254        */
 255       template<typename _InputIterator>
 256         map(_InputIterator __first, _InputIterator __last)
 257         : _M_t()
 258         { _M_t._M_insert_unique(__first, __last); }
 259
 260       /**
 261        *  @brief  Builds a %map from a range.
 262        *  @param  __first  An input iterator.
 263        *  @param  __last  An input iterator.
 264        *  @param  __comp  A comparison functor.
 265        *  @param  __a  An allocator object.
 266        *
 267        *  Create a %map consisting of copies of the elements from
 268        *  [__first,__last).  This is linear in N if the range is
 269        *  already sorted, and NlogN otherwise (where N is
 270        *  distance(__first,__last)).
 271        */
 272       template<typename _InputIterator>
 273         map(_InputIterator __first, _InputIterator __last,
 274             const _Compare& __comp,
 275             const allocator_type& __a = allocator_type())
 276         : _M_t(__comp, _Pair_alloc_type(__a))
 277         { _M_t._M_insert_unique(__first, __last); }
 278
 279       // FIXME There is no dtor declared, but we should have something
 280       // generated by Doxygen.  I don't know what tags to add to this
 281       // paragraph to make that happen:
 282       /**
 283        *  The dtor only erases the elements, and note that if the elements
 284        *  themselves are pointers, the pointed-to memory is not touched in any
 285        *  way.  Managing the pointer is the user's responsibility.
 286        */
 287
 288       /**
 289        *  @brief  %Map assignment operator.
 290        *  @param  __x  A %map of identical element and allocator types.
 291        *
 292        *  All the elements of @a __x are copied, but unlike the copy
 293        *  constructor, the allocator object is not copied.
 294        */
 295       map&
 296       operator=(const map& __x)
 297       {
 298         _M_t = __x._M_t;
 299         return *this;
 300       }
 301
 302 #if __cplusplus >= 201103L
 303       /// Move assignment operator.
 304       map&
 305       operator=(map&&) = default;
 306
 307       /**
 308        *  @brief  %Map list assignment operator.
 309        *  @param  __l  An initializer_list.
 310        *
 311        *  This function fills a %map with copies of the elements in the
 312        *  initializer list @a __l.
 313        *
 314        *  Note that the assignment completely changes the %map and
 315        *  that the resulting %map's size is the same as the number
 316        *  of elements assigned.  Old data may be lost.
 317        */
 318       map&
 319       operator=(initializer_list<value_type> __l)
 320       {
 321         _M_t._M_assign_unique(__l.begin(), __l.end());
 322         return *this;
 323       }
 324 #endif
 325
 326       /// Get a copy of the memory allocation object.
 327       allocator_type
 328       get_allocator() const _GLIBCXX_NOEXCEPT
 329       { return allocator_type(_M_t.get_allocator()); }
 330
 331       // iterators
 332       /**
 333        *  Returns a read/write iterator that points to the first pair in the
 334        *  %map.
 335        *  Iteration is done in ascending order according to the keys.
 336        */
 337       iterator
 338       begin() _GLIBCXX_NOEXCEPT
 339       { return _M_t.begin(); }
 340
 341       /**
 342        *  Returns a read-only (constant) iterator that points to the first pair
 343        *  in the %map.  Iteration is done in ascending order according to the
 344        *  keys.
 345        */
 346       const_iterator
 347       begin() const _GLIBCXX_NOEXCEPT
 348       { return _M_t.begin(); }
 349
 350       /**
 351        *  Returns a read/write iterator that points one past the last
 352        *  pair in the %map.  Iteration is done in ascending order
 353        *  according to the keys.
 354        */
 355       iterator
 356       end() _GLIBCXX_NOEXCEPT
 357       { return _M_t.end(); }
 358
 359       /**
 360        *  Returns a read-only (constant) iterator that points one past the last
 361        *  pair in the %map.  Iteration is done in ascending order according to
 362        *  the keys.
 363        */
 364       const_iterator
 365       end() const _GLIBCXX_NOEXCEPT
 366       { return _M_t.end(); }
 367
 368       /**
 369        *  Returns a read/write reverse iterator that points to the last pair in
 370        *  the %map.  Iteration is done in descending order according to the
 371        *  keys.
 372        */
 373       reverse_iterator
 374       rbegin() _GLIBCXX_NOEXCEPT
 375       { return _M_t.rbegin(); }
 376
 377       /**
 378        *  Returns a read-only (constant) reverse iterator that points to the
 379        *  last pair in the %map.  Iteration is done in descending order
 380        *  according to the keys.
 381        */
 382       const_reverse_iterator
 383       rbegin() const _GLIBCXX_NOEXCEPT
 384       { return _M_t.rbegin(); }
 385
 386       /**
 387        *  Returns a read/write reverse iterator that points to one before the
 388        *  first pair in the %map.  Iteration is done in descending order
 389        *  according to the keys.
 390        */
 391       reverse_iterator
 392       rend() _GLIBCXX_NOEXCEPT
 393       { return _M_t.rend(); }
 394
 395       /**
 396        *  Returns a read-only (constant) reverse iterator that points to one
 397        *  before the first pair in the %map.  Iteration is done in descending
 398        *  order according to the keys.
 399        */
 400       const_reverse_iterator
 401       rend() const _GLIBCXX_NOEXCEPT
 402       { return _M_t.rend(); }
 403
 404 #if __cplusplus >= 201103L
 405       /**
 406        *  Returns a read-only (constant) iterator that points to the first pair
 407        *  in the %map.  Iteration is done in ascending order according to the
 408        *  keys.
 409        */
 410       const_iterator
 411       cbegin() const noexcept
 412       { return _M_t.begin(); }
 413
 414       /**
 415        *  Returns a read-only (constant) iterator that points one past the last
 416        *  pair in the %map.  Iteration is done in ascending order according to
 417        *  the keys.
 418        */
 419       const_iterator
 420       cend() const noexcept
 421       { return _M_t.end(); }
 422
 423       /**
 424        *  Returns a read-only (constant) reverse iterator that points to the
 425        *  last pair in the %map.  Iteration is done in descending order
 426        *  according to the keys.
 427        */
 428       const_reverse_iterator
 429       crbegin() const noexcept
 430       { return _M_t.rbegin(); }
 431
 432       /**
 433        *  Returns a read-only (constant) reverse iterator that points to one
 434        *  before the first pair in the %map.  Iteration is done in descending
 435        *  order according to the keys.
 436        */
 437       const_reverse_iterator
 438       crend() const noexcept
 439       { return _M_t.rend(); }
 440 #endif
 441
 442       // capacity
 443       /** Returns true if the %map is empty.  (Thus begin() would equal
 444        *  end().)
 445       */
 446       bool
 447       empty() const _GLIBCXX_NOEXCEPT
 448       { return _M_t.empty(); }
 449
 450       /** Returns the size of the %map.  */
 451       size_type
 452       size() const _GLIBCXX_NOEXCEPT
 453       { return _M_t.size(); }
 454
 455       /** Returns the maximum size of the %map.  */
 456       size_type
 457       max_size() const _GLIBCXX_NOEXCEPT
 458       { return _M_t.max_size(); }
 459
 460       // [23.3.1.2] element access
 461       /**
 462        *  @brief  Subscript ( @c [] ) access to %map data.
 463        *  @param  __k  The key for which data should be retrieved.
 464        *  @return  A reference to the data of the (key,data) %pair.
 465        *
 466        *  Allows for easy lookup with the subscript ( @c [] )
 467        *  operator.  Returns data associated with the key specified in
 468        *  subscript.  If the key does not exist, a pair with that key
 469        *  is created using default values, which is then returned.
 470        *
 471        *  Lookup requires logarithmic time.
 472        */
 473       mapped_type&
 474       operator[](const key_type& __k)
 475       {
 476         // concept requirements
 477         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
 478
 479         iterator __i = lower_bound(__k);
 480         // __i->first is greater than or equivalent to __k.
 481         if (__i == end() || key_comp()(__k, (*__i).first))
 482 #if __cplusplus >= 201103L
 483           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
 484                                             std::tuple<const key_type&>(__k),
 485                                             std::tuple<>());
 486 #else
 487           __i = insert(__i, value_type(__k, mapped_type()));
 488 #endif
 489         return (*__i).second;
 490       }
 491
 492 #if __cplusplus >= 201103L
 493       mapped_type&
 494       operator[](key_type&& __k)
 495       {
 496         // concept requirements
 497         __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
 498
 499         iterator __i = lower_bound(__k);
 500         // __i->first is greater than or equivalent to __k.
 501         if (__i == end() || key_comp()(__k, (*__i).first))
 502           __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
 503                                         std::forward_as_tuple(std::move(__k)),
 504                                         std::tuple<>());
 505         return (*__i).second;
 506       }
 507 #endif
 508
 509       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 510       // DR 464. Suggestion for new member functions in standard containers.
 511       /**
 512        *  @brief  Access to %map data.
 513        *  @param  __k  The key for which data should be retrieved.
 514        *  @return  A reference to the data whose key is equivalent to @a __k, if
 515        *           such a data is present in the %map.
 516        *  @throw  std::out_of_range  If no such data is present.
 517        */
 518       mapped_type&
 519       at(const key_type& __k)
 520       {
 521         iterator __i = lower_bound(__k);
 522         if (__i == end() || key_comp()(__k, (*__i).first))
 523           __throw_out_of_range(__N("map::at"));
 524         return (*__i).second;
 525       }
 526
 527       const mapped_type&
 528       at(const key_type& __k) const
 529       {
 530         const_iterator __i = lower_bound(__k);
 531         if (__i == end() || key_comp()(__k, (*__i).first))
 532           __throw_out_of_range(__N("map::at"));
 533         return (*__i).second;
 534       }
 535
 536       // modifiers
 537 #if __cplusplus >= 201103L
 538       /**
 539        *  @brief Attempts to build and insert a std::pair into the %map.
 540        *
 541        *  @param __args  Arguments used to generate a new pair instance (see
 542        *                std::piecewise_contruct for passing arguments to each
 543        *                part of the pair constructor).
 544        *
 545        *  @return  A pair, of which the first element is an iterator that points
 546        *           to the possibly inserted pair, and the second is a bool that
 547        *           is true if the pair was actually inserted.
 548        *
 549        *  This function attempts to build and insert a (key, value) %pair into
 550        *  the %map.
 551        *  A %map relies on unique keys and thus a %pair is only inserted if its
 552        *  first element (the key) is not already present in the %map.
 553        *
 554        *  Insertion requires logarithmic time.
 555        */
 556       template<typename... _Args>
 557         std::pair<iterator, bool>
 558         emplace(_Args&&... __args)
 559         { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
 560
 561       /**
 562        *  @brief Attempts to build and insert a std::pair into the %map.
 563        *
 564        *  @param  __pos  An iterator that serves as a hint as to where the pair
 565        *                should be inserted.
 566        *  @param  __args  Arguments used to generate a new pair instance (see
 567        *                 std::piecewise_contruct for passing arguments to each
 568        *                 part of the pair constructor).
 569        *  @return An iterator that points to the element with key of the
 570        *          std::pair built from @a __args (may or may not be that
 571        *          std::pair).
 572        *
 573        *  This function is not concerned about whether the insertion took place,
 574        *  and thus does not return a boolean like the single-argument emplace()
 575        *  does.
 576        *  Note that the first parameter is only a hint and can potentially
 577        *  improve the performance of the insertion process. A bad hint would
 578        *  cause no gains in efficiency.
 579        *
 580        *  See
 581        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
 582        *  for more on @a hinting.
 583        *
 584        *  Insertion requires logarithmic time (if the hint is not taken).
 585        */
 586       template<typename... _Args>
 587         iterator
 588         emplace_hint(const_iterator __pos, _Args&&... __args)
 589         {
 590           return _M_t._M_emplace_hint_unique(__pos,
 591                                              std::forward<_Args>(__args)...);
 592         }
 593 #endif
 594
 595       /**
 596        *  @brief Attempts to insert a std::pair into the %map.
 597
 598        *  @param __x Pair to be inserted (see std::make_pair for easy
 599        *             creation of pairs).
 600        *
 601        *  @return  A pair, of which the first element is an iterator that
 602        *           points to the possibly inserted pair, and the second is
 603        *           a bool that is true if the pair was actually inserted.
 604        *
 605        *  This function attempts to insert a (key, value) %pair into the %map.
 606        *  A %map relies on unique keys and thus a %pair is only inserted if its
 607        *  first element (the key) is not already present in the %map.
 608        *
 609        *  Insertion requires logarithmic time.
 610        */
 611       std::pair<iterator, bool>
 612       insert(const value_type& __x)
 613       { return _M_t._M_insert_unique(__x); }
 614
 615 #if __cplusplus >= 201103L
 616       template<typename _Pair, typename = typename
 617                std::enable_if<std::is_constructible<value_type,
 618                                                     _Pair&&>::value>::type>
 619         std::pair<iterator, bool>
 620         insert(_Pair&& __x)
 621         { return _M_t._M_insert_unique(std::forward<_Pair>(__x)); }
 622 #endif
 623
 624 #if __cplusplus >= 201103L
 625       /**
 626        *  @brief Attempts to insert a list of std::pairs into the %map.
 627        *  @param  __list  A std::initializer_list<value_type> of pairs to be
 628        *                  inserted.
 629        *
 630        *  Complexity similar to that of the range constructor.
 631        */
 632       void
 633       insert(std::initializer_list<value_type> __list)
 634       { insert(__list.begin(), __list.end()); }
 635 #endif
 636
 637       /**
 638        *  @brief Attempts to insert a std::pair into the %map.
 639        *  @param  __position  An iterator that serves as a hint as to where the
 640        *                    pair should be inserted.
 641        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
 642        *               of pairs).
 643        *  @return An iterator that points to the element with key of
 644        *           @a __x (may or may not be the %pair passed in).
 645        *
 646
 647        *  This function is not concerned about whether the insertion
 648        *  took place, and thus does not return a boolean like the
 649        *  single-argument insert() does.  Note that the first
 650        *  parameter is only a hint and can potentially improve the
 651        *  performance of the insertion process.  A bad hint would
 652        *  cause no gains in efficiency.
 653        *
 654        *  See
 655        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
 656        *  for more on @a hinting.
 657        *
 658        *  Insertion requires logarithmic time (if the hint is not taken).
 659        */
 660       iterator
 661 #if __cplusplus >= 201103L
 662       insert(const_iterator __position, const value_type& __x)
 663 #else
 664       insert(iterator __position, const value_type& __x)
 665 #endif
 666       { return _M_t._M_insert_unique_(__position, __x); }
 667
 668 #if __cplusplus >= 201103L
 669       template<typename _Pair, typename = typename
 670                std::enable_if<std::is_constructible<value_type,
 671                                                     _Pair&&>::value>::type>
 672         iterator
 673         insert(const_iterator __position, _Pair&& __x)
 674         { return _M_t._M_insert_unique_(__position,
 675                                         std::forward<_Pair>(__x)); }
 676 #endif
 677
 678       /**
 679        *  @brief Template function that attempts to insert a range of elements.
 680        *  @param  __first  Iterator pointing to the start of the range to be
 681        *                   inserted.
 682        *  @param  __last  Iterator pointing to the end of the range.
 683        *
 684        *  Complexity similar to that of the range constructor.
 685        */
 686       template<typename _InputIterator>
 687         void
 688         insert(_InputIterator __first, _InputIterator __last)
 689         { _M_t._M_insert_unique(__first, __last); }
 690
 691 #if __cplusplus >= 201103L
 692       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 693       // DR 130. Associative erase should return an iterator.
 694       /**
 695        *  @brief Erases an element from a %map.
 696        *  @param  __position  An iterator pointing to the element to be erased.
 697        *  @return An iterator pointing to the element immediately following
 698        *          @a position prior to the element being erased. If no such
 699        *          element exists, end() is returned.
 700        *
 701        *  This function erases an element, pointed to by the given
 702        *  iterator, from a %map.  Note that this function only erases
 703        *  the element, and that if the element is itself a pointer,
 704        *  the pointed-to memory is not touched in any way.  Managing
 705        *  the pointer is the user's responsibility.
 706        */
 707       iterator
 708       erase(const_iterator __position)
 709       { return _M_t.erase(__position); }
 710
 711       // LWG 2059
 712       _GLIBCXX_ABI_TAG_CXX11
 713       iterator
 714       erase(iterator __position)
 715       { return _M_t.erase(__position); }
 716 #else
 717       /**
 718        *  @brief Erases an element from a %map.
 719        *  @param  __position  An iterator pointing to the element to be erased.
 720        *
 721        *  This function erases an element, pointed to by the given
 722        *  iterator, from a %map.  Note that this function only erases
 723        *  the element, and that if the element is itself a pointer,
 724        *  the pointed-to memory is not touched in any way.  Managing
 725        *  the pointer is the user's responsibility.
 726        */
 727       void
 728       erase(iterator __position)
 729       { _M_t.erase(__position); }
 730 #endif
 731
 732       /**
 733        *  @brief Erases elements according to the provided key.
 734        *  @param  __x  Key of element to be erased.
 735        *  @return  The number of elements erased.
 736        *
 737        *  This function erases all the elements located by the given key from
 738        *  a %map.
 739        *  Note that this function only erases the element, and that if
 740        *  the element is itself a pointer, the pointed-to memory is not touched
 741        *  in any way.  Managing the pointer is the user's responsibility.
 742        */
 743       size_type
 744       erase(const key_type& __x)
 745       { return _M_t.erase(__x); }
 746
 747 #if __cplusplus >= 201103L
 748       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 749       // DR 130. Associative erase should return an iterator.
 750       /**
 751        *  @brief Erases a [first,last) range of elements from a %map.
 752        *  @param  __first  Iterator pointing to the start of the range to be
 753        *                   erased.
 754        *  @param __last Iterator pointing to the end of the range to
 755        *                be erased.
 756        *  @return The iterator @a __last.
 757        *
 758        *  This function erases a sequence of elements from a %map.
 759        *  Note that this function only erases the element, and that if
 760        *  the element is itself a pointer, the pointed-to memory is not touched
 761        *  in any way.  Managing the pointer is the user's responsibility.
 762        */
 763       iterator
 764       erase(const_iterator __first, const_iterator __last)
 765       { return _M_t.erase(__first, __last); }
 766 #else
 767       /**
 768        *  @brief Erases a [__first,__last) range of elements from a %map.
 769        *  @param  __first  Iterator pointing to the start of the range to be
 770        *                   erased.
 771        *  @param __last Iterator pointing to the end of the range to
 772        *                be erased.
 773        *
 774        *  This function erases a sequence of elements from a %map.
 775        *  Note that this function only erases the element, and that if
 776        *  the element is itself a pointer, the pointed-to memory is not touched
 777        *  in any way.  Managing the pointer is the user's responsibility.
 778        */
 779       void
 780       erase(iterator __first, iterator __last)
 781       { _M_t.erase(__first, __last); }
 782 #endif
 783
 784       /**
 785        *  @brief  Swaps data with another %map.
 786        *  @param  __x  A %map of the same element and allocator types.
 787        *
 788        *  This exchanges the elements between two maps in constant
 789        *  time.  (It is only swapping a pointer, an integer, and an
 790        *  instance of the @c Compare type (which itself is often
 791        *  stateless and empty), so it should be quite fast.)  Note
 792        *  that the global std::swap() function is specialized such
 793        *  that std::swap(m1,m2) will feed to this function.
 794        */
 795       void
 796       swap(map& __x)
 797 #if __cplusplus >= 201103L
 798       noexcept(_Alloc_traits::_S_nothrow_swap())
 799 #endif
 800       { _M_t.swap(__x._M_t); }
 801
 802       /**
 803        *  Erases all elements in a %map.  Note that this function only
 804        *  erases the elements, and that if the elements themselves are
 805        *  pointers, the pointed-to memory is not touched in any way.
 806        *  Managing the pointer is the user's responsibility.
 807        */
 808       void
 809       clear() _GLIBCXX_NOEXCEPT
 810       { _M_t.clear(); }
 811
 812       // observers
 813       /**
 814        *  Returns the key comparison object out of which the %map was
 815        *  constructed.
 816        */
 817       key_compare
 818       key_comp() const
 819       { return _M_t.key_comp(); }
 820
 821       /**
 822        *  Returns a value comparison object, built from the key comparison
 823        *  object out of which the %map was constructed.
 824        */
 825       value_compare
 826       value_comp() const
 827       { return value_compare(_M_t.key_comp()); }
 828
 829       // [23.3.1.3] map operations
 830
 831       //@{
 832       /**
 833        *  @brief Tries to locate an element in a %map.
 834        *  @param  __x  Key of (key, value) %pair to be located.
 835        *  @return  Iterator pointing to sought-after element, or end() if not
 836        *           found.
 837        *
 838        *  This function takes a key and tries to locate the element with which
 839        *  the key matches.  If successful the function returns an iterator
 840        *  pointing to the sought after %pair.  If unsuccessful it returns the
 841        *  past-the-end ( @c end() ) iterator.
 842        */
 843
 844       iterator
 845       find(const key_type& __x)
 846       { return _M_t.find(__x); }
 847
 848 #if __cplusplus > 201103L
 849       template<typename _Kt>
 850         auto
 851         find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
 852         { return _M_t._M_find_tr(__x); }
 853 #endif
 854       //@}
 855
 856       //@{
 857       /**
 858        *  @brief Tries to locate an element in a %map.
 859        *  @param  __x  Key of (key, value) %pair to be located.
 860        *  @return  Read-only (constant) iterator pointing to sought-after
 861        *           element, or end() if not found.
 862        *
 863        *  This function takes a key and tries to locate the element with which
 864        *  the key matches.  If successful the function returns a constant
 865        *  iterator pointing to the sought after %pair. If unsuccessful it
 866        *  returns the past-the-end ( @c end() ) iterator.
 867        */
 868
 869       const_iterator
 870       find(const key_type& __x) const
 871       { return _M_t.find(__x); }
 872
 873 #if __cplusplus > 201103L
 874       template<typename _Kt>
 875         auto
 876         find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
 877         { return _M_t._M_find_tr(__x); }
 878 #endif
 879       //@}
 880
 881       //@{
 882       /**
 883        *  @brief  Finds the number of elements with given key.
 884        *  @param  __x  Key of (key, value) pairs to be located.
 885        *  @return  Number of elements with specified key.
 886        *
 887        *  This function only makes sense for multimaps; for map the result will
 888        *  either be 0 (not present) or 1 (present).
 889        */
 890       size_type
 891       count(const key_type& __x) const
 892       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
 893
 894 #if __cplusplus > 201103L
 895       template<typename _Kt>
 896         auto
 897         count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
 898         { return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; }
 899 #endif
 900       //@}
 901
 902       //@{
 903       /**
 904        *  @brief Finds the beginning of a subsequence matching given key.
 905        *  @param  __x  Key of (key, value) pair to be located.
 906        *  @return  Iterator pointing to first element equal to or greater
 907        *           than key, or end().
 908        *
 909        *  This function returns the first element of a subsequence of elements
 910        *  that matches the given key.  If unsuccessful it returns an iterator
 911        *  pointing to the first element that has a greater value than given key
 912        *  or end() if no such element exists.
 913        */
 914       iterator
 915       lower_bound(const key_type& __x)
 916       { return _M_t.lower_bound(__x); }
 917
 918 #if __cplusplus > 201103L
 919       template<typename _Kt>
 920         auto
 921         lower_bound(const _Kt& __x)
 922         -> decltype(_M_t._M_lower_bound_tr(__x))
 923         { return _M_t._M_lower_bound_tr(__x); }
 924 #endif
 925       //@}
 926
 927       //@{
 928       /**
 929        *  @brief Finds the beginning of a subsequence matching given key.
 930        *  @param  __x  Key of (key, value) pair to be located.
 931        *  @return  Read-only (constant) iterator pointing to first element
 932        *           equal to or greater than key, or end().
 933        *
 934        *  This function returns the first element of a subsequence of elements
 935        *  that matches the given key.  If unsuccessful it returns an iterator
 936        *  pointing to the first element that has a greater value than given key
 937        *  or end() if no such element exists.
 938        */
 939       const_iterator
 940       lower_bound(const key_type& __x) const
 941       { return _M_t.lower_bound(__x); }
 942
 943 #if __cplusplus > 201103L
 944       template<typename _Kt>
 945         auto
 946         lower_bound(const _Kt& __x) const
 947         -> decltype(_M_t._M_lower_bound_tr(__x))
 948         { return _M_t._M_lower_bound_tr(__x); }
 949 #endif
 950       //@}
 951
 952       //@{
 953       /**
 954        *  @brief Finds the end of a subsequence matching given key.
 955        *  @param  __x  Key of (key, value) pair to be located.
 956        *  @return Iterator pointing to the first element
 957        *          greater than key, or end().
 958        */
 959       iterator
 960       upper_bound(const key_type& __x)
 961       { return _M_t.upper_bound(__x); }
 962
 963 #if __cplusplus > 201103L
 964       template<typename _Kt>
 965         auto
 966         upper_bound(const _Kt& __x)
 967         -> decltype(_M_t._M_upper_bound_tr(__x))
 968         { return _M_t._M_upper_bound_tr(__x); }
 969 #endif
 970       //@}
 971
 972       //@{
 973       /**
 974        *  @brief Finds the end of a subsequence matching given key.
 975        *  @param  __x  Key of (key, value) pair to be located.
 976        *  @return  Read-only (constant) iterator pointing to first iterator
 977        *           greater than key, or end().
 978        */
 979       const_iterator
 980       upper_bound(const key_type& __x) const
 981       { return _M_t.upper_bound(__x); }
 982
 983 #if __cplusplus > 201103L
 984       template<typename _Kt>
 985         auto
 986         upper_bound(const _Kt& __x) const
 987         -> decltype(_M_t._M_upper_bound_tr(__x))
 988         { return _M_t._M_upper_bound_tr(__x); }
 989 #endif
 990       //@}
 991
 992       //@{
 993       /**
 994        *  @brief Finds a subsequence matching given key.
 995        *  @param  __x  Key of (key, value) pairs to be located.
 996        *  @return  Pair of iterators that possibly points to the subsequence
 997        *           matching given key.
 998        *
 999        *  This function is equivalent to
1000        *  @code
1001        *    std::make_pair(c.lower_bound(val),
1002        *                   c.upper_bound(val))
1003        *  @endcode
1004        *  (but is faster than making the calls separately).
1005        *
1006        *  This function probably only makes sense for multimaps.
1007        */
1008       std::pair<iterator, iterator>
1009       equal_range(const key_type& __x)
1010       { return _M_t.equal_range(__x); }
1011
1012 #if __cplusplus > 201103L
1013       template<typename _Kt>
1014         auto
1015         equal_range(const _Kt& __x)
1016         -> decltype(_M_t._M_equal_range_tr(__x))
1017         { return _M_t._M_equal_range_tr(__x); }
1018 #endif
1019       //@}
1020
1021       //@{
1022       /**
1023        *  @brief Finds a subsequence matching given key.
1024        *  @param  __x  Key of (key, value) pairs to be located.
1025        *  @return  Pair of read-only (constant) iterators that possibly points
1026        *           to the subsequence matching given key.
1027        *
1028        *  This function is equivalent to
1029        *  @code
1030        *    std::make_pair(c.lower_bound(val),
1031        *                   c.upper_bound(val))
1032        *  @endcode
1033        *  (but is faster than making the calls separately).
1034        *
1035        *  This function probably only makes sense for multimaps.
1036        */
1037       std::pair<const_iterator, const_iterator>
1038       equal_range(const key_type& __x) const
1039       { return _M_t.equal_range(__x); }
1040
1041 #if __cplusplus > 201103L
1042       template<typename _Kt>
1043         auto
1044         equal_range(const _Kt& __x) const
1045         -> decltype(_M_t._M_equal_range_tr(__x))
1046         { return _M_t._M_equal_range_tr(__x); }
1047 #endif
1048       //@}
1049
1050       template<typename _K1, typename _T1, typename _C1, typename _A1>
1051         friend bool
1052         operator==(const map<_K1, _T1, _C1, _A1>&,
1053                    const map<_K1, _T1, _C1, _A1>&);
1054
1055       template<typename _K1, typename _T1, typename _C1, typename _A1>
1056         friend bool
1057         operator<(const map<_K1, _T1, _C1, _A1>&,
1058                   const map<_K1, _T1, _C1, _A1>&);
1059     };
1060
1061   /**
1062    *  @brief  Map equality comparison.
1063    *  @param  __x  A %map.
1064    *  @param  __y  A %map of the same type as @a x.
1065    *  @return  True iff the size and elements of the maps are equal.
1066    *
1067    *  This is an equivalence relation.  It is linear in the size of the
1068    *  maps.  Maps are considered equivalent if their sizes are equal,
1069    *  and if corresponding elements compare equal.
1070   */
1071   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1072     inline bool
1073     operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1074                const map<_Key, _Tp, _Compare, _Alloc>& __y)
1075     { return __x._M_t == __y._M_t; }
1076
1077   /**
1078    *  @brief  Map ordering relation.
1079    *  @param  __x  A %map.
1080    *  @param  __y  A %map of the same type as @a x.
1081    *  @return  True iff @a x is lexicographically less than @a y.
1082    *
1083    *  This is a total ordering relation.  It is linear in the size of the
1084    *  maps.  The elements must be comparable with @c <.
1085    *
1086    *  See std::lexicographical_compare() for how the determination is made.
1087   */
1088   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1089     inline bool
1090     operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1091               const map<_Key, _Tp, _Compare, _Alloc>& __y)
1092     { return __x._M_t < __y._M_t; }
1093
1094   /// Based on operator==
1095   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1096     inline bool
1097     operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1098                const map<_Key, _Tp, _Compare, _Alloc>& __y)
1099     { return !(__x == __y); }
1100
1101   /// Based on operator<
1102   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1103     inline bool
1104     operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1105               const map<_Key, _Tp, _Compare, _Alloc>& __y)
1106     { return __y < __x; }
1107
1108   /// Based on operator<
1109   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1110     inline bool
1111     operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1112                const map<_Key, _Tp, _Compare, _Alloc>& __y)
1113     { return !(__y < __x); }
1114
1115   /// Based on operator<
1116   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1117     inline bool
1118     operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
1119                const map<_Key, _Tp, _Compare, _Alloc>& __y)
1120     { return !(__x < __y); }
1121
1122   /// See std::map::swap().
1123   template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
1124     inline void
1125     swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
1126          map<_Key, _Tp, _Compare, _Alloc>& __y)
1127     { __x.swap(__y); }
1128
1129 _GLIBCXX_END_NAMESPACE_CONTAINER
1130 } // namespace std
1131
1132 #endif /* _STL_MAP_H */