| OLD | NEW |
|---|
| (Empty) | |
| 1 // -*- C++ -*- |
| 2 //===----------------------------- map ------------------------------------===// |
| 3 // |
| 4 // The LLVM Compiler Infrastructure |
| 5 // |
| 6 // This file is dual licensed under the MIT and the University of Illinois Open |
| 7 // Source Licenses. See LICENSE.TXT for details. |
| 8 // |
| 9 //===----------------------------------------------------------------------===// |
| 10 |
| 11 #ifndef _LIBCPP_MAP |
| 12 #define _LIBCPP_MAP |
| 13 |
| 14 /* |
| 15 |
| 16 map synopsis |
| 17 |
| 18 namespace std |
| 19 { |
| 20 |
| 21 template <class Key, class T, class Compare = less<Key>, |
| 22 class Allocator = allocator<pair<const Key, T>>> |
| 23 class map |
| 24 { |
| 25 public: |
| 26 // types: |
| 27 typedef Key key_type; |
| 28 typedef T mapped_type; |
| 29 typedef pair<const key_type, mapped_type> value_type; |
| 30 typedef Compare key_compare; |
| 31 typedef Allocator allocator_type; |
| 32 typedef typename allocator_type::reference reference; |
| 33 typedef typename allocator_type::const_reference const_reference; |
| 34 typedef typename allocator_type::pointer pointer; |
| 35 typedef typename allocator_type::const_pointer const_pointer; |
| 36 typedef typename allocator_type::size_type size_type; |
| 37 typedef typename allocator_type::difference_type difference_type; |
| 38 |
| 39 typedef implementation-defined iterator; |
| 40 typedef implementation-defined const_iterator; |
| 41 typedef std::reverse_iterator<iterator> reverse_iterator; |
| 42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| 43 |
| 44 class value_compare |
| 45 : public binary_function<value_type, value_type, bool> |
| 46 { |
| 47 friend class map; |
| 48 protected: |
| 49 key_compare comp; |
| 50 |
| 51 value_compare(key_compare c); |
| 52 public: |
| 53 bool operator()(const value_type& x, const value_type& y) const; |
| 54 }; |
| 55 |
| 56 // construct/copy/destroy: |
| 57 map() |
| 58 noexcept( |
| 59 is_nothrow_default_constructible<allocator_type>::value && |
| 60 is_nothrow_default_constructible<key_compare>::value && |
| 61 is_nothrow_copy_constructible<key_compare>::value); |
| 62 explicit map(const key_compare& comp); |
| 63 map(const key_compare& comp, const allocator_type& a); |
| 64 template <class InputIterator> |
| 65 map(InputIterator first, InputIterator last, |
| 66 const key_compare& comp = key_compare()); |
| 67 template <class InputIterator> |
| 68 map(InputIterator first, InputIterator last, |
| 69 const key_compare& comp, const allocator_type& a); |
| 70 map(const map& m); |
| 71 map(map&& m) |
| 72 noexcept( |
| 73 is_nothrow_move_constructible<allocator_type>::value && |
| 74 is_nothrow_move_constructible<key_compare>::value); |
| 75 explicit map(const allocator_type& a); |
| 76 map(const map& m, const allocator_type& a); |
| 77 map(map&& m, const allocator_type& a); |
| 78 map(initializer_list<value_type> il, const key_compare& comp = key_compare()
); |
| 79 map(initializer_list<value_type> il, const key_compare& comp, const allocato
r_type& a); |
| 80 template <class InputIterator> |
| 81 map(InputIterator first, InputIterator last, const allocator_type& a) |
| 82 : map(first, last, Compare(), a) {} // C++14 |
| 83 map(initializer_list<value_type> il, const allocator_type& a) |
| 84 : map(il, Compare(), a) {} // C++14 |
| 85 ~map(); |
| 86 |
| 87 map& operator=(const map& m); |
| 88 map& operator=(map&& m) |
| 89 noexcept( |
| 90 allocator_type::propagate_on_container_move_assignment::value && |
| 91 is_nothrow_move_assignable<allocator_type>::value && |
| 92 is_nothrow_move_assignable<key_compare>::value); |
| 93 map& operator=(initializer_list<value_type> il); |
| 94 |
| 95 // iterators: |
| 96 iterator begin() noexcept; |
| 97 const_iterator begin() const noexcept; |
| 98 iterator end() noexcept; |
| 99 const_iterator end() const noexcept; |
| 100 |
| 101 reverse_iterator rbegin() noexcept; |
| 102 const_reverse_iterator rbegin() const noexcept; |
| 103 reverse_iterator rend() noexcept; |
| 104 const_reverse_iterator rend() const noexcept; |
| 105 |
| 106 const_iterator cbegin() const noexcept; |
| 107 const_iterator cend() const noexcept; |
| 108 const_reverse_iterator crbegin() const noexcept; |
| 109 const_reverse_iterator crend() const noexcept; |
| 110 |
| 111 // capacity: |
| 112 bool empty() const noexcept; |
| 113 size_type size() const noexcept; |
| 114 size_type max_size() const noexcept; |
| 115 |
| 116 // element access: |
| 117 mapped_type& operator[](const key_type& k); |
| 118 mapped_type& operator[](key_type&& k); |
| 119 |
| 120 mapped_type& at(const key_type& k); |
| 121 const mapped_type& at(const key_type& k) const; |
| 122 |
| 123 // modifiers: |
| 124 template <class... Args> |
| 125 pair<iterator, bool> emplace(Args&&... args); |
| 126 template <class... Args> |
| 127 iterator emplace_hint(const_iterator position, Args&&... args); |
| 128 pair<iterator, bool> insert(const value_type& v); |
| 129 template <class P> |
| 130 pair<iterator, bool> insert(P&& p); |
| 131 iterator insert(const_iterator position, const value_type& v); |
| 132 template <class P> |
| 133 iterator insert(const_iterator position, P&& p); |
| 134 template <class InputIterator> |
| 135 void insert(InputIterator first, InputIterator last); |
| 136 void insert(initializer_list<value_type> il); |
| 137 |
| 138 iterator erase(const_iterator position); |
| 139 size_type erase(const key_type& k); |
| 140 iterator erase(const_iterator first, const_iterator last); |
| 141 void clear() noexcept; |
| 142 |
| 143 void swap(map& m) |
| 144 noexcept( |
| 145 __is_nothrow_swappable<key_compare>::value && |
| 146 (!allocator_type::propagate_on_container_swap::value || |
| 147 __is_nothrow_swappable<allocator_type>::value)); |
| 148 |
| 149 // observers: |
| 150 allocator_type get_allocator() const noexcept; |
| 151 key_compare key_comp() const; |
| 152 value_compare value_comp() const; |
| 153 |
| 154 // map operations: |
| 155 iterator find(const key_type& k); |
| 156 const_iterator find(const key_type& k) const; |
| 157 template<typename K> |
| 158 iterator find(const K& x); // C++14 |
| 159 template<typename K> |
| 160 const_iterator find(const K& x) const; // C++14 |
| 161 template<typename K> |
| 162 size_type count(const K& x) const; |
| 163 |
| 164 size_type count(const key_type& k) const; |
| 165 iterator lower_bound(const key_type& k); |
| 166 const_iterator lower_bound(const key_type& k) const; |
| 167 template<typename K> |
| 168 iterator lower_bound(const K& x); // C++14 |
| 169 template<typename K> |
| 170 const_iterator lower_bound(const K& x) const; // C++14 |
| 171 |
| 172 iterator upper_bound(const key_type& k); |
| 173 const_iterator upper_bound(const key_type& k) const; |
| 174 template<typename K> |
| 175 iterator upper_bound(const K& x); // C++14 |
| 176 template<typename K> |
| 177 const_iterator upper_bound(const K& x) const; // C++14 |
| 178 |
| 179 pair<iterator,iterator> equal_range(const key_type& k); |
| 180 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
| 181 template<typename K> |
| 182 pair<iterator,iterator> equal_range(const K& x); // C
++14 |
| 183 template<typename K> |
| 184 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C
++14 |
| 185 }; |
| 186 |
| 187 template <class Key, class T, class Compare, class Allocator> |
| 188 bool |
| 189 operator==(const map<Key, T, Compare, Allocator>& x, |
| 190 const map<Key, T, Compare, Allocator>& y); |
| 191 |
| 192 template <class Key, class T, class Compare, class Allocator> |
| 193 bool |
| 194 operator< (const map<Key, T, Compare, Allocator>& x, |
| 195 const map<Key, T, Compare, Allocator>& y); |
| 196 |
| 197 template <class Key, class T, class Compare, class Allocator> |
| 198 bool |
| 199 operator!=(const map<Key, T, Compare, Allocator>& x, |
| 200 const map<Key, T, Compare, Allocator>& y); |
| 201 |
| 202 template <class Key, class T, class Compare, class Allocator> |
| 203 bool |
| 204 operator> (const map<Key, T, Compare, Allocator>& x, |
| 205 const map<Key, T, Compare, Allocator>& y); |
| 206 |
| 207 template <class Key, class T, class Compare, class Allocator> |
| 208 bool |
| 209 operator>=(const map<Key, T, Compare, Allocator>& x, |
| 210 const map<Key, T, Compare, Allocator>& y); |
| 211 |
| 212 template <class Key, class T, class Compare, class Allocator> |
| 213 bool |
| 214 operator<=(const map<Key, T, Compare, Allocator>& x, |
| 215 const map<Key, T, Compare, Allocator>& y); |
| 216 |
| 217 // specialized algorithms: |
| 218 template <class Key, class T, class Compare, class Allocator> |
| 219 void |
| 220 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y) |
| 221 noexcept(noexcept(x.swap(y))); |
| 222 |
| 223 template <class Key, class T, class Compare = less<Key>, |
| 224 class Allocator = allocator<pair<const Key, T>>> |
| 225 class multimap |
| 226 { |
| 227 public: |
| 228 // types: |
| 229 typedef Key key_type; |
| 230 typedef T mapped_type; |
| 231 typedef pair<const key_type,mapped_type> value_type; |
| 232 typedef Compare key_compare; |
| 233 typedef Allocator allocator_type; |
| 234 typedef typename allocator_type::reference reference; |
| 235 typedef typename allocator_type::const_reference const_reference; |
| 236 typedef typename allocator_type::size_type size_type; |
| 237 typedef typename allocator_type::difference_type difference_type; |
| 238 typedef typename allocator_type::pointer pointer; |
| 239 typedef typename allocator_type::const_pointer const_pointer; |
| 240 |
| 241 typedef implementation-defined iterator; |
| 242 typedef implementation-defined const_iterator; |
| 243 typedef std::reverse_iterator<iterator> reverse_iterator; |
| 244 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| 245 |
| 246 class value_compare |
| 247 : public binary_function<value_type,value_type,bool> |
| 248 { |
| 249 friend class multimap; |
| 250 protected: |
| 251 key_compare comp; |
| 252 value_compare(key_compare c); |
| 253 public: |
| 254 bool operator()(const value_type& x, const value_type& y) const; |
| 255 }; |
| 256 |
| 257 // construct/copy/destroy: |
| 258 multimap() |
| 259 noexcept( |
| 260 is_nothrow_default_constructible<allocator_type>::value && |
| 261 is_nothrow_default_constructible<key_compare>::value && |
| 262 is_nothrow_copy_constructible<key_compare>::value); |
| 263 explicit multimap(const key_compare& comp); |
| 264 multimap(const key_compare& comp, const allocator_type& a); |
| 265 template <class InputIterator> |
| 266 multimap(InputIterator first, InputIterator last, const key_compare& com
p); |
| 267 template <class InputIterator> |
| 268 multimap(InputIterator first, InputIterator last, const key_compare& com
p, |
| 269 const allocator_type& a); |
| 270 multimap(const multimap& m); |
| 271 multimap(multimap&& m) |
| 272 noexcept( |
| 273 is_nothrow_move_constructible<allocator_type>::value && |
| 274 is_nothrow_move_constructible<key_compare>::value); |
| 275 explicit multimap(const allocator_type& a); |
| 276 multimap(const multimap& m, const allocator_type& a); |
| 277 multimap(multimap&& m, const allocator_type& a); |
| 278 multimap(initializer_list<value_type> il, const key_compare& comp = key_comp
are()); |
| 279 multimap(initializer_list<value_type> il, const key_compare& comp, |
| 280 const allocator_type& a); |
| 281 template <class InputIterator> |
| 282 multimap(InputIterator first, InputIterator last, const allocator_type&
a) |
| 283 : multimap(first, last, Compare(), a) {} // C++14 |
| 284 multimap(initializer_list<value_type> il, const allocator_type& a) |
| 285 : multimap(il, Compare(), a) {} // C++14 |
| 286 ~multimap(); |
| 287 |
| 288 multimap& operator=(const multimap& m); |
| 289 multimap& operator=(multimap&& m) |
| 290 noexcept( |
| 291 allocator_type::propagate_on_container_move_assignment::value && |
| 292 is_nothrow_move_assignable<allocator_type>::value && |
| 293 is_nothrow_move_assignable<key_compare>::value); |
| 294 multimap& operator=(initializer_list<value_type> il); |
| 295 |
| 296 // iterators: |
| 297 iterator begin() noexcept; |
| 298 const_iterator begin() const noexcept; |
| 299 iterator end() noexcept; |
| 300 const_iterator end() const noexcept; |
| 301 |
| 302 reverse_iterator rbegin() noexcept; |
| 303 const_reverse_iterator rbegin() const noexcept; |
| 304 reverse_iterator rend() noexcept; |
| 305 const_reverse_iterator rend() const noexcept; |
| 306 |
| 307 const_iterator cbegin() const noexcept; |
| 308 const_iterator cend() const noexcept; |
| 309 const_reverse_iterator crbegin() const noexcept; |
| 310 const_reverse_iterator crend() const noexcept; |
| 311 |
| 312 // capacity: |
| 313 bool empty() const noexcept; |
| 314 size_type size() const noexcept; |
| 315 size_type max_size() const noexcept; |
| 316 |
| 317 // modifiers: |
| 318 template <class... Args> |
| 319 iterator emplace(Args&&... args); |
| 320 template <class... Args> |
| 321 iterator emplace_hint(const_iterator position, Args&&... args); |
| 322 iterator insert(const value_type& v); |
| 323 template <class P> |
| 324 iterator insert(P&& p); |
| 325 iterator insert(const_iterator position, const value_type& v); |
| 326 template <class P> |
| 327 iterator insert(const_iterator position, P&& p); |
| 328 template <class InputIterator> |
| 329 void insert(InputIterator first, InputIterator last); |
| 330 void insert(initializer_list<value_type> il); |
| 331 |
| 332 iterator erase(const_iterator position); |
| 333 size_type erase(const key_type& k); |
| 334 iterator erase(const_iterator first, const_iterator last); |
| 335 void clear() noexcept; |
| 336 |
| 337 void swap(multimap& m) |
| 338 noexcept( |
| 339 __is_nothrow_swappable<key_compare>::value && |
| 340 (!allocator_type::propagate_on_container_swap::value || |
| 341 __is_nothrow_swappable<allocator_type>::value)); |
| 342 |
| 343 // observers: |
| 344 allocator_type get_allocator() const noexcept; |
| 345 key_compare key_comp() const; |
| 346 value_compare value_comp() const; |
| 347 |
| 348 // map operations: |
| 349 iterator find(const key_type& k); |
| 350 const_iterator find(const key_type& k) const; |
| 351 template<typename K> |
| 352 iterator find(const K& x); // C++14 |
| 353 template<typename K> |
| 354 const_iterator find(const K& x) const; // C++14 |
| 355 template<typename K> |
| 356 size_type count(const K& x) const; |
| 357 |
| 358 size_type count(const key_type& k) const; |
| 359 iterator lower_bound(const key_type& k); |
| 360 const_iterator lower_bound(const key_type& k) const; |
| 361 template<typename K> |
| 362 iterator lower_bound(const K& x); // C++14 |
| 363 template<typename K> |
| 364 const_iterator lower_bound(const K& x) const; // C++14 |
| 365 |
| 366 iterator upper_bound(const key_type& k); |
| 367 const_iterator upper_bound(const key_type& k) const; |
| 368 template<typename K> |
| 369 iterator upper_bound(const K& x); // C++14 |
| 370 template<typename K> |
| 371 const_iterator upper_bound(const K& x) const; // C++14 |
| 372 |
| 373 pair<iterator,iterator> equal_range(const key_type& k); |
| 374 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
| 375 template<typename K> |
| 376 pair<iterator,iterator> equal_range(const K& x); // C
++14 |
| 377 template<typename K> |
| 378 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C
++14 |
| 379 }; |
| 380 |
| 381 template <class Key, class T, class Compare, class Allocator> |
| 382 bool |
| 383 operator==(const multimap<Key, T, Compare, Allocator>& x, |
| 384 const multimap<Key, T, Compare, Allocator>& y); |
| 385 |
| 386 template <class Key, class T, class Compare, class Allocator> |
| 387 bool |
| 388 operator< (const multimap<Key, T, Compare, Allocator>& x, |
| 389 const multimap<Key, T, Compare, Allocator>& y); |
| 390 |
| 391 template <class Key, class T, class Compare, class Allocator> |
| 392 bool |
| 393 operator!=(const multimap<Key, T, Compare, Allocator>& x, |
| 394 const multimap<Key, T, Compare, Allocator>& y); |
| 395 |
| 396 template <class Key, class T, class Compare, class Allocator> |
| 397 bool |
| 398 operator> (const multimap<Key, T, Compare, Allocator>& x, |
| 399 const multimap<Key, T, Compare, Allocator>& y); |
| 400 |
| 401 template <class Key, class T, class Compare, class Allocator> |
| 402 bool |
| 403 operator>=(const multimap<Key, T, Compare, Allocator>& x, |
| 404 const multimap<Key, T, Compare, Allocator>& y); |
| 405 |
| 406 template <class Key, class T, class Compare, class Allocator> |
| 407 bool |
| 408 operator<=(const multimap<Key, T, Compare, Allocator>& x, |
| 409 const multimap<Key, T, Compare, Allocator>& y); |
| 410 |
| 411 // specialized algorithms: |
| 412 template <class Key, class T, class Compare, class Allocator> |
| 413 void |
| 414 swap(multimap<Key, T, Compare, Allocator>& x, |
| 415 multimap<Key, T, Compare, Allocator>& y) |
| 416 noexcept(noexcept(x.swap(y))); |
| 417 |
| 418 } // std |
| 419 |
| 420 */ |
| 421 |
| 422 #include <__config> |
| 423 #include <__tree> |
| 424 #include <iterator> |
| 425 #include <memory> |
| 426 #include <utility> |
| 427 #include <functional> |
| 428 #include <initializer_list> |
| 429 |
| 430 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 431 #pragma GCC system_header |
| 432 #endif |
| 433 |
| 434 _LIBCPP_BEGIN_NAMESPACE_STD |
| 435 |
| 436 template <class _Key, class _CP, class _Compare, bool = is_empty<_Compare>::valu
e |
| 437 #if __has_feature(is_final) |
| 438 && !__is_final(_Compare) |
| 439 #endif |
| 440 > |
| 441 class __map_value_compare |
| 442 : private _Compare |
| 443 { |
| 444 public: |
| 445 _LIBCPP_INLINE_VISIBILITY |
| 446 __map_value_compare() |
| 447 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) |
| 448 : _Compare() {} |
| 449 _LIBCPP_INLINE_VISIBILITY |
| 450 __map_value_compare(_Compare c) |
| 451 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) |
| 452 : _Compare(c) {} |
| 453 _LIBCPP_INLINE_VISIBILITY |
| 454 const _Compare& key_comp() const _NOEXCEPT {return *this;} |
| 455 _LIBCPP_INLINE_VISIBILITY |
| 456 bool operator()(const _CP& __x, const _CP& __y) const |
| 457 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.fir
st);} |
| 458 _LIBCPP_INLINE_VISIBILITY |
| 459 bool operator()(const _CP& __x, const _Key& __y) const |
| 460 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);} |
| 461 _LIBCPP_INLINE_VISIBILITY |
| 462 bool operator()(const _Key& __x, const _CP& __y) const |
| 463 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);} |
| 464 |
| 465 #if _LIBCPP_STD_VER > 11 |
| 466 template <typename _K2> |
| 467 _LIBCPP_INLINE_VISIBILITY |
| 468 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type |
| 469 operator () ( const _K2& __x, const _CP& __y ) const |
| 470 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);} |
| 471 |
| 472 template <typename _K2> |
| 473 _LIBCPP_INLINE_VISIBILITY |
| 474 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type |
| 475 operator () (const _CP& __x, const _K2& __y) const |
| 476 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);} |
| 477 #endif |
| 478 }; |
| 479 |
| 480 template <class _Key, class _CP, class _Compare> |
| 481 class __map_value_compare<_Key, _CP, _Compare, false> |
| 482 { |
| 483 _Compare comp; |
| 484 |
| 485 public: |
| 486 _LIBCPP_INLINE_VISIBILITY |
| 487 __map_value_compare() |
| 488 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) |
| 489 : comp() {} |
| 490 _LIBCPP_INLINE_VISIBILITY |
| 491 __map_value_compare(_Compare c) |
| 492 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) |
| 493 : comp(c) {} |
| 494 _LIBCPP_INLINE_VISIBILITY |
| 495 const _Compare& key_comp() const _NOEXCEPT {return comp;} |
| 496 |
| 497 _LIBCPP_INLINE_VISIBILITY |
| 498 bool operator()(const _CP& __x, const _CP& __y) const |
| 499 {return comp(__x.__cc.first, __y.__cc.first);} |
| 500 _LIBCPP_INLINE_VISIBILITY |
| 501 bool operator()(const _CP& __x, const _Key& __y) const |
| 502 {return comp(__x.__cc.first, __y);} |
| 503 _LIBCPP_INLINE_VISIBILITY |
| 504 bool operator()(const _Key& __x, const _CP& __y) const |
| 505 {return comp(__x, __y.__cc.first);} |
| 506 |
| 507 #if _LIBCPP_STD_VER > 11 |
| 508 template <typename _K2> |
| 509 _LIBCPP_INLINE_VISIBILITY |
| 510 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type |
| 511 operator () ( const _K2& __x, const _CP& __y ) const |
| 512 {return comp (__x, __y.__cc.first);} |
| 513 |
| 514 template <typename _K2> |
| 515 _LIBCPP_INLINE_VISIBILITY |
| 516 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type |
| 517 operator () (const _CP& __x, const _K2& __y) const |
| 518 {return comp (__x.__cc.first, __y);} |
| 519 #endif |
| 520 }; |
| 521 |
| 522 template <class _Allocator> |
| 523 class __map_node_destructor |
| 524 { |
| 525 typedef _Allocator allocator_type; |
| 526 typedef allocator_traits<allocator_type> __alloc_traits; |
| 527 typedef typename __alloc_traits::value_type::value_type value_type; |
| 528 public: |
| 529 typedef typename __alloc_traits::pointer pointer; |
| 530 private: |
| 531 typedef typename value_type::value_type::first_type first_type; |
| 532 typedef typename value_type::value_type::second_type second_type; |
| 533 |
| 534 allocator_type& __na_; |
| 535 |
| 536 __map_node_destructor& operator=(const __map_node_destructor&); |
| 537 |
| 538 public: |
| 539 bool __first_constructed; |
| 540 bool __second_constructed; |
| 541 |
| 542 _LIBCPP_INLINE_VISIBILITY |
| 543 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT |
| 544 : __na_(__na), |
| 545 __first_constructed(false), |
| 546 __second_constructed(false) |
| 547 {} |
| 548 |
| 549 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 550 _LIBCPP_INLINE_VISIBILITY |
| 551 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEP
T |
| 552 : __na_(__x.__na_), |
| 553 __first_constructed(__x.__value_constructed), |
| 554 __second_constructed(__x.__value_constructed) |
| 555 { |
| 556 __x.__value_constructed = false; |
| 557 } |
| 558 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 559 |
| 560 _LIBCPP_INLINE_VISIBILITY |
| 561 void operator()(pointer __p) _NOEXCEPT |
| 562 { |
| 563 if (__second_constructed) |
| 564 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.s
econd)); |
| 565 if (__first_constructed) |
| 566 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.f
irst)); |
| 567 if (__p) |
| 568 __alloc_traits::deallocate(__na_, __p, 1); |
| 569 } |
| 570 }; |
| 571 |
| 572 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 573 class map; |
| 574 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 575 class multimap; |
| 576 template <class _TreeIterator> class __map_const_iterator; |
| 577 |
| 578 #if __cplusplus >= 201103L |
| 579 |
| 580 template <class _Key, class _Tp> |
| 581 union __value_type |
| 582 { |
| 583 typedef _Key key_type; |
| 584 typedef _Tp mapped_type; |
| 585 typedef pair<const key_type, mapped_type> value_type; |
| 586 typedef pair<key_type, mapped_type> __nc_value_type; |
| 587 |
| 588 value_type __cc; |
| 589 __nc_value_type __nc; |
| 590 |
| 591 template <class ..._Args> |
| 592 _LIBCPP_INLINE_VISIBILITY |
| 593 __value_type(_Args&& ...__args) |
| 594 : __cc(std::forward<_Args>(__args)...) {} |
| 595 |
| 596 _LIBCPP_INLINE_VISIBILITY |
| 597 __value_type(const __value_type& __v) |
| 598 : __cc(__v.__cc) {} |
| 599 |
| 600 _LIBCPP_INLINE_VISIBILITY |
| 601 __value_type(__value_type& __v) |
| 602 : __cc(__v.__cc) {} |
| 603 |
| 604 _LIBCPP_INLINE_VISIBILITY |
| 605 __value_type(__value_type&& __v) |
| 606 : __nc(std::move(__v.__nc)) {} |
| 607 |
| 608 _LIBCPP_INLINE_VISIBILITY |
| 609 __value_type& operator=(const __value_type& __v) |
| 610 {__nc = __v.__cc; return *this;} |
| 611 |
| 612 _LIBCPP_INLINE_VISIBILITY |
| 613 __value_type& operator=(__value_type&& __v) |
| 614 {__nc = std::move(__v.__nc); return *this;} |
| 615 |
| 616 _LIBCPP_INLINE_VISIBILITY |
| 617 ~__value_type() {__cc.~value_type();} |
| 618 }; |
| 619 |
| 620 #else |
| 621 |
| 622 template <class _Key, class _Tp> |
| 623 struct __value_type |
| 624 { |
| 625 typedef _Key key_type; |
| 626 typedef _Tp mapped_type; |
| 627 typedef pair<const key_type, mapped_type> value_type; |
| 628 |
| 629 value_type __cc; |
| 630 |
| 631 _LIBCPP_INLINE_VISIBILITY |
| 632 __value_type() {} |
| 633 |
| 634 template <class _A0> |
| 635 _LIBCPP_INLINE_VISIBILITY |
| 636 __value_type(const _A0& __a0) |
| 637 : __cc(__a0) {} |
| 638 |
| 639 template <class _A0, class _A1> |
| 640 _LIBCPP_INLINE_VISIBILITY |
| 641 __value_type(const _A0& __a0, const _A1& __a1) |
| 642 : __cc(__a0, __a1) {} |
| 643 }; |
| 644 |
| 645 #endif |
| 646 |
| 647 template <class _TreeIterator> |
| 648 class _LIBCPP_TYPE_VIS_ONLY __map_iterator |
| 649 { |
| 650 _TreeIterator __i_; |
| 651 |
| 652 typedef typename _TreeIterator::__pointer_traits __pointer_trait
s; |
| 653 typedef const typename _TreeIterator::value_type::value_type::first_type __k
ey_type; |
| 654 typedef typename _TreeIterator::value_type::value_type::second_type __m
apped_type; |
| 655 public: |
| 656 typedef bidirectional_iterator_tag iterator_catego
ry; |
| 657 typedef pair<__key_type, __mapped_type> value_type; |
| 658 typedef typename _TreeIterator::difference_type difference_type
; |
| 659 typedef value_type& reference; |
| 660 typedef typename __pointer_traits::template |
| 661 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES |
| 662 rebind<value_type> |
| 663 #else |
| 664 rebind<value_type>::other |
| 665 #endif |
| 666 pointer; |
| 667 |
| 668 _LIBCPP_INLINE_VISIBILITY |
| 669 __map_iterator() _NOEXCEPT {} |
| 670 |
| 671 _LIBCPP_INLINE_VISIBILITY |
| 672 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} |
| 673 |
| 674 _LIBCPP_INLINE_VISIBILITY |
| 675 reference operator*() const {return __i_->__cc;} |
| 676 _LIBCPP_INLINE_VISIBILITY |
| 677 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_-
>__cc);} |
| 678 |
| 679 _LIBCPP_INLINE_VISIBILITY |
| 680 __map_iterator& operator++() {++__i_; return *this;} |
| 681 _LIBCPP_INLINE_VISIBILITY |
| 682 __map_iterator operator++(int) |
| 683 { |
| 684 __map_iterator __t(*this); |
| 685 ++(*this); |
| 686 return __t; |
| 687 } |
| 688 |
| 689 _LIBCPP_INLINE_VISIBILITY |
| 690 __map_iterator& operator--() {--__i_; return *this;} |
| 691 _LIBCPP_INLINE_VISIBILITY |
| 692 __map_iterator operator--(int) |
| 693 { |
| 694 __map_iterator __t(*this); |
| 695 --(*this); |
| 696 return __t; |
| 697 } |
| 698 |
| 699 friend _LIBCPP_INLINE_VISIBILITY |
| 700 bool operator==(const __map_iterator& __x, const __map_iterator& __y) |
| 701 {return __x.__i_ == __y.__i_;} |
| 702 friend |
| 703 _LIBCPP_INLINE_VISIBILITY |
| 704 bool operator!=(const __map_iterator& __x, const __map_iterator& __y) |
| 705 {return __x.__i_ != __y.__i_;} |
| 706 |
| 707 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map
; |
| 708 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY mul
timap; |
| 709 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator; |
| 710 }; |
| 711 |
| 712 template <class _TreeIterator> |
| 713 class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator |
| 714 { |
| 715 _TreeIterator __i_; |
| 716 |
| 717 typedef typename _TreeIterator::__pointer_traits __pointer_trait
s; |
| 718 typedef const typename _TreeIterator::value_type::value_type::first_type __k
ey_type; |
| 719 typedef typename _TreeIterator::value_type::value_type::second_type __m
apped_type; |
| 720 public: |
| 721 typedef bidirectional_iterator_tag iterator_catego
ry; |
| 722 typedef pair<__key_type, __mapped_type> value_type; |
| 723 typedef typename _TreeIterator::difference_type difference_type
; |
| 724 typedef const value_type& reference; |
| 725 typedef typename __pointer_traits::template |
| 726 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES |
| 727 rebind<const value_type> |
| 728 #else |
| 729 rebind<const value_type>::other |
| 730 #endif |
| 731 pointer; |
| 732 |
| 733 _LIBCPP_INLINE_VISIBILITY |
| 734 __map_const_iterator() _NOEXCEPT {} |
| 735 |
| 736 _LIBCPP_INLINE_VISIBILITY |
| 737 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} |
| 738 _LIBCPP_INLINE_VISIBILITY |
| 739 __map_const_iterator( |
| 740 __map_iterator<typename _TreeIterator::__non_const_iterator> __i) |
| 741 _NOEXCEPT |
| 742 : __i_(__i.__i_) {} |
| 743 |
| 744 _LIBCPP_INLINE_VISIBILITY |
| 745 reference operator*() const {return __i_->__cc;} |
| 746 _LIBCPP_INLINE_VISIBILITY |
| 747 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_-
>__cc);} |
| 748 |
| 749 _LIBCPP_INLINE_VISIBILITY |
| 750 __map_const_iterator& operator++() {++__i_; return *this;} |
| 751 _LIBCPP_INLINE_VISIBILITY |
| 752 __map_const_iterator operator++(int) |
| 753 { |
| 754 __map_const_iterator __t(*this); |
| 755 ++(*this); |
| 756 return __t; |
| 757 } |
| 758 |
| 759 _LIBCPP_INLINE_VISIBILITY |
| 760 __map_const_iterator& operator--() {--__i_; return *this;} |
| 761 _LIBCPP_INLINE_VISIBILITY |
| 762 __map_const_iterator operator--(int) |
| 763 { |
| 764 __map_const_iterator __t(*this); |
| 765 --(*this); |
| 766 return __t; |
| 767 } |
| 768 |
| 769 friend _LIBCPP_INLINE_VISIBILITY |
| 770 bool operator==(const __map_const_iterator& __x, const __map_const_iterator&
__y) |
| 771 {return __x.__i_ == __y.__i_;} |
| 772 friend _LIBCPP_INLINE_VISIBILITY |
| 773 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator&
__y) |
| 774 {return __x.__i_ != __y.__i_;} |
| 775 |
| 776 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map
; |
| 777 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY mul
timap; |
| 778 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_con
st_iterator; |
| 779 }; |
| 780 |
| 781 template <class _Key, class _Tp, class _Compare = less<_Key>, |
| 782 class _Allocator = allocator<pair<const _Key, _Tp> > > |
| 783 class _LIBCPP_TYPE_VIS_ONLY map |
| 784 { |
| 785 public: |
| 786 // types: |
| 787 typedef _Key key_type; |
| 788 typedef _Tp mapped_type; |
| 789 typedef pair<const key_type, mapped_type> value_type; |
| 790 typedef pair<key_type, mapped_type> __nc_value_type; |
| 791 typedef _Compare key_compare; |
| 792 typedef _Allocator allocator_type; |
| 793 typedef value_type& reference; |
| 794 typedef const value_type& const_reference; |
| 795 |
| 796 class _LIBCPP_TYPE_VIS_ONLY value_compare |
| 797 : public binary_function<value_type, value_type, bool> |
| 798 { |
| 799 friend class map; |
| 800 protected: |
| 801 key_compare comp; |
| 802 |
| 803 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} |
| 804 public: |
| 805 _LIBCPP_INLINE_VISIBILITY |
| 806 bool operator()(const value_type& __x, const value_type& __y) const |
| 807 {return comp(__x.first, __y.first);} |
| 808 }; |
| 809 |
| 810 private: |
| 811 |
| 812 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; |
| 813 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; |
| 814 typedef typename allocator_traits<allocator_type>::template |
| 815 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES |
| 816 rebind_alloc<__value_type> |
| 817 #else |
| 818 rebind_alloc<__value_type>::other |
| 819 #endif |
| 820 __allocator_type; |
| 821 typedef __tree<__value_type, __vc, __allocator_type> __base; |
| 822 typedef typename __base::__node_traits __node_traits; |
| 823 typedef allocator_traits<allocator_type> __alloc_traits; |
| 824 |
| 825 __base __tree_; |
| 826 |
| 827 public: |
| 828 typedef typename __alloc_traits::pointer pointer; |
| 829 typedef typename __alloc_traits::const_pointer const_pointer; |
| 830 typedef typename __alloc_traits::size_type size_type; |
| 831 typedef typename __alloc_traits::difference_type difference_type; |
| 832 typedef __map_iterator<typename __base::iterator> iterator; |
| 833 typedef __map_const_iterator<typename __base::const_iterator> const_iterator
; |
| 834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
| 835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterat
or; |
| 836 |
| 837 _LIBCPP_INLINE_VISIBILITY |
| 838 explicit map(const key_compare& __comp = key_compare()) |
| 839 _NOEXCEPT_( |
| 840 is_nothrow_default_constructible<allocator_type>::value && |
| 841 is_nothrow_default_constructible<key_compare>::value && |
| 842 is_nothrow_copy_constructible<key_compare>::value) |
| 843 : __tree_(__vc(__comp)) {} |
| 844 |
| 845 _LIBCPP_INLINE_VISIBILITY |
| 846 explicit map(const key_compare& __comp, const allocator_type& __a) |
| 847 : __tree_(__vc(__comp), __a) {} |
| 848 |
| 849 template <class _InputIterator> |
| 850 _LIBCPP_INLINE_VISIBILITY |
| 851 map(_InputIterator __f, _InputIterator __l, |
| 852 const key_compare& __comp = key_compare()) |
| 853 : __tree_(__vc(__comp)) |
| 854 { |
| 855 insert(__f, __l); |
| 856 } |
| 857 |
| 858 template <class _InputIterator> |
| 859 _LIBCPP_INLINE_VISIBILITY |
| 860 map(_InputIterator __f, _InputIterator __l, |
| 861 const key_compare& __comp, const allocator_type& __a) |
| 862 : __tree_(__vc(__comp), __a) |
| 863 { |
| 864 insert(__f, __l); |
| 865 } |
| 866 |
| 867 #if _LIBCPP_STD_VER > 11 |
| 868 template <class _InputIterator> |
| 869 _LIBCPP_INLINE_VISIBILITY |
| 870 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) |
| 871 : map(__f, __l, key_compare(), __a) {} |
| 872 #endif |
| 873 |
| 874 _LIBCPP_INLINE_VISIBILITY |
| 875 map(const map& __m) |
| 876 : __tree_(__m.__tree_) |
| 877 { |
| 878 insert(__m.begin(), __m.end()); |
| 879 } |
| 880 |
| 881 _LIBCPP_INLINE_VISIBILITY |
| 882 map& operator=(const map& __m) |
| 883 { |
| 884 #if __cplusplus >= 201103L |
| 885 __tree_ = __m.__tree_; |
| 886 #else |
| 887 __tree_.clear(); |
| 888 __tree_.value_comp() = __m.__tree_.value_comp(); |
| 889 __tree_.__copy_assign_alloc(__m.__tree_); |
| 890 insert(__m.begin(), __m.end()); |
| 891 #endif |
| 892 return *this; |
| 893 } |
| 894 |
| 895 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 896 |
| 897 _LIBCPP_INLINE_VISIBILITY |
| 898 map(map&& __m) |
| 899 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
| 900 : __tree_(_VSTD::move(__m.__tree_)) |
| 901 { |
| 902 } |
| 903 |
| 904 map(map&& __m, const allocator_type& __a); |
| 905 |
| 906 _LIBCPP_INLINE_VISIBILITY |
| 907 map& operator=(map&& __m) |
| 908 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
| 909 { |
| 910 __tree_ = _VSTD::move(__m.__tree_); |
| 911 return *this; |
| 912 } |
| 913 |
| 914 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 915 |
| 916 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 917 |
| 918 _LIBCPP_INLINE_VISIBILITY |
| 919 map(initializer_list<value_type> __il, const key_compare& __comp = key_compa
re()) |
| 920 : __tree_(__vc(__comp)) |
| 921 { |
| 922 insert(__il.begin(), __il.end()); |
| 923 } |
| 924 |
| 925 _LIBCPP_INLINE_VISIBILITY |
| 926 map(initializer_list<value_type> __il, const key_compare& __comp, const allo
cator_type& __a) |
| 927 : __tree_(__vc(__comp), __a) |
| 928 { |
| 929 insert(__il.begin(), __il.end()); |
| 930 } |
| 931 |
| 932 #if _LIBCPP_STD_VER > 11 |
| 933 _LIBCPP_INLINE_VISIBILITY |
| 934 map(initializer_list<value_type> __il, const allocator_type& __a) |
| 935 : map(__il, key_compare(), __a) {} |
| 936 #endif |
| 937 |
| 938 _LIBCPP_INLINE_VISIBILITY |
| 939 map& operator=(initializer_list<value_type> __il) |
| 940 { |
| 941 __tree_.__assign_unique(__il.begin(), __il.end()); |
| 942 return *this; |
| 943 } |
| 944 |
| 945 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 946 |
| 947 _LIBCPP_INLINE_VISIBILITY |
| 948 explicit map(const allocator_type& __a) |
| 949 : __tree_(__a) |
| 950 { |
| 951 } |
| 952 |
| 953 _LIBCPP_INLINE_VISIBILITY |
| 954 map(const map& __m, const allocator_type& __a) |
| 955 : __tree_(__m.__tree_.value_comp(), __a) |
| 956 { |
| 957 insert(__m.begin(), __m.end()); |
| 958 } |
| 959 |
| 960 _LIBCPP_INLINE_VISIBILITY |
| 961 iterator begin() _NOEXCEPT {return __tree_.begin();} |
| 962 _LIBCPP_INLINE_VISIBILITY |
| 963 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
| 964 _LIBCPP_INLINE_VISIBILITY |
| 965 iterator end() _NOEXCEPT {return __tree_.end();} |
| 966 _LIBCPP_INLINE_VISIBILITY |
| 967 const_iterator end() const _NOEXCEPT {return __tree_.end();} |
| 968 |
| 969 _LIBCPP_INLINE_VISIBILITY |
| 970 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} |
| 971 _LIBCPP_INLINE_VISIBILITY |
| 972 const_reverse_iterator rbegin() const _NOEXCEPT |
| 973 {return const_reverse_iterator(end());} |
| 974 _LIBCPP_INLINE_VISIBILITY |
| 975 reverse_iterator rend() _NOEXCEPT |
| 976 {return reverse_iterator(begin());} |
| 977 _LIBCPP_INLINE_VISIBILITY |
| 978 const_reverse_iterator rend() const _NOEXCEPT |
| 979 {return const_reverse_iterator(begin());} |
| 980 |
| 981 _LIBCPP_INLINE_VISIBILITY |
| 982 const_iterator cbegin() const _NOEXCEPT {return begin();} |
| 983 _LIBCPP_INLINE_VISIBILITY |
| 984 const_iterator cend() const _NOEXCEPT {return end();} |
| 985 _LIBCPP_INLINE_VISIBILITY |
| 986 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
| 987 _LIBCPP_INLINE_VISIBILITY |
| 988 const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
| 989 |
| 990 _LIBCPP_INLINE_VISIBILITY |
| 991 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
| 992 _LIBCPP_INLINE_VISIBILITY |
| 993 size_type size() const _NOEXCEPT {return __tree_.size();} |
| 994 _LIBCPP_INLINE_VISIBILITY |
| 995 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
| 996 |
| 997 mapped_type& operator[](const key_type& __k); |
| 998 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 999 mapped_type& operator[](key_type&& __k); |
| 1000 #endif |
| 1001 |
| 1002 mapped_type& at(const key_type& __k); |
| 1003 const mapped_type& at(const key_type& __k) const; |
| 1004 |
| 1005 _LIBCPP_INLINE_VISIBILITY |
| 1006 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
| 1007 _LIBCPP_INLINE_VISIBILITY |
| 1008 key_compare key_comp() const {return __tree_.value_comp().key_comp()
;} |
| 1009 _LIBCPP_INLINE_VISIBILITY |
| 1010 value_compare value_comp() const {return value_compare(__tree_.value_com
p().key_comp());} |
| 1011 |
| 1012 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1013 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1014 |
| 1015 template <class ..._Args> |
| 1016 pair<iterator, bool> |
| 1017 emplace(_Args&& ...__args); |
| 1018 |
| 1019 template <class ..._Args> |
| 1020 iterator |
| 1021 emplace_hint(const_iterator __p, _Args&& ...__args); |
| 1022 |
| 1023 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1024 |
| 1025 template <class _Pp, |
| 1026 class = typename enable_if<is_constructible<value_type, _Pp>::valu
e>::type> |
| 1027 _LIBCPP_INLINE_VISIBILITY |
| 1028 pair<iterator, bool> insert(_Pp&& __p) |
| 1029 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));} |
| 1030 |
| 1031 template <class _Pp, |
| 1032 class = typename enable_if<is_constructible<value_type, _Pp>::valu
e>::type> |
| 1033 _LIBCPP_INLINE_VISIBILITY |
| 1034 iterator insert(const_iterator __pos, _Pp&& __p) |
| 1035 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p)
);} |
| 1036 |
| 1037 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1038 |
| 1039 _LIBCPP_INLINE_VISIBILITY |
| 1040 pair<iterator, bool> |
| 1041 insert(const value_type& __v) {return __tree_.__insert_unique(__v);} |
| 1042 |
| 1043 _LIBCPP_INLINE_VISIBILITY |
| 1044 iterator |
| 1045 insert(const_iterator __p, const value_type& __v) |
| 1046 {return __tree_.__insert_unique(__p.__i_, __v);} |
| 1047 |
| 1048 template <class _InputIterator> |
| 1049 _LIBCPP_INLINE_VISIBILITY |
| 1050 void insert(_InputIterator __f, _InputIterator __l) |
| 1051 { |
| 1052 for (const_iterator __e = cend(); __f != __l; ++__f) |
| 1053 insert(__e.__i_, *__f); |
| 1054 } |
| 1055 |
| 1056 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1057 |
| 1058 _LIBCPP_INLINE_VISIBILITY |
| 1059 void insert(initializer_list<value_type> __il) |
| 1060 {insert(__il.begin(), __il.end());} |
| 1061 |
| 1062 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1063 |
| 1064 _LIBCPP_INLINE_VISIBILITY |
| 1065 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} |
| 1066 _LIBCPP_INLINE_VISIBILITY |
| 1067 size_type erase(const key_type& __k) |
| 1068 {return __tree_.__erase_unique(__k);} |
| 1069 _LIBCPP_INLINE_VISIBILITY |
| 1070 iterator erase(const_iterator __f, const_iterator __l) |
| 1071 {return __tree_.erase(__f.__i_, __l.__i_);} |
| 1072 _LIBCPP_INLINE_VISIBILITY |
| 1073 void clear() _NOEXCEPT {__tree_.clear();} |
| 1074 |
| 1075 _LIBCPP_INLINE_VISIBILITY |
| 1076 void swap(map& __m) |
| 1077 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
| 1078 {__tree_.swap(__m.__tree_);} |
| 1079 |
| 1080 _LIBCPP_INLINE_VISIBILITY |
| 1081 iterator find(const key_type& __k) {return __tree_.find(__k);} |
| 1082 _LIBCPP_INLINE_VISIBILITY |
| 1083 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
| 1084 #if _LIBCPP_STD_VER > 11 |
| 1085 template <typename _K2> |
| 1086 _LIBCPP_INLINE_VISIBILITY |
| 1087 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1088 find(const _K2& __k) {return __tree_.find(__k);} |
| 1089 template <typename _K2> |
| 1090 _LIBCPP_INLINE_VISIBILITY |
| 1091 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1092 find(const _K2& __k) const {return __tree_.find(__k);} |
| 1093 #endif |
| 1094 |
| 1095 _LIBCPP_INLINE_VISIBILITY |
| 1096 size_type count(const key_type& __k) const |
| 1097 {return __tree_.__count_unique(__k);} |
| 1098 _LIBCPP_INLINE_VISIBILITY |
| 1099 iterator lower_bound(const key_type& __k) |
| 1100 {return __tree_.lower_bound(__k);} |
| 1101 _LIBCPP_INLINE_VISIBILITY |
| 1102 const_iterator lower_bound(const key_type& __k) const |
| 1103 {return __tree_.lower_bound(__k);} |
| 1104 #if _LIBCPP_STD_VER > 11 |
| 1105 template <typename _K2> |
| 1106 _LIBCPP_INLINE_VISIBILITY |
| 1107 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1108 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
| 1109 |
| 1110 template <typename _K2> |
| 1111 _LIBCPP_INLINE_VISIBILITY |
| 1112 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1113 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
| 1114 #endif |
| 1115 |
| 1116 _LIBCPP_INLINE_VISIBILITY |
| 1117 iterator upper_bound(const key_type& __k) |
| 1118 {return __tree_.upper_bound(__k);} |
| 1119 _LIBCPP_INLINE_VISIBILITY |
| 1120 const_iterator upper_bound(const key_type& __k) const |
| 1121 {return __tree_.upper_bound(__k);} |
| 1122 #if _LIBCPP_STD_VER > 11 |
| 1123 template <typename _K2> |
| 1124 _LIBCPP_INLINE_VISIBILITY |
| 1125 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1126 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
| 1127 template <typename _K2> |
| 1128 _LIBCPP_INLINE_VISIBILITY |
| 1129 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1130 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
| 1131 #endif |
| 1132 |
| 1133 _LIBCPP_INLINE_VISIBILITY |
| 1134 pair<iterator,iterator> equal_range(const key_type& __k) |
| 1135 {return __tree_.__equal_range_unique(__k);} |
| 1136 _LIBCPP_INLINE_VISIBILITY |
| 1137 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
| 1138 {return __tree_.__equal_range_unique(__k);} |
| 1139 #if _LIBCPP_STD_VER > 11 |
| 1140 template <typename _K2> |
| 1141 _LIBCPP_INLINE_VISIBILITY |
| 1142 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iter
ator>>::type |
| 1143 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);
} |
| 1144 template <typename _K2> |
| 1145 _LIBCPP_INLINE_VISIBILITY |
| 1146 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterato
r,const_iterator>>::type |
| 1147 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);
} |
| 1148 #endif |
| 1149 |
| 1150 private: |
| 1151 typedef typename __base::__node __node; |
| 1152 typedef typename __base::__node_allocator __node_allocator; |
| 1153 typedef typename __base::__node_pointer __node_pointer; |
| 1154 typedef typename __base::__node_const_pointer __node_const_pointer; |
| 1155 typedef typename __base::__node_base_pointer __node_base_pointer; |
| 1156 typedef typename __base::__node_base_const_pointer __node_base_const_pointer
; |
| 1157 typedef __map_node_destructor<__node_allocator> _Dp; |
| 1158 typedef unique_ptr<__node, _Dp> __node_holder; |
| 1159 |
| 1160 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1161 __node_holder __construct_node(); |
| 1162 template <class _A0> |
| 1163 __node_holder __construct_node(_A0&& __a0); |
| 1164 __node_holder __construct_node_with_key(key_type&& __k); |
| 1165 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1166 template <class _A0, class _A1, class ..._Args> |
| 1167 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args
); |
| 1168 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1169 #endif |
| 1170 __node_holder __construct_node_with_key(const key_type& __k); |
| 1171 |
| 1172 __node_base_pointer& |
| 1173 __find_equal_key(__node_base_pointer& __parent, const key_type& __k); |
| 1174 __node_base_const_pointer |
| 1175 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __
k) const; |
| 1176 }; |
| 1177 |
| 1178 // Find place to insert if __k doesn't exist |
| 1179 // Set __parent to parent of null leaf |
| 1180 // Return reference to null leaf |
| 1181 // If __k exists, set parent to node of __k and return reference to node of __k |
| 1182 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1183 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer& |
| 1184 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __pa
rent, |
| 1185 const key_type& __k) |
| 1186 { |
| 1187 __node_pointer __nd = __tree_.__root(); |
| 1188 if (__nd != nullptr) |
| 1189 { |
| 1190 while (true) |
| 1191 { |
| 1192 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first)) |
| 1193 { |
| 1194 if (__nd->__left_ != nullptr) |
| 1195 __nd = static_cast<__node_pointer>(__nd->__left_); |
| 1196 else |
| 1197 { |
| 1198 __parent = static_cast<__node_base_pointer>(__nd); |
| 1199 return __parent->__left_; |
| 1200 } |
| 1201 } |
| 1202 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first,
__k)) |
| 1203 { |
| 1204 if (__nd->__right_ != nullptr) |
| 1205 __nd = static_cast<__node_pointer>(__nd->__right_); |
| 1206 else |
| 1207 { |
| 1208 __parent = static_cast<__node_base_pointer>(__nd); |
| 1209 return __parent->__right_; |
| 1210 } |
| 1211 } |
| 1212 else |
| 1213 { |
| 1214 __parent = static_cast<__node_base_pointer>(__nd); |
| 1215 return __parent; |
| 1216 } |
| 1217 } |
| 1218 } |
| 1219 __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); |
| 1220 return __parent->__left_; |
| 1221 } |
| 1222 |
| 1223 // Find __k |
| 1224 // Set __parent to parent of null leaf and |
| 1225 // return reference to null leaf iv __k does not exist. |
| 1226 // If __k exists, set parent to node of __k and return reference to node of __k |
| 1227 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1228 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer |
| 1229 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer
& __parent, |
| 1230 const key_type& __k) cons
t |
| 1231 { |
| 1232 __node_const_pointer __nd = __tree_.__root(); |
| 1233 if (__nd != nullptr) |
| 1234 { |
| 1235 while (true) |
| 1236 { |
| 1237 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first)) |
| 1238 { |
| 1239 if (__nd->__left_ != nullptr) |
| 1240 __nd = static_cast<__node_pointer>(__nd->__left_); |
| 1241 else |
| 1242 { |
| 1243 __parent = static_cast<__node_base_pointer>(__nd); |
| 1244 return const_cast<const __node_base_const_pointer&>(__parent
->__left_); |
| 1245 } |
| 1246 } |
| 1247 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first,
__k)) |
| 1248 { |
| 1249 if (__nd->__right_ != nullptr) |
| 1250 __nd = static_cast<__node_pointer>(__nd->__right_); |
| 1251 else |
| 1252 { |
| 1253 __parent = static_cast<__node_base_pointer>(__nd); |
| 1254 return const_cast<const __node_base_const_pointer&>(__parent
->__right_); |
| 1255 } |
| 1256 } |
| 1257 else |
| 1258 { |
| 1259 __parent = static_cast<__node_base_pointer>(__nd); |
| 1260 return __parent; |
| 1261 } |
| 1262 } |
| 1263 } |
| 1264 __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); |
| 1265 return const_cast<const __node_base_const_pointer&>(__parent->__left_); |
| 1266 } |
| 1267 |
| 1268 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1269 |
| 1270 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1271 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) |
| 1272 : __tree_(_VSTD::move(__m.__tree_), __a) |
| 1273 { |
| 1274 if (__a != __m.get_allocator()) |
| 1275 { |
| 1276 const_iterator __e = cend(); |
| 1277 while (!__m.empty()) |
| 1278 __tree_.__insert_unique(__e.__i_, |
| 1279 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_))
; |
| 1280 } |
| 1281 } |
| 1282 |
| 1283 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1284 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1285 map<_Key, _Tp, _Compare, _Allocator>::__construct_node() |
| 1286 { |
| 1287 __node_allocator& __na = __tree_.__node_alloc(); |
| 1288 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1289 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); |
| 1290 __h.get_deleter().__first_constructed = true; |
| 1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); |
| 1292 __h.get_deleter().__second_constructed = true; |
| 1293 return __h; |
| 1294 } |
| 1295 |
| 1296 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1297 template <class _A0> |
| 1298 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1299 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) |
| 1300 { |
| 1301 __node_allocator& __na = __tree_.__node_alloc(); |
| 1302 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1303 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forwa
rd<_A0>(__a0)); |
| 1304 __h.get_deleter().__first_constructed = true; |
| 1305 __h.get_deleter().__second_constructed = true; |
| 1306 return __h; |
| 1307 } |
| 1308 |
| 1309 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1310 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1311 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k) |
| 1312 { |
| 1313 __node_allocator& __na = __tree_.__node_alloc(); |
| 1314 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1315 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _
VSTD::move(__k)); |
| 1316 __h.get_deleter().__first_constructed = true; |
| 1317 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); |
| 1318 __h.get_deleter().__second_constructed = true; |
| 1319 return __h; |
| 1320 } |
| 1321 |
| 1322 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1323 |
| 1324 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1325 template <class _A0, class _A1, class ..._Args> |
| 1326 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1327 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _
Args&& ...__args) |
| 1328 { |
| 1329 __node_allocator& __na = __tree_.__node_alloc(); |
| 1330 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1331 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), |
| 1332 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1
), |
| 1333 _VSTD::forward<_Args>(__args)...); |
| 1334 __h.get_deleter().__first_constructed = true; |
| 1335 __h.get_deleter().__second_constructed = true; |
| 1336 return __h; |
| 1337 } |
| 1338 |
| 1339 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1340 |
| 1341 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1342 |
| 1343 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1344 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1345 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type&
__k) |
| 1346 { |
| 1347 __node_allocator& __na = __tree_.__node_alloc(); |
| 1348 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1349 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _
_k); |
| 1350 __h.get_deleter().__first_constructed = true; |
| 1351 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); |
| 1352 __h.get_deleter().__second_constructed = true; |
| 1353 return _VSTD::move(__h); // explicitly moved for C++03 |
| 1354 } |
| 1355 |
| 1356 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1357 _Tp& |
| 1358 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) |
| 1359 { |
| 1360 __node_base_pointer __parent; |
| 1361 __node_base_pointer& __child = __find_equal_key(__parent, __k); |
| 1362 __node_pointer __r = static_cast<__node_pointer>(__child); |
| 1363 if (__child == nullptr) |
| 1364 { |
| 1365 __node_holder __h = __construct_node_with_key(__k); |
| 1366 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_poin
ter>(__h.get())); |
| 1367 __r = __h.release(); |
| 1368 } |
| 1369 return __r->__value_.__cc.second; |
| 1370 } |
| 1371 |
| 1372 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1373 |
| 1374 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1375 _Tp& |
| 1376 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) |
| 1377 { |
| 1378 __node_base_pointer __parent; |
| 1379 __node_base_pointer& __child = __find_equal_key(__parent, __k); |
| 1380 __node_pointer __r = static_cast<__node_pointer>(__child); |
| 1381 if (__child == nullptr) |
| 1382 { |
| 1383 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); |
| 1384 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_poin
ter>(__h.get())); |
| 1385 __r = __h.release(); |
| 1386 } |
| 1387 return __r->__value_.__cc.second; |
| 1388 } |
| 1389 |
| 1390 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1391 |
| 1392 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1393 _Tp& |
| 1394 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) |
| 1395 { |
| 1396 __node_base_pointer __parent; |
| 1397 __node_base_pointer& __child = __find_equal_key(__parent, __k); |
| 1398 #ifndef _LIBCPP_NO_EXCEPTIONS |
| 1399 if (__child == nullptr) |
| 1400 throw out_of_range("map::at: key not found"); |
| 1401 #endif // _LIBCPP_NO_EXCEPTIONS |
| 1402 return static_cast<__node_pointer>(__child)->__value_.__cc.second; |
| 1403 } |
| 1404 |
| 1405 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1406 const _Tp& |
| 1407 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const |
| 1408 { |
| 1409 __node_base_const_pointer __parent; |
| 1410 __node_base_const_pointer __child = __find_equal_key(__parent, __k); |
| 1411 #ifndef _LIBCPP_NO_EXCEPTIONS |
| 1412 if (__child == nullptr) |
| 1413 throw out_of_range("map::at: key not found"); |
| 1414 #endif // _LIBCPP_NO_EXCEPTIONS |
| 1415 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second; |
| 1416 } |
| 1417 |
| 1418 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIAD
ICS) |
| 1419 |
| 1420 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1421 template <class ..._Args> |
| 1422 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool> |
| 1423 map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) |
| 1424 { |
| 1425 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); |
| 1426 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get()); |
| 1427 if (__r.second) |
| 1428 __h.release(); |
| 1429 return __r; |
| 1430 } |
| 1431 |
| 1432 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1433 template <class ..._Args> |
| 1434 typename map<_Key, _Tp, _Compare, _Allocator>::iterator |
| 1435 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, |
| 1436 _Args&& ...__args) |
| 1437 { |
| 1438 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); |
| 1439 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); |
| 1440 if (__r.__i_.__ptr_ == __h.get()) |
| 1441 __h.release(); |
| 1442 return __r; |
| 1443 } |
| 1444 |
| 1445 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO
_VARIADICS) |
| 1446 |
| 1447 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1448 inline _LIBCPP_INLINE_VISIBILITY |
| 1449 bool |
| 1450 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1451 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1452 { |
| 1453 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.
begin()); |
| 1454 } |
| 1455 |
| 1456 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1457 inline _LIBCPP_INLINE_VISIBILITY |
| 1458 bool |
| 1459 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1460 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1461 { |
| 1462 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), _
_y.end()); |
| 1463 } |
| 1464 |
| 1465 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1466 inline _LIBCPP_INLINE_VISIBILITY |
| 1467 bool |
| 1468 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1469 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1470 { |
| 1471 return !(__x == __y); |
| 1472 } |
| 1473 |
| 1474 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1475 inline _LIBCPP_INLINE_VISIBILITY |
| 1476 bool |
| 1477 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1478 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1479 { |
| 1480 return __y < __x; |
| 1481 } |
| 1482 |
| 1483 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1484 inline _LIBCPP_INLINE_VISIBILITY |
| 1485 bool |
| 1486 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1487 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1488 { |
| 1489 return !(__x < __y); |
| 1490 } |
| 1491 |
| 1492 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1493 inline _LIBCPP_INLINE_VISIBILITY |
| 1494 bool |
| 1495 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1496 const map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1497 { |
| 1498 return !(__y < __x); |
| 1499 } |
| 1500 |
| 1501 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1502 inline _LIBCPP_INLINE_VISIBILITY |
| 1503 void |
| 1504 swap(map<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1505 map<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1506 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| 1507 { |
| 1508 __x.swap(__y); |
| 1509 } |
| 1510 |
| 1511 template <class _Key, class _Tp, class _Compare = less<_Key>, |
| 1512 class _Allocator = allocator<pair<const _Key, _Tp> > > |
| 1513 class _LIBCPP_TYPE_VIS_ONLY multimap |
| 1514 { |
| 1515 public: |
| 1516 // types: |
| 1517 typedef _Key key_type; |
| 1518 typedef _Tp mapped_type; |
| 1519 typedef pair<const key_type, mapped_type> value_type; |
| 1520 typedef pair<key_type, mapped_type> __nc_value_type; |
| 1521 typedef _Compare key_compare; |
| 1522 typedef _Allocator allocator_type; |
| 1523 typedef value_type& reference; |
| 1524 typedef const value_type& const_reference; |
| 1525 |
| 1526 class _LIBCPP_TYPE_VIS_ONLY value_compare |
| 1527 : public binary_function<value_type, value_type, bool> |
| 1528 { |
| 1529 friend class multimap; |
| 1530 protected: |
| 1531 key_compare comp; |
| 1532 |
| 1533 _LIBCPP_INLINE_VISIBILITY |
| 1534 value_compare(key_compare c) : comp(c) {} |
| 1535 public: |
| 1536 _LIBCPP_INLINE_VISIBILITY |
| 1537 bool operator()(const value_type& __x, const value_type& __y) const |
| 1538 {return comp(__x.first, __y.first);} |
| 1539 }; |
| 1540 |
| 1541 private: |
| 1542 |
| 1543 typedef _VSTD::__value_type<key_type, mapped_type> __value_type; |
| 1544 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; |
| 1545 typedef typename allocator_traits<allocator_type>::template |
| 1546 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES |
| 1547 rebind_alloc<__value_type> |
| 1548 #else |
| 1549 rebind_alloc<__value_type>::other |
| 1550 #endif |
| 1551 __allocator_
type; |
| 1552 typedef __tree<__value_type, __vc, __allocator_type> __base; |
| 1553 typedef typename __base::__node_traits __node_trait
s; |
| 1554 typedef allocator_traits<allocator_type> __alloc_trai
ts; |
| 1555 |
| 1556 __base __tree_; |
| 1557 |
| 1558 public: |
| 1559 typedef typename __alloc_traits::pointer pointer; |
| 1560 typedef typename __alloc_traits::const_pointer const_pointer; |
| 1561 typedef typename __alloc_traits::size_type size_type; |
| 1562 typedef typename __alloc_traits::difference_type difference_type; |
| 1563 typedef __map_iterator<typename __base::iterator> iterator; |
| 1564 typedef __map_const_iterator<typename __base::const_iterator> const_iterator
; |
| 1565 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
| 1566 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterat
or; |
| 1567 |
| 1568 _LIBCPP_INLINE_VISIBILITY |
| 1569 explicit multimap(const key_compare& __comp = key_compare()) |
| 1570 _NOEXCEPT_( |
| 1571 is_nothrow_default_constructible<allocator_type>::value && |
| 1572 is_nothrow_default_constructible<key_compare>::value && |
| 1573 is_nothrow_copy_constructible<key_compare>::value) |
| 1574 : __tree_(__vc(__comp)) {} |
| 1575 |
| 1576 _LIBCPP_INLINE_VISIBILITY |
| 1577 explicit multimap(const key_compare& __comp, const allocator_type& __a) |
| 1578 : __tree_(__vc(__comp), __a) {} |
| 1579 |
| 1580 template <class _InputIterator> |
| 1581 _LIBCPP_INLINE_VISIBILITY |
| 1582 multimap(_InputIterator __f, _InputIterator __l, |
| 1583 const key_compare& __comp = key_compare()) |
| 1584 : __tree_(__vc(__comp)) |
| 1585 { |
| 1586 insert(__f, __l); |
| 1587 } |
| 1588 |
| 1589 template <class _InputIterator> |
| 1590 _LIBCPP_INLINE_VISIBILITY |
| 1591 multimap(_InputIterator __f, _InputIterator __l, |
| 1592 const key_compare& __comp, const allocator_type& __a) |
| 1593 : __tree_(__vc(__comp), __a) |
| 1594 { |
| 1595 insert(__f, __l); |
| 1596 } |
| 1597 |
| 1598 #if _LIBCPP_STD_VER > 11 |
| 1599 template <class _InputIterator> |
| 1600 _LIBCPP_INLINE_VISIBILITY |
| 1601 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) |
| 1602 : multimap(__f, __l, key_compare(), __a) {} |
| 1603 #endif |
| 1604 |
| 1605 _LIBCPP_INLINE_VISIBILITY |
| 1606 multimap(const multimap& __m) |
| 1607 : __tree_(__m.__tree_.value_comp(), |
| 1608 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__al
loc())) |
| 1609 { |
| 1610 insert(__m.begin(), __m.end()); |
| 1611 } |
| 1612 |
| 1613 _LIBCPP_INLINE_VISIBILITY |
| 1614 multimap& operator=(const multimap& __m) |
| 1615 { |
| 1616 #if __cplusplus >= 201103L |
| 1617 __tree_ = __m.__tree_; |
| 1618 #else |
| 1619 __tree_.clear(); |
| 1620 __tree_.value_comp() = __m.__tree_.value_comp(); |
| 1621 __tree_.__copy_assign_alloc(__m.__tree_); |
| 1622 insert(__m.begin(), __m.end()); |
| 1623 #endif |
| 1624 return *this; |
| 1625 } |
| 1626 |
| 1627 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1628 |
| 1629 _LIBCPP_INLINE_VISIBILITY |
| 1630 multimap(multimap&& __m) |
| 1631 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
| 1632 : __tree_(_VSTD::move(__m.__tree_)) |
| 1633 { |
| 1634 } |
| 1635 |
| 1636 multimap(multimap&& __m, const allocator_type& __a); |
| 1637 |
| 1638 _LIBCPP_INLINE_VISIBILITY |
| 1639 multimap& operator=(multimap&& __m) |
| 1640 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
| 1641 { |
| 1642 __tree_ = _VSTD::move(__m.__tree_); |
| 1643 return *this; |
| 1644 } |
| 1645 |
| 1646 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1647 |
| 1648 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1649 |
| 1650 _LIBCPP_INLINE_VISIBILITY |
| 1651 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_
compare()) |
| 1652 : __tree_(__vc(__comp)) |
| 1653 { |
| 1654 insert(__il.begin(), __il.end()); |
| 1655 } |
| 1656 |
| 1657 _LIBCPP_INLINE_VISIBILITY |
| 1658 multimap(initializer_list<value_type> __il, const key_compare& __comp, const
allocator_type& __a) |
| 1659 : __tree_(__vc(__comp), __a) |
| 1660 { |
| 1661 insert(__il.begin(), __il.end()); |
| 1662 } |
| 1663 |
| 1664 #if _LIBCPP_STD_VER > 11 |
| 1665 _LIBCPP_INLINE_VISIBILITY |
| 1666 multimap(initializer_list<value_type> __il, const allocator_type& __a) |
| 1667 : multimap(__il, key_compare(), __a) {} |
| 1668 #endif |
| 1669 |
| 1670 _LIBCPP_INLINE_VISIBILITY |
| 1671 multimap& operator=(initializer_list<value_type> __il) |
| 1672 { |
| 1673 __tree_.__assign_multi(__il.begin(), __il.end()); |
| 1674 return *this; |
| 1675 } |
| 1676 |
| 1677 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1678 |
| 1679 _LIBCPP_INLINE_VISIBILITY |
| 1680 explicit multimap(const allocator_type& __a) |
| 1681 : __tree_(__a) |
| 1682 { |
| 1683 } |
| 1684 |
| 1685 _LIBCPP_INLINE_VISIBILITY |
| 1686 multimap(const multimap& __m, const allocator_type& __a) |
| 1687 : __tree_(__m.__tree_.value_comp(), __a) |
| 1688 { |
| 1689 insert(__m.begin(), __m.end()); |
| 1690 } |
| 1691 |
| 1692 _LIBCPP_INLINE_VISIBILITY |
| 1693 iterator begin() _NOEXCEPT {return __tree_.begin();} |
| 1694 _LIBCPP_INLINE_VISIBILITY |
| 1695 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
| 1696 _LIBCPP_INLINE_VISIBILITY |
| 1697 iterator end() _NOEXCEPT {return __tree_.end();} |
| 1698 _LIBCPP_INLINE_VISIBILITY |
| 1699 const_iterator end() const _NOEXCEPT {return __tree_.end();} |
| 1700 |
| 1701 _LIBCPP_INLINE_VISIBILITY |
| 1702 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} |
| 1703 _LIBCPP_INLINE_VISIBILITY |
| 1704 const_reverse_iterator rbegin() const _NOEXCEPT |
| 1705 {return const_reverse_iterator(end());} |
| 1706 _LIBCPP_INLINE_VISIBILITY |
| 1707 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} |
| 1708 _LIBCPP_INLINE_VISIBILITY |
| 1709 const_reverse_iterator rend() const _NOEXCEPT |
| 1710 {return const_reverse_iterator(begin());} |
| 1711 |
| 1712 _LIBCPP_INLINE_VISIBILITY |
| 1713 const_iterator cbegin() const _NOEXCEPT {return begin();} |
| 1714 _LIBCPP_INLINE_VISIBILITY |
| 1715 const_iterator cend() const _NOEXCEPT {return end();} |
| 1716 _LIBCPP_INLINE_VISIBILITY |
| 1717 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
| 1718 _LIBCPP_INLINE_VISIBILITY |
| 1719 const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
| 1720 |
| 1721 _LIBCPP_INLINE_VISIBILITY |
| 1722 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
| 1723 _LIBCPP_INLINE_VISIBILITY |
| 1724 size_type size() const _NOEXCEPT {return __tree_.size();} |
| 1725 _LIBCPP_INLINE_VISIBILITY |
| 1726 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
| 1727 |
| 1728 _LIBCPP_INLINE_VISIBILITY |
| 1729 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
| 1730 _LIBCPP_INLINE_VISIBILITY |
| 1731 key_compare key_comp() const {return __tree_.value_comp().key_comp();} |
| 1732 _LIBCPP_INLINE_VISIBILITY |
| 1733 value_compare value_comp() const |
| 1734 {return value_compare(__tree_.value_comp().key_comp());} |
| 1735 |
| 1736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1737 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1738 |
| 1739 template <class ..._Args> |
| 1740 iterator |
| 1741 emplace(_Args&& ...__args); |
| 1742 |
| 1743 template <class ..._Args> |
| 1744 iterator |
| 1745 emplace_hint(const_iterator __p, _Args&& ...__args); |
| 1746 |
| 1747 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1748 |
| 1749 template <class _Pp, |
| 1750 class = typename enable_if<is_constructible<value_type, _Pp>::valu
e>::type> |
| 1751 _LIBCPP_INLINE_VISIBILITY |
| 1752 iterator insert(_Pp&& __p) |
| 1753 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));} |
| 1754 |
| 1755 template <class _Pp, |
| 1756 class = typename enable_if<is_constructible<value_type, _Pp>::valu
e>::type> |
| 1757 _LIBCPP_INLINE_VISIBILITY |
| 1758 iterator insert(const_iterator __pos, _Pp&& __p) |
| 1759 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p))
;} |
| 1760 |
| 1761 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1762 |
| 1763 _LIBCPP_INLINE_VISIBILITY |
| 1764 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} |
| 1765 |
| 1766 _LIBCPP_INLINE_VISIBILITY |
| 1767 iterator insert(const_iterator __p, const value_type& __v) |
| 1768 {return __tree_.__insert_multi(__p.__i_, __v);} |
| 1769 |
| 1770 template <class _InputIterator> |
| 1771 _LIBCPP_INLINE_VISIBILITY |
| 1772 void insert(_InputIterator __f, _InputIterator __l) |
| 1773 { |
| 1774 for (const_iterator __e = cend(); __f != __l; ++__f) |
| 1775 __tree_.__insert_multi(__e.__i_, *__f); |
| 1776 } |
| 1777 |
| 1778 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1779 |
| 1780 _LIBCPP_INLINE_VISIBILITY |
| 1781 void insert(initializer_list<value_type> __il) |
| 1782 {insert(__il.begin(), __il.end());} |
| 1783 |
| 1784 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1785 |
| 1786 _LIBCPP_INLINE_VISIBILITY |
| 1787 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} |
| 1788 _LIBCPP_INLINE_VISIBILITY |
| 1789 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} |
| 1790 _LIBCPP_INLINE_VISIBILITY |
| 1791 iterator erase(const_iterator __f, const_iterator __l) |
| 1792 {return __tree_.erase(__f.__i_, __l.__i_);} |
| 1793 _LIBCPP_INLINE_VISIBILITY |
| 1794 void clear() {__tree_.clear();} |
| 1795 |
| 1796 _LIBCPP_INLINE_VISIBILITY |
| 1797 void swap(multimap& __m) |
| 1798 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
| 1799 {__tree_.swap(__m.__tree_);} |
| 1800 |
| 1801 _LIBCPP_INLINE_VISIBILITY |
| 1802 iterator find(const key_type& __k) {return __tree_.find(__k);} |
| 1803 _LIBCPP_INLINE_VISIBILITY |
| 1804 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
| 1805 #if _LIBCPP_STD_VER > 11 |
| 1806 template <typename _K2> |
| 1807 _LIBCPP_INLINE_VISIBILITY |
| 1808 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1809 find(const _K2& __k) {return __tree_.find(__k);} |
| 1810 template <typename _K2> |
| 1811 _LIBCPP_INLINE_VISIBILITY |
| 1812 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1813 find(const _K2& __k) const {return __tree_.find(__k);} |
| 1814 #endif |
| 1815 |
| 1816 _LIBCPP_INLINE_VISIBILITY |
| 1817 size_type count(const key_type& __k) const |
| 1818 {return __tree_.__count_multi(__k);} |
| 1819 _LIBCPP_INLINE_VISIBILITY |
| 1820 iterator lower_bound(const key_type& __k) |
| 1821 {return __tree_.lower_bound(__k);} |
| 1822 _LIBCPP_INLINE_VISIBILITY |
| 1823 const_iterator lower_bound(const key_type& __k) const |
| 1824 {return __tree_.lower_bound(__k);} |
| 1825 #if _LIBCPP_STD_VER > 11 |
| 1826 template <typename _K2> |
| 1827 _LIBCPP_INLINE_VISIBILITY |
| 1828 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1829 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
| 1830 |
| 1831 template <typename _K2> |
| 1832 _LIBCPP_INLINE_VISIBILITY |
| 1833 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1834 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
| 1835 #endif |
| 1836 |
| 1837 _LIBCPP_INLINE_VISIBILITY |
| 1838 iterator upper_bound(const key_type& __k) |
| 1839 {return __tree_.upper_bound(__k);} |
| 1840 _LIBCPP_INLINE_VISIBILITY |
| 1841 const_iterator upper_bound(const key_type& __k) const |
| 1842 {return __tree_.upper_bound(__k);} |
| 1843 #if _LIBCPP_STD_VER > 11 |
| 1844 template <typename _K2> |
| 1845 _LIBCPP_INLINE_VISIBILITY |
| 1846 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 1847 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
| 1848 template <typename _K2> |
| 1849 _LIBCPP_INLINE_VISIBILITY |
| 1850 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 1851 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
| 1852 #endif |
| 1853 |
| 1854 _LIBCPP_INLINE_VISIBILITY |
| 1855 pair<iterator,iterator> equal_range(const key_type& __k) |
| 1856 {return __tree_.__equal_range_multi(__k);} |
| 1857 _LIBCPP_INLINE_VISIBILITY |
| 1858 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
| 1859 {return __tree_.__equal_range_multi(__k);} |
| 1860 #if _LIBCPP_STD_VER > 11 |
| 1861 template <typename _K2> |
| 1862 _LIBCPP_INLINE_VISIBILITY |
| 1863 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iter
ator>>::type |
| 1864 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} |
| 1865 template <typename _K2> |
| 1866 _LIBCPP_INLINE_VISIBILITY |
| 1867 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterato
r,const_iterator>>::type |
| 1868 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} |
| 1869 #endif |
| 1870 |
| 1871 private: |
| 1872 typedef typename __base::__node __node; |
| 1873 typedef typename __base::__node_allocator __node_allocator; |
| 1874 typedef typename __base::__node_pointer __node_pointer; |
| 1875 typedef typename __base::__node_const_pointer __node_const_pointer; |
| 1876 typedef __map_node_destructor<__node_allocator> _Dp; |
| 1877 typedef unique_ptr<__node, _Dp> __node_holder; |
| 1878 |
| 1879 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1880 __node_holder __construct_node(); |
| 1881 template <class _A0> |
| 1882 __node_holder |
| 1883 __construct_node(_A0&& __a0); |
| 1884 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1885 template <class _A0, class _A1, class ..._Args> |
| 1886 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args
); |
| 1887 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1888 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1889 }; |
| 1890 |
| 1891 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1892 |
| 1893 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1894 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const alloca
tor_type& __a) |
| 1895 : __tree_(_VSTD::move(__m.__tree_), __a) |
| 1896 { |
| 1897 if (__a != __m.get_allocator()) |
| 1898 { |
| 1899 const_iterator __e = cend(); |
| 1900 while (!__m.empty()) |
| 1901 __tree_.__insert_multi(__e.__i_, |
| 1902 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_))
; |
| 1903 } |
| 1904 } |
| 1905 |
| 1906 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1907 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1908 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() |
| 1909 { |
| 1910 __node_allocator& __na = __tree_.__node_alloc(); |
| 1911 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1912 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); |
| 1913 __h.get_deleter().__first_constructed = true; |
| 1914 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); |
| 1915 __h.get_deleter().__second_constructed = true; |
| 1916 return __h; |
| 1917 } |
| 1918 |
| 1919 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1920 template <class _A0> |
| 1921 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1922 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) |
| 1923 { |
| 1924 __node_allocator& __na = __tree_.__node_alloc(); |
| 1925 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1926 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forwa
rd<_A0>(__a0)); |
| 1927 __h.get_deleter().__first_constructed = true; |
| 1928 __h.get_deleter().__second_constructed = true; |
| 1929 return __h; |
| 1930 } |
| 1931 |
| 1932 #ifndef _LIBCPP_HAS_NO_VARIADICS |
| 1933 |
| 1934 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1935 template <class _A0, class _A1, class ..._Args> |
| 1936 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder |
| 1937 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __
a1, _Args&& ...__args) |
| 1938 { |
| 1939 __node_allocator& __na = __tree_.__node_alloc(); |
| 1940 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); |
| 1941 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), |
| 1942 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1
), |
| 1943 _VSTD::forward<_Args>(__args)...); |
| 1944 __h.get_deleter().__first_constructed = true; |
| 1945 __h.get_deleter().__second_constructed = true; |
| 1946 return __h; |
| 1947 } |
| 1948 |
| 1949 #endif // _LIBCPP_HAS_NO_VARIADICS |
| 1950 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1951 |
| 1952 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIAD
ICS) |
| 1953 |
| 1954 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1955 template <class ..._Args> |
| 1956 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator |
| 1957 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) |
| 1958 { |
| 1959 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); |
| 1960 iterator __r = __tree_.__node_insert_multi(__h.get()); |
| 1961 __h.release(); |
| 1962 return __r; |
| 1963 } |
| 1964 |
| 1965 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1966 template <class ..._Args> |
| 1967 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator |
| 1968 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, |
| 1969 _Args&& ...__args) |
| 1970 { |
| 1971 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); |
| 1972 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); |
| 1973 __h.release(); |
| 1974 return __r; |
| 1975 } |
| 1976 |
| 1977 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO
_VARIADICS) |
| 1978 |
| 1979 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1980 inline _LIBCPP_INLINE_VISIBILITY |
| 1981 bool |
| 1982 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1983 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1984 { |
| 1985 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.
begin()); |
| 1986 } |
| 1987 |
| 1988 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1989 inline _LIBCPP_INLINE_VISIBILITY |
| 1990 bool |
| 1991 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 1992 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 1993 { |
| 1994 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), _
_y.end()); |
| 1995 } |
| 1996 |
| 1997 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 1998 inline _LIBCPP_INLINE_VISIBILITY |
| 1999 bool |
| 2000 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 2001 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 2002 { |
| 2003 return !(__x == __y); |
| 2004 } |
| 2005 |
| 2006 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 2007 inline _LIBCPP_INLINE_VISIBILITY |
| 2008 bool |
| 2009 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 2010 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 2011 { |
| 2012 return __y < __x; |
| 2013 } |
| 2014 |
| 2015 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 2016 inline _LIBCPP_INLINE_VISIBILITY |
| 2017 bool |
| 2018 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 2019 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 2020 { |
| 2021 return !(__x < __y); |
| 2022 } |
| 2023 |
| 2024 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 2025 inline _LIBCPP_INLINE_VISIBILITY |
| 2026 bool |
| 2027 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 2028 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 2029 { |
| 2030 return !(__y < __x); |
| 2031 } |
| 2032 |
| 2033 template <class _Key, class _Tp, class _Compare, class _Allocator> |
| 2034 inline _LIBCPP_INLINE_VISIBILITY |
| 2035 void |
| 2036 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, |
| 2037 multimap<_Key, _Tp, _Compare, _Allocator>& __y) |
| 2038 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| 2039 { |
| 2040 __x.swap(__y); |
| 2041 } |
| 2042 |
| 2043 _LIBCPP_END_NAMESPACE_STD |
| 2044 |
| 2045 #endif // _LIBCPP_MAP |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 75213003:
Add libc++ and libc++abi to third-party. (Closed)
Base URL: https://src.chromium.org/chrome/trunk/src/