1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___CXX03_MAP 11#define _LIBCPP___CXX03_MAP 12 13/* 14 15 map synopsis 16 17namespace std 18{ 19 20template <class Key, class T, class Compare = less<Key>, 21 class Allocator = allocator<pair<const Key, T>>> 22class map 23{ 24public: 25 // types: 26 typedef Key key_type; 27 typedef T mapped_type; 28 typedef pair<const key_type, mapped_type> value_type; 29 typedef Compare key_compare; 30 typedef Allocator allocator_type; 31 typedef typename allocator_type::reference reference; 32 typedef typename allocator_type::const_reference const_reference; 33 typedef typename allocator_type::pointer pointer; 34 typedef typename allocator_type::const_pointer const_pointer; 35 typedef typename allocator_type::size_type size_type; 36 typedef typename allocator_type::difference_type difference_type; 37 38 typedef implementation-defined iterator; 39 typedef implementation-defined const_iterator; 40 typedef std::reverse_iterator<iterator> reverse_iterator; 41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 42 typedef unspecified node_type; // C++17 43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 44 45 class value_compare 46 { 47 friend class map; 48 protected: 49 key_compare comp; 50 51 value_compare(key_compare c); 52 public: 53 typedef bool result_type; // deprecated in C++17, removed in C++20 54 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20 55 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20 56 bool operator()(const value_type& x, const value_type& y) const; 57 }; 58 59 // construct/copy/destroy: 60 map() 61 noexcept( 62 is_nothrow_default_constructible<allocator_type>::value && 63 is_nothrow_default_constructible<key_compare>::value && 64 is_nothrow_copy_constructible<key_compare>::value); 65 explicit map(const key_compare& comp); 66 map(const key_compare& comp, const allocator_type& a); 67 template <class InputIterator> 68 map(InputIterator first, InputIterator last, 69 const key_compare& comp = key_compare()); 70 template <class InputIterator> 71 map(InputIterator first, InputIterator last, 72 const key_compare& comp, const allocator_type& a); 73 template<container-compatible-range<value_type> R> 74 map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 75 map(const map& m); 76 map(map&& m) 77 noexcept( 78 is_nothrow_move_constructible<allocator_type>::value && 79 is_nothrow_move_constructible<key_compare>::value); 80 explicit map(const allocator_type& a); 81 map(const map& m, const allocator_type& a); 82 map(map&& m, const allocator_type& a); 83 map(initializer_list<value_type> il, const key_compare& comp = key_compare()); 84 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a); 85 template <class InputIterator> 86 map(InputIterator first, InputIterator last, const allocator_type& a) 87 : map(first, last, Compare(), a) {} // C++14 88 template<container-compatible-range<value_type> R> 89 map(from_range_t, R&& rg, const Allocator& a)) 90 : map(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 91 map(initializer_list<value_type> il, const allocator_type& a) 92 : map(il, Compare(), a) {} // C++14 93 ~map(); 94 95 map& operator=(const map& m); 96 map& operator=(map&& m) 97 noexcept( 98 allocator_type::propagate_on_container_move_assignment::value && 99 is_nothrow_move_assignable<allocator_type>::value && 100 is_nothrow_move_assignable<key_compare>::value); 101 map& operator=(initializer_list<value_type> il); 102 103 // iterators: 104 iterator begin() noexcept; 105 const_iterator begin() const noexcept; 106 iterator end() noexcept; 107 const_iterator end() const noexcept; 108 109 reverse_iterator rbegin() noexcept; 110 const_reverse_iterator rbegin() const noexcept; 111 reverse_iterator rend() noexcept; 112 const_reverse_iterator rend() const noexcept; 113 114 const_iterator cbegin() const noexcept; 115 const_iterator cend() const noexcept; 116 const_reverse_iterator crbegin() const noexcept; 117 const_reverse_iterator crend() const noexcept; 118 119 // capacity: 120 bool empty() const noexcept; 121 size_type size() const noexcept; 122 size_type max_size() const noexcept; 123 124 // element access: 125 mapped_type& operator[](const key_type& k); 126 mapped_type& operator[](key_type&& k); 127 128 mapped_type& at(const key_type& k); 129 const mapped_type& at(const key_type& k) const; 130 131 // modifiers: 132 template <class... Args> 133 pair<iterator, bool> emplace(Args&&... args); 134 template <class... Args> 135 iterator emplace_hint(const_iterator position, Args&&... args); 136 pair<iterator, bool> insert(const value_type& v); 137 pair<iterator, bool> insert( value_type&& v); // C++17 138 template <class P> 139 pair<iterator, bool> insert(P&& p); 140 iterator insert(const_iterator position, const value_type& v); 141 iterator insert(const_iterator position, value_type&& v); // C++17 142 template <class P> 143 iterator insert(const_iterator position, P&& p); 144 template <class InputIterator> 145 void insert(InputIterator first, InputIterator last); 146 template<container-compatible-range<value_type> R> 147 void insert_range(R&& rg); // C++23 148 void insert(initializer_list<value_type> il); 149 150 node_type extract(const_iterator position); // C++17 151 node_type extract(const key_type& x); // C++17 152 insert_return_type insert(node_type&& nh); // C++17 153 iterator insert(const_iterator hint, node_type&& nh); // C++17 154 155 template <class... Args> 156 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 157 template <class... Args> 158 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 159 template <class... Args> 160 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 161 template <class... Args> 162 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 163 template <class M> 164 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 165 template <class M> 166 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 167 template <class M> 168 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 169 template <class M> 170 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 171 172 iterator erase(const_iterator position); 173 iterator erase(iterator position); // C++14 174 size_type erase(const key_type& k); 175 iterator erase(const_iterator first, const_iterator last); 176 void clear() noexcept; 177 178 template<class C2> 179 void merge(map<Key, T, C2, Allocator>& source); // C++17 180 template<class C2> 181 void merge(map<Key, T, C2, Allocator>&& source); // C++17 182 template<class C2> 183 void merge(multimap<Key, T, C2, Allocator>& source); // C++17 184 template<class C2> 185 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 186 187 void swap(map& m) 188 noexcept(allocator_traits<allocator_type>::is_always_equal::value && 189 is_nothrow_swappable<key_compare>::value); // C++17 190 191 // observers: 192 allocator_type get_allocator() const noexcept; 193 key_compare key_comp() const; 194 value_compare value_comp() const; 195 196 // map operations: 197 iterator find(const key_type& k); 198 const_iterator find(const key_type& k) const; 199 template<typename K> 200 iterator find(const K& x); // C++14 201 template<typename K> 202 const_iterator find(const K& x) const; // C++14 203 204 template<typename K> 205 size_type count(const K& x) const; // C++14 206 size_type count(const key_type& k) const; 207 208 bool contains(const key_type& x) const; // C++20 209 template<class K> bool contains(const K& x) const; // C++20 210 211 iterator lower_bound(const key_type& k); 212 const_iterator lower_bound(const key_type& k) const; 213 template<typename K> 214 iterator lower_bound(const K& x); // C++14 215 template<typename K> 216 const_iterator lower_bound(const K& x) const; // C++14 217 218 iterator upper_bound(const key_type& k); 219 const_iterator upper_bound(const key_type& k) const; 220 template<typename K> 221 iterator upper_bound(const K& x); // C++14 222 template<typename K> 223 const_iterator upper_bound(const K& x) const; // C++14 224 225 pair<iterator,iterator> equal_range(const key_type& k); 226 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 227 template<typename K> 228 pair<iterator,iterator> equal_range(const K& x); // C++14 229 template<typename K> 230 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 231}; 232 233template <class InputIterator, 234 class Compare = less<iter_key_t<InputIterator>>, 235 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 236map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator()) 237 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17 238 239template<ranges::input_range R, class Compare = less<range-key-type<R>, 240 class Allocator = allocator<range-to-alloc-type<R>>> 241 map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 242 -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23 243 244template<class Key, class T, class Compare = less<Key>, 245 class Allocator = allocator<pair<const Key, T>>> 246map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator()) 247 -> map<Key, T, Compare, Allocator>; // C++17 248 249template <class InputIterator, class Allocator> 250map(InputIterator, InputIterator, Allocator) 251 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>, 252 Allocator>; // C++17 253 254template<ranges::input_range R, class Allocator> 255 map(from_range_t, R&&, Allocator) 256 -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23 257 258template<class Key, class T, class Allocator> 259map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17 260 261template <class Key, class T, class Compare, class Allocator> 262bool 263operator==(const map<Key, T, Compare, Allocator>& x, 264 const map<Key, T, Compare, Allocator>& y); 265 266template <class Key, class T, class Compare, class Allocator> 267bool 268operator< (const map<Key, T, Compare, Allocator>& x, 269 const map<Key, T, Compare, Allocator>& y); // removed in C++20 270 271template <class Key, class T, class Compare, class Allocator> 272bool 273operator!=(const map<Key, T, Compare, Allocator>& x, 274 const map<Key, T, Compare, Allocator>& y); // removed in C++20 275 276template <class Key, class T, class Compare, class Allocator> 277bool 278operator> (const map<Key, T, Compare, Allocator>& x, 279 const map<Key, T, Compare, Allocator>& y); // removed in C++20 280 281template <class Key, class T, class Compare, class Allocator> 282bool 283operator>=(const map<Key, T, Compare, Allocator>& x, 284 const map<Key, T, Compare, Allocator>& y); // removed in C++20 285 286template <class Key, class T, class Compare, class Allocator> 287bool 288operator<=(const map<Key, T, Compare, Allocator>& x, 289 const map<Key, T, Compare, Allocator>& y); // removed in C++20 290 291template<class Key, class T, class Compare, class Allocator> 292 synth-three-way-result<pair<const Key, T>> 293 operator<=>(const map<Key, T, Compare, Allocator>& x, 294 const map<Key, T, Compare, Allocator>& y); // since C++20 295 296// specialized algorithms: 297template <class Key, class T, class Compare, class Allocator> 298void 299swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y) 300 noexcept(noexcept(x.swap(y))); 301 302template <class Key, class T, class Compare, class Allocator, class Predicate> 303typename map<Key, T, Compare, Allocator>::size_type 304erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 305 306 307template <class Key, class T, class Compare = less<Key>, 308 class Allocator = allocator<pair<const Key, T>>> 309class multimap 310{ 311public: 312 // types: 313 typedef Key key_type; 314 typedef T mapped_type; 315 typedef pair<const key_type,mapped_type> value_type; 316 typedef Compare key_compare; 317 typedef Allocator allocator_type; 318 typedef typename allocator_type::reference reference; 319 typedef typename allocator_type::const_reference const_reference; 320 typedef typename allocator_type::size_type size_type; 321 typedef typename allocator_type::difference_type difference_type; 322 typedef typename allocator_type::pointer pointer; 323 typedef typename allocator_type::const_pointer const_pointer; 324 325 typedef implementation-defined iterator; 326 typedef implementation-defined const_iterator; 327 typedef std::reverse_iterator<iterator> reverse_iterator; 328 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 329 typedef unspecified node_type; // C++17 330 331 class value_compare 332 { 333 friend class multimap; 334 protected: 335 key_compare comp; 336 value_compare(key_compare c); 337 public: 338 typedef bool result_type; // deprecated in C++17, removed in C++20 339 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20 340 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20 341 bool operator()(const value_type& x, const value_type& y) const; 342 }; 343 344 // construct/copy/destroy: 345 multimap() 346 noexcept( 347 is_nothrow_default_constructible<allocator_type>::value && 348 is_nothrow_default_constructible<key_compare>::value && 349 is_nothrow_copy_constructible<key_compare>::value); 350 explicit multimap(const key_compare& comp); 351 multimap(const key_compare& comp, const allocator_type& a); 352 template <class InputIterator> 353 multimap(InputIterator first, InputIterator last, const key_compare& comp); 354 template <class InputIterator> 355 multimap(InputIterator first, InputIterator last, const key_compare& comp, 356 const allocator_type& a); 357 template<container-compatible-range<value_type> R> 358 multimap(from_range_t, R&& rg, 359 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 360 multimap(const multimap& m); 361 multimap(multimap&& m) 362 noexcept( 363 is_nothrow_move_constructible<allocator_type>::value && 364 is_nothrow_move_constructible<key_compare>::value); 365 explicit multimap(const allocator_type& a); 366 multimap(const multimap& m, const allocator_type& a); 367 multimap(multimap&& m, const allocator_type& a); 368 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare()); 369 multimap(initializer_list<value_type> il, const key_compare& comp, 370 const allocator_type& a); 371 template <class InputIterator> 372 multimap(InputIterator first, InputIterator last, const allocator_type& a) 373 : multimap(first, last, Compare(), a) {} // C++14 374 template<container-compatible-range<value_type> R> 375 multimap(from_range_t, R&& rg, const Allocator& a)) 376 : multimap(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 377 multimap(initializer_list<value_type> il, const allocator_type& a) 378 : multimap(il, Compare(), a) {} // C++14 379 ~multimap(); 380 381 multimap& operator=(const multimap& m); 382 multimap& operator=(multimap&& m) 383 noexcept( 384 allocator_type::propagate_on_container_move_assignment::value && 385 is_nothrow_move_assignable<allocator_type>::value && 386 is_nothrow_move_assignable<key_compare>::value); 387 multimap& operator=(initializer_list<value_type> il); 388 389 // iterators: 390 iterator begin() noexcept; 391 const_iterator begin() const noexcept; 392 iterator end() noexcept; 393 const_iterator end() const noexcept; 394 395 reverse_iterator rbegin() noexcept; 396 const_reverse_iterator rbegin() const noexcept; 397 reverse_iterator rend() noexcept; 398 const_reverse_iterator rend() const noexcept; 399 400 const_iterator cbegin() const noexcept; 401 const_iterator cend() const noexcept; 402 const_reverse_iterator crbegin() const noexcept; 403 const_reverse_iterator crend() const noexcept; 404 405 // capacity: 406 bool empty() const noexcept; 407 size_type size() const noexcept; 408 size_type max_size() const noexcept; 409 410 // modifiers: 411 template <class... Args> 412 iterator emplace(Args&&... args); 413 template <class... Args> 414 iterator emplace_hint(const_iterator position, Args&&... args); 415 iterator insert(const value_type& v); 416 iterator insert( value_type&& v); // C++17 417 template <class P> 418 iterator insert(P&& p); 419 iterator insert(const_iterator position, const value_type& v); 420 iterator insert(const_iterator position, value_type&& v); // C++17 421 template <class P> 422 iterator insert(const_iterator position, P&& p); 423 template <class InputIterator> 424 void insert(InputIterator first, InputIterator last); 425 template<container-compatible-range<value_type> R> 426 void insert_range(R&& rg); // C++23 427 void insert(initializer_list<value_type> il); 428 429 node_type extract(const_iterator position); // C++17 430 node_type extract(const key_type& x); // C++17 431 iterator insert(node_type&& nh); // C++17 432 iterator insert(const_iterator hint, node_type&& nh); // C++17 433 434 iterator erase(const_iterator position); 435 iterator erase(iterator position); // C++14 436 size_type erase(const key_type& k); 437 iterator erase(const_iterator first, const_iterator last); 438 void clear() noexcept; 439 440 template<class C2> 441 void merge(multimap<Key, T, C2, Allocator>& source); // C++17 442 template<class C2> 443 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 444 template<class C2> 445 void merge(map<Key, T, C2, Allocator>& source); // C++17 446 template<class C2> 447 void merge(map<Key, T, C2, Allocator>&& source); // C++17 448 449 void swap(multimap& m) 450 noexcept(allocator_traits<allocator_type>::is_always_equal::value && 451 is_nothrow_swappable<key_compare>::value); // C++17 452 453 // observers: 454 allocator_type get_allocator() const noexcept; 455 key_compare key_comp() const; 456 value_compare value_comp() const; 457 458 // map operations: 459 iterator find(const key_type& k); 460 const_iterator find(const key_type& k) const; 461 template<typename K> 462 iterator find(const K& x); // C++14 463 template<typename K> 464 const_iterator find(const K& x) const; // C++14 465 466 template<typename K> 467 size_type count(const K& x) const; // C++14 468 size_type count(const key_type& k) const; 469 470 bool contains(const key_type& x) const; // C++20 471 template<class K> bool contains(const K& x) const; // C++20 472 473 iterator lower_bound(const key_type& k); 474 const_iterator lower_bound(const key_type& k) const; 475 template<typename K> 476 iterator lower_bound(const K& x); // C++14 477 template<typename K> 478 const_iterator lower_bound(const K& x) const; // C++14 479 480 iterator upper_bound(const key_type& k); 481 const_iterator upper_bound(const key_type& k) const; 482 template<typename K> 483 iterator upper_bound(const K& x); // C++14 484 template<typename K> 485 const_iterator upper_bound(const K& x) const; // C++14 486 487 pair<iterator,iterator> equal_range(const key_type& k); 488 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 489 template<typename K> 490 pair<iterator,iterator> equal_range(const K& x); // C++14 491 template<typename K> 492 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 493}; 494 495template <class InputIterator, 496 class Compare = less<iter_key_t<InputIterator>>, 497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 498multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator()) 499 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17 500 501template<ranges::input_range R, class Compare = less<range-key-type<R>>, 502 class Allocator = allocator<range-to-alloc-type<R>>> 503 multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 504 -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23 505 506template<class Key, class T, class Compare = less<Key>, 507 class Allocator = allocator<pair<const Key, T>>> 508multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator()) 509 -> multimap<Key, T, Compare, Allocator>; // C++17 510 511template <class InputIterator, class Allocator> 512multimap(InputIterator, InputIterator, Allocator) 513 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 514 less<iter_key_t<InputIterator>>, Allocator>; // C++17 515 516template<ranges::input_range R, class Allocator> 517 multimap(from_range_t, R&&, Allocator) 518 -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23 519 520template<class Key, class T, class Allocator> 521multimap(initializer_list<pair<const Key, T>>, Allocator) 522 -> multimap<Key, T, less<Key>, Allocator>; // C++17 523 524template <class Key, class T, class Compare, class Allocator> 525bool 526operator==(const multimap<Key, T, Compare, Allocator>& x, 527 const multimap<Key, T, Compare, Allocator>& y); 528 529template <class Key, class T, class Compare, class Allocator> 530bool 531operator< (const multimap<Key, T, Compare, Allocator>& x, 532 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20 533 534template <class Key, class T, class Compare, class Allocator> 535bool 536operator!=(const multimap<Key, T, Compare, Allocator>& x, 537 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20 538 539template <class Key, class T, class Compare, class Allocator> 540bool 541operator> (const multimap<Key, T, Compare, Allocator>& x, 542 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20 543 544template <class Key, class T, class Compare, class Allocator> 545bool 546operator>=(const multimap<Key, T, Compare, Allocator>& x, 547 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20 548 549template <class Key, class T, class Compare, class Allocator> 550bool 551operator<=(const multimap<Key, T, Compare, Allocator>& x, 552 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20 553 554template<class Key, class T, class Compare, class Allocator> 555 synth-three-way-result<pair<const Key, T>> 556 operator<=>(const multimap<Key, T, Compare, Allocator>& x, 557 const multimap<Key, T, Compare, Allocator>& y); // since c++20 558 559// specialized algorithms: 560template <class Key, class T, class Compare, class Allocator> 561void 562swap(multimap<Key, T, Compare, Allocator>& x, 563 multimap<Key, T, Compare, Allocator>& y) 564 noexcept(noexcept(x.swap(y))); 565 566template <class Key, class T, class Compare, class Allocator, class Predicate> 567typename multimap<Key, T, Compare, Allocator>::size_type 568erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 569 570} // std 571 572*/ 573 574#include <__cxx03/__algorithm/equal.h> 575#include <__cxx03/__algorithm/lexicographical_compare.h> 576#include <__cxx03/__assert> 577#include <__cxx03/__config> 578#include <__cxx03/__functional/binary_function.h> 579#include <__cxx03/__functional/operations.h> 580#include <__cxx03/__iterator/erase_if_container.h> 581#include <__cxx03/__iterator/iterator_traits.h> 582#include <__cxx03/__iterator/reverse_iterator.h> 583#include <__cxx03/__memory/addressof.h> 584#include <__cxx03/__memory/allocator.h> 585#include <__cxx03/__tree> 586#include <__cxx03/__type_traits/is_allocator.h> 587#include <__cxx03/__utility/forward.h> 588#include <__cxx03/__utility/piecewise_construct.h> 589#include <__cxx03/__utility/swap.h> 590#include <__cxx03/stdexcept> 591#include <__cxx03/version> 592 593// standard-mandated includes 594 595// [iterator.range] 596#include <__cxx03/__iterator/access.h> 597 598#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 599# pragma GCC system_header 600#endif 601 602_LIBCPP_PUSH_MACROS 603#include <__cxx03/__undef_macros> 604 605_LIBCPP_BEGIN_NAMESPACE_STD 606 607template <class _Key, 608 class _CP, 609 class _Compare, 610 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> 611class __map_value_compare : private _Compare { 612public: 613 _LIBCPP_HIDE_FROM_ABI __map_value_compare() : _Compare() {} 614 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) : _Compare(__c) {} 615 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; } 616 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { 617 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first); 618 } 619 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { 620 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y); 621 } 622 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { 623 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first); 624 } 625 _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) { 626 using std::swap; 627 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); 628 } 629}; 630 631template <class _Key, class _CP, class _Compare> 632class __map_value_compare<_Key, _CP, _Compare, false> { 633 _Compare __comp_; 634 635public: 636 _LIBCPP_HIDE_FROM_ABI __map_value_compare() : __comp_() {} 637 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) : __comp_(__c) {} 638 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; } 639 640 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { 641 return __comp_(__x.__get_value().first, __y.__get_value().first); 642 } 643 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { 644 return __comp_(__x.__get_value().first, __y); 645 } 646 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { 647 return __comp_(__x, __y.__get_value().first); 648 } 649 void swap(__map_value_compare& __y) { 650 using std::swap; 651 swap(__comp_, __y.__comp_); 652 } 653}; 654 655template <class _Key, class _CP, class _Compare, bool __b> 656inline _LIBCPP_HIDE_FROM_ABI void 657swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y) { 658 __x.swap(__y); 659} 660 661template <class _Allocator> 662class __map_node_destructor { 663 typedef _Allocator allocator_type; 664 typedef allocator_traits<allocator_type> __alloc_traits; 665 666public: 667 typedef typename __alloc_traits::pointer pointer; 668 669private: 670 allocator_type& __na_; 671 672public: 673 bool __first_constructed; 674 bool __second_constructed; 675 676 _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT 677 : __na_(__na), 678 __first_constructed(false), 679 __second_constructed(false) {} 680 681 __map_node_destructor& operator=(const __map_node_destructor&) = delete; 682 683 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 684 if (__second_constructed) 685 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second)); 686 if (__first_constructed) 687 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first)); 688 if (__p) 689 __alloc_traits::deallocate(__na_, __p, 1); 690 } 691}; 692 693template <class _Key, class _Tp, class _Compare, class _Allocator> 694class map; 695template <class _Key, class _Tp, class _Compare, class _Allocator> 696class multimap; 697template <class _TreeIterator> 698class __map_const_iterator; 699 700template <class _Key, class _Tp> 701struct __value_type { 702 typedef _Key key_type; 703 typedef _Tp mapped_type; 704 typedef pair<const key_type, mapped_type> value_type; 705 706private: 707 value_type __cc_; 708 709public: 710 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } 711 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } 712 713 __value_type() = delete; 714 __value_type(__value_type const&) = delete; 715 __value_type& operator=(__value_type const&) = delete; 716 ~__value_type() = delete; 717}; 718 719template <class _Tp> 720struct __extract_key_value_types; 721 722template <class _Key, class _Tp> 723struct __extract_key_value_types<__value_type<_Key, _Tp> > { 724 typedef _Key const __key_type; 725 typedef _Tp __mapped_type; 726}; 727 728template <class _TreeIterator> 729class _LIBCPP_TEMPLATE_VIS __map_iterator { 730 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 731 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 732 733 _TreeIterator __i_; 734 735public: 736 typedef bidirectional_iterator_tag iterator_category; 737 typedef typename _NodeTypes::__map_value_type value_type; 738 typedef typename _TreeIterator::difference_type difference_type; 739 typedef value_type& reference; 740 typedef typename _NodeTypes::__map_value_type_pointer pointer; 741 742 _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {} 743 744 _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 745 746 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 747 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 748 749 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() { 750 ++__i_; 751 return *this; 752 } 753 _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) { 754 __map_iterator __t(*this); 755 ++(*this); 756 return __t; 757 } 758 759 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() { 760 --__i_; 761 return *this; 762 } 763 _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) { 764 __map_iterator __t(*this); 765 --(*this); 766 return __t; 767 } 768 769 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) { 770 return __x.__i_ == __y.__i_; 771 } 772 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) { 773 return __x.__i_ != __y.__i_; 774 } 775 776 template <class, class, class, class> 777 friend class _LIBCPP_TEMPLATE_VIS map; 778 template <class, class, class, class> 779 friend class _LIBCPP_TEMPLATE_VIS multimap; 780 template <class> 781 friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; 782}; 783 784template <class _TreeIterator> 785class _LIBCPP_TEMPLATE_VIS __map_const_iterator { 786 typedef typename _TreeIterator::_NodeTypes _NodeTypes; 787 typedef typename _TreeIterator::__pointer_traits __pointer_traits; 788 789 _TreeIterator __i_; 790 791public: 792 typedef bidirectional_iterator_tag iterator_category; 793 typedef typename _NodeTypes::__map_value_type value_type; 794 typedef typename _TreeIterator::difference_type difference_type; 795 typedef const value_type& reference; 796 typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 797 798 _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {} 799 800 _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} 801 _LIBCPP_HIDE_FROM_ABI 802 __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {} 803 804 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 805 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 806 807 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() { 808 ++__i_; 809 return *this; 810 } 811 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) { 812 __map_const_iterator __t(*this); 813 ++(*this); 814 return __t; 815 } 816 817 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() { 818 --__i_; 819 return *this; 820 } 821 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) { 822 __map_const_iterator __t(*this); 823 --(*this); 824 return __t; 825 } 826 827 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) { 828 return __x.__i_ == __y.__i_; 829 } 830 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) { 831 return __x.__i_ != __y.__i_; 832 } 833 834 template <class, class, class, class> 835 friend class _LIBCPP_TEMPLATE_VIS map; 836 template <class, class, class, class> 837 friend class _LIBCPP_TEMPLATE_VIS multimap; 838 template <class, class, class> 839 friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; 840}; 841 842template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > > 843class _LIBCPP_TEMPLATE_VIS map { 844public: 845 // types: 846 typedef _Key key_type; 847 typedef _Tp mapped_type; 848 typedef pair<const key_type, mapped_type> value_type; 849 typedef __type_identity_t<_Compare> key_compare; 850 typedef __type_identity_t<_Allocator> allocator_type; 851 typedef value_type& reference; 852 typedef const value_type& const_reference; 853 854 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 855 "Allocator::value_type must be same type as value_type"); 856 857 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> { 858 friend class map; 859 860 protected: 861 key_compare comp; 862 863 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} 864 865 public: 866 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const { 867 return comp(__x.first, __y.first); 868 } 869 }; 870 871private: 872 typedef std::__value_type<key_type, mapped_type> __value_type; 873 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 874 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 875 typedef __tree<__value_type, __vc, __allocator_type> __base; 876 typedef typename __base::__node_traits __node_traits; 877 typedef allocator_traits<allocator_type> __alloc_traits; 878 879 static_assert(__check_valid_allocator<allocator_type>::value, ""); 880 881 __base __tree_; 882 883public: 884 typedef typename __alloc_traits::pointer pointer; 885 typedef typename __alloc_traits::const_pointer const_pointer; 886 typedef typename __alloc_traits::size_type size_type; 887 typedef typename __alloc_traits::difference_type difference_type; 888 typedef __map_iterator<typename __base::iterator> iterator; 889 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 890 typedef std::reverse_iterator<iterator> reverse_iterator; 891 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 892 893 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 894 friend class _LIBCPP_TEMPLATE_VIS map; 895 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 896 friend class _LIBCPP_TEMPLATE_VIS multimap; 897 898 _LIBCPP_HIDE_FROM_ABI map() : __tree_(__vc(key_compare())) {} 899 900 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) : __tree_(__vc(__comp)) {} 901 902 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a) 903 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 904 905 template <class _InputIterator> 906 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) 907 : __tree_(__vc(__comp)) { 908 insert(__f, __l); 909 } 910 911 template <class _InputIterator> 912 _LIBCPP_HIDE_FROM_ABI 913 map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) 914 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 915 insert(__f, __l); 916 } 917 918 _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); } 919 920 _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) { 921 if (this != std::addressof(__m)) { 922 __tree_.clear(); 923 __tree_.value_comp() = __m.__tree_.value_comp(); 924 __tree_.__copy_assign_alloc(__m.__tree_); 925 insert(__m.begin(), __m.end()); 926 } 927 return *this; 928 } 929 930 _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} 931 932 _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a) 933 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { 934 insert(__m.begin(), __m.end()); 935 } 936 937 _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 938 939 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 940 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 941 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 942 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 943 944 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 945 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 946 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 947 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 948 949 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 950 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 951 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 952 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 953 954 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 955 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 956 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 957 958 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 959 960 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); 961 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; 962 963 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } 964 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } 965 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } 966 967 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); } 968 969 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 970 return __tree_.__insert_unique(__p.__i_, __v); 971 } 972 973 template <class _InputIterator> 974 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 975 for (const_iterator __e = cend(); __f != __l; ++__f) 976 insert(__e.__i_, *__f); 977 } 978 979 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } 980 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } 981 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); } 982 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { 983 return __tree_.erase(__f.__i_, __l.__i_); 984 } 985 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 986 987 _LIBCPP_HIDE_FROM_ABI void swap(map& __m) { __tree_.swap(__m.__tree_); } 988 989 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 990 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 991 992 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); } 993 994 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 995 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 996 997 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 998 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 999 1000 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1001 return __tree_.__equal_range_unique(__k); 1002 } 1003 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1004 return __tree_.__equal_range_unique(__k); 1005 } 1006 1007private: 1008 typedef typename __base::__node __node; 1009 typedef typename __base::__node_allocator __node_allocator; 1010 typedef typename __base::__node_pointer __node_pointer; 1011 typedef typename __base::__node_base_pointer __node_base_pointer; 1012 typedef typename __base::__parent_pointer __parent_pointer; 1013 1014 typedef __map_node_destructor<__node_allocator> _Dp; 1015 typedef unique_ptr<__node, _Dp> __node_holder; 1016 1017 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); 1018}; 1019 1020template <class _Key, class _Tp, class _Compare, class _Allocator> 1021typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder 1022map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) { 1023 __node_allocator& __na = __tree_.__node_alloc(); 1024 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1025 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k); 1026 __h.get_deleter().__first_constructed = true; 1027 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second)); 1028 __h.get_deleter().__second_constructed = true; 1029 return __h; 1030} 1031 1032template <class _Key, class _Tp, class _Compare, class _Allocator> 1033_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { 1034 __parent_pointer __parent; 1035 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1036 __node_pointer __r = static_cast<__node_pointer>(__child); 1037 if (__child == nullptr) { 1038 __node_holder __h = __construct_node_with_key(__k); 1039 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); 1040 __r = __h.release(); 1041 } 1042 return __r->__value_.__get_value().second; 1043} 1044 1045template <class _Key, class _Tp, class _Compare, class _Allocator> 1046_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) { 1047 __parent_pointer __parent; 1048 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); 1049 if (__child == nullptr) 1050 __throw_out_of_range("map::at: key not found"); 1051 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1052} 1053 1054template <class _Key, class _Tp, class _Compare, class _Allocator> 1055const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const { 1056 __parent_pointer __parent; 1057 __node_base_pointer __child = __tree_.__find_equal(__parent, __k); 1058 if (__child == nullptr) 1059 __throw_out_of_range("map::at: key not found"); 1060 return static_cast<__node_pointer>(__child)->__value_.__get_value().second; 1061} 1062 1063template <class _Key, class _Tp, class _Compare, class _Allocator> 1064inline _LIBCPP_HIDE_FROM_ABI bool 1065operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1066 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 1067} 1068 1069template <class _Key, class _Tp, class _Compare, class _Allocator> 1070inline _LIBCPP_HIDE_FROM_ABI bool 1071operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1072 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1073} 1074 1075template <class _Key, class _Tp, class _Compare, class _Allocator> 1076inline _LIBCPP_HIDE_FROM_ABI bool 1077operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1078 return !(__x == __y); 1079} 1080 1081template <class _Key, class _Tp, class _Compare, class _Allocator> 1082inline _LIBCPP_HIDE_FROM_ABI bool 1083operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1084 return __y < __x; 1085} 1086 1087template <class _Key, class _Tp, class _Compare, class _Allocator> 1088inline _LIBCPP_HIDE_FROM_ABI bool 1089operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1090 return !(__x < __y); 1091} 1092 1093template <class _Key, class _Tp, class _Compare, class _Allocator> 1094inline _LIBCPP_HIDE_FROM_ABI bool 1095operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { 1096 return !(__y < __x); 1097} 1098 1099template <class _Key, class _Tp, class _Compare, class _Allocator> 1100inline _LIBCPP_HIDE_FROM_ABI void 1101swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y) { 1102 __x.swap(__y); 1103} 1104 1105template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > > 1106class _LIBCPP_TEMPLATE_VIS multimap { 1107public: 1108 // types: 1109 typedef _Key key_type; 1110 typedef _Tp mapped_type; 1111 typedef pair<const key_type, mapped_type> value_type; 1112 typedef __type_identity_t<_Compare> key_compare; 1113 typedef __type_identity_t<_Allocator> allocator_type; 1114 typedef value_type& reference; 1115 typedef const value_type& const_reference; 1116 1117 static_assert(__check_valid_allocator<allocator_type>::value, ""); 1118 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 1119 "Allocator::value_type must be same type as value_type"); 1120 1121 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> { 1122 friend class multimap; 1123 1124 protected: 1125 key_compare comp; 1126 1127 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} 1128 1129 public: 1130 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const { 1131 return comp(__x.first, __y.first); 1132 } 1133 }; 1134 1135private: 1136 typedef std::__value_type<key_type, mapped_type> __value_type; 1137 typedef __map_value_compare<key_type, __value_type, key_compare> __vc; 1138 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 1139 typedef __tree<__value_type, __vc, __allocator_type> __base; 1140 typedef typename __base::__node_traits __node_traits; 1141 typedef allocator_traits<allocator_type> __alloc_traits; 1142 1143 __base __tree_; 1144 1145public: 1146 typedef typename __alloc_traits::pointer pointer; 1147 typedef typename __alloc_traits::const_pointer const_pointer; 1148 typedef typename __alloc_traits::size_type size_type; 1149 typedef typename __alloc_traits::difference_type difference_type; 1150 typedef __map_iterator<typename __base::iterator> iterator; 1151 typedef __map_const_iterator<typename __base::const_iterator> const_iterator; 1152 typedef std::reverse_iterator<iterator> reverse_iterator; 1153 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1154 1155 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1156 friend class _LIBCPP_TEMPLATE_VIS map; 1157 template <class _Key2, class _Value2, class _Comp2, class _Alloc2> 1158 friend class _LIBCPP_TEMPLATE_VIS multimap; 1159 1160 _LIBCPP_HIDE_FROM_ABI multimap() : __tree_(__vc(key_compare())) {} 1161 1162 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) : __tree_(__vc(__comp)) {} 1163 1164 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a) 1165 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} 1166 1167 template <class _InputIterator> 1168 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) 1169 : __tree_(__vc(__comp)) { 1170 insert(__f, __l); 1171 } 1172 1173 template <class _InputIterator> 1174 _LIBCPP_HIDE_FROM_ABI 1175 multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) 1176 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { 1177 insert(__f, __l); 1178 } 1179 1180 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m) 1181 : __tree_(__m.__tree_.value_comp(), 1182 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) { 1183 insert(__m.begin(), __m.end()); 1184 } 1185 1186 _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) { 1187 if (this != std::addressof(__m)) { 1188 __tree_.clear(); 1189 __tree_.value_comp() = __m.__tree_.value_comp(); 1190 __tree_.__copy_assign_alloc(__m.__tree_); 1191 insert(__m.begin(), __m.end()); 1192 } 1193 return *this; 1194 } 1195 1196 _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} 1197 1198 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a) 1199 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { 1200 insert(__m.begin(), __m.end()); 1201 } 1202 1203 _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 1204 1205 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 1206 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 1207 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 1208 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 1209 1210 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 1211 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 1212 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 1213 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 1214 1215 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 1216 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 1217 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 1218 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 1219 1220 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 1221 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 1222 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 1223 1224 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } 1225 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } 1226 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } 1227 1228 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); } 1229 1230 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 1231 return __tree_.__insert_multi(__p.__i_, __v); 1232 } 1233 1234 template <class _InputIterator> 1235 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 1236 for (const_iterator __e = cend(); __f != __l; ++__f) 1237 __tree_.__insert_multi(__e.__i_, *__f); 1238 } 1239 1240 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } 1241 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } 1242 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); } 1243 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { 1244 return __tree_.erase(__f.__i_, __l.__i_); 1245 } 1246 1247 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 1248 1249 _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) { __tree_.swap(__m.__tree_); } 1250 1251 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 1252 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 1253 1254 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); } 1255 1256 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 1257 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 1258 1259 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 1260 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 1261 1262 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1263 return __tree_.__equal_range_multi(__k); 1264 } 1265 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1266 return __tree_.__equal_range_multi(__k); 1267 } 1268 1269private: 1270 typedef typename __base::__node __node; 1271 typedef typename __base::__node_allocator __node_allocator; 1272 typedef typename __base::__node_pointer __node_pointer; 1273 1274 typedef __map_node_destructor<__node_allocator> _Dp; 1275 typedef unique_ptr<__node, _Dp> __node_holder; 1276}; 1277 1278template <class _Key, class _Tp, class _Compare, class _Allocator> 1279inline _LIBCPP_HIDE_FROM_ABI bool 1280operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1281 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 1282} 1283 1284template <class _Key, class _Tp, class _Compare, class _Allocator> 1285inline _LIBCPP_HIDE_FROM_ABI bool 1286operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1287 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1288} 1289 1290template <class _Key, class _Tp, class _Compare, class _Allocator> 1291inline _LIBCPP_HIDE_FROM_ABI bool 1292operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1293 return !(__x == __y); 1294} 1295 1296template <class _Key, class _Tp, class _Compare, class _Allocator> 1297inline _LIBCPP_HIDE_FROM_ABI bool 1298operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1299 return __y < __x; 1300} 1301 1302template <class _Key, class _Tp, class _Compare, class _Allocator> 1303inline _LIBCPP_HIDE_FROM_ABI bool 1304operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1305 return !(__x < __y); 1306} 1307 1308template <class _Key, class _Tp, class _Compare, class _Allocator> 1309inline _LIBCPP_HIDE_FROM_ABI bool 1310operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1311 return !(__y < __x); 1312} 1313 1314template <class _Key, class _Tp, class _Compare, class _Allocator> 1315inline _LIBCPP_HIDE_FROM_ABI void 1316swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y) { 1317 __x.swap(__y); 1318} 1319 1320_LIBCPP_END_NAMESPACE_STD 1321 1322_LIBCPP_POP_MACROS 1323 1324#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) 1325# include <__cxx03/cstdlib> 1326# include <__cxx03/functional> 1327# include <__cxx03/iterator> 1328# include <__cxx03/type_traits> 1329# include <__cxx03/utility> 1330#endif 1331 1332#endif // _LIBCPP___CXX03_MAP 1333