1 | // Map implementation -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2001-2021 Free Software Foundation, Inc. |

4 | // |

5 | // This file is part of the GNU ISO C++ Library. This library is free |

6 | // software; you can redistribute it and/or modify it under the |

7 | // terms of the GNU General Public License as published by the |

8 | // Free Software Foundation; either version 3, or (at your option) |

9 | // any later version. |

10 | |

11 | // This library is distributed in the hope that it will be useful, |

12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |

13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

14 | // GNU General Public License for more details. |

15 | |

16 | // Under Section 7 of GPL version 3, you are granted additional |

17 | // permissions described in the GCC Runtime Library Exception, version |

18 | // 3.1, as published by the Free Software Foundation. |

19 | |

20 | // You should have received a copy of the GNU General Public License and |

21 | // a copy of the GCC Runtime Library Exception along with this program; |

22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |

23 | // <http://www.gnu.org/licenses/>. |

24 | |

25 | /* |

26 | * |

27 | * Copyright (c) 1994 |

28 | * Hewlett-Packard Company |

29 | * |

30 | * Permission to use, copy, modify, distribute and sell this software |

31 | * and its documentation for any purpose is hereby granted without fee, |

32 | * provided that the above copyright notice appear in all copies and |

33 | * that both that copyright notice and this permission notice appear |

34 | * in supporting documentation. Hewlett-Packard Company makes no |

35 | * representations about the suitability of this software for any |

36 | * purpose. It is provided "as is" without express or implied warranty. |

37 | * |

38 | * |

39 | * Copyright (c) 1996,1997 |

40 | * Silicon Graphics Computer Systems, Inc. |

41 | * |

42 | * Permission to use, copy, modify, distribute and sell this software |

43 | * and its documentation for any purpose is hereby granted without fee, |

44 | * provided that the above copyright notice appear in all copies and |

45 | * that both that copyright notice and this permission notice appear |

46 | * in supporting documentation. Silicon Graphics makes no |

47 | * representations about the suitability of this software for any |

48 | * purpose. It is provided "as is" without express or implied warranty. |

49 | */ |

50 | |

51 | /** @file bits/stl_map.h |

52 | * This is an internal header file, included by other library headers. |

53 | * Do not attempt to use it directly. @headername{map} |

54 | */ |

55 | |

56 | #ifndef _STL_MAP_H |

57 | #define _STL_MAP_H 1 |

58 | |

59 | #include <bits/functexcept.h> |

60 | #include <bits/concept_check.h> |

61 | #if __cplusplus >= 201103L |

62 | #include <initializer_list> |

63 | #include <tuple> |

64 | #endif |

65 | |

66 | namespace std _GLIBCXX_VISIBILITY(default) |

67 | { |

68 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

69 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

70 | |

71 | template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

72 | class multimap; |

73 | |

74 | /** |

75 | * @brief A standard container made up of (key,value) pairs, which can be |

76 | * retrieved based on a key, in logarithmic time. |

77 | * |

78 | * @ingroup associative_containers |

79 | * |

80 | * @tparam _Key Type of key objects. |

81 | * @tparam _Tp Type of mapped objects. |

82 | * @tparam _Compare Comparison function object type, defaults to less<_Key>. |

83 | * @tparam _Alloc Allocator type, defaults to |

84 | * allocator<pair<const _Key, _Tp>. |

85 | * |

86 | * Meets the requirements of a <a href="tables.html#65">container</a>, a |

87 | * <a href="tables.html#66">reversible container</a>, and an |

88 | * <a href="tables.html#69">associative container</a> (using unique keys). |

89 | * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the |

90 | * value_type is std::pair<const Key,T>. |

91 | * |

92 | * Maps support bidirectional iterators. |

93 | * |

94 | * The private tree data is declared exactly the same way for map and |

95 | * multimap; the distinction is made entirely in how the tree functions are |

96 | * called (*_unique versus *_equal, same as the standard). |

97 | */ |

98 | template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>, |

99 | typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > |

100 | class map |

101 | { |

102 | public: |

103 | typedef _Key key_type; |

104 | typedef _Tp mapped_type; |

105 | typedef std::pair<const _Key, _Tp> value_type; |

106 | typedef _Compare key_compare; |

107 | typedef _Alloc allocator_type; |

108 | |

109 | private: |

110 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

111 | // concept requirements |

112 | typedef typename _Alloc::value_type _Alloc_value_type; |

113 | # if __cplusplus < 201103L |

114 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

115 | # endif |

116 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, |

117 | _BinaryFunctionConcept) |

118 | __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) |

119 | #endif |

120 | |

121 | #if __cplusplus >= 201103L |

122 | #if __cplusplus > 201703L || defined __STRICT_ANSI__ |

123 | static_assert(is_same<typename _Alloc::value_type, value_type>::value, |

124 | "std::map must have the same value_type as its allocator"); |

125 | #endif |

126 | #endif |

127 | |

128 | public: |

129 | class value_compare |

130 | : public std::binary_function<value_type, value_type, bool> |

131 | { |

132 | friend class map<_Key, _Tp, _Compare, _Alloc>; |

133 | protected: |

134 | _Compare comp; |

135 | |

136 | value_compare(_Compare __c) |

137 | : comp(__c) { } |

138 | |

139 | public: |

140 | bool operator()(const value_type& __x, const value_type& __y) const |

141 | { return comp(__x.first, __y.first); } |

142 | }; |

143 | |

144 | private: |

145 | /// This turns a red-black tree into a [multi]map. |

146 | typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template |

147 | rebind<value_type>::other _Pair_alloc_type; |

148 | |

149 | typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, |

150 | key_compare, _Pair_alloc_type> _Rep_type; |

151 | |

152 | /// The actual tree structure. |

153 | _Rep_type _M_t; |

154 | |

155 | typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits; |

156 | |

157 | public: |

158 | // many of these are specified differently in ISO, but the following are |

159 | // "functionally equivalent" |

160 | typedef typename _Alloc_traits::pointer pointer; |

161 | typedef typename _Alloc_traits::const_pointer const_pointer; |

162 | typedef typename _Alloc_traits::reference reference; |

163 | typedef typename _Alloc_traits::const_reference const_reference; |

164 | typedef typename _Rep_type::iterator iterator; |

165 | typedef typename _Rep_type::const_iterator const_iterator; |

166 | typedef typename _Rep_type::size_type size_type; |

167 | typedef typename _Rep_type::difference_type difference_type; |

168 | typedef typename _Rep_type::reverse_iterator reverse_iterator; |

169 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

170 | |

171 | #if __cplusplus > 201402L |

172 | using node_type = typename _Rep_type::node_type; |

173 | using insert_return_type = typename _Rep_type::insert_return_type; |

174 | #endif |

175 | |

176 | // [23.3.1.1] construct/copy/destroy |

177 | // (get_allocator() is also listed in this section) |

178 | |

179 | /** |

180 | * @brief Default constructor creates no elements. |

181 | */ |

182 | #if __cplusplus < 201103L |

183 | map() : _M_t() { } |

184 | #else |

185 | map() = default; |

186 | #endif |

187 | |

188 | /** |

189 | * @brief Creates a %map with no elements. |

190 | * @param __comp A comparison object. |

191 | * @param __a An allocator object. |

192 | */ |

193 | explicit |

194 | map(const _Compare& __comp, |

195 | const allocator_type& __a = allocator_type()) |

196 | : _M_t(__comp, _Pair_alloc_type(__a)) { } |

197 | |

198 | /** |

199 | * @brief %Map copy constructor. |

200 | * |

201 | * Whether the allocator is copied depends on the allocator traits. |

202 | */ |

203 | #if __cplusplus < 201103L |

204 | map(const map& __x) |

205 | : _M_t(__x._M_t) { } |

206 | #else |

207 | map(const map&) = default; |

208 | |

209 | /** |

210 | * @brief %Map move constructor. |

211 | * |

212 | * The newly-created %map contains the exact contents of the moved |

213 | * instance. The moved instance is a valid, but unspecified, %map. |

214 | */ |

215 | map(map&&) = default; |

216 | |

217 | /** |

218 | * @brief Builds a %map from an initializer_list. |

219 | * @param __l An initializer_list. |

220 | * @param __comp A comparison object. |

221 | * @param __a An allocator object. |

222 | * |

223 | * Create a %map consisting of copies of the elements in the |

224 | * initializer_list @a __l. |

225 | * This is linear in N if the range is already sorted, and NlogN |

226 | * otherwise (where N is @a __l.size()). |

227 | */ |

228 | map(initializer_list<value_type> __l, |

229 | const _Compare& __comp = _Compare(), |

230 | const allocator_type& __a = allocator_type()) |

231 | : _M_t(__comp, _Pair_alloc_type(__a)) |

232 | { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } |

233 | |

234 | /// Allocator-extended default constructor. |

235 | explicit |

236 | map(const allocator_type& __a) |

237 | : _M_t(_Pair_alloc_type(__a)) { } |

238 | |

239 | /// Allocator-extended copy constructor. |

240 | map(const map& __m, const allocator_type& __a) |

241 | : _M_t(__m._M_t, _Pair_alloc_type(__a)) { } |

242 | |

243 | /// Allocator-extended move constructor. |

244 | map(map&& __m, const allocator_type& __a) |

245 | noexcept(is_nothrow_copy_constructible<_Compare>::value |

246 | && _Alloc_traits::_S_always_equal()) |

247 | : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { } |

248 | |

249 | /// Allocator-extended initialier-list constructor. |

250 | map(initializer_list<value_type> __l, const allocator_type& __a) |

251 | : _M_t(_Pair_alloc_type(__a)) |

252 | { _M_t._M_insert_range_unique(__l.begin(), __l.end()); } |

253 | |

254 | /// Allocator-extended range constructor. |

255 | template<typename _InputIterator> |

256 | map(_InputIterator __first, _InputIterator __last, |

257 | const allocator_type& __a) |

258 | : _M_t(_Pair_alloc_type(__a)) |

259 | { _M_t._M_insert_range_unique(__first, __last); } |

260 | #endif |

261 | |

262 | /** |

263 | * @brief Builds a %map from a range. |

264 | * @param __first An input iterator. |

265 | * @param __last An input iterator. |

266 | * |

267 | * Create a %map consisting of copies of the elements from |

268 | * [__first,__last). This is linear in N if the range is |

269 | * already sorted, and NlogN otherwise (where N is |

270 | * distance(__first,__last)). |

271 | */ |

272 | template<typename _InputIterator> |

273 | map(_InputIterator __first, _InputIterator __last) |

274 | : _M_t() |

275 | { _M_t._M_insert_range_unique(__first, __last); } |

276 | |

277 | /** |

278 | * @brief Builds a %map from a range. |

279 | * @param __first An input iterator. |

280 | * @param __last An input iterator. |

281 | * @param __comp A comparison functor. |

282 | * @param __a An allocator object. |

283 | * |

284 | * Create a %map consisting of copies of the elements from |

285 | * [__first,__last). This is linear in N if the range is |

286 | * already sorted, and NlogN otherwise (where N is |

287 | * distance(__first,__last)). |

288 | */ |

289 | template<typename _InputIterator> |

290 | map(_InputIterator __first, _InputIterator __last, |

291 | const _Compare& __comp, |

292 | const allocator_type& __a = allocator_type()) |

293 | : _M_t(__comp, _Pair_alloc_type(__a)) |

294 | { _M_t._M_insert_range_unique(__first, __last); } |

295 | |

296 | #if __cplusplus >= 201103L |

297 | /** |

298 | * The dtor only erases the elements, and note that if the elements |

299 | * themselves are pointers, the pointed-to memory is not touched in any |

300 | * way. Managing the pointer is the user's responsibility. |

301 | */ |

302 | ~map() = default; |

303 | #endif |

304 | |

305 | /** |

306 | * @brief %Map assignment operator. |

307 | * |

308 | * Whether the allocator is copied depends on the allocator traits. |

309 | */ |

310 | #if __cplusplus < 201103L |

311 | map& |

312 | operator=(const map& __x) |

313 | { |

314 | _M_t = __x._M_t; |

315 | return *this; |

316 | } |

317 | #else |

318 | map& |

319 | operator=(const map&) = default; |

320 | |

321 | /// Move assignment operator. |

322 | map& |

323 | operator=(map&&) = default; |

324 | |

325 | /** |

326 | * @brief %Map list assignment operator. |

327 | * @param __l An initializer_list. |

328 | * |

329 | * This function fills a %map with copies of the elements in the |

330 | * initializer list @a __l. |

331 | * |

332 | * Note that the assignment completely changes the %map and |

333 | * that the resulting %map's size is the same as the number |

334 | * of elements assigned. |

335 | */ |

336 | map& |

337 | operator=(initializer_list<value_type> __l) |

338 | { |

339 | _M_t._M_assign_unique(__l.begin(), __l.end()); |

340 | return *this; |

341 | } |

342 | #endif |

343 | |

344 | /// Get a copy of the memory allocation object. |

345 | allocator_type |

346 | get_allocator() const _GLIBCXX_NOEXCEPT |

347 | { return allocator_type(_M_t.get_allocator()); } |

348 | |

349 | // iterators |

350 | /** |

351 | * Returns a read/write iterator that points to the first pair in the |

352 | * %map. |

353 | * Iteration is done in ascending order according to the keys. |

354 | */ |

355 | iterator |

356 | begin() _GLIBCXX_NOEXCEPT |

357 | { return _M_t.begin(); } |

358 | |

359 | /** |

360 | * Returns a read-only (constant) iterator that points to the first pair |

361 | * in the %map. Iteration is done in ascending order according to the |

362 | * keys. |

363 | */ |

364 | const_iterator |

365 | begin() const _GLIBCXX_NOEXCEPT |

366 | { return _M_t.begin(); } |

367 | |

368 | /** |

369 | * Returns a read/write iterator that points one past the last |

370 | * pair in the %map. Iteration is done in ascending order |

371 | * according to the keys. |

372 | */ |

373 | iterator |

374 | end() _GLIBCXX_NOEXCEPT |

375 | { return _M_t.end(); } |

376 | |

377 | /** |

378 | * Returns a read-only (constant) iterator that points one past the last |

379 | * pair in the %map. Iteration is done in ascending order according to |

380 | * the keys. |

381 | */ |

382 | const_iterator |

383 | end() const _GLIBCXX_NOEXCEPT |

384 | { return _M_t.end(); } |

385 | |

386 | /** |

387 | * Returns a read/write reverse iterator that points to the last pair in |

388 | * the %map. Iteration is done in descending order according to the |

389 | * keys. |

390 | */ |

391 | reverse_iterator |

392 | rbegin() _GLIBCXX_NOEXCEPT |

393 | { return _M_t.rbegin(); } |

394 | |

395 | /** |

396 | * Returns a read-only (constant) reverse iterator that points to the |

397 | * last pair in the %map. Iteration is done in descending order |

398 | * according to the keys. |

399 | */ |

400 | const_reverse_iterator |

401 | rbegin() const _GLIBCXX_NOEXCEPT |

402 | { return _M_t.rbegin(); } |

403 | |

404 | /** |

405 | * Returns a read/write reverse iterator that points to one before the |

406 | * first pair in the %map. Iteration is done in descending order |

407 | * according to the keys. |

408 | */ |

409 | reverse_iterator |

410 | rend() _GLIBCXX_NOEXCEPT |

411 | { return _M_t.rend(); } |

412 | |

413 | /** |

414 | * Returns a read-only (constant) reverse iterator that points to one |

415 | * before the first pair in the %map. Iteration is done in descending |

416 | * order according to the keys. |

417 | */ |

418 | const_reverse_iterator |

419 | rend() const _GLIBCXX_NOEXCEPT |

420 | { return _M_t.rend(); } |

421 | |

422 | #if __cplusplus >= 201103L |

423 | /** |

424 | * Returns a read-only (constant) iterator that points to the first pair |

425 | * in the %map. Iteration is done in ascending order according to the |

426 | * keys. |

427 | */ |

428 | const_iterator |

429 | cbegin() const noexcept |

430 | { return _M_t.begin(); } |

431 | |

432 | /** |

433 | * Returns a read-only (constant) iterator that points one past the last |

434 | * pair in the %map. Iteration is done in ascending order according to |

435 | * the keys. |

436 | */ |

437 | const_iterator |

438 | cend() const noexcept |

439 | { return _M_t.end(); } |

440 | |

441 | /** |

442 | * Returns a read-only (constant) reverse iterator that points to the |

443 | * last pair in the %map. Iteration is done in descending order |

444 | * according to the keys. |

445 | */ |

446 | const_reverse_iterator |

447 | crbegin() const noexcept |

448 | { return _M_t.rbegin(); } |

449 | |

450 | /** |

451 | * Returns a read-only (constant) reverse iterator that points to one |

452 | * before the first pair in the %map. Iteration is done in descending |

453 | * order according to the keys. |

454 | */ |

455 | const_reverse_iterator |

456 | crend() const noexcept |

457 | { return _M_t.rend(); } |

458 | #endif |

459 | |

460 | // capacity |

461 | /** Returns true if the %map is empty. (Thus begin() would equal |

462 | * end().) |

463 | */ |

464 | _GLIBCXX_NODISCARD bool |

465 | empty() const _GLIBCXX_NOEXCEPT |

466 | { return _M_t.empty(); } |

467 | |

468 | /** Returns the size of the %map. */ |

469 | size_type |

470 | size() const _GLIBCXX_NOEXCEPT |

471 | { return _M_t.size(); } |

472 | |

473 | /** Returns the maximum size of the %map. */ |

474 | size_type |

475 | max_size() const _GLIBCXX_NOEXCEPT |

476 | { return _M_t.max_size(); } |

477 | |

478 | // [23.3.1.2] element access |

479 | /** |

480 | * @brief Subscript ( @c [] ) access to %map data. |

481 | * @param __k The key for which data should be retrieved. |

482 | * @return A reference to the data of the (key,data) %pair. |

483 | * |

484 | * Allows for easy lookup with the subscript ( @c [] ) |

485 | * operator. Returns data associated with the key specified in |

486 | * subscript. If the key does not exist, a pair with that key |

487 | * is created using default values, which is then returned. |

488 | * |

489 | * Lookup requires logarithmic time. |

490 | */ |

491 | mapped_type& |

492 | operator[](const key_type& __k) |

493 | { |

494 | // concept requirements |

495 | __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) |

496 | |

497 | iterator __i = lower_bound(__k); |

498 | // __i->first is greater than or equivalent to __k. |

499 | if (__i == end() || key_comp()(__k, (*__i).first)) |

500 | #if __cplusplus >= 201103L |

501 | __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, |

502 | std::tuple<const key_type&>(__k), |

503 | std::tuple<>()); |

504 | #else |

505 | __i = insert(__i, value_type(__k, mapped_type())); |

506 | #endif |

507 | return (*__i).second; |

508 | } |

509 | |

510 | #if __cplusplus >= 201103L |

511 | mapped_type& |

512 | operator[](key_type&& __k) |

513 | { |

514 | // concept requirements |

515 | __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) |

516 | |

517 | iterator __i = lower_bound(__k); |

518 | // __i->first is greater than or equivalent to __k. |

519 | if (__i == end() || key_comp()(__k, (*__i).first)) |

520 | __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct, |

521 | std::forward_as_tuple(std::move(__k)), |

522 | std::tuple<>()); |

523 | return (*__i).second; |

524 | } |

525 | #endif |

526 | |

527 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

528 | // DR 464. Suggestion for new member functions in standard containers. |

529 | /** |

530 | * @brief Access to %map data. |

531 | * @param __k The key for which data should be retrieved. |

532 | * @return A reference to the data whose key is equivalent to @a __k, if |

533 | * such a data is present in the %map. |

534 | * @throw std::out_of_range If no such data is present. |

535 | */ |

536 | mapped_type& |

537 | at(const key_type& __k) |

538 | { |

539 | iterator __i = lower_bound(__k); |

540 | if (__i == end() || key_comp()(__k, (*__i).first)) |

541 | __throw_out_of_range(__N("map::at")); |

542 | return (*__i).second; |

543 | } |

544 | |

545 | const mapped_type& |

546 | at(const key_type& __k) const |

547 | { |

548 | const_iterator __i = lower_bound(__k); |

549 | if (__i == end() || key_comp()(__k, (*__i).first)) |

550 | __throw_out_of_range(__N("map::at")); |

551 | return (*__i).second; |

552 | } |

553 | |

554 | // modifiers |

555 | #if __cplusplus >= 201103L |

556 | /** |

557 | * @brief Attempts to build and insert a std::pair into the %map. |

558 | * |

559 | * @param __args Arguments used to generate a new pair instance (see |

560 | * std::piecewise_contruct for passing arguments to each |

561 | * part of the pair constructor). |

562 | * |

563 | * @return A pair, of which the first element is an iterator that points |

564 | * to the possibly inserted pair, and the second is a bool that |

565 | * is true if the pair was actually inserted. |

566 | * |

567 | * This function attempts to build and insert a (key, value) %pair into |

568 | * the %map. |

569 | * A %map relies on unique keys and thus a %pair is only inserted if its |

570 | * first element (the key) is not already present in the %map. |

571 | * |

572 | * Insertion requires logarithmic time. |

573 | */ |

574 | template<typename... _Args> |

575 | std::pair<iterator, bool> |

576 | emplace(_Args&&... __args) |

577 | { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); } |

578 | |

579 | /** |

580 | * @brief Attempts to build and insert a std::pair into the %map. |

581 | * |

582 | * @param __pos An iterator that serves as a hint as to where the pair |

583 | * should be inserted. |

584 | * @param __args Arguments used to generate a new pair instance (see |

585 | * std::piecewise_contruct for passing arguments to each |

586 | * part of the pair constructor). |

587 | * @return An iterator that points to the element with key of the |

588 | * std::pair built from @a __args (may or may not be that |

589 | * std::pair). |

590 | * |

591 | * This function is not concerned about whether the insertion took place, |

592 | * and thus does not return a boolean like the single-argument emplace() |

593 | * does. |

594 | * Note that the first parameter is only a hint and can potentially |

595 | * improve the performance of the insertion process. A bad hint would |

596 | * cause no gains in efficiency. |

597 | * |

598 | * See |

599 | * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints |

600 | * for more on @a hinting. |

601 | * |

602 | * Insertion requires logarithmic time (if the hint is not taken). |

603 | */ |

604 | template<typename... _Args> |

605 | iterator |

606 | emplace_hint(const_iterator __pos, _Args&&... __args) |

607 | { |

608 | return _M_t._M_emplace_hint_unique(__pos, |

609 | std::forward<_Args>(__args)...); |

610 | } |

611 | #endif |

612 | |

613 | #if __cplusplus > 201402L |

614 | /// Extract a node. |

615 | node_type |

616 | extract(const_iterator __pos) |

617 | { |

618 | __glibcxx_assert(__pos != end()); |

619 | return _M_t.extract(__pos); |

620 | } |

621 | |

622 | /// Extract a node. |

623 | node_type |

624 | extract(const key_type& __x) |

625 | { return _M_t.extract(__x); } |

626 | |

627 | /// Re-insert an extracted node. |

628 | insert_return_type |

629 | insert(node_type&& __nh) |

630 | { return _M_t._M_reinsert_node_unique(std::move(__nh)); } |

631 | |

632 | /// Re-insert an extracted node. |

633 | iterator |

634 | insert(const_iterator __hint, node_type&& __nh) |

635 | { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); } |

636 | |

637 | template<typename, typename> |

638 | friend struct std::_Rb_tree_merge_helper; |

639 | |

640 | template<typename _Cmp2> |

641 | void |

642 | merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source) |

643 | { |

644 | using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>; |

645 | _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); |

646 | } |

647 | |

648 | template<typename _Cmp2> |

649 | void |

650 | merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source) |

651 | { merge(__source); } |

652 | |

653 | template<typename _Cmp2> |

654 | void |

655 | merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source) |

656 | { |

657 | using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>; |

658 | _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source)); |

659 | } |

660 | |

661 | template<typename _Cmp2> |

662 | void |

663 | merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source) |

664 | { merge(__source); } |

665 | #endif // C++17 |

666 | |

667 | #if __cplusplus > 201402L |

668 | #define __cpp_lib_map_try_emplace 201411 |

669 | /** |

670 | * @brief Attempts to build and insert a std::pair into the %map. |

671 | * |

672 | * @param __k Key to use for finding a possibly existing pair in |

673 | * the map. |

674 | * @param __args Arguments used to generate the .second for a new pair |

675 | * instance. |

676 | * |

677 | * @return A pair, of which the first element is an iterator that points |

678 | * to the possibly inserted pair, and the second is a bool that |

679 | * is true if the pair was actually inserted. |

680 | * |

681 | * This function attempts to build and insert a (key, value) %pair into |

682 | * the %map. |

683 | * A %map relies on unique keys and thus a %pair is only inserted if its |

684 | * first element (the key) is not already present in the %map. |

685 | * If a %pair is not inserted, this function has no effect. |

686 | * |

687 | * Insertion requires logarithmic time. |

688 | */ |

689 | template <typename... _Args> |

690 | pair<iterator, bool> |

691 | try_emplace(const key_type& __k, _Args&&... __args) |

692 | { |

693 | iterator __i = lower_bound(__k); |

694 | if (__i == end() || key_comp()(__k, (*__i).first)) |

695 | { |

696 | __i = emplace_hint(__i, std::piecewise_construct, |

697 | std::forward_as_tuple(__k), |

698 | std::forward_as_tuple( |

699 | std::forward<_Args>(__args)...)); |

700 | return {__i, true}; |

701 | } |

702 | return {__i, false}; |

703 | } |

704 | |

705 | // move-capable overload |

706 | template <typename... _Args> |

707 | pair<iterator, bool> |

708 | try_emplace(key_type&& __k, _Args&&... __args) |

709 | { |

710 | iterator __i = lower_bound(__k); |

711 | if (__i == end() || key_comp()(__k, (*__i).first)) |

712 | { |

713 | __i = emplace_hint(__i, std::piecewise_construct, |

714 | std::forward_as_tuple(std::move(__k)), |

715 | std::forward_as_tuple( |

716 | std::forward<_Args>(__args)...)); |

717 | return {__i, true}; |

718 | } |

719 | return {__i, false}; |

720 | } |

721 | |

722 | /** |

723 | * @brief Attempts to build and insert a std::pair into the %map. |

724 | * |

725 | * @param __hint An iterator that serves as a hint as to where the |

726 | * pair should be inserted. |

727 | * @param __k Key to use for finding a possibly existing pair in |

728 | * the map. |

729 | * @param __args Arguments used to generate the .second for a new pair |

730 | * instance. |

731 | * @return An iterator that points to the element with key of the |

732 | * std::pair built from @a __args (may or may not be that |

733 | * std::pair). |

734 | * |

735 | * This function is not concerned about whether the insertion took place, |

736 | * and thus does not return a boolean like the single-argument |

737 | * try_emplace() does. However, if insertion did not take place, |

738 | * this function has no effect. |

739 | * Note that the first parameter is only a hint and can potentially |

740 | * improve the performance of the insertion process. A bad hint would |

741 | * cause no gains in efficiency. |

742 | * |

743 | * See |

744 | * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints |

745 | * for more on @a hinting. |

746 | * |

747 | * Insertion requires logarithmic time (if the hint is not taken). |

748 | */ |

749 | template <typename... _Args> |

750 | iterator |

751 | try_emplace(const_iterator __hint, const key_type& __k, |

752 | _Args&&... __args) |

753 | { |

754 | iterator __i; |

755 | auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); |

756 | if (__true_hint.second) |

757 | __i = emplace_hint(iterator(__true_hint.second), |

758 | std::piecewise_construct, |

759 | std::forward_as_tuple(__k), |

760 | std::forward_as_tuple( |

761 | std::forward<_Args>(__args)...)); |

762 | else |

763 | __i = iterator(__true_hint.first); |

764 | return __i; |

765 | } |

766 | |

767 | // move-capable overload |

768 | template <typename... _Args> |

769 | iterator |

770 | try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) |

771 | { |

772 | iterator __i; |

773 | auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); |

774 | if (__true_hint.second) |

775 | __i = emplace_hint(iterator(__true_hint.second), |

776 | std::piecewise_construct, |

777 | std::forward_as_tuple(std::move(__k)), |

778 | std::forward_as_tuple( |

779 | std::forward<_Args>(__args)...)); |

780 | else |

781 | __i = iterator(__true_hint.first); |

782 | return __i; |

783 | } |

784 | #endif |

785 | |

786 | /** |

787 | * @brief Attempts to insert a std::pair into the %map. |

788 | * @param __x Pair to be inserted (see std::make_pair for easy |

789 | * creation of pairs). |

790 | * |

791 | * @return A pair, of which the first element is an iterator that |

792 | * points to the possibly inserted pair, and the second is |

793 | * a bool that is true if the pair was actually inserted. |

794 | * |

795 | * This function attempts to insert a (key, value) %pair into the %map. |

796 | * A %map relies on unique keys and thus a %pair is only inserted if its |

797 | * first element (the key) is not already present in the %map. |

798 | * |

799 | * Insertion requires logarithmic time. |

800 | * @{ |

801 | */ |

802 | std::pair<iterator, bool> |

803 | insert(const value_type& __x) |

804 | { return _M_t._M_insert_unique(__x); } |

805 | |

806 | #if __cplusplus >= 201103L |

807 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

808 | // 2354. Unnecessary copying when inserting into maps with braced-init |

809 | std::pair<iterator, bool> |

810 | insert(value_type&& __x) |

811 | { return _M_t._M_insert_unique(std::move(__x)); } |

812 | |

813 | template<typename _Pair> |

814 | __enable_if_t<is_constructible<value_type, _Pair>::value, |

815 | pair<iterator, bool>> |

816 | insert(_Pair&& __x) |

817 | { return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); } |

818 | #endif |

819 | /// @} |

820 | |

821 | #if __cplusplus >= 201103L |

822 | /** |

823 | * @brief Attempts to insert a list of std::pairs into the %map. |

824 | * @param __list A std::initializer_list<value_type> of pairs to be |

825 | * inserted. |

826 | * |

827 | * Complexity similar to that of the range constructor. |

828 | */ |

829 | void |

830 | insert(std::initializer_list<value_type> __list) |

831 | { insert(__list.begin(), __list.end()); } |

832 | #endif |

833 | |

834 | /** |

835 | * @brief Attempts to insert a std::pair into the %map. |

836 | * @param __position An iterator that serves as a hint as to where the |

837 | * pair should be inserted. |

838 | * @param __x Pair to be inserted (see std::make_pair for easy creation |

839 | * of pairs). |

840 | * @return An iterator that points to the element with key of |

841 | * @a __x (may or may not be the %pair passed in). |

842 | * |

843 | |

844 | * This function is not concerned about whether the insertion |

845 | * took place, and thus does not return a boolean like the |

846 | * single-argument insert() does. Note that the first |

847 | * parameter is only a hint and can potentially improve the |

848 | * performance of the insertion process. A bad hint would |

849 | * cause no gains in efficiency. |

850 | * |

851 | * See |

852 | * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints |

853 | * for more on @a hinting. |

854 | * |

855 | * Insertion requires logarithmic time (if the hint is not taken). |

856 | * @{ |

857 | */ |

858 | iterator |

859 | #if __cplusplus >= 201103L |

860 | insert(const_iterator __position, const value_type& __x) |

861 | #else |

862 | insert(iterator __position, const value_type& __x) |

863 | #endif |

864 | { return _M_t._M_insert_unique_(__position, __x); } |

865 | |

866 | #if __cplusplus >= 201103L |

867 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

868 | // 2354. Unnecessary copying when inserting into maps with braced-init |

869 | iterator |

870 | insert(const_iterator __position, value_type&& __x) |

871 | { return _M_t._M_insert_unique_(__position, std::move(__x)); } |

872 | |

873 | template<typename _Pair> |

874 | __enable_if_t<is_constructible<value_type, _Pair>::value, iterator> |

875 | insert(const_iterator __position, _Pair&& __x) |

876 | { |

877 | return _M_t._M_emplace_hint_unique(__position, |

878 | std::forward<_Pair>(__x)); |

879 | } |

880 | #endif |

881 | /// @} |

882 | |

883 | /** |

884 | * @brief Template function that attempts to insert a range of elements. |

885 | * @param __first Iterator pointing to the start of the range to be |

886 | * inserted. |

887 | * @param __last Iterator pointing to the end of the range. |

888 | * |

889 | * Complexity similar to that of the range constructor. |

890 | */ |

891 | template<typename _InputIterator> |

892 | void |

893 | insert(_InputIterator __first, _InputIterator __last) |

894 | { _M_t._M_insert_range_unique(__first, __last); } |

895 | |

896 | #if __cplusplus > 201402L |

897 | /** |

898 | * @brief Attempts to insert or assign a std::pair into the %map. |

899 | * @param __k Key to use for finding a possibly existing pair in |

900 | * the map. |

901 | * @param __obj Argument used to generate the .second for a pair |

902 | * instance. |

903 | * |

904 | * @return A pair, of which the first element is an iterator that |

905 | * points to the possibly inserted pair, and the second is |

906 | * a bool that is true if the pair was actually inserted. |

907 | * |

908 | * This function attempts to insert a (key, value) %pair into the %map. |

909 | * A %map relies on unique keys and thus a %pair is only inserted if its |

910 | * first element (the key) is not already present in the %map. |

911 | * If the %pair was already in the %map, the .second of the %pair |

912 | * is assigned from __obj. |

913 | * |

914 | * Insertion requires logarithmic time. |

915 | */ |

916 | template <typename _Obj> |

917 | pair<iterator, bool> |

918 | insert_or_assign(const key_type& __k, _Obj&& __obj) |

919 | { |

920 | iterator __i = lower_bound(__k); |

921 | if (__i == end() || key_comp()(__k, (*__i).first)) |

922 | { |

923 | __i = emplace_hint(__i, std::piecewise_construct, |

924 | std::forward_as_tuple(__k), |

925 | std::forward_as_tuple( |

926 | std::forward<_Obj>(__obj))); |

927 | return {__i, true}; |

928 | } |

929 | (*__i).second = std::forward<_Obj>(__obj); |

930 | return {__i, false}; |

931 | } |

932 | |

933 | // move-capable overload |

934 | template <typename _Obj> |

935 | pair<iterator, bool> |

936 | insert_or_assign(key_type&& __k, _Obj&& __obj) |

937 | { |

938 | iterator __i = lower_bound(__k); |

939 | if (__i == end() || key_comp()(__k, (*__i).first)) |

940 | { |

941 | __i = emplace_hint(__i, std::piecewise_construct, |

942 | std::forward_as_tuple(std::move(__k)), |

943 | std::forward_as_tuple( |

944 | std::forward<_Obj>(__obj))); |

945 | return {__i, true}; |

946 | } |

947 | (*__i).second = std::forward<_Obj>(__obj); |

948 | return {__i, false}; |

949 | } |

950 | |

951 | /** |

952 | * @brief Attempts to insert or assign a std::pair into the %map. |

953 | * @param __hint An iterator that serves as a hint as to where the |

954 | * pair should be inserted. |

955 | * @param __k Key to use for finding a possibly existing pair in |

956 | * the map. |

957 | * @param __obj Argument used to generate the .second for a pair |

958 | * instance. |

959 | * |

960 | * @return An iterator that points to the element with key of |

961 | * @a __x (may or may not be the %pair passed in). |

962 | * |

963 | * This function attempts to insert a (key, value) %pair into the %map. |

964 | * A %map relies on unique keys and thus a %pair is only inserted if its |

965 | * first element (the key) is not already present in the %map. |

966 | * If the %pair was already in the %map, the .second of the %pair |

967 | * is assigned from __obj. |

968 | * |

969 | * Insertion requires logarithmic time. |

970 | */ |

971 | template <typename _Obj> |

972 | iterator |

973 | insert_or_assign(const_iterator __hint, |

974 | const key_type& __k, _Obj&& __obj) |

975 | { |

976 | iterator __i; |

977 | auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); |

978 | if (__true_hint.second) |

979 | { |

980 | return emplace_hint(iterator(__true_hint.second), |

981 | std::piecewise_construct, |

982 | std::forward_as_tuple(__k), |

983 | std::forward_as_tuple( |

984 | std::forward<_Obj>(__obj))); |

985 | } |

986 | __i = iterator(__true_hint.first); |

987 | (*__i).second = std::forward<_Obj>(__obj); |

988 | return __i; |

989 | } |

990 | |

991 | // move-capable overload |

992 | template <typename _Obj> |

993 | iterator |

994 | insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) |

995 | { |

996 | iterator __i; |

997 | auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k); |

998 | if (__true_hint.second) |

999 | { |

1000 | return emplace_hint(iterator(__true_hint.second), |

1001 | std::piecewise_construct, |

1002 | std::forward_as_tuple(std::move(__k)), |

1003 | std::forward_as_tuple( |

1004 | std::forward<_Obj>(__obj))); |

1005 | } |

1006 | __i = iterator(__true_hint.first); |

1007 | (*__i).second = std::forward<_Obj>(__obj); |

1008 | return __i; |

1009 | } |

1010 | #endif |

1011 | |

1012 | #if __cplusplus >= 201103L |

1013 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

1014 | // DR 130. Associative erase should return an iterator. |

1015 | /** |

1016 | * @brief Erases an element from a %map. |

1017 | * @param __position An iterator pointing to the element to be erased. |

1018 | * @return An iterator pointing to the element immediately following |

1019 | * @a position prior to the element being erased. If no such |

1020 | * element exists, end() is returned. |

1021 | * |

1022 | * This function erases an element, pointed to by the given |

1023 | * iterator, from a %map. Note that this function only erases |

1024 | * the element, and that if the element is itself a pointer, |

1025 | * the pointed-to memory is not touched in any way. Managing |

1026 | * the pointer is the user's responsibility. |

1027 | * |

1028 | * @{ |

1029 | */ |

1030 | iterator |

1031 | erase(const_iterator __position) |

1032 | { return _M_t.erase(__position); } |

1033 | |

1034 | // LWG 2059 |

1035 | _GLIBCXX_ABI_TAG_CXX11 |

1036 | iterator |

1037 | erase(iterator __position) |

1038 | { return _M_t.erase(__position); } |

1039 | /// @} |

1040 | #else |

1041 | /** |

1042 | * @brief Erases an element from a %map. |

1043 | * @param __position An iterator pointing to the element to be erased. |

1044 | * |

1045 | * This function erases an element, pointed to by the given |

1046 | * iterator, from a %map. Note that this function only erases |

1047 | * the element, and that if the element is itself a pointer, |

1048 | * the pointed-to memory is not touched in any way. Managing |

1049 | * the pointer is the user's responsibility. |

1050 | */ |

1051 | void |

1052 | erase(iterator __position) |

1053 | { _M_t.erase(__position); } |

1054 | #endif |

1055 | |

1056 | /** |

1057 | * @brief Erases elements according to the provided key. |

1058 | * @param __x Key of element to be erased. |

1059 | * @return The number of elements erased. |

1060 | * |

1061 | * This function erases all the elements located by the given key from |

1062 | * a %map. |

1063 | * Note that this function only erases the element, and that if |

1064 | * the element is itself a pointer, the pointed-to memory is not touched |

1065 | * in any way. Managing the pointer is the user's responsibility. |

1066 | */ |

1067 | size_type |

1068 | erase(const key_type& __x) |

1069 | { return _M_t.erase(__x); } |

1070 | |

1071 | #if __cplusplus >= 201103L |

1072 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

1073 | // DR 130. Associative erase should return an iterator. |

1074 | /** |

1075 | * @brief Erases a [first,last) range of elements from a %map. |

1076 | * @param __first Iterator pointing to the start of the range to be |

1077 | * erased. |

1078 | * @param __last Iterator pointing to the end of the range to |

1079 | * be erased. |

1080 | * @return The iterator @a __last. |

1081 | * |

1082 | * This function erases a sequence of elements from a %map. |

1083 | * Note that this function only erases the element, and that if |

1084 | * the element is itself a pointer, the pointed-to memory is not touched |

1085 | * in any way. Managing the pointer is the user's responsibility. |

1086 | */ |

1087 | iterator |

1088 | erase(const_iterator __first, const_iterator __last) |

1089 | { return _M_t.erase(__first, __last); } |

1090 | #else |

1091 | /** |

1092 | * @brief Erases a [__first,__last) range of elements from a %map. |

1093 | * @param __first Iterator pointing to the start of the range to be |

1094 | * erased. |

1095 | * @param __last Iterator pointing to the end of the range to |

1096 | * be erased. |

1097 | * |

1098 | * This function erases a sequence of elements from a %map. |

1099 | * Note that this function only erases the element, and that if |

1100 | * the element is itself a pointer, the pointed-to memory is not touched |

1101 | * in any way. Managing the pointer is the user's responsibility. |

1102 | */ |

1103 | void |

1104 | erase(iterator __first, iterator __last) |

1105 | { _M_t.erase(__first, __last); } |

1106 | #endif |

1107 | |

1108 | /** |

1109 | * @brief Swaps data with another %map. |

1110 | * @param __x A %map of the same element and allocator types. |

1111 | * |

1112 | * This exchanges the elements between two maps in constant |

1113 | * time. (It is only swapping a pointer, an integer, and an |

1114 | * instance of the @c Compare type (which itself is often |

1115 | * stateless and empty), so it should be quite fast.) Note |

1116 | * that the global std::swap() function is specialized such |

1117 | * that std::swap(m1,m2) will feed to this function. |

1118 | * |

1119 | * Whether the allocators are swapped depends on the allocator traits. |

1120 | */ |

1121 | void |

1122 | swap(map& __x) |

1123 | _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) |

1124 | { _M_t.swap(__x._M_t); } |

1125 | |

1126 | /** |

1127 | * Erases all elements in a %map. Note that this function only |

1128 | * erases the elements, and that if the elements themselves are |

1129 | * pointers, the pointed-to memory is not touched in any way. |

1130 | * Managing the pointer is the user's responsibility. |

1131 | */ |

1132 | void |

1133 | clear() _GLIBCXX_NOEXCEPT |

1134 | { _M_t.clear(); } |

1135 | |

1136 | // observers |

1137 | /** |

1138 | * Returns the key comparison object out of which the %map was |

1139 | * constructed. |

1140 | */ |

1141 | key_compare |

1142 | key_comp() const |

1143 | { return _M_t.key_comp(); } |

1144 | |

1145 | /** |

1146 | * Returns a value comparison object, built from the key comparison |

1147 | * object out of which the %map was constructed. |

1148 | */ |

1149 | value_compare |

1150 | value_comp() const |

1151 | { return value_compare(_M_t.key_comp()); } |

1152 | |

1153 | // [23.3.1.3] map operations |

1154 | |

1155 | ///@{ |

1156 | /** |

1157 | * @brief Tries to locate an element in a %map. |

1158 | * @param __x Key of (key, value) %pair to be located. |

1159 | * @return Iterator pointing to sought-after element, or end() if not |

1160 | * found. |

1161 | * |

1162 | * This function takes a key and tries to locate the element with which |

1163 | * the key matches. If successful the function returns an iterator |

1164 | * pointing to the sought after %pair. If unsuccessful it returns the |

1165 | * past-the-end ( @c end() ) iterator. |

1166 | */ |

1167 | |

1168 | iterator |

1169 | find(const key_type& __x) |

1170 | { return _M_t.find(__x); } |

1171 | |

1172 | #if __cplusplus > 201103L |

1173 | template<typename _Kt> |

1174 | auto |

1175 | find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x)) |

1176 | { return _M_t._M_find_tr(__x); } |

1177 | #endif |

1178 | ///@} |

1179 | |

1180 | ///@{ |

1181 | /** |

1182 | * @brief Tries to locate an element in a %map. |

1183 | * @param __x Key of (key, value) %pair to be located. |

1184 | * @return Read-only (constant) iterator pointing to sought-after |

1185 | * element, or end() if not found. |

1186 | * |

1187 | * This function takes a key and tries to locate the element with which |

1188 | * the key matches. If successful the function returns a constant |

1189 | * iterator pointing to the sought after %pair. If unsuccessful it |

1190 | * returns the past-the-end ( @c end() ) iterator. |

1191 | */ |

1192 | |

1193 | const_iterator |

1194 | find(const key_type& __x) const |

1195 | { return _M_t.find(__x); } |

1196 | |

1197 | #if __cplusplus > 201103L |

1198 | template<typename _Kt> |

1199 | auto |

1200 | find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x)) |

1201 | { return _M_t._M_find_tr(__x); } |

1202 | #endif |

1203 | ///@} |

1204 | |

1205 | ///@{ |

1206 | /** |

1207 | * @brief Finds the number of elements with given key. |

1208 | * @param __x Key of (key, value) pairs to be located. |

1209 | * @return Number of elements with specified key. |

1210 | * |

1211 | * This function only makes sense for multimaps; for map the result will |

1212 | * either be 0 (not present) or 1 (present). |

1213 | */ |

1214 | size_type |

1215 | count(const key_type& __x) const |

1216 | { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } |

1217 | |

1218 | #if __cplusplus > 201103L |

1219 | template<typename _Kt> |

1220 | auto |

1221 | count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x)) |

1222 | { return _M_t._M_count_tr(__x); } |

1223 | #endif |

1224 | ///@} |

1225 | |

1226 | #if __cplusplus > 201703L |

1227 | ///@{ |

1228 | /** |

1229 | * @brief Finds whether an element with the given key exists. |

1230 | * @param __x Key of (key, value) pairs to be located. |

1231 | * @return True if there is an element with the specified key. |

1232 | */ |

1233 | bool |

1234 | contains(const key_type& __x) const |

1235 | { return _M_t.find(__x) != _M_t.end(); } |

1236 | |

1237 | template<typename _Kt> |

1238 | auto |

1239 | contains(const _Kt& __x) const |

1240 | -> decltype(_M_t._M_find_tr(__x), void(), true) |

1241 | { return _M_t._M_find_tr(__x) != _M_t.end(); } |

1242 | ///@} |

1243 | #endif |

1244 | |

1245 | ///@{ |

1246 | /** |

1247 | * @brief Finds the beginning of a subsequence matching given key. |

1248 | * @param __x Key of (key, value) pair to be located. |

1249 | * @return Iterator pointing to first element equal to or greater |

1250 | * than key, or end(). |

1251 | * |

1252 | * This function returns the first element of a subsequence of elements |

1253 | * that matches the given key. If unsuccessful it returns an iterator |

1254 | * pointing to the first element that has a greater value than given key |

1255 | * or end() if no such element exists. |

1256 | */ |

1257 | iterator |

1258 | lower_bound(const key_type& __x) |

1259 | { return _M_t.lower_bound(__x); } |

1260 | |

1261 | #if __cplusplus > 201103L |

1262 | template<typename _Kt> |

1263 | auto |

1264 | lower_bound(const _Kt& __x) |

1265 | -> decltype(iterator(_M_t._M_lower_bound_tr(__x))) |

1266 | { return iterator(_M_t._M_lower_bound_tr(__x)); } |

1267 | #endif |

1268 | ///@} |

1269 | |

1270 | ///@{ |

1271 | /** |

1272 | * @brief Finds the beginning of a subsequence matching given key. |

1273 | * @param __x Key of (key, value) pair to be located. |

1274 | * @return Read-only (constant) iterator pointing to first element |

1275 | * equal to or greater than key, or end(). |

1276 | * |

1277 | * This function returns the first element of a subsequence of elements |

1278 | * that matches the given key. If unsuccessful it returns an iterator |

1279 | * pointing to the first element that has a greater value than given key |

1280 | * or end() if no such element exists. |

1281 | */ |

1282 | const_iterator |

1283 | lower_bound(const key_type& __x) const |

1284 | { return _M_t.lower_bound(__x); } |

1285 | |

1286 | #if __cplusplus > 201103L |

1287 | template<typename _Kt> |

1288 | auto |

1289 | lower_bound(const _Kt& __x) const |

1290 | -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x))) |

1291 | { return const_iterator(_M_t._M_lower_bound_tr(__x)); } |

1292 | #endif |

1293 | ///@} |

1294 | |

1295 | ///@{ |

1296 | /** |

1297 | * @brief Finds the end of a subsequence matching given key. |

1298 | * @param __x Key of (key, value) pair to be located. |

1299 | * @return Iterator pointing to the first element |

1300 | * greater than key, or end(). |

1301 | */ |

1302 | iterator |

1303 | upper_bound(const key_type& __x) |

1304 | { return _M_t.upper_bound(__x); } |

1305 | |

1306 | #if __cplusplus > 201103L |

1307 | template<typename _Kt> |

1308 | auto |

1309 | upper_bound(const _Kt& __x) |

1310 | -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) |

1311 | { return iterator(_M_t._M_upper_bound_tr(__x)); } |

1312 | #endif |

1313 | ///@} |

1314 | |

1315 | ///@{ |

1316 | /** |

1317 | * @brief Finds the end of a subsequence matching given key. |

1318 | * @param __x Key of (key, value) pair to be located. |

1319 | * @return Read-only (constant) iterator pointing to first iterator |

1320 | * greater than key, or end(). |

1321 | */ |

1322 | const_iterator |

1323 | upper_bound(const key_type& __x) const |

1324 | { return _M_t.upper_bound(__x); } |

1325 | |

1326 | #if __cplusplus > 201103L |

1327 | template<typename _Kt> |

1328 | auto |

1329 | upper_bound(const _Kt& __x) const |

1330 | -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) |

1331 | { return const_iterator(_M_t._M_upper_bound_tr(__x)); } |

1332 | #endif |

1333 | ///@} |

1334 | |

1335 | ///@{ |

1336 | /** |

1337 | * @brief Finds a subsequence matching given key. |

1338 | * @param __x Key of (key, value) pairs to be located. |

1339 | * @return Pair of iterators that possibly points to the subsequence |

1340 | * matching given key. |

1341 | * |

1342 | * This function is equivalent to |

1343 | * @code |

1344 | * std::make_pair(c.lower_bound(val), |

1345 | * c.upper_bound(val)) |

1346 | * @endcode |

1347 | * (but is faster than making the calls separately). |

1348 | * |

1349 | * This function probably only makes sense for multimaps. |

1350 | */ |

1351 | std::pair<iterator, iterator> |

1352 | equal_range(const key_type& __x) |

1353 | { return _M_t.equal_range(__x); } |

1354 | |

1355 | #if __cplusplus > 201103L |

1356 | template<typename _Kt> |

1357 | auto |

1358 | equal_range(const _Kt& __x) |

1359 | -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x))) |

1360 | { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); } |

1361 | #endif |

1362 | ///@} |

1363 | |

1364 | ///@{ |

1365 | /** |

1366 | * @brief Finds a subsequence matching given key. |

1367 | * @param __x Key of (key, value) pairs to be located. |

1368 | * @return Pair of read-only (constant) iterators that possibly points |

1369 | * to the subsequence matching given key. |

1370 | * |

1371 | * This function is equivalent to |

1372 | * @code |

1373 | * std::make_pair(c.lower_bound(val), |

1374 | * c.upper_bound(val)) |

1375 | * @endcode |

1376 | * (but is faster than making the calls separately). |

1377 | * |

1378 | * This function probably only makes sense for multimaps. |

1379 | */ |

1380 | std::pair<const_iterator, const_iterator> |

1381 | equal_range(const key_type& __x) const |

1382 | { return _M_t.equal_range(__x); } |

1383 | |

1384 | #if __cplusplus > 201103L |

1385 | template<typename _Kt> |

1386 | auto |

1387 | equal_range(const _Kt& __x) const |

1388 | -> decltype(pair<const_iterator, const_iterator>( |

1389 | _M_t._M_equal_range_tr(__x))) |

1390 | { |

1391 | return pair<const_iterator, const_iterator>( |

1392 | _M_t._M_equal_range_tr(__x)); |

1393 | } |

1394 | #endif |

1395 | ///@} |

1396 | |

1397 | template<typename _K1, typename _T1, typename _C1, typename _A1> |

1398 | friend bool |

1399 | operator==(const map<_K1, _T1, _C1, _A1>&, |

1400 | const map<_K1, _T1, _C1, _A1>&); |

1401 | |

1402 | #if __cpp_lib_three_way_comparison |

1403 | template<typename _K1, typename _T1, typename _C1, typename _A1> |

1404 | friend __detail::__synth3way_t<pair<const _K1, _T1>> |

1405 | operator<=>(const map<_K1, _T1, _C1, _A1>&, |

1406 | const map<_K1, _T1, _C1, _A1>&); |

1407 | #else |

1408 | template<typename _K1, typename _T1, typename _C1, typename _A1> |

1409 | friend bool |

1410 | operator<(const map<_K1, _T1, _C1, _A1>&, |

1411 | const map<_K1, _T1, _C1, _A1>&); |

1412 | #endif |

1413 | }; |

1414 | |

1415 | |

1416 | #if __cpp_deduction_guides >= 201606 |

1417 | |

1418 | template<typename _InputIterator, |

1419 | typename _Compare = less<__iter_key_t<_InputIterator>>, |

1420 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, |

1421 | typename = _RequireInputIter<_InputIterator>, |

1422 | typename = _RequireNotAllocator<_Compare>, |

1423 | typename = _RequireAllocator<_Allocator>> |

1424 | map(_InputIterator, _InputIterator, |

1425 | _Compare = _Compare(), _Allocator = _Allocator()) |

1426 | -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |

1427 | _Compare, _Allocator>; |

1428 | |

1429 | template<typename _Key, typename _Tp, typename _Compare = less<_Key>, |

1430 | typename _Allocator = allocator<pair<const _Key, _Tp>>, |

1431 | typename = _RequireNotAllocator<_Compare>, |

1432 | typename = _RequireAllocator<_Allocator>> |

1433 | map(initializer_list<pair<_Key, _Tp>>, |

1434 | _Compare = _Compare(), _Allocator = _Allocator()) |

1435 | -> map<_Key, _Tp, _Compare, _Allocator>; |

1436 | |

1437 | template <typename _InputIterator, typename _Allocator, |

1438 | typename = _RequireInputIter<_InputIterator>, |

1439 | typename = _RequireAllocator<_Allocator>> |

1440 | map(_InputIterator, _InputIterator, _Allocator) |

1441 | -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |

1442 | less<__iter_key_t<_InputIterator>>, _Allocator>; |

1443 | |

1444 | template<typename _Key, typename _Tp, typename _Allocator, |

1445 | typename = _RequireAllocator<_Allocator>> |

1446 | map(initializer_list<pair<_Key, _Tp>>, _Allocator) |

1447 | -> map<_Key, _Tp, less<_Key>, _Allocator>; |

1448 | |

1449 | #endif // deduction guides |

1450 | |

1451 | /** |

1452 | * @brief Map equality comparison. |

1453 | * @param __x A %map. |

1454 | * @param __y A %map of the same type as @a x. |

1455 | * @return True iff the size and elements of the maps are equal. |

1456 | * |

1457 | * This is an equivalence relation. It is linear in the size of the |

1458 | * maps. Maps are considered equivalent if their sizes are equal, |

1459 | * and if corresponding elements compare equal. |

1460 | */ |

1461 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1462 | inline bool |

1463 | operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1464 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1465 | { return __x._M_t == __y._M_t; } |

1466 | |

1467 | #if __cpp_lib_three_way_comparison |

1468 | /** |

1469 | * @brief Map ordering relation. |

1470 | * @param __x A `map`. |

1471 | * @param __y A `map` of the same type as `x`. |

1472 | * @return A value indicating whether `__x` is less than, equal to, |

1473 | * greater than, or incomparable with `__y`. |

1474 | * |

1475 | * This is a total ordering relation. It is linear in the size of the |

1476 | * maps. The elements must be comparable with @c <. |

1477 | * |

1478 | * See `std::lexicographical_compare_three_way()` for how the determination |

1479 | * is made. This operator is used to synthesize relational operators like |

1480 | * `<` and `>=` etc. |

1481 | */ |

1482 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1483 | inline __detail::__synth3way_t<pair<const _Key, _Tp>> |

1484 | operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1485 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1486 | { return __x._M_t <=> __y._M_t; } |

1487 | #else |

1488 | /** |

1489 | * @brief Map ordering relation. |

1490 | * @param __x A %map. |

1491 | * @param __y A %map of the same type as @a x. |

1492 | * @return True iff @a x is lexicographically less than @a y. |

1493 | * |

1494 | * This is a total ordering relation. It is linear in the size of the |

1495 | * maps. The elements must be comparable with @c <. |

1496 | * |

1497 | * See std::lexicographical_compare() for how the determination is made. |

1498 | */ |

1499 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1500 | inline bool |

1501 | operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1502 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1503 | { return __x._M_t < __y._M_t; } |

1504 | |

1505 | /// Based on operator== |

1506 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1507 | inline bool |

1508 | operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1509 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1510 | { return !(__x == __y); } |

1511 | |

1512 | /// Based on operator< |

1513 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1514 | inline bool |

1515 | operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1516 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1517 | { return __y < __x; } |

1518 | |

1519 | /// Based on operator< |

1520 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1521 | inline bool |

1522 | operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1523 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1524 | { return !(__y < __x); } |

1525 | |

1526 | /// Based on operator< |

1527 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1528 | inline bool |

1529 | operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, |

1530 | const map<_Key, _Tp, _Compare, _Alloc>& __y) |

1531 | { return !(__x < __y); } |

1532 | #endif // three-way comparison |

1533 | |

1534 | /// See std::map::swap(). |

1535 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |

1536 | inline void |

1537 | swap(map<_Key, _Tp, _Compare, _Alloc>& __x, |

1538 | map<_Key, _Tp, _Compare, _Alloc>& __y) |

1539 | _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) |

1540 | { __x.swap(__y); } |

1541 | |

1542 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1543 | |

1544 | #if __cplusplus > 201402L |

1545 | // Allow std::map access to internals of compatible maps. |

1546 | template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc, |

1547 | typename _Cmp2> |

1548 | struct |

1549 | _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>, |

1550 | _Cmp2> |

1551 | { |

1552 | private: |

1553 | friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>; |

1554 | |

1555 | static auto& |

1556 | _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map) |

1557 | { return __map._M_t; } |

1558 | |

1559 | static auto& |

1560 | _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map) |

1561 | { return __map._M_t; } |

1562 | }; |

1563 | #endif // C++17 |

1564 | |

1565 | _GLIBCXX_END_NAMESPACE_VERSION |

1566 | } // namespace std |

1567 | |

1568 | #endif /* _STL_MAP_H */ |

1569 |