1333 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_MAP11#define _LIBCPP___CXX03_MAP12 13/*14 15 map synopsis16 17namespace std18{19 20template <class Key, class T, class Compare = less<Key>,21 class Allocator = allocator<pair<const Key, T>>>22class map23{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++1743 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1744 45 class value_compare46 {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++2054 typedef value_type first_argument_type; // deprecated in C++17, removed in C++2055 typedef value_type second_argument_type; // deprecated in C++17, removed in C++2056 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++2375 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++1488 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++2391 map(initializer_list<value_type> il, const allocator_type& a)92 : map(il, Compare(), a) {} // C++1493 ~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++17138 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++17142 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++23148 void insert(initializer_list<value_type> il);149 150 node_type extract(const_iterator position); // C++17151 node_type extract(const key_type& x); // C++17152 insert_return_type insert(node_type&& nh); // C++17153 iterator insert(const_iterator hint, node_type&& nh); // C++17154 155 template <class... Args>156 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17157 template <class... Args>158 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17159 template <class... Args>160 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17161 template <class... Args>162 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17163 template <class M>164 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17165 template <class M>166 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17167 template <class M>168 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17169 template <class M>170 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17171 172 iterator erase(const_iterator position);173 iterator erase(iterator position); // C++14174 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++17180 template<class C2>181 void merge(map<Key, T, C2, Allocator>&& source); // C++17182 template<class C2>183 void merge(multimap<Key, T, C2, Allocator>& source); // C++17184 template<class C2>185 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17186 187 void swap(map& m)188 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&189 is_nothrow_swappable<key_compare>::value); // C++17190 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++14201 template<typename K>202 const_iterator find(const K& x) const; // C++14203 204 template<typename K>205 size_type count(const K& x) const; // C++14206 size_type count(const key_type& k) const;207 208 bool contains(const key_type& x) const; // C++20209 template<class K> bool contains(const K& x) const; // C++20210 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++14215 template<typename K>216 const_iterator lower_bound(const K& x) const; // C++14217 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++14222 template<typename K>223 const_iterator upper_bound(const K& x) const; // C++14224 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++14229 template<typename K>230 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14231};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++17238 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++23243 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++17248 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++17253 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++23257 258template<class Key, class T, class Allocator>259map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17260 261template <class Key, class T, class Compare, class Allocator>262bool263operator==(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>267bool268operator< (const map<Key, T, Compare, Allocator>& x,269 const map<Key, T, Compare, Allocator>& y); // removed in C++20270 271template <class Key, class T, class Compare, class Allocator>272bool273operator!=(const map<Key, T, Compare, Allocator>& x,274 const map<Key, T, Compare, Allocator>& y); // removed in C++20275 276template <class Key, class T, class Compare, class Allocator>277bool278operator> (const map<Key, T, Compare, Allocator>& x,279 const map<Key, T, Compare, Allocator>& y); // removed in C++20280 281template <class Key, class T, class Compare, class Allocator>282bool283operator>=(const map<Key, T, Compare, Allocator>& x,284 const map<Key, T, Compare, Allocator>& y); // removed in C++20285 286template <class Key, class T, class Compare, class Allocator>287bool288operator<=(const map<Key, T, Compare, Allocator>& x,289 const map<Key, T, Compare, Allocator>& y); // removed in C++20290 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++20295 296// specialized algorithms:297template <class Key, class T, class Compare, class Allocator>298void299swap(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_type304erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20305 306 307template <class Key, class T, class Compare = less<Key>,308 class Allocator = allocator<pair<const Key, T>>>309class multimap310{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++17330 331 class value_compare332 {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++20339 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20340 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20341 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++23360 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++14374 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++23377 multimap(initializer_list<value_type> il, const allocator_type& a)378 : multimap(il, Compare(), a) {} // C++14379 ~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++17417 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++17421 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++23427 void insert(initializer_list<value_type> il);428 429 node_type extract(const_iterator position); // C++17430 node_type extract(const key_type& x); // C++17431 iterator insert(node_type&& nh); // C++17432 iterator insert(const_iterator hint, node_type&& nh); // C++17433 434 iterator erase(const_iterator position);435 iterator erase(iterator position); // C++14436 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++17442 template<class C2>443 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17444 template<class C2>445 void merge(map<Key, T, C2, Allocator>& source); // C++17446 template<class C2>447 void merge(map<Key, T, C2, Allocator>&& source); // C++17448 449 void swap(multimap& m)450 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&451 is_nothrow_swappable<key_compare>::value); // C++17452 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++14463 template<typename K>464 const_iterator find(const K& x) const; // C++14465 466 template<typename K>467 size_type count(const K& x) const; // C++14468 size_type count(const key_type& k) const;469 470 bool contains(const key_type& x) const; // C++20471 template<class K> bool contains(const K& x) const; // C++20472 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++14477 template<typename K>478 const_iterator lower_bound(const K& x) const; // C++14479 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++14484 template<typename K>485 const_iterator upper_bound(const K& x) const; // C++14486 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++14491 template<typename K>492 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14493};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++17500 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++23505 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++17510 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++17515 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++23519 520template<class Key, class T, class Allocator>521multimap(initializer_list<pair<const Key, T>>, Allocator)522 -> multimap<Key, T, less<Key>, Allocator>; // C++17523 524template <class Key, class T, class Compare, class Allocator>525bool526operator==(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>530bool531operator< (const multimap<Key, T, Compare, Allocator>& x,532 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20533 534template <class Key, class T, class Compare, class Allocator>535bool536operator!=(const multimap<Key, T, Compare, Allocator>& x,537 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20538 539template <class Key, class T, class Compare, class Allocator>540bool541operator> (const multimap<Key, T, Compare, Allocator>& x,542 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20543 544template <class Key, class T, class Compare, class Allocator>545bool546operator>=(const multimap<Key, T, Compare, Allocator>& x,547 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20548 549template <class Key, class T, class Compare, class Allocator>550bool551operator<=(const multimap<Key, T, Compare, Allocator>& x,552 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20553 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++20558 559// specialized algorithms:560template <class Key, class T, class Compare, class Allocator>561void562swap(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_type568erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20569 570} // std571 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 includes594 595// [iterator.range]596#include <__cxx03/__iterator/access.h>597 598#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)599# pragma GCC system_header600#endif601 602_LIBCPP_PUSH_MACROS603#include <__cxx03/__undef_macros>604 605_LIBCPP_BEGIN_NAMESPACE_STD606 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 void657swap(__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) _NOEXCEPT677 : __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_ABI802 __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_ABI913 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_holder1022map<_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 bool1065operator==(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 bool1071operator<(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 bool1077operator!=(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 bool1083operator>(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 bool1089operator>=(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 bool1095operator<=(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 void1101swap(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_ABI1175 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 bool1280operator==(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 bool1286operator<(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 bool1292operator!=(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 bool1298operator>(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 bool1304operator>=(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 bool1310operator<=(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 void1316swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y) {1317 __x.swap(__y);1318}1319 1320_LIBCPP_END_NAMESPACE_STD1321 1322_LIBCPP_POP_MACROS1323 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#endif1331 1332#endif // _LIBCPP___CXX03_MAP1333