File Coverage

/usr/include/c++/5/bits/stl_map.h
Criterion Covered Total %
statement 9 9 100.0
branch n/a
condition n/a
subroutine n/a
pod n/a
total 9 9 100.0


line stmt bran cond sub pod time code
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             // .
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
60             #include
61             #if __cplusplus >= 201103L
62             #include
63             #include
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.
81             *
82             * Meets the requirements of a container, a
83             * reversible container, and an
84             * associative container (using unique keys).
85             * For a @c map the key_type is Key, the mapped_type is T, and the
86             * value_type is std::pair.
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 ,
95             typename _Alloc = std::allocator > >
96 102           class map
97             {
98             public:
99             typedef _Key key_type;
100             typedef _Tp mapped_type;
101             typedef std::pair 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
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::other _Pair_alloc_type;
133              
134             typedef _Rb_tree,
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 34           map()
163             #if __cplusplus >= 201103L
164             noexcept(is_nothrow_default_constructible::value)
165             #endif
166 34           : _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 __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 __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
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
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
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 __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 267           begin() _GLIBCXX_NOEXCEPT
339 267           { 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 267           end() _GLIBCXX_NOEXCEPT
357 267           { 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)
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(__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)
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
557             std::pair
558 527           emplace(_Args&&... __args)
559 527           { 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
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
612             insert(const value_type& __x)
613             { return _M_t._M_insert_unique(__x); }
614              
615             #if __cplusplus >= 201103L
616             template
617             std::enable_if
618             _Pair&&>::value>::type>
619             std::pair
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 of pairs to be
628             * inserted.
629             *
630             * Complexity similar to that of the range constructor.
631             */
632             void
633             insert(std::initializer_list __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
670             std::enable_if
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
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
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
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
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
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
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
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
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
1009             equal_range(const key_type& __x)
1010             { return _M_t.equal_range(__x); }
1011              
1012             #if __cplusplus > 201103L
1013             template
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
1038             equal_range(const key_type& __x) const
1039             { return _M_t.equal_range(__x); }
1040              
1041             #if __cplusplus > 201103L
1042             template
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
1051             friend bool
1052             operator==(const map<_K1, _T1, _C1, _A1>&,
1053             const map<_K1, _T1, _C1, _A1>&);
1054              
1055             template
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
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
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
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
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
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
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
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 */