| 1 | // Debugging multimap implementation -*- C++ -*-
|
|---|
| 2 |
|
|---|
| 3 | // Copyright (C) 2003-2021 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 | /** @file debug/multimap.h
|
|---|
| 26 | * This file is a GNU debug extension to the Standard C++ Library.
|
|---|
| 27 | */
|
|---|
| 28 |
|
|---|
| 29 | #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
|
|---|
| 30 | #define _GLIBCXX_DEBUG_MULTIMAP_H 1
|
|---|
| 31 |
|
|---|
| 32 | #include <debug/safe_sequence.h>
|
|---|
| 33 | #include <debug/safe_container.h>
|
|---|
| 34 | #include <debug/safe_iterator.h>
|
|---|
| 35 | #include <utility>
|
|---|
| 36 |
|
|---|
| 37 | namespace std _GLIBCXX_VISIBILITY(default)
|
|---|
| 38 | {
|
|---|
| 39 | namespace __debug
|
|---|
| 40 | {
|
|---|
| 41 | /// Class std::multimap with safety/checking/debug instrumentation.
|
|---|
| 42 | template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
|
|---|
| 43 | typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
|
|---|
| 44 | class multimap
|
|---|
| 45 | : public __gnu_debug::_Safe_container<
|
|---|
| 46 | multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator,
|
|---|
| 47 | __gnu_debug::_Safe_node_sequence>,
|
|---|
| 48 | public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
|
|---|
| 49 | {
|
|---|
| 50 | typedef _GLIBCXX_STD_C::multimap<
|
|---|
| 51 | _Key, _Tp, _Compare, _Allocator> _Base;
|
|---|
| 52 | typedef __gnu_debug::_Safe_container<
|
|---|
| 53 | multimap, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
|
|---|
| 54 |
|
|---|
| 55 | typedef typename _Base::const_iterator _Base_const_iterator;
|
|---|
| 56 | typedef typename _Base::iterator _Base_iterator;
|
|---|
| 57 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
|
|---|
| 58 |
|
|---|
| 59 | template<typename _ItT, typename _SeqT, typename _CatT>
|
|---|
| 60 | friend class ::__gnu_debug::_Safe_iterator;
|
|---|
| 61 |
|
|---|
| 62 | // Reference wrapper for base class. Disambiguates multimap(const _Base&)
|
|---|
| 63 | // from copy constructor by requiring a user-defined conversion.
|
|---|
| 64 | // See PR libstdc++/90102.
|
|---|
| 65 | struct _Base_ref
|
|---|
| 66 | {
|
|---|
| 67 | _Base_ref(const _Base& __r) : _M_ref(__r) { }
|
|---|
| 68 |
|
|---|
| 69 | const _Base& _M_ref;
|
|---|
| 70 | };
|
|---|
| 71 |
|
|---|
| 72 | public:
|
|---|
| 73 | // types:
|
|---|
| 74 | typedef _Key key_type;
|
|---|
| 75 | typedef _Tp mapped_type;
|
|---|
| 76 | typedef std::pair<const _Key, _Tp> value_type;
|
|---|
| 77 | typedef _Compare key_compare;
|
|---|
| 78 | typedef _Allocator allocator_type;
|
|---|
| 79 | typedef typename _Base::reference reference;
|
|---|
| 80 | typedef typename _Base::const_reference const_reference;
|
|---|
| 81 |
|
|---|
| 82 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
|
|---|
| 83 | iterator;
|
|---|
| 84 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
|
|---|
| 85 | multimap> const_iterator;
|
|---|
| 86 |
|
|---|
| 87 | typedef typename _Base::size_type size_type;
|
|---|
| 88 | typedef typename _Base::difference_type difference_type;
|
|---|
| 89 | typedef typename _Base::pointer pointer;
|
|---|
| 90 | typedef typename _Base::const_pointer const_pointer;
|
|---|
| 91 | typedef std::reverse_iterator<iterator> reverse_iterator;
|
|---|
| 92 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
|
|---|
| 93 |
|
|---|
| 94 | // 23.3.1.1 construct/copy/destroy:
|
|---|
| 95 |
|
|---|
| 96 | #if __cplusplus < 201103L
|
|---|
| 97 | multimap() : _Base() { }
|
|---|
| 98 |
|
|---|
| 99 | multimap(const multimap& __x)
|
|---|
| 100 | : _Base(__x) { }
|
|---|
| 101 |
|
|---|
| 102 | ~multimap() { }
|
|---|
| 103 | #else
|
|---|
| 104 | multimap() = default;
|
|---|
| 105 | multimap(const multimap&) = default;
|
|---|
| 106 | multimap(multimap&&) = default;
|
|---|
| 107 |
|
|---|
| 108 | multimap(initializer_list<value_type> __l,
|
|---|
| 109 | const _Compare& __c = _Compare(),
|
|---|
| 110 | const allocator_type& __a = allocator_type())
|
|---|
| 111 | : _Base(__l, __c, __a) { }
|
|---|
| 112 |
|
|---|
| 113 | explicit
|
|---|
| 114 | multimap(const allocator_type& __a)
|
|---|
| 115 | : _Base(__a) { }
|
|---|
| 116 |
|
|---|
| 117 | multimap(const multimap& __m, const allocator_type& __a)
|
|---|
| 118 | : _Base(__m, __a) { }
|
|---|
| 119 |
|
|---|
| 120 | multimap(multimap&& __m, const allocator_type& __a)
|
|---|
| 121 | noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
|
|---|
| 122 | : _Safe(std::move(__m._M_safe()), __a),
|
|---|
| 123 | _Base(std::move(__m._M_base()), __a) { }
|
|---|
| 124 |
|
|---|
| 125 | multimap(initializer_list<value_type> __l, const allocator_type& __a)
|
|---|
| 126 | : _Base(__l, __a) { }
|
|---|
| 127 |
|
|---|
| 128 | template<typename _InputIterator>
|
|---|
| 129 | multimap(_InputIterator __first, _InputIterator __last,
|
|---|
| 130 | const allocator_type& __a)
|
|---|
| 131 | : _Base(__gnu_debug::__base(
|
|---|
| 132 | __glibcxx_check_valid_constructor_range(__first, __last)),
|
|---|
| 133 | __gnu_debug::__base(__last), __a) { }
|
|---|
| 134 |
|
|---|
| 135 | ~multimap() = default;
|
|---|
| 136 | #endif
|
|---|
| 137 |
|
|---|
| 138 | explicit multimap(const _Compare& __comp,
|
|---|
| 139 | const _Allocator& __a = _Allocator())
|
|---|
| 140 | : _Base(__comp, __a) { }
|
|---|
| 141 |
|
|---|
| 142 | template<typename _InputIterator>
|
|---|
| 143 | multimap(_InputIterator __first, _InputIterator __last,
|
|---|
| 144 | const _Compare& __comp = _Compare(),
|
|---|
| 145 | const _Allocator& __a = _Allocator())
|
|---|
| 146 | : _Base(__gnu_debug::__base(
|
|---|
| 147 | __glibcxx_check_valid_constructor_range(__first, __last)),
|
|---|
| 148 | __gnu_debug::__base(__last),
|
|---|
| 149 | __comp, __a) { }
|
|---|
| 150 |
|
|---|
| 151 | multimap(_Base_ref __x)
|
|---|
| 152 | : _Base(__x._M_ref) { }
|
|---|
| 153 |
|
|---|
| 154 | #if __cplusplus < 201103L
|
|---|
| 155 | multimap&
|
|---|
| 156 | operator=(const multimap& __x)
|
|---|
| 157 | {
|
|---|
| 158 | this->_M_safe() = __x;
|
|---|
| 159 | _M_base() = __x;
|
|---|
| 160 | return *this;
|
|---|
| 161 | }
|
|---|
| 162 | #else
|
|---|
| 163 | multimap&
|
|---|
| 164 | operator=(const multimap&) = default;
|
|---|
| 165 |
|
|---|
| 166 | multimap&
|
|---|
| 167 | operator=(multimap&&) = default;
|
|---|
| 168 |
|
|---|
| 169 | multimap&
|
|---|
| 170 | operator=(initializer_list<value_type> __l)
|
|---|
| 171 | {
|
|---|
| 172 | _M_base() = __l;
|
|---|
| 173 | this->_M_invalidate_all();
|
|---|
| 174 | return *this;
|
|---|
| 175 | }
|
|---|
| 176 | #endif
|
|---|
| 177 |
|
|---|
| 178 | using _Base::get_allocator;
|
|---|
| 179 |
|
|---|
| 180 | // iterators:
|
|---|
| 181 | iterator
|
|---|
| 182 | begin() _GLIBCXX_NOEXCEPT
|
|---|
| 183 | { return iterator(_Base::begin(), this); }
|
|---|
| 184 |
|
|---|
| 185 | const_iterator
|
|---|
| 186 | begin() const _GLIBCXX_NOEXCEPT
|
|---|
| 187 | { return const_iterator(_Base::begin(), this); }
|
|---|
| 188 |
|
|---|
| 189 | iterator
|
|---|
| 190 | end() _GLIBCXX_NOEXCEPT
|
|---|
| 191 | { return iterator(_Base::end(), this); }
|
|---|
| 192 |
|
|---|
| 193 | const_iterator
|
|---|
| 194 | end() const _GLIBCXX_NOEXCEPT
|
|---|
| 195 | { return const_iterator(_Base::end(), this); }
|
|---|
| 196 |
|
|---|
| 197 | reverse_iterator
|
|---|
| 198 | rbegin() _GLIBCXX_NOEXCEPT
|
|---|
| 199 | { return reverse_iterator(end()); }
|
|---|
| 200 |
|
|---|
| 201 | const_reverse_iterator
|
|---|
| 202 | rbegin() const _GLIBCXX_NOEXCEPT
|
|---|
| 203 | { return const_reverse_iterator(end()); }
|
|---|
| 204 |
|
|---|
| 205 | reverse_iterator
|
|---|
| 206 | rend() _GLIBCXX_NOEXCEPT
|
|---|
| 207 | { return reverse_iterator(begin()); }
|
|---|
| 208 |
|
|---|
| 209 | const_reverse_iterator
|
|---|
| 210 | rend() const _GLIBCXX_NOEXCEPT
|
|---|
| 211 | { return const_reverse_iterator(begin()); }
|
|---|
| 212 |
|
|---|
| 213 | #if __cplusplus >= 201103L
|
|---|
| 214 | const_iterator
|
|---|
| 215 | cbegin() const noexcept
|
|---|
| 216 | { return const_iterator(_Base::begin(), this); }
|
|---|
| 217 |
|
|---|
| 218 | const_iterator
|
|---|
| 219 | cend() const noexcept
|
|---|
| 220 | { return const_iterator(_Base::end(), this); }
|
|---|
| 221 |
|
|---|
| 222 | const_reverse_iterator
|
|---|
| 223 | crbegin() const noexcept
|
|---|
| 224 | { return const_reverse_iterator(end()); }
|
|---|
| 225 |
|
|---|
| 226 | const_reverse_iterator
|
|---|
| 227 | crend() const noexcept
|
|---|
| 228 | { return const_reverse_iterator(begin()); }
|
|---|
| 229 | #endif
|
|---|
| 230 |
|
|---|
| 231 | // capacity:
|
|---|
| 232 | using _Base::empty;
|
|---|
| 233 | using _Base::size;
|
|---|
| 234 | using _Base::max_size;
|
|---|
| 235 |
|
|---|
| 236 | // modifiers:
|
|---|
| 237 | #if __cplusplus >= 201103L
|
|---|
| 238 | template<typename... _Args>
|
|---|
| 239 | iterator
|
|---|
| 240 | emplace(_Args&&... __args)
|
|---|
| 241 | { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
|
|---|
| 242 |
|
|---|
| 243 | template<typename... _Args>
|
|---|
| 244 | iterator
|
|---|
| 245 | emplace_hint(const_iterator __pos, _Args&&... __args)
|
|---|
| 246 | {
|
|---|
| 247 | __glibcxx_check_insert(__pos);
|
|---|
| 248 | return
|
|---|
| 249 | {
|
|---|
| 250 | _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
|
|---|
| 251 | this
|
|---|
| 252 | };
|
|---|
| 253 | }
|
|---|
| 254 | #endif
|
|---|
| 255 |
|
|---|
| 256 | iterator
|
|---|
| 257 | insert(const value_type& __x)
|
|---|
| 258 | { return iterator(_Base::insert(__x), this); }
|
|---|
| 259 |
|
|---|
| 260 | #if __cplusplus >= 201103L
|
|---|
| 261 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|---|
| 262 | // 2354. Unnecessary copying when inserting into maps with braced-init
|
|---|
| 263 | iterator
|
|---|
| 264 | insert(value_type&& __x)
|
|---|
| 265 | { return { _Base::insert(std::move(__x)), this }; }
|
|---|
| 266 |
|
|---|
| 267 | template<typename _Pair, typename = typename
|
|---|
| 268 | std::enable_if<std::is_constructible<value_type,
|
|---|
| 269 | _Pair&&>::value>::type>
|
|---|
| 270 | iterator
|
|---|
| 271 | insert(_Pair&& __x)
|
|---|
| 272 | { return { _Base::insert(std::forward<_Pair>(__x)), this }; }
|
|---|
| 273 | #endif
|
|---|
| 274 |
|
|---|
| 275 | #if __cplusplus >= 201103L
|
|---|
| 276 | void
|
|---|
| 277 | insert(std::initializer_list<value_type> __list)
|
|---|
| 278 | { _Base::insert(__list); }
|
|---|
| 279 | #endif
|
|---|
| 280 |
|
|---|
| 281 | iterator
|
|---|
| 282 | #if __cplusplus >= 201103L
|
|---|
| 283 | insert(const_iterator __position, const value_type& __x)
|
|---|
| 284 | #else
|
|---|
| 285 | insert(iterator __position, const value_type& __x)
|
|---|
| 286 | #endif
|
|---|
| 287 | {
|
|---|
| 288 | __glibcxx_check_insert(__position);
|
|---|
| 289 | return iterator(_Base::insert(__position.base(), __x), this);
|
|---|
| 290 | }
|
|---|
| 291 |
|
|---|
| 292 | #if __cplusplus >= 201103L
|
|---|
| 293 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|---|
| 294 | // 2354. Unnecessary copying when inserting into maps with braced-init
|
|---|
| 295 | iterator
|
|---|
| 296 | insert(const_iterator __position, value_type&& __x)
|
|---|
| 297 | {
|
|---|
| 298 | __glibcxx_check_insert(__position);
|
|---|
| 299 | return { _Base::insert(__position.base(), std::move(__x)), this };
|
|---|
| 300 | }
|
|---|
| 301 |
|
|---|
| 302 | template<typename _Pair, typename = typename
|
|---|
| 303 | std::enable_if<std::is_constructible<value_type,
|
|---|
| 304 | _Pair&&>::value>::type>
|
|---|
| 305 | iterator
|
|---|
| 306 | insert(const_iterator __position, _Pair&& __x)
|
|---|
| 307 | {
|
|---|
| 308 | __glibcxx_check_insert(__position);
|
|---|
| 309 | return
|
|---|
| 310 | {
|
|---|
| 311 | _Base::insert(__position.base(), std::forward<_Pair>(__x)),
|
|---|
| 312 | this
|
|---|
| 313 | };
|
|---|
| 314 | }
|
|---|
| 315 | #endif
|
|---|
| 316 |
|
|---|
| 317 | template<typename _InputIterator>
|
|---|
| 318 | void
|
|---|
| 319 | insert(_InputIterator __first, _InputIterator __last)
|
|---|
| 320 | {
|
|---|
| 321 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
|
|---|
| 322 | __glibcxx_check_valid_range2(__first, __last, __dist);
|
|---|
| 323 |
|
|---|
| 324 | if (__dist.second >= __gnu_debug::__dp_sign)
|
|---|
| 325 | _Base::insert(__gnu_debug::__unsafe(__first),
|
|---|
| 326 | __gnu_debug::__unsafe(__last));
|
|---|
| 327 | else
|
|---|
| 328 | _Base::insert(__first, __last);
|
|---|
| 329 | }
|
|---|
| 330 |
|
|---|
| 331 | #if __cplusplus > 201402L
|
|---|
| 332 | using node_type = typename _Base::node_type;
|
|---|
| 333 |
|
|---|
| 334 | node_type
|
|---|
| 335 | extract(const_iterator __position)
|
|---|
| 336 | {
|
|---|
| 337 | __glibcxx_check_erase(__position);
|
|---|
| 338 | this->_M_invalidate_if(_Equal(__position.base()));
|
|---|
| 339 | return _Base::extract(__position.base());
|
|---|
| 340 | }
|
|---|
| 341 |
|
|---|
| 342 | node_type
|
|---|
| 343 | extract(const key_type& __key)
|
|---|
| 344 | {
|
|---|
| 345 | const auto __position = find(__key);
|
|---|
| 346 | if (__position != end())
|
|---|
| 347 | return extract(__position);
|
|---|
| 348 | return {};
|
|---|
| 349 | }
|
|---|
| 350 |
|
|---|
| 351 | iterator
|
|---|
| 352 | insert(node_type&& __nh)
|
|---|
| 353 | { return { _Base::insert(std::move(__nh)), this }; }
|
|---|
| 354 |
|
|---|
| 355 | iterator
|
|---|
| 356 | insert(const_iterator __hint, node_type&& __nh)
|
|---|
| 357 | {
|
|---|
| 358 | __glibcxx_check_insert(__hint);
|
|---|
| 359 | return { _Base::insert(__hint.base(), std::move(__nh)), this };
|
|---|
| 360 | }
|
|---|
| 361 |
|
|---|
| 362 | using _Base::merge;
|
|---|
| 363 | #endif // C++17
|
|---|
| 364 |
|
|---|
| 365 | #if __cplusplus >= 201103L
|
|---|
| 366 | iterator
|
|---|
| 367 | erase(const_iterator __position)
|
|---|
| 368 | {
|
|---|
| 369 | __glibcxx_check_erase(__position);
|
|---|
| 370 | this->_M_invalidate_if(_Equal(__position.base()));
|
|---|
| 371 | return { _Base::erase(__position.base()), this };
|
|---|
| 372 | }
|
|---|
| 373 |
|
|---|
| 374 | _GLIBCXX_ABI_TAG_CXX11
|
|---|
| 375 | iterator
|
|---|
| 376 | erase(iterator __position)
|
|---|
| 377 | { return erase(const_iterator(__position)); }
|
|---|
| 378 | #else
|
|---|
| 379 | void
|
|---|
| 380 | erase(iterator __position)
|
|---|
| 381 | {
|
|---|
| 382 | __glibcxx_check_erase(__position);
|
|---|
| 383 | this->_M_invalidate_if(_Equal(__position.base()));
|
|---|
| 384 | _Base::erase(__position.base());
|
|---|
| 385 | }
|
|---|
| 386 | #endif
|
|---|
| 387 |
|
|---|
| 388 | size_type
|
|---|
| 389 | erase(const key_type& __x)
|
|---|
| 390 | {
|
|---|
| 391 | std::pair<_Base_iterator, _Base_iterator> __victims =
|
|---|
| 392 | _Base::equal_range(__x);
|
|---|
| 393 | size_type __count = 0;
|
|---|
| 394 | _Base_iterator __victim = __victims.first;
|
|---|
| 395 | while (__victim != __victims.second)
|
|---|
| 396 | {
|
|---|
| 397 | this->_M_invalidate_if(_Equal(__victim));
|
|---|
| 398 | _Base::erase(__victim++);
|
|---|
| 399 | ++__count;
|
|---|
| 400 | }
|
|---|
| 401 | return __count;
|
|---|
| 402 | }
|
|---|
| 403 |
|
|---|
| 404 | #if __cplusplus >= 201103L
|
|---|
| 405 | iterator
|
|---|
| 406 | erase(const_iterator __first, const_iterator __last)
|
|---|
| 407 | {
|
|---|
| 408 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|---|
| 409 | // 151. can't currently clear() empty container
|
|---|
| 410 | __glibcxx_check_erase_range(__first, __last);
|
|---|
| 411 | for (_Base_const_iterator __victim = __first.base();
|
|---|
| 412 | __victim != __last.base(); ++__victim)
|
|---|
| 413 | {
|
|---|
| 414 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
|
|---|
| 415 | _M_message(__gnu_debug::__msg_valid_range)
|
|---|
| 416 | ._M_iterator(__first, "first")
|
|---|
| 417 | ._M_iterator(__last, "last"));
|
|---|
| 418 | this->_M_invalidate_if(_Equal(__victim));
|
|---|
| 419 | }
|
|---|
| 420 |
|
|---|
| 421 | return { _Base::erase(__first.base(), __last.base()), this };
|
|---|
| 422 | }
|
|---|
| 423 | #else
|
|---|
| 424 | void
|
|---|
| 425 | erase(iterator __first, iterator __last)
|
|---|
| 426 | {
|
|---|
| 427 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|---|
| 428 | // 151. can't currently clear() empty container
|
|---|
| 429 | __glibcxx_check_erase_range(__first, __last);
|
|---|
| 430 | for (_Base_iterator __victim = __first.base();
|
|---|
| 431 | __victim != __last.base(); ++__victim)
|
|---|
| 432 | {
|
|---|
| 433 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
|
|---|
| 434 | _M_message(__gnu_debug::__msg_valid_range)
|
|---|
| 435 | ._M_iterator(__first, "first")
|
|---|
| 436 | ._M_iterator(__last, "last"));
|
|---|
| 437 | this->_M_invalidate_if(_Equal(__victim));
|
|---|
| 438 | }
|
|---|
| 439 | _Base::erase(__first.base(), __last.base());
|
|---|
| 440 | }
|
|---|
| 441 | #endif
|
|---|
| 442 |
|
|---|
| 443 | void
|
|---|
| 444 | swap(multimap& __x)
|
|---|
| 445 | _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
|
|---|
| 446 | {
|
|---|
| 447 | _Safe::_M_swap(__x);
|
|---|
| 448 | _Base::swap(__x);
|
|---|
| 449 | }
|
|---|
| 450 |
|
|---|
| 451 | void
|
|---|
| 452 | clear() _GLIBCXX_NOEXCEPT
|
|---|
| 453 | {
|
|---|
| 454 | this->_M_invalidate_all();
|
|---|
| 455 | _Base::clear();
|
|---|
| 456 | }
|
|---|
| 457 |
|
|---|
| 458 | // observers:
|
|---|
| 459 | using _Base::key_comp;
|
|---|
| 460 | using _Base::value_comp;
|
|---|
| 461 |
|
|---|
| 462 | // 23.3.1.3 multimap operations:
|
|---|
| 463 | iterator
|
|---|
| 464 | find(const key_type& __x)
|
|---|
| 465 | { return iterator(_Base::find(__x), this); }
|
|---|
| 466 |
|
|---|
| 467 | #if __cplusplus > 201103L
|
|---|
| 468 | template<typename _Kt,
|
|---|
| 469 | typename _Req =
|
|---|
| 470 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 471 | iterator
|
|---|
| 472 | find(const _Kt& __x)
|
|---|
| 473 | { return { _Base::find(__x), this }; }
|
|---|
| 474 | #endif
|
|---|
| 475 |
|
|---|
| 476 | const_iterator
|
|---|
| 477 | find(const key_type& __x) const
|
|---|
| 478 | { return const_iterator(_Base::find(__x), this); }
|
|---|
| 479 |
|
|---|
| 480 | #if __cplusplus > 201103L
|
|---|
| 481 | template<typename _Kt,
|
|---|
| 482 | typename _Req =
|
|---|
| 483 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 484 | const_iterator
|
|---|
| 485 | find(const _Kt& __x) const
|
|---|
| 486 | { return { _Base::find(__x), this }; }
|
|---|
| 487 | #endif
|
|---|
| 488 |
|
|---|
| 489 | using _Base::count;
|
|---|
| 490 |
|
|---|
| 491 | iterator
|
|---|
| 492 | lower_bound(const key_type& __x)
|
|---|
| 493 | { return iterator(_Base::lower_bound(__x), this); }
|
|---|
| 494 |
|
|---|
| 495 | #if __cplusplus > 201103L
|
|---|
| 496 | template<typename _Kt,
|
|---|
| 497 | typename _Req =
|
|---|
| 498 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 499 | iterator
|
|---|
| 500 | lower_bound(const _Kt& __x)
|
|---|
| 501 | { return { _Base::lower_bound(__x), this }; }
|
|---|
| 502 | #endif
|
|---|
| 503 |
|
|---|
| 504 | const_iterator
|
|---|
| 505 | lower_bound(const key_type& __x) const
|
|---|
| 506 | { return const_iterator(_Base::lower_bound(__x), this); }
|
|---|
| 507 |
|
|---|
| 508 | #if __cplusplus > 201103L
|
|---|
| 509 | template<typename _Kt,
|
|---|
| 510 | typename _Req =
|
|---|
| 511 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 512 | const_iterator
|
|---|
| 513 | lower_bound(const _Kt& __x) const
|
|---|
| 514 | { return { _Base::lower_bound(__x), this }; }
|
|---|
| 515 | #endif
|
|---|
| 516 |
|
|---|
| 517 | iterator
|
|---|
| 518 | upper_bound(const key_type& __x)
|
|---|
| 519 | { return iterator(_Base::upper_bound(__x), this); }
|
|---|
| 520 |
|
|---|
| 521 | #if __cplusplus > 201103L
|
|---|
| 522 | template<typename _Kt,
|
|---|
| 523 | typename _Req =
|
|---|
| 524 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 525 | iterator
|
|---|
| 526 | upper_bound(const _Kt& __x)
|
|---|
| 527 | { return { _Base::upper_bound(__x), this }; }
|
|---|
| 528 | #endif
|
|---|
| 529 |
|
|---|
| 530 | const_iterator
|
|---|
| 531 | upper_bound(const key_type& __x) const
|
|---|
| 532 | { return const_iterator(_Base::upper_bound(__x), this); }
|
|---|
| 533 |
|
|---|
| 534 | #if __cplusplus > 201103L
|
|---|
| 535 | template<typename _Kt,
|
|---|
| 536 | typename _Req =
|
|---|
| 537 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 538 | const_iterator
|
|---|
| 539 | upper_bound(const _Kt& __x) const
|
|---|
| 540 | { return { _Base::upper_bound(__x), this }; }
|
|---|
| 541 | #endif
|
|---|
| 542 |
|
|---|
| 543 | std::pair<iterator,iterator>
|
|---|
| 544 | equal_range(const key_type& __x)
|
|---|
| 545 | {
|
|---|
| 546 | std::pair<_Base_iterator, _Base_iterator> __res =
|
|---|
| 547 | _Base::equal_range(__x);
|
|---|
| 548 | return std::make_pair(iterator(__res.first, this),
|
|---|
| 549 | iterator(__res.second, this));
|
|---|
| 550 | }
|
|---|
| 551 |
|
|---|
| 552 | #if __cplusplus > 201103L
|
|---|
| 553 | template<typename _Kt,
|
|---|
| 554 | typename _Req =
|
|---|
| 555 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 556 | std::pair<iterator, iterator>
|
|---|
| 557 | equal_range(const _Kt& __x)
|
|---|
| 558 | {
|
|---|
| 559 | auto __res = _Base::equal_range(__x);
|
|---|
| 560 | return { { __res.first, this }, { __res.second, this } };
|
|---|
| 561 | }
|
|---|
| 562 | #endif
|
|---|
| 563 |
|
|---|
| 564 | std::pair<const_iterator,const_iterator>
|
|---|
| 565 | equal_range(const key_type& __x) const
|
|---|
| 566 | {
|
|---|
| 567 | std::pair<_Base_const_iterator, _Base_const_iterator> __res =
|
|---|
| 568 | _Base::equal_range(__x);
|
|---|
| 569 | return std::make_pair(const_iterator(__res.first, this),
|
|---|
| 570 | const_iterator(__res.second, this));
|
|---|
| 571 | }
|
|---|
| 572 |
|
|---|
| 573 | #if __cplusplus > 201103L
|
|---|
| 574 | template<typename _Kt,
|
|---|
| 575 | typename _Req =
|
|---|
| 576 | typename __has_is_transparent<_Compare, _Kt>::type>
|
|---|
| 577 | std::pair<const_iterator, const_iterator>
|
|---|
| 578 | equal_range(const _Kt& __x) const
|
|---|
| 579 | {
|
|---|
| 580 | auto __res = _Base::equal_range(__x);
|
|---|
| 581 | return { { __res.first, this }, { __res.second, this } };
|
|---|
| 582 | }
|
|---|
| 583 | #endif
|
|---|
| 584 |
|
|---|
| 585 | _Base&
|
|---|
| 586 | _M_base() _GLIBCXX_NOEXCEPT { return *this; }
|
|---|
| 587 |
|
|---|
| 588 | const _Base&
|
|---|
| 589 | _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
|
|---|
| 590 | };
|
|---|
| 591 |
|
|---|
| 592 | #if __cpp_deduction_guides >= 201606
|
|---|
| 593 |
|
|---|
| 594 | template<typename _InputIterator,
|
|---|
| 595 | typename _Compare = less<__iter_key_t<_InputIterator>>,
|
|---|
| 596 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
|
|---|
| 597 | typename = _RequireInputIter<_InputIterator>,
|
|---|
| 598 | typename = _RequireNotAllocator<_Compare>,
|
|---|
| 599 | typename = _RequireAllocator<_Allocator>>
|
|---|
| 600 | multimap(_InputIterator, _InputIterator,
|
|---|
| 601 | _Compare = _Compare(), _Allocator = _Allocator())
|
|---|
| 602 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
|
|---|
| 603 | _Compare, _Allocator>;
|
|---|
| 604 |
|
|---|
| 605 | template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
|
|---|
| 606 | typename _Allocator = allocator<pair<const _Key, _Tp>>,
|
|---|
| 607 | typename = _RequireNotAllocator<_Compare>,
|
|---|
| 608 | typename = _RequireAllocator<_Allocator>>
|
|---|
| 609 | multimap(initializer_list<pair<_Key, _Tp>>,
|
|---|
| 610 | _Compare = _Compare(), _Allocator = _Allocator())
|
|---|
| 611 | -> multimap<_Key, _Tp, _Compare, _Allocator>;
|
|---|
| 612 |
|
|---|
| 613 | template<typename _InputIterator, typename _Allocator,
|
|---|
| 614 | typename = _RequireInputIter<_InputIterator>,
|
|---|
| 615 | typename = _RequireAllocator<_Allocator>>
|
|---|
| 616 | multimap(_InputIterator, _InputIterator, _Allocator)
|
|---|
| 617 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
|
|---|
| 618 | less<__iter_key_t<_InputIterator>>, _Allocator>;
|
|---|
| 619 |
|
|---|
| 620 | template<typename _Key, typename _Tp, typename _Allocator,
|
|---|
| 621 | typename = _RequireAllocator<_Allocator>>
|
|---|
| 622 | multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
|
|---|
| 623 | -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
|
|---|
| 624 |
|
|---|
| 625 | #endif
|
|---|
| 626 |
|
|---|
| 627 | template<typename _Key, typename _Tp,
|
|---|
| 628 | typename _Compare, typename _Allocator>
|
|---|
| 629 | inline bool
|
|---|
| 630 | operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 631 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 632 | { return __lhs._M_base() == __rhs._M_base(); }
|
|---|
| 633 |
|
|---|
| 634 | #if __cpp_lib_three_way_comparison
|
|---|
| 635 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
|
|---|
| 636 | inline __detail::__synth3way_t<pair<const _Key, _Tp>>
|
|---|
| 637 | operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs,
|
|---|
| 638 | const multimap<_Key, _Tp, _Compare, _Alloc>& __rhs)
|
|---|
| 639 | { return __lhs._M_base() <=> __rhs._M_base(); }
|
|---|
| 640 | #else
|
|---|
| 641 | template<typename _Key, typename _Tp,
|
|---|
| 642 | typename _Compare, typename _Allocator>
|
|---|
| 643 | inline bool
|
|---|
| 644 | operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 645 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 646 | { return __lhs._M_base() != __rhs._M_base(); }
|
|---|
| 647 |
|
|---|
| 648 | template<typename _Key, typename _Tp,
|
|---|
| 649 | typename _Compare, typename _Allocator>
|
|---|
| 650 | inline bool
|
|---|
| 651 | operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 652 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 653 | { return __lhs._M_base() < __rhs._M_base(); }
|
|---|
| 654 |
|
|---|
| 655 | template<typename _Key, typename _Tp,
|
|---|
| 656 | typename _Compare, typename _Allocator>
|
|---|
| 657 | inline bool
|
|---|
| 658 | operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 659 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 660 | { return __lhs._M_base() <= __rhs._M_base(); }
|
|---|
| 661 |
|
|---|
| 662 | template<typename _Key, typename _Tp,
|
|---|
| 663 | typename _Compare, typename _Allocator>
|
|---|
| 664 | inline bool
|
|---|
| 665 | operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 666 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 667 | { return __lhs._M_base() >= __rhs._M_base(); }
|
|---|
| 668 |
|
|---|
| 669 | template<typename _Key, typename _Tp,
|
|---|
| 670 | typename _Compare, typename _Allocator>
|
|---|
| 671 | inline bool
|
|---|
| 672 | operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 673 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 674 | { return __lhs._M_base() > __rhs._M_base(); }
|
|---|
| 675 | #endif // three-way comparison
|
|---|
| 676 |
|
|---|
| 677 | template<typename _Key, typename _Tp,
|
|---|
| 678 | typename _Compare, typename _Allocator>
|
|---|
| 679 | inline void
|
|---|
| 680 | swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
|
|---|
| 681 | multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
|
|---|
| 682 | _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
|
|---|
| 683 | { __lhs.swap(__rhs); }
|
|---|
| 684 |
|
|---|
| 685 | } // namespace __debug
|
|---|
| 686 | } // namespace std
|
|---|
| 687 |
|
|---|
| 688 | #endif
|
|---|
