Warning, /include/c++/v1/__cxx03/map is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03_MAP
0011 #define _LIBCPP___CXX03_MAP
0012
0013 /*
0014
0015 map synopsis
0016
0017 namespace std
0018 {
0019
0020 template <class Key, class T, class Compare = less<Key>,
0021 class Allocator = allocator<pair<const Key, T>>>
0022 class map
0023 {
0024 public:
0025 // types:
0026 typedef Key key_type;
0027 typedef T mapped_type;
0028 typedef pair<const key_type, mapped_type> value_type;
0029 typedef Compare key_compare;
0030 typedef Allocator allocator_type;
0031 typedef typename allocator_type::reference reference;
0032 typedef typename allocator_type::const_reference const_reference;
0033 typedef typename allocator_type::pointer pointer;
0034 typedef typename allocator_type::const_pointer const_pointer;
0035 typedef typename allocator_type::size_type size_type;
0036 typedef typename allocator_type::difference_type difference_type;
0037
0038 typedef implementation-defined iterator;
0039 typedef implementation-defined const_iterator;
0040 typedef std::reverse_iterator<iterator> reverse_iterator;
0041 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0042 typedef unspecified node_type; // C++17
0043 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
0044
0045 class value_compare
0046 {
0047 friend class map;
0048 protected:
0049 key_compare comp;
0050
0051 value_compare(key_compare c);
0052 public:
0053 typedef bool result_type; // deprecated in C++17, removed in C++20
0054 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
0055 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
0056 bool operator()(const value_type& x, const value_type& y) const;
0057 };
0058
0059 // construct/copy/destroy:
0060 map()
0061 noexcept(
0062 is_nothrow_default_constructible<allocator_type>::value &&
0063 is_nothrow_default_constructible<key_compare>::value &&
0064 is_nothrow_copy_constructible<key_compare>::value);
0065 explicit map(const key_compare& comp);
0066 map(const key_compare& comp, const allocator_type& a);
0067 template <class InputIterator>
0068 map(InputIterator first, InputIterator last,
0069 const key_compare& comp = key_compare());
0070 template <class InputIterator>
0071 map(InputIterator first, InputIterator last,
0072 const key_compare& comp, const allocator_type& a);
0073 template<container-compatible-range<value_type> R>
0074 map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
0075 map(const map& m);
0076 map(map&& m)
0077 noexcept(
0078 is_nothrow_move_constructible<allocator_type>::value &&
0079 is_nothrow_move_constructible<key_compare>::value);
0080 explicit map(const allocator_type& a);
0081 map(const map& m, const allocator_type& a);
0082 map(map&& m, const allocator_type& a);
0083 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
0084 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
0085 template <class InputIterator>
0086 map(InputIterator first, InputIterator last, const allocator_type& a)
0087 : map(first, last, Compare(), a) {} // C++14
0088 template<container-compatible-range<value_type> R>
0089 map(from_range_t, R&& rg, const Allocator& a))
0090 : map(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
0091 map(initializer_list<value_type> il, const allocator_type& a)
0092 : map(il, Compare(), a) {} // C++14
0093 ~map();
0094
0095 map& operator=(const map& m);
0096 map& operator=(map&& m)
0097 noexcept(
0098 allocator_type::propagate_on_container_move_assignment::value &&
0099 is_nothrow_move_assignable<allocator_type>::value &&
0100 is_nothrow_move_assignable<key_compare>::value);
0101 map& operator=(initializer_list<value_type> il);
0102
0103 // iterators:
0104 iterator begin() noexcept;
0105 const_iterator begin() const noexcept;
0106 iterator end() noexcept;
0107 const_iterator end() const noexcept;
0108
0109 reverse_iterator rbegin() noexcept;
0110 const_reverse_iterator rbegin() const noexcept;
0111 reverse_iterator rend() noexcept;
0112 const_reverse_iterator rend() const noexcept;
0113
0114 const_iterator cbegin() const noexcept;
0115 const_iterator cend() const noexcept;
0116 const_reverse_iterator crbegin() const noexcept;
0117 const_reverse_iterator crend() const noexcept;
0118
0119 // capacity:
0120 bool empty() const noexcept;
0121 size_type size() const noexcept;
0122 size_type max_size() const noexcept;
0123
0124 // element access:
0125 mapped_type& operator[](const key_type& k);
0126 mapped_type& operator[](key_type&& k);
0127
0128 mapped_type& at(const key_type& k);
0129 const mapped_type& at(const key_type& k) const;
0130
0131 // modifiers:
0132 template <class... Args>
0133 pair<iterator, bool> emplace(Args&&... args);
0134 template <class... Args>
0135 iterator emplace_hint(const_iterator position, Args&&... args);
0136 pair<iterator, bool> insert(const value_type& v);
0137 pair<iterator, bool> insert( value_type&& v); // C++17
0138 template <class P>
0139 pair<iterator, bool> insert(P&& p);
0140 iterator insert(const_iterator position, const value_type& v);
0141 iterator insert(const_iterator position, value_type&& v); // C++17
0142 template <class P>
0143 iterator insert(const_iterator position, P&& p);
0144 template <class InputIterator>
0145 void insert(InputIterator first, InputIterator last);
0146 template<container-compatible-range<value_type> R>
0147 void insert_range(R&& rg); // C++23
0148 void insert(initializer_list<value_type> il);
0149
0150 node_type extract(const_iterator position); // C++17
0151 node_type extract(const key_type& x); // C++17
0152 insert_return_type insert(node_type&& nh); // C++17
0153 iterator insert(const_iterator hint, node_type&& nh); // C++17
0154
0155 template <class... Args>
0156 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
0157 template <class... Args>
0158 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
0159 template <class... Args>
0160 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
0161 template <class... Args>
0162 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
0163 template <class M>
0164 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
0165 template <class M>
0166 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
0167 template <class M>
0168 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
0169 template <class M>
0170 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
0171
0172 iterator erase(const_iterator position);
0173 iterator erase(iterator position); // C++14
0174 size_type erase(const key_type& k);
0175 iterator erase(const_iterator first, const_iterator last);
0176 void clear() noexcept;
0177
0178 template<class C2>
0179 void merge(map<Key, T, C2, Allocator>& source); // C++17
0180 template<class C2>
0181 void merge(map<Key, T, C2, Allocator>&& source); // C++17
0182 template<class C2>
0183 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
0184 template<class C2>
0185 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
0186
0187 void swap(map& m)
0188 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
0189 is_nothrow_swappable<key_compare>::value); // C++17
0190
0191 // observers:
0192 allocator_type get_allocator() const noexcept;
0193 key_compare key_comp() const;
0194 value_compare value_comp() const;
0195
0196 // map operations:
0197 iterator find(const key_type& k);
0198 const_iterator find(const key_type& k) const;
0199 template<typename K>
0200 iterator find(const K& x); // C++14
0201 template<typename K>
0202 const_iterator find(const K& x) const; // C++14
0203
0204 template<typename K>
0205 size_type count(const K& x) const; // C++14
0206 size_type count(const key_type& k) const;
0207
0208 bool contains(const key_type& x) const; // C++20
0209 template<class K> bool contains(const K& x) const; // C++20
0210
0211 iterator lower_bound(const key_type& k);
0212 const_iterator lower_bound(const key_type& k) const;
0213 template<typename K>
0214 iterator lower_bound(const K& x); // C++14
0215 template<typename K>
0216 const_iterator lower_bound(const K& x) const; // C++14
0217
0218 iterator upper_bound(const key_type& k);
0219 const_iterator upper_bound(const key_type& k) const;
0220 template<typename K>
0221 iterator upper_bound(const K& x); // C++14
0222 template<typename K>
0223 const_iterator upper_bound(const K& x) const; // C++14
0224
0225 pair<iterator,iterator> equal_range(const key_type& k);
0226 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
0227 template<typename K>
0228 pair<iterator,iterator> equal_range(const K& x); // C++14
0229 template<typename K>
0230 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
0231 };
0232
0233 template <class InputIterator,
0234 class Compare = less<iter_key_t<InputIterator>>,
0235 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
0236 map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
0237 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
0238
0239 template<ranges::input_range R, class Compare = less<range-key-type<R>,
0240 class Allocator = allocator<range-to-alloc-type<R>>>
0241 map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
0242 -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
0243
0244 template<class Key, class T, class Compare = less<Key>,
0245 class Allocator = allocator<pair<const Key, T>>>
0246 map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
0247 -> map<Key, T, Compare, Allocator>; // C++17
0248
0249 template <class InputIterator, class Allocator>
0250 map(InputIterator, InputIterator, Allocator)
0251 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,
0252 Allocator>; // C++17
0253
0254 template<ranges::input_range R, class Allocator>
0255 map(from_range_t, R&&, Allocator)
0256 -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
0257
0258 template<class Key, class T, class Allocator>
0259 map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17
0260
0261 template <class Key, class T, class Compare, class Allocator>
0262 bool
0263 operator==(const map<Key, T, Compare, Allocator>& x,
0264 const map<Key, T, Compare, Allocator>& y);
0265
0266 template <class Key, class T, class Compare, class Allocator>
0267 bool
0268 operator< (const map<Key, T, Compare, Allocator>& x,
0269 const map<Key, T, Compare, Allocator>& y); // removed in C++20
0270
0271 template <class Key, class T, class Compare, class Allocator>
0272 bool
0273 operator!=(const map<Key, T, Compare, Allocator>& x,
0274 const map<Key, T, Compare, Allocator>& y); // removed in C++20
0275
0276 template <class Key, class T, class Compare, class Allocator>
0277 bool
0278 operator> (const map<Key, T, Compare, Allocator>& x,
0279 const map<Key, T, Compare, Allocator>& y); // removed in C++20
0280
0281 template <class Key, class T, class Compare, class Allocator>
0282 bool
0283 operator>=(const map<Key, T, Compare, Allocator>& x,
0284 const map<Key, T, Compare, Allocator>& y); // removed in C++20
0285
0286 template <class Key, class T, class Compare, class Allocator>
0287 bool
0288 operator<=(const map<Key, T, Compare, Allocator>& x,
0289 const map<Key, T, Compare, Allocator>& y); // removed in C++20
0290
0291 template<class Key, class T, class Compare, class Allocator>
0292 synth-three-way-result<pair<const Key, T>>
0293 operator<=>(const map<Key, T, Compare, Allocator>& x,
0294 const map<Key, T, Compare, Allocator>& y); // since C++20
0295
0296 // specialized algorithms:
0297 template <class Key, class T, class Compare, class Allocator>
0298 void
0299 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
0300 noexcept(noexcept(x.swap(y)));
0301
0302 template <class Key, class T, class Compare, class Allocator, class Predicate>
0303 typename map<Key, T, Compare, Allocator>::size_type
0304 erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
0305
0306
0307 template <class Key, class T, class Compare = less<Key>,
0308 class Allocator = allocator<pair<const Key, T>>>
0309 class multimap
0310 {
0311 public:
0312 // types:
0313 typedef Key key_type;
0314 typedef T mapped_type;
0315 typedef pair<const key_type,mapped_type> value_type;
0316 typedef Compare key_compare;
0317 typedef Allocator allocator_type;
0318 typedef typename allocator_type::reference reference;
0319 typedef typename allocator_type::const_reference const_reference;
0320 typedef typename allocator_type::size_type size_type;
0321 typedef typename allocator_type::difference_type difference_type;
0322 typedef typename allocator_type::pointer pointer;
0323 typedef typename allocator_type::const_pointer const_pointer;
0324
0325 typedef implementation-defined iterator;
0326 typedef implementation-defined const_iterator;
0327 typedef std::reverse_iterator<iterator> reverse_iterator;
0328 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0329 typedef unspecified node_type; // C++17
0330
0331 class value_compare
0332 {
0333 friend class multimap;
0334 protected:
0335 key_compare comp;
0336 value_compare(key_compare c);
0337 public:
0338 typedef bool result_type; // deprecated in C++17, removed in C++20
0339 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
0340 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
0341 bool operator()(const value_type& x, const value_type& y) const;
0342 };
0343
0344 // construct/copy/destroy:
0345 multimap()
0346 noexcept(
0347 is_nothrow_default_constructible<allocator_type>::value &&
0348 is_nothrow_default_constructible<key_compare>::value &&
0349 is_nothrow_copy_constructible<key_compare>::value);
0350 explicit multimap(const key_compare& comp);
0351 multimap(const key_compare& comp, const allocator_type& a);
0352 template <class InputIterator>
0353 multimap(InputIterator first, InputIterator last, const key_compare& comp);
0354 template <class InputIterator>
0355 multimap(InputIterator first, InputIterator last, const key_compare& comp,
0356 const allocator_type& a);
0357 template<container-compatible-range<value_type> R>
0358 multimap(from_range_t, R&& rg,
0359 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
0360 multimap(const multimap& m);
0361 multimap(multimap&& m)
0362 noexcept(
0363 is_nothrow_move_constructible<allocator_type>::value &&
0364 is_nothrow_move_constructible<key_compare>::value);
0365 explicit multimap(const allocator_type& a);
0366 multimap(const multimap& m, const allocator_type& a);
0367 multimap(multimap&& m, const allocator_type& a);
0368 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
0369 multimap(initializer_list<value_type> il, const key_compare& comp,
0370 const allocator_type& a);
0371 template <class InputIterator>
0372 multimap(InputIterator first, InputIterator last, const allocator_type& a)
0373 : multimap(first, last, Compare(), a) {} // C++14
0374 template<container-compatible-range<value_type> R>
0375 multimap(from_range_t, R&& rg, const Allocator& a))
0376 : multimap(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
0377 multimap(initializer_list<value_type> il, const allocator_type& a)
0378 : multimap(il, Compare(), a) {} // C++14
0379 ~multimap();
0380
0381 multimap& operator=(const multimap& m);
0382 multimap& operator=(multimap&& m)
0383 noexcept(
0384 allocator_type::propagate_on_container_move_assignment::value &&
0385 is_nothrow_move_assignable<allocator_type>::value &&
0386 is_nothrow_move_assignable<key_compare>::value);
0387 multimap& operator=(initializer_list<value_type> il);
0388
0389 // iterators:
0390 iterator begin() noexcept;
0391 const_iterator begin() const noexcept;
0392 iterator end() noexcept;
0393 const_iterator end() const noexcept;
0394
0395 reverse_iterator rbegin() noexcept;
0396 const_reverse_iterator rbegin() const noexcept;
0397 reverse_iterator rend() noexcept;
0398 const_reverse_iterator rend() const noexcept;
0399
0400 const_iterator cbegin() const noexcept;
0401 const_iterator cend() const noexcept;
0402 const_reverse_iterator crbegin() const noexcept;
0403 const_reverse_iterator crend() const noexcept;
0404
0405 // capacity:
0406 bool empty() const noexcept;
0407 size_type size() const noexcept;
0408 size_type max_size() const noexcept;
0409
0410 // modifiers:
0411 template <class... Args>
0412 iterator emplace(Args&&... args);
0413 template <class... Args>
0414 iterator emplace_hint(const_iterator position, Args&&... args);
0415 iterator insert(const value_type& v);
0416 iterator insert( value_type&& v); // C++17
0417 template <class P>
0418 iterator insert(P&& p);
0419 iterator insert(const_iterator position, const value_type& v);
0420 iterator insert(const_iterator position, value_type&& v); // C++17
0421 template <class P>
0422 iterator insert(const_iterator position, P&& p);
0423 template <class InputIterator>
0424 void insert(InputIterator first, InputIterator last);
0425 template<container-compatible-range<value_type> R>
0426 void insert_range(R&& rg); // C++23
0427 void insert(initializer_list<value_type> il);
0428
0429 node_type extract(const_iterator position); // C++17
0430 node_type extract(const key_type& x); // C++17
0431 iterator insert(node_type&& nh); // C++17
0432 iterator insert(const_iterator hint, node_type&& nh); // C++17
0433
0434 iterator erase(const_iterator position);
0435 iterator erase(iterator position); // C++14
0436 size_type erase(const key_type& k);
0437 iterator erase(const_iterator first, const_iterator last);
0438 void clear() noexcept;
0439
0440 template<class C2>
0441 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
0442 template<class C2>
0443 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
0444 template<class C2>
0445 void merge(map<Key, T, C2, Allocator>& source); // C++17
0446 template<class C2>
0447 void merge(map<Key, T, C2, Allocator>&& source); // C++17
0448
0449 void swap(multimap& m)
0450 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
0451 is_nothrow_swappable<key_compare>::value); // C++17
0452
0453 // observers:
0454 allocator_type get_allocator() const noexcept;
0455 key_compare key_comp() const;
0456 value_compare value_comp() const;
0457
0458 // map operations:
0459 iterator find(const key_type& k);
0460 const_iterator find(const key_type& k) const;
0461 template<typename K>
0462 iterator find(const K& x); // C++14
0463 template<typename K>
0464 const_iterator find(const K& x) const; // C++14
0465
0466 template<typename K>
0467 size_type count(const K& x) const; // C++14
0468 size_type count(const key_type& k) const;
0469
0470 bool contains(const key_type& x) const; // C++20
0471 template<class K> bool contains(const K& x) const; // C++20
0472
0473 iterator lower_bound(const key_type& k);
0474 const_iterator lower_bound(const key_type& k) const;
0475 template<typename K>
0476 iterator lower_bound(const K& x); // C++14
0477 template<typename K>
0478 const_iterator lower_bound(const K& x) const; // C++14
0479
0480 iterator upper_bound(const key_type& k);
0481 const_iterator upper_bound(const key_type& k) const;
0482 template<typename K>
0483 iterator upper_bound(const K& x); // C++14
0484 template<typename K>
0485 const_iterator upper_bound(const K& x) const; // C++14
0486
0487 pair<iterator,iterator> equal_range(const key_type& k);
0488 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
0489 template<typename K>
0490 pair<iterator,iterator> equal_range(const K& x); // C++14
0491 template<typename K>
0492 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
0493 };
0494
0495 template <class InputIterator,
0496 class Compare = less<iter_key_t<InputIterator>>,
0497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
0498 multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
0499 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
0500
0501 template<ranges::input_range R, class Compare = less<range-key-type<R>>,
0502 class Allocator = allocator<range-to-alloc-type<R>>>
0503 multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
0504 -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
0505
0506 template<class Key, class T, class Compare = less<Key>,
0507 class Allocator = allocator<pair<const Key, T>>>
0508 multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
0509 -> multimap<Key, T, Compare, Allocator>; // C++17
0510
0511 template <class InputIterator, class Allocator>
0512 multimap(InputIterator, InputIterator, Allocator)
0513 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
0514 less<iter_key_t<InputIterator>>, Allocator>; // C++17
0515
0516 template<ranges::input_range R, class Allocator>
0517 multimap(from_range_t, R&&, Allocator)
0518 -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
0519
0520 template<class Key, class T, class Allocator>
0521 multimap(initializer_list<pair<const Key, T>>, Allocator)
0522 -> multimap<Key, T, less<Key>, Allocator>; // C++17
0523
0524 template <class Key, class T, class Compare, class Allocator>
0525 bool
0526 operator==(const multimap<Key, T, Compare, Allocator>& x,
0527 const multimap<Key, T, Compare, Allocator>& y);
0528
0529 template <class Key, class T, class Compare, class Allocator>
0530 bool
0531 operator< (const multimap<Key, T, Compare, Allocator>& x,
0532 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
0533
0534 template <class Key, class T, class Compare, class Allocator>
0535 bool
0536 operator!=(const multimap<Key, T, Compare, Allocator>& x,
0537 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
0538
0539 template <class Key, class T, class Compare, class Allocator>
0540 bool
0541 operator> (const multimap<Key, T, Compare, Allocator>& x,
0542 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
0543
0544 template <class Key, class T, class Compare, class Allocator>
0545 bool
0546 operator>=(const multimap<Key, T, Compare, Allocator>& x,
0547 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
0548
0549 template <class Key, class T, class Compare, class Allocator>
0550 bool
0551 operator<=(const multimap<Key, T, Compare, Allocator>& x,
0552 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
0553
0554 template<class Key, class T, class Compare, class Allocator>
0555 synth-three-way-result<pair<const Key, T>>
0556 operator<=>(const multimap<Key, T, Compare, Allocator>& x,
0557 const multimap<Key, T, Compare, Allocator>& y); // since c++20
0558
0559 // specialized algorithms:
0560 template <class Key, class T, class Compare, class Allocator>
0561 void
0562 swap(multimap<Key, T, Compare, Allocator>& x,
0563 multimap<Key, T, Compare, Allocator>& y)
0564 noexcept(noexcept(x.swap(y)));
0565
0566 template <class Key, class T, class Compare, class Allocator, class Predicate>
0567 typename multimap<Key, T, Compare, Allocator>::size_type
0568 erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
0569
0570 } // std
0571
0572 */
0573
0574 #include <__cxx03/__algorithm/equal.h>
0575 #include <__cxx03/__algorithm/lexicographical_compare.h>
0576 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
0577 #include <__cxx03/__assert>
0578 #include <__cxx03/__config>
0579 #include <__cxx03/__functional/binary_function.h>
0580 #include <__cxx03/__functional/is_transparent.h>
0581 #include <__cxx03/__functional/operations.h>
0582 #include <__cxx03/__iterator/erase_if_container.h>
0583 #include <__cxx03/__iterator/iterator_traits.h>
0584 #include <__cxx03/__iterator/ranges_iterator_traits.h>
0585 #include <__cxx03/__iterator/reverse_iterator.h>
0586 #include <__cxx03/__memory/addressof.h>
0587 #include <__cxx03/__memory/allocator.h>
0588 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
0589 #include <__cxx03/__node_handle>
0590 #include <__cxx03/__ranges/concepts.h>
0591 #include <__cxx03/__ranges/container_compatible_range.h>
0592 #include <__cxx03/__ranges/from_range.h>
0593 #include <__cxx03/__tree>
0594 #include <__cxx03/__type_traits/is_allocator.h>
0595 #include <__cxx03/__utility/forward.h>
0596 #include <__cxx03/__utility/piecewise_construct.h>
0597 #include <__cxx03/__utility/swap.h>
0598 #include <__cxx03/stdexcept>
0599 #include <__cxx03/tuple>
0600 #include <__cxx03/version>
0601
0602 // standard-mandated includes
0603
0604 // [iterator.range]
0605 #include <__cxx03/__iterator/access.h>
0606 #include <__cxx03/__iterator/data.h>
0607 #include <__cxx03/__iterator/empty.h>
0608 #include <__cxx03/__iterator/reverse_access.h>
0609 #include <__cxx03/__iterator/size.h>
0610
0611 // [associative.map.syn]
0612 #include <__cxx03/compare>
0613 #include <__cxx03/initializer_list>
0614
0615 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0616 # pragma GCC system_header
0617 #endif
0618
0619 _LIBCPP_PUSH_MACROS
0620 #include <__cxx03/__undef_macros>
0621
0622 _LIBCPP_BEGIN_NAMESPACE_STD
0623
0624 template <class _Key,
0625 class _CP,
0626 class _Compare,
0627 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
0628 class __map_value_compare : private _Compare {
0629 public:
0630 _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
0631 : _Compare() {}
0632 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
0633 : _Compare(__c) {}
0634 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; }
0635 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
0636 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);
0637 }
0638 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
0639 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
0640 }
0641 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
0642 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
0643 }
0644 _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
0645 using std::swap;
0646 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
0647 }
0648
0649 #if _LIBCPP_STD_VER >= 14
0650 template <typename _K2>
0651 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
0652 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
0653 }
0654
0655 template <typename _K2>
0656 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
0657 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
0658 }
0659 #endif
0660 };
0661
0662 template <class _Key, class _CP, class _Compare>
0663 class __map_value_compare<_Key, _CP, _Compare, false> {
0664 _Compare __comp_;
0665
0666 public:
0667 _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
0668 : __comp_() {}
0669 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
0670 : __comp_(__c) {}
0671 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }
0672
0673 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
0674 return __comp_(__x.__get_value().first, __y.__get_value().first);
0675 }
0676 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
0677 return __comp_(__x.__get_value().first, __y);
0678 }
0679 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
0680 return __comp_(__x, __y.__get_value().first);
0681 }
0682 void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
0683 using std::swap;
0684 swap(__comp_, __y.__comp_);
0685 }
0686
0687 #if _LIBCPP_STD_VER >= 14
0688 template <typename _K2>
0689 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
0690 return __comp_(__x, __y.__get_value().first);
0691 }
0692
0693 template <typename _K2>
0694 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
0695 return __comp_(__x.__get_value().first, __y);
0696 }
0697 #endif
0698 };
0699
0700 template <class _Key, class _CP, class _Compare, bool __b>
0701 inline _LIBCPP_HIDE_FROM_ABI void
0702 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y)
0703 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0704 __x.swap(__y);
0705 }
0706
0707 template <class _Allocator>
0708 class __map_node_destructor {
0709 typedef _Allocator allocator_type;
0710 typedef allocator_traits<allocator_type> __alloc_traits;
0711
0712 public:
0713 typedef typename __alloc_traits::pointer pointer;
0714
0715 private:
0716 allocator_type& __na_;
0717
0718 public:
0719 bool __first_constructed;
0720 bool __second_constructed;
0721
0722 _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
0723 : __na_(__na),
0724 __first_constructed(false),
0725 __second_constructed(false) {}
0726
0727 #ifndef _LIBCPP_CXX03_LANG
0728 _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
0729 : __na_(__x.__na_),
0730 __first_constructed(__x.__value_constructed),
0731 __second_constructed(__x.__value_constructed) {
0732 __x.__value_constructed = false;
0733 }
0734 #endif // _LIBCPP_CXX03_LANG
0735
0736 __map_node_destructor& operator=(const __map_node_destructor&) = delete;
0737
0738 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
0739 if (__second_constructed)
0740 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second));
0741 if (__first_constructed)
0742 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first));
0743 if (__p)
0744 __alloc_traits::deallocate(__na_, __p, 1);
0745 }
0746 };
0747
0748 template <class _Key, class _Tp, class _Compare, class _Allocator>
0749 class map;
0750 template <class _Key, class _Tp, class _Compare, class _Allocator>
0751 class multimap;
0752 template <class _TreeIterator>
0753 class __map_const_iterator;
0754
0755 #ifndef _LIBCPP_CXX03_LANG
0756
0757 template <class _Key, class _Tp>
0758 struct _LIBCPP_STANDALONE_DEBUG __value_type {
0759 typedef _Key key_type;
0760 typedef _Tp mapped_type;
0761 typedef pair<const key_type, mapped_type> value_type;
0762 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
0763 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
0764
0765 private:
0766 value_type __cc_;
0767
0768 public:
0769 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
0770 # if _LIBCPP_STD_VER >= 17
0771 return *std::launder(std::addressof(__cc_));
0772 # else
0773 return __cc_;
0774 # endif
0775 }
0776
0777 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
0778 # if _LIBCPP_STD_VER >= 17
0779 return *std::launder(std::addressof(__cc_));
0780 # else
0781 return __cc_;
0782 # endif
0783 }
0784
0785 _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
0786 value_type& __v = __get_value();
0787 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
0788 }
0789
0790 _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
0791 value_type& __v = __get_value();
0792 return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
0793 }
0794
0795 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) {
0796 __ref() = __v.__get_value();
0797 return *this;
0798 }
0799
0800 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) {
0801 __ref() = __v.__move();
0802 return *this;
0803 }
0804
0805 template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0>
0806 _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) {
0807 __ref() = std::forward<_ValueTp>(__v);
0808 return *this;
0809 }
0810
0811 __value_type() = delete;
0812 ~__value_type() = delete;
0813 __value_type(const __value_type&) = delete;
0814 __value_type(__value_type&&) = delete;
0815 };
0816
0817 #else
0818
0819 template <class _Key, class _Tp>
0820 struct __value_type {
0821 typedef _Key key_type;
0822 typedef _Tp mapped_type;
0823 typedef pair<const key_type, mapped_type> value_type;
0824
0825 private:
0826 value_type __cc_;
0827
0828 public:
0829 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
0830 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
0831
0832 __value_type() = delete;
0833 __value_type(__value_type const&) = delete;
0834 __value_type& operator=(__value_type const&) = delete;
0835 ~__value_type() = delete;
0836 };
0837
0838 #endif // _LIBCPP_CXX03_LANG
0839
0840 template <class _Tp>
0841 struct __extract_key_value_types;
0842
0843 template <class _Key, class _Tp>
0844 struct __extract_key_value_types<__value_type<_Key, _Tp> > {
0845 typedef _Key const __key_type;
0846 typedef _Tp __mapped_type;
0847 };
0848
0849 template <class _TreeIterator>
0850 class _LIBCPP_TEMPLATE_VIS __map_iterator {
0851 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
0852 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
0853
0854 _TreeIterator __i_;
0855
0856 public:
0857 typedef bidirectional_iterator_tag iterator_category;
0858 typedef typename _NodeTypes::__map_value_type value_type;
0859 typedef typename _TreeIterator::difference_type difference_type;
0860 typedef value_type& reference;
0861 typedef typename _NodeTypes::__map_value_type_pointer pointer;
0862
0863 _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}
0864
0865 _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
0866
0867 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
0868 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
0869
0870 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {
0871 ++__i_;
0872 return *this;
0873 }
0874 _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {
0875 __map_iterator __t(*this);
0876 ++(*this);
0877 return __t;
0878 }
0879
0880 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {
0881 --__i_;
0882 return *this;
0883 }
0884 _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {
0885 __map_iterator __t(*this);
0886 --(*this);
0887 return __t;
0888 }
0889
0890 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {
0891 return __x.__i_ == __y.__i_;
0892 }
0893 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) {
0894 return __x.__i_ != __y.__i_;
0895 }
0896
0897 template <class, class, class, class>
0898 friend class _LIBCPP_TEMPLATE_VIS map;
0899 template <class, class, class, class>
0900 friend class _LIBCPP_TEMPLATE_VIS multimap;
0901 template <class>
0902 friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
0903 };
0904
0905 template <class _TreeIterator>
0906 class _LIBCPP_TEMPLATE_VIS __map_const_iterator {
0907 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
0908 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
0909
0910 _TreeIterator __i_;
0911
0912 public:
0913 typedef bidirectional_iterator_tag iterator_category;
0914 typedef typename _NodeTypes::__map_value_type value_type;
0915 typedef typename _TreeIterator::difference_type difference_type;
0916 typedef const value_type& reference;
0917 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
0918
0919 _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}
0920
0921 _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
0922 _LIBCPP_HIDE_FROM_ABI
0923 __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}
0924
0925 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
0926 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
0927
0928 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {
0929 ++__i_;
0930 return *this;
0931 }
0932 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {
0933 __map_const_iterator __t(*this);
0934 ++(*this);
0935 return __t;
0936 }
0937
0938 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {
0939 --__i_;
0940 return *this;
0941 }
0942 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {
0943 __map_const_iterator __t(*this);
0944 --(*this);
0945 return __t;
0946 }
0947
0948 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {
0949 return __x.__i_ == __y.__i_;
0950 }
0951 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) {
0952 return __x.__i_ != __y.__i_;
0953 }
0954
0955 template <class, class, class, class>
0956 friend class _LIBCPP_TEMPLATE_VIS map;
0957 template <class, class, class, class>
0958 friend class _LIBCPP_TEMPLATE_VIS multimap;
0959 template <class, class, class>
0960 friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
0961 };
0962
0963 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
0964 class _LIBCPP_TEMPLATE_VIS map {
0965 public:
0966 // types:
0967 typedef _Key key_type;
0968 typedef _Tp mapped_type;
0969 typedef pair<const key_type, mapped_type> value_type;
0970 typedef __type_identity_t<_Compare> key_compare;
0971 typedef __type_identity_t<_Allocator> allocator_type;
0972 typedef value_type& reference;
0973 typedef const value_type& const_reference;
0974
0975 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
0976 "Allocator::value_type must be same type as value_type");
0977
0978 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
0979 friend class map;
0980
0981 protected:
0982 key_compare comp;
0983
0984 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
0985
0986 public:
0987 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
0988 return comp(__x.first, __y.first);
0989 }
0990 };
0991
0992 private:
0993 typedef std::__value_type<key_type, mapped_type> __value_type;
0994 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
0995 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
0996 typedef __tree<__value_type, __vc, __allocator_type> __base;
0997 typedef typename __base::__node_traits __node_traits;
0998 typedef allocator_traits<allocator_type> __alloc_traits;
0999
1000 static_assert(__check_valid_allocator<allocator_type>::value, "");
1001
1002 __base __tree_;
1003
1004 public:
1005 typedef typename __alloc_traits::pointer pointer;
1006 typedef typename __alloc_traits::const_pointer const_pointer;
1007 typedef typename __alloc_traits::size_type size_type;
1008 typedef typename __alloc_traits::difference_type difference_type;
1009 typedef __map_iterator<typename __base::iterator> iterator;
1010 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1011 typedef std::reverse_iterator<iterator> reverse_iterator;
1012 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1013
1014 #if _LIBCPP_STD_VER >= 17
1015 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1016 typedef __insert_return_type<iterator, node_type> insert_return_type;
1017 #endif
1018
1019 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1020 friend class _LIBCPP_TEMPLATE_VIS map;
1021 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1022 friend class _LIBCPP_TEMPLATE_VIS multimap;
1023
1024 _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_(
1025 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1026 is_nothrow_copy_constructible<key_compare>::value)
1027 : __tree_(__vc(key_compare())) {}
1028
1029 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_(
1030 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1031 : __tree_(__vc(__comp)) {}
1032
1033 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)
1034 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1035
1036 template <class _InputIterator>
1037 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1038 : __tree_(__vc(__comp)) {
1039 insert(__f, __l);
1040 }
1041
1042 template <class _InputIterator>
1043 _LIBCPP_HIDE_FROM_ABI
1044 map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1045 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1046 insert(__f, __l);
1047 }
1048
1049 #if _LIBCPP_STD_VER >= 23
1050 template <_ContainerCompatibleRange<value_type> _Range>
1051 _LIBCPP_HIDE_FROM_ABI
1052 map(from_range_t,
1053 _Range&& __range,
1054 const key_compare& __comp = key_compare(),
1055 const allocator_type& __a = allocator_type())
1056 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1057 insert_range(std::forward<_Range>(__range));
1058 }
1059 #endif
1060
1061 #if _LIBCPP_STD_VER >= 14
1062 template <class _InputIterator>
1063 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1064 : map(__f, __l, key_compare(), __a) {}
1065 #endif
1066
1067 #if _LIBCPP_STD_VER >= 23
1068 template <_ContainerCompatibleRange<value_type> _Range>
1069 _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a)
1070 : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1071 #endif
1072
1073 _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); }
1074
1075 _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) {
1076 #ifndef _LIBCPP_CXX03_LANG
1077 __tree_ = __m.__tree_;
1078 #else
1079 if (this != std::addressof(__m)) {
1080 __tree_.clear();
1081 __tree_.value_comp() = __m.__tree_.value_comp();
1082 __tree_.__copy_assign_alloc(__m.__tree_);
1083 insert(__m.begin(), __m.end());
1084 }
1085 #endif
1086 return *this;
1087 }
1088
1089 #ifndef _LIBCPP_CXX03_LANG
1090
1091 _LIBCPP_HIDE_FROM_ABI map(map&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1092 : __tree_(std::move(__m.__tree_)) {}
1093
1094 _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a);
1095
1096 _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1097 __tree_ = std::move(__m.__tree_);
1098 return *this;
1099 }
1100
1101 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1102 : __tree_(__vc(__comp)) {
1103 insert(__il.begin(), __il.end());
1104 }
1105
1106 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1107 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1108 insert(__il.begin(), __il.end());
1109 }
1110
1111 # if _LIBCPP_STD_VER >= 14
1112 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)
1113 : map(__il, key_compare(), __a) {}
1114 # endif
1115
1116 _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {
1117 __tree_.__assign_unique(__il.begin(), __il.end());
1118 return *this;
1119 }
1120
1121 #endif // _LIBCPP_CXX03_LANG
1122
1123 _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1124
1125 _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
1126 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1127 insert(__m.begin(), __m.end());
1128 }
1129
1130 _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1131
1132 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1133 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1134 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1135 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1136
1137 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1138 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1139 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1140 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1141
1142 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1143 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1144 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1145 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1146
1147 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1148 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1149 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1150
1151 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1152 #ifndef _LIBCPP_CXX03_LANG
1153 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1154 #endif
1155
1156 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1157 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1158
1159 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1160 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1161 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1162
1163 #ifndef _LIBCPP_CXX03_LANG
1164 template <class... _Args>
1165 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1166 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
1167 }
1168
1169 template <class... _Args>
1170 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1171 return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
1172 }
1173
1174 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1175 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {
1176 return __tree_.__insert_unique(std::forward<_Pp>(__p));
1177 }
1178
1179 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1180 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1181 return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
1182 }
1183
1184 #endif // _LIBCPP_CXX03_LANG
1185
1186 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
1187
1188 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1189 return __tree_.__insert_unique(__p.__i_, __v);
1190 }
1191
1192 #ifndef _LIBCPP_CXX03_LANG
1193 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
1194 return __tree_.__insert_unique(std::move(__v));
1195 }
1196
1197 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1198 return __tree_.__insert_unique(__p.__i_, std::move(__v));
1199 }
1200
1201 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1202 #endif
1203
1204 template <class _InputIterator>
1205 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1206 for (const_iterator __e = cend(); __f != __l; ++__f)
1207 insert(__e.__i_, *__f);
1208 }
1209
1210 #if _LIBCPP_STD_VER >= 23
1211 template <_ContainerCompatibleRange<value_type> _Range>
1212 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1213 const_iterator __end = cend();
1214 for (auto&& __element : __range) {
1215 insert(__end.__i_, std::forward<decltype(__element)>(__element));
1216 }
1217 }
1218 #endif
1219
1220 #if _LIBCPP_STD_VER >= 17
1221
1222 template <class... _Args>
1223 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1224 return __tree_.__emplace_unique_key_args(
1225 __k,
1226 std::piecewise_construct,
1227 std::forward_as_tuple(__k),
1228 std::forward_as_tuple(std::forward<_Args>(__args)...));
1229 }
1230
1231 template <class... _Args>
1232 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1233 return __tree_.__emplace_unique_key_args(
1234 __k,
1235 std::piecewise_construct,
1236 std::forward_as_tuple(std::move(__k)),
1237 std::forward_as_tuple(std::forward<_Args>(__args)...));
1238 }
1239
1240 template <class... _Args>
1241 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
1242 return __tree_
1243 .__emplace_hint_unique_key_args(
1244 __h.__i_,
1245 __k,
1246 std::piecewise_construct,
1247 std::forward_as_tuple(__k),
1248 std::forward_as_tuple(std::forward<_Args>(__args)...))
1249 .first;
1250 }
1251
1252 template <class... _Args>
1253 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
1254 return __tree_
1255 .__emplace_hint_unique_key_args(
1256 __h.__i_,
1257 __k,
1258 std::piecewise_construct,
1259 std::forward_as_tuple(std::move(__k)),
1260 std::forward_as_tuple(std::forward<_Args>(__args)...))
1261 .first;
1262 }
1263
1264 template <class _Vp>
1265 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1266 iterator __p = lower_bound(__k);
1267 if (__p != end() && !key_comp()(__k, __p->first)) {
1268 __p->second = std::forward<_Vp>(__v);
1269 return std::make_pair(__p, false);
1270 }
1271 return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true);
1272 }
1273
1274 template <class _Vp>
1275 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1276 iterator __p = lower_bound(__k);
1277 if (__p != end() && !key_comp()(__k, __p->first)) {
1278 __p->second = std::forward<_Vp>(__v);
1279 return std::make_pair(__p, false);
1280 }
1281 return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true);
1282 }
1283
1284 template <class _Vp>
1285 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
1286 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
1287
1288 if (!__inserted)
1289 __r->__get_value().second = std::forward<_Vp>(__v);
1290
1291 return __r;
1292 }
1293
1294 template <class _Vp>
1295 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
1296 auto [__r, __inserted] =
1297 __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
1298
1299 if (!__inserted)
1300 __r->__get_value().second = std::forward<_Vp>(__v);
1301
1302 return __r;
1303 }
1304
1305 #endif // _LIBCPP_STD_VER >= 17
1306
1307 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1308 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1309 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
1310 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1311 return __tree_.erase(__f.__i_, __l.__i_);
1312 }
1313 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1314
1315 #if _LIBCPP_STD_VER >= 17
1316 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1317 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1318 "node_type with incompatible allocator passed to map::insert()");
1319 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1320 }
1321 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1322 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1323 "node_type with incompatible allocator passed to map::insert()");
1324 return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1325 }
1326 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1327 return __tree_.template __node_handle_extract<node_type>(__key);
1328 }
1329 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1330 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1331 }
1332 template <class _Compare2>
1333 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1334 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1335 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1336 __tree_.__node_handle_merge_unique(__source.__tree_);
1337 }
1338 template <class _Compare2>
1339 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1340 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1341 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1342 __tree_.__node_handle_merge_unique(__source.__tree_);
1343 }
1344 template <class _Compare2>
1345 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1346 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1347 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1348 __tree_.__node_handle_merge_unique(__source.__tree_);
1349 }
1350 template <class _Compare2>
1351 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1352 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1353 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1354 __tree_.__node_handle_merge_unique(__source.__tree_);
1355 }
1356 #endif
1357
1358 _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); }
1359
1360 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1361 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1362 #if _LIBCPP_STD_VER >= 14
1363 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1364 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1365 return __tree_.find(__k);
1366 }
1367 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1368 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1369 return __tree_.find(__k);
1370 }
1371 #endif
1372
1373 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
1374 #if _LIBCPP_STD_VER >= 14
1375 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1376 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1377 return __tree_.__count_multi(__k);
1378 }
1379 #endif
1380
1381 #if _LIBCPP_STD_VER >= 20
1382 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1383 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1384 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1385 return find(__k) != end();
1386 }
1387 #endif // _LIBCPP_STD_VER >= 20
1388
1389 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1390 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1391 #if _LIBCPP_STD_VER >= 14
1392 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1393 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1394 return __tree_.lower_bound(__k);
1395 }
1396
1397 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1398 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1399 return __tree_.lower_bound(__k);
1400 }
1401 #endif
1402
1403 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1404 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1405 #if _LIBCPP_STD_VER >= 14
1406 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1407 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1408 return __tree_.upper_bound(__k);
1409 }
1410 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1411 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1412 return __tree_.upper_bound(__k);
1413 }
1414 #endif
1415
1416 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1417 return __tree_.__equal_range_unique(__k);
1418 }
1419 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1420 return __tree_.__equal_range_unique(__k);
1421 }
1422 #if _LIBCPP_STD_VER >= 14
1423 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1424 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1425 return __tree_.__equal_range_multi(__k);
1426 }
1427 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1428 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1429 return __tree_.__equal_range_multi(__k);
1430 }
1431 #endif
1432
1433 private:
1434 typedef typename __base::__node __node;
1435 typedef typename __base::__node_allocator __node_allocator;
1436 typedef typename __base::__node_pointer __node_pointer;
1437 typedef typename __base::__node_base_pointer __node_base_pointer;
1438 typedef typename __base::__parent_pointer __parent_pointer;
1439
1440 typedef __map_node_destructor<__node_allocator> _Dp;
1441 typedef unique_ptr<__node, _Dp> __node_holder;
1442
1443 #ifdef _LIBCPP_CXX03_LANG
1444 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1445 #endif
1446 };
1447
1448 #if _LIBCPP_STD_VER >= 17
1449 template <class _InputIterator,
1450 class _Compare = less<__iter_key_type<_InputIterator>>,
1451 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1452 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1453 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1454 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1455 map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1456 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1457
1458 # if _LIBCPP_STD_VER >= 23
1459 template <ranges::input_range _Range,
1460 class _Compare = less<__range_key_type<_Range>>,
1461 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1462 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1463 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1464 map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1465 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1466 # endif
1467
1468 template <class _Key,
1469 class _Tp,
1470 class _Compare = less<remove_const_t<_Key>>,
1471 class _Allocator = allocator<pair<const _Key, _Tp>>,
1472 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1473 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1474 map(initializer_list<pair<_Key, _Tp>>,
1475 _Compare = _Compare(),
1476 _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1477
1478 template <class _InputIterator,
1479 class _Allocator,
1480 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1481 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1482 map(_InputIterator, _InputIterator, _Allocator)
1483 -> map<__iter_key_type<_InputIterator>,
1484 __iter_mapped_type<_InputIterator>,
1485 less<__iter_key_type<_InputIterator>>,
1486 _Allocator>;
1487
1488 # if _LIBCPP_STD_VER >= 23
1489 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1490 map(from_range_t, _Range&&, _Allocator)
1491 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1492 # endif
1493
1494 template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1495 map(initializer_list<pair<_Key, _Tp>>,
1496 _Allocator) -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1497 #endif
1498
1499 #ifndef _LIBCPP_CXX03_LANG
1500 template <class _Key, class _Tp, class _Compare, class _Allocator>
1501 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1502 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1503 if (__a != __m.get_allocator()) {
1504 const_iterator __e = cend();
1505 while (!__m.empty())
1506 __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1507 }
1508 }
1509
1510 template <class _Key, class _Tp, class _Compare, class _Allocator>
1511 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1512 return __tree_
1513 .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1514 .first->__get_value()
1515 .second;
1516 }
1517
1518 template <class _Key, class _Tp, class _Compare, class _Allocator>
1519 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
1520 // TODO investigate this clang-tidy warning.
1521 // NOLINTBEGIN(bugprone-use-after-move)
1522 return __tree_
1523 .__emplace_unique_key_args(
1524 __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1525 .first->__get_value()
1526 .second;
1527 // NOLINTEND(bugprone-use-after-move)
1528 }
1529
1530 #else // _LIBCPP_CXX03_LANG
1531
1532 template <class _Key, class _Tp, class _Compare, class _Allocator>
1533 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1534 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1535 __node_allocator& __na = __tree_.__node_alloc();
1536 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1537 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k);
1538 __h.get_deleter().__first_constructed = true;
1539 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second));
1540 __h.get_deleter().__second_constructed = true;
1541 return __h;
1542 }
1543
1544 template <class _Key, class _Tp, class _Compare, class _Allocator>
1545 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1546 __parent_pointer __parent;
1547 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1548 __node_pointer __r = static_cast<__node_pointer>(__child);
1549 if (__child == nullptr) {
1550 __node_holder __h = __construct_node_with_key(__k);
1551 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1552 __r = __h.release();
1553 }
1554 return __r->__value_.__get_value().second;
1555 }
1556
1557 #endif // _LIBCPP_CXX03_LANG
1558
1559 template <class _Key, class _Tp, class _Compare, class _Allocator>
1560 _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1561 __parent_pointer __parent;
1562 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1563 if (__child == nullptr)
1564 __throw_out_of_range("map::at: key not found");
1565 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1566 }
1567
1568 template <class _Key, class _Tp, class _Compare, class _Allocator>
1569 const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1570 __parent_pointer __parent;
1571 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1572 if (__child == nullptr)
1573 __throw_out_of_range("map::at: key not found");
1574 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1575 }
1576
1577 template <class _Key, class _Tp, class _Compare, class _Allocator>
1578 inline _LIBCPP_HIDE_FROM_ABI bool
1579 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1580 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1581 }
1582
1583 #if _LIBCPP_STD_VER <= 17
1584
1585 template <class _Key, class _Tp, class _Compare, class _Allocator>
1586 inline _LIBCPP_HIDE_FROM_ABI bool
1587 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1588 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1589 }
1590
1591 template <class _Key, class _Tp, class _Compare, class _Allocator>
1592 inline _LIBCPP_HIDE_FROM_ABI bool
1593 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1594 return !(__x == __y);
1595 }
1596
1597 template <class _Key, class _Tp, class _Compare, class _Allocator>
1598 inline _LIBCPP_HIDE_FROM_ABI bool
1599 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1600 return __y < __x;
1601 }
1602
1603 template <class _Key, class _Tp, class _Compare, class _Allocator>
1604 inline _LIBCPP_HIDE_FROM_ABI bool
1605 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1606 return !(__x < __y);
1607 }
1608
1609 template <class _Key, class _Tp, class _Compare, class _Allocator>
1610 inline _LIBCPP_HIDE_FROM_ABI bool
1611 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1612 return !(__y < __x);
1613 }
1614
1615 #else // #if _LIBCPP_STD_VER <= 17
1616
1617 template <class _Key, class _Tp, class _Compare, class _Allocator>
1618 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1619 operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1620 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1621 }
1622
1623 #endif // #if _LIBCPP_STD_VER <= 17
1624
1625 template <class _Key, class _Tp, class _Compare, class _Allocator>
1626 inline _LIBCPP_HIDE_FROM_ABI void
1627 swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y)
1628 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1629 __x.swap(__y);
1630 }
1631
1632 #if _LIBCPP_STD_VER >= 20
1633 template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1634 inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1635 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1636 return std::__libcpp_erase_if_container(__c, __pred);
1637 }
1638 #endif
1639
1640 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1641 class _LIBCPP_TEMPLATE_VIS multimap {
1642 public:
1643 // types:
1644 typedef _Key key_type;
1645 typedef _Tp mapped_type;
1646 typedef pair<const key_type, mapped_type> value_type;
1647 typedef __type_identity_t<_Compare> key_compare;
1648 typedef __type_identity_t<_Allocator> allocator_type;
1649 typedef value_type& reference;
1650 typedef const value_type& const_reference;
1651
1652 static_assert(__check_valid_allocator<allocator_type>::value, "");
1653 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1654 "Allocator::value_type must be same type as value_type");
1655
1656 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
1657 friend class multimap;
1658
1659 protected:
1660 key_compare comp;
1661
1662 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1663
1664 public:
1665 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1666 return comp(__x.first, __y.first);
1667 }
1668 };
1669
1670 private:
1671 typedef std::__value_type<key_type, mapped_type> __value_type;
1672 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1673 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1674 typedef __tree<__value_type, __vc, __allocator_type> __base;
1675 typedef typename __base::__node_traits __node_traits;
1676 typedef allocator_traits<allocator_type> __alloc_traits;
1677
1678 __base __tree_;
1679
1680 public:
1681 typedef typename __alloc_traits::pointer pointer;
1682 typedef typename __alloc_traits::const_pointer const_pointer;
1683 typedef typename __alloc_traits::size_type size_type;
1684 typedef typename __alloc_traits::difference_type difference_type;
1685 typedef __map_iterator<typename __base::iterator> iterator;
1686 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1687 typedef std::reverse_iterator<iterator> reverse_iterator;
1688 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1689
1690 #if _LIBCPP_STD_VER >= 17
1691 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1692 #endif
1693
1694 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1695 friend class _LIBCPP_TEMPLATE_VIS map;
1696 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1697 friend class _LIBCPP_TEMPLATE_VIS multimap;
1698
1699 _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(
1700 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1701 is_nothrow_copy_constructible<key_compare>::value)
1702 : __tree_(__vc(key_compare())) {}
1703
1704 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(
1705 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1706 : __tree_(__vc(__comp)) {}
1707
1708 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1709 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1710
1711 template <class _InputIterator>
1712 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1713 : __tree_(__vc(__comp)) {
1714 insert(__f, __l);
1715 }
1716
1717 template <class _InputIterator>
1718 _LIBCPP_HIDE_FROM_ABI
1719 multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1720 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1721 insert(__f, __l);
1722 }
1723
1724 #if _LIBCPP_STD_VER >= 23
1725 template <_ContainerCompatibleRange<value_type> _Range>
1726 _LIBCPP_HIDE_FROM_ABI
1727 multimap(from_range_t,
1728 _Range&& __range,
1729 const key_compare& __comp = key_compare(),
1730 const allocator_type& __a = allocator_type())
1731 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1732 insert_range(std::forward<_Range>(__range));
1733 }
1734 #endif
1735
1736 #if _LIBCPP_STD_VER >= 14
1737 template <class _InputIterator>
1738 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1739 : multimap(__f, __l, key_compare(), __a) {}
1740 #endif
1741
1742 #if _LIBCPP_STD_VER >= 23
1743 template <_ContainerCompatibleRange<value_type> _Range>
1744 _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)
1745 : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1746 #endif
1747
1748 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1749 : __tree_(__m.__tree_.value_comp(),
1750 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1751 insert(__m.begin(), __m.end());
1752 }
1753
1754 _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1755 #ifndef _LIBCPP_CXX03_LANG
1756 __tree_ = __m.__tree_;
1757 #else
1758 if (this != std::addressof(__m)) {
1759 __tree_.clear();
1760 __tree_.value_comp() = __m.__tree_.value_comp();
1761 __tree_.__copy_assign_alloc(__m.__tree_);
1762 insert(__m.begin(), __m.end());
1763 }
1764 #endif
1765 return *this;
1766 }
1767
1768 #ifndef _LIBCPP_CXX03_LANG
1769
1770 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1771 : __tree_(std::move(__m.__tree_)) {}
1772
1773 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a);
1774
1775 _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1776 __tree_ = std::move(__m.__tree_);
1777 return *this;
1778 }
1779
1780 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1781 : __tree_(__vc(__comp)) {
1782 insert(__il.begin(), __il.end());
1783 }
1784
1785 _LIBCPP_HIDE_FROM_ABI
1786 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1787 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1788 insert(__il.begin(), __il.end());
1789 }
1790
1791 # if _LIBCPP_STD_VER >= 14
1792 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)
1793 : multimap(__il, key_compare(), __a) {}
1794 # endif
1795
1796 _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {
1797 __tree_.__assign_multi(__il.begin(), __il.end());
1798 return *this;
1799 }
1800
1801 #endif // _LIBCPP_CXX03_LANG
1802
1803 _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1804
1805 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1806 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1807 insert(__m.begin(), __m.end());
1808 }
1809
1810 _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1811
1812 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1813 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1814 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1815 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1816
1817 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1818 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1819 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1820 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1821
1822 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1823 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1824 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1825 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1826
1827 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1828 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1829 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1830
1831 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1832 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1833 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1834
1835 #ifndef _LIBCPP_CXX03_LANG
1836
1837 template <class... _Args>
1838 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1839 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1840 }
1841
1842 template <class... _Args>
1843 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1844 return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1845 }
1846
1847 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1848 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {
1849 return __tree_.__insert_multi(std::forward<_Pp>(__p));
1850 }
1851
1852 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1853 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1854 return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));
1855 }
1856
1857 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1858
1859 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1860 return __tree_.__insert_multi(__p.__i_, std::move(__v));
1861 }
1862
1863 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1864
1865 #endif // _LIBCPP_CXX03_LANG
1866
1867 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1868
1869 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1870 return __tree_.__insert_multi(__p.__i_, __v);
1871 }
1872
1873 template <class _InputIterator>
1874 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1875 for (const_iterator __e = cend(); __f != __l; ++__f)
1876 __tree_.__insert_multi(__e.__i_, *__f);
1877 }
1878
1879 #if _LIBCPP_STD_VER >= 23
1880 template <_ContainerCompatibleRange<value_type> _Range>
1881 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1882 const_iterator __end = cend();
1883 for (auto&& __element : __range) {
1884 __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element));
1885 }
1886 }
1887 #endif
1888
1889 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1890 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1891 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1892 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1893 return __tree_.erase(__f.__i_, __l.__i_);
1894 }
1895
1896 #if _LIBCPP_STD_VER >= 17
1897 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1898 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1899 "node_type with incompatible allocator passed to multimap::insert()");
1900 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1901 }
1902 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1903 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1904 "node_type with incompatible allocator passed to multimap::insert()");
1905 return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
1906 }
1907 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1908 return __tree_.template __node_handle_extract<node_type>(__key);
1909 }
1910 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1911 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1912 }
1913 template <class _Compare2>
1914 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1915 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1916 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1917 return __tree_.__node_handle_merge_multi(__source.__tree_);
1918 }
1919 template <class _Compare2>
1920 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1921 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1922 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1923 return __tree_.__node_handle_merge_multi(__source.__tree_);
1924 }
1925 template <class _Compare2>
1926 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1927 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1928 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1929 return __tree_.__node_handle_merge_multi(__source.__tree_);
1930 }
1931 template <class _Compare2>
1932 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1933 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1934 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1935 return __tree_.__node_handle_merge_multi(__source.__tree_);
1936 }
1937 #endif
1938
1939 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1940
1941 _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1942 __tree_.swap(__m.__tree_);
1943 }
1944
1945 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1946 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1947 #if _LIBCPP_STD_VER >= 14
1948 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1949 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1950 return __tree_.find(__k);
1951 }
1952 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1953 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1954 return __tree_.find(__k);
1955 }
1956 #endif
1957
1958 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1959 #if _LIBCPP_STD_VER >= 14
1960 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1961 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1962 return __tree_.__count_multi(__k);
1963 }
1964 #endif
1965
1966 #if _LIBCPP_STD_VER >= 20
1967 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1968 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1969 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1970 return find(__k) != end();
1971 }
1972 #endif // _LIBCPP_STD_VER >= 20
1973
1974 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1975 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1976 #if _LIBCPP_STD_VER >= 14
1977 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1978 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1979 return __tree_.lower_bound(__k);
1980 }
1981
1982 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1983 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1984 return __tree_.lower_bound(__k);
1985 }
1986 #endif
1987
1988 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1989 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1990 #if _LIBCPP_STD_VER >= 14
1991 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1992 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1993 return __tree_.upper_bound(__k);
1994 }
1995 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1996 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1997 return __tree_.upper_bound(__k);
1998 }
1999 #endif
2000
2001 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2002 return __tree_.__equal_range_multi(__k);
2003 }
2004 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2005 return __tree_.__equal_range_multi(__k);
2006 }
2007 #if _LIBCPP_STD_VER >= 14
2008 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2009 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2010 return __tree_.__equal_range_multi(__k);
2011 }
2012 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2013 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2014 return __tree_.__equal_range_multi(__k);
2015 }
2016 #endif
2017
2018 private:
2019 typedef typename __base::__node __node;
2020 typedef typename __base::__node_allocator __node_allocator;
2021 typedef typename __base::__node_pointer __node_pointer;
2022
2023 typedef __map_node_destructor<__node_allocator> _Dp;
2024 typedef unique_ptr<__node, _Dp> __node_holder;
2025 };
2026
2027 #if _LIBCPP_STD_VER >= 17
2028 template <class _InputIterator,
2029 class _Compare = less<__iter_key_type<_InputIterator>>,
2030 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2031 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2032 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
2033 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2034 multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2035 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2036
2037 # if _LIBCPP_STD_VER >= 23
2038 template <ranges::input_range _Range,
2039 class _Compare = less<__range_key_type<_Range>>,
2040 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2041 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
2042 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2043 multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
2044 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
2045 # endif
2046
2047 template <class _Key,
2048 class _Tp,
2049 class _Compare = less<remove_const_t<_Key>>,
2050 class _Allocator = allocator<pair<const _Key, _Tp>>,
2051 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
2052 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2053 multimap(initializer_list<pair<_Key, _Tp>>,
2054 _Compare = _Compare(),
2055 _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2056
2057 template <class _InputIterator,
2058 class _Allocator,
2059 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2060 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2061 multimap(_InputIterator, _InputIterator, _Allocator)
2062 -> multimap<__iter_key_type<_InputIterator>,
2063 __iter_mapped_type<_InputIterator>,
2064 less<__iter_key_type<_InputIterator>>,
2065 _Allocator>;
2066
2067 # if _LIBCPP_STD_VER >= 23
2068 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2069 multimap(from_range_t, _Range&&, _Allocator)
2070 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
2071 # endif
2072
2073 template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2074 multimap(initializer_list<pair<_Key, _Tp>>,
2075 _Allocator) -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2076 #endif
2077
2078 #ifndef _LIBCPP_CXX03_LANG
2079 template <class _Key, class _Tp, class _Compare, class _Allocator>
2080 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2081 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
2082 if (__a != __m.get_allocator()) {
2083 const_iterator __e = cend();
2084 while (!__m.empty())
2085 __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2086 }
2087 }
2088 #endif
2089
2090 template <class _Key, class _Tp, class _Compare, class _Allocator>
2091 inline _LIBCPP_HIDE_FROM_ABI bool
2092 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2093 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2094 }
2095
2096 #if _LIBCPP_STD_VER <= 17
2097
2098 template <class _Key, class _Tp, class _Compare, class _Allocator>
2099 inline _LIBCPP_HIDE_FROM_ABI bool
2100 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2101 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2102 }
2103
2104 template <class _Key, class _Tp, class _Compare, class _Allocator>
2105 inline _LIBCPP_HIDE_FROM_ABI bool
2106 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2107 return !(__x == __y);
2108 }
2109
2110 template <class _Key, class _Tp, class _Compare, class _Allocator>
2111 inline _LIBCPP_HIDE_FROM_ABI bool
2112 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2113 return __y < __x;
2114 }
2115
2116 template <class _Key, class _Tp, class _Compare, class _Allocator>
2117 inline _LIBCPP_HIDE_FROM_ABI bool
2118 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2119 return !(__x < __y);
2120 }
2121
2122 template <class _Key, class _Tp, class _Compare, class _Allocator>
2123 inline _LIBCPP_HIDE_FROM_ABI bool
2124 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2125 return !(__y < __x);
2126 }
2127
2128 #else // #if _LIBCPP_STD_VER <= 17
2129
2130 template <class _Key, class _Tp, class _Compare, class _Allocator>
2131 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2132 operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2133 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2134 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
2135 }
2136
2137 #endif // #if _LIBCPP_STD_VER <= 17
2138
2139 template <class _Key, class _Tp, class _Compare, class _Allocator>
2140 inline _LIBCPP_HIDE_FROM_ABI void
2141 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2142 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2143 __x.swap(__y);
2144 }
2145
2146 #if _LIBCPP_STD_VER >= 20
2147 template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2148 inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2149 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
2150 return std::__libcpp_erase_if_container(__c, __pred);
2151 }
2152 #endif
2153
2154 _LIBCPP_END_NAMESPACE_STD
2155
2156 #if _LIBCPP_STD_VER >= 17
2157 _LIBCPP_BEGIN_NAMESPACE_STD
2158 namespace pmr {
2159 template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2160 using map _LIBCPP_AVAILABILITY_PMR =
2161 std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2162
2163 template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2164 using multimap _LIBCPP_AVAILABILITY_PMR =
2165 std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2166 } // namespace pmr
2167 _LIBCPP_END_NAMESPACE_STD
2168 #endif
2169
2170 _LIBCPP_POP_MACROS
2171
2172 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2173 # include <__cxx03/concepts>
2174 # include <__cxx03/cstdlib>
2175 # include <__cxx03/functional>
2176 # include <__cxx03/iterator>
2177 # include <__cxx03/type_traits>
2178 # include <__cxx03/utility>
2179 #endif
2180
2181 #endif // _LIBCPP___CXX03_MAP
