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

2 | |

3 | // Copyright (C) 2001-2017 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_CONTAINER |

69 | |

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

71 | class multimap; |

72 | |

73 | /** |

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

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

76 | * |

77 | * @ingroup associative_containers |

78 | * |

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

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

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

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

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

84 | * |

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

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

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

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

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

90 | * |

91 | * Maps support bidirectional iterators. |

92 | * |

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

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

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

96 | */ |

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

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

99 | class map |

100 | { |

101 | public: |

102 | typedef _Key key_type; |

103 | typedef _Tp mapped_type; |

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

105 | typedef _Compare key_compare; |

106 | typedef _Alloc allocator_type; |

107 | |

108 | private: |

109 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

110 | // concept requirements |

111 | typedef typename _Alloc::value_type _Alloc_value_type; |

112 | # if __cplusplus < 201103L |

113 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

114 | # endif |

115 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, |

116 | _BinaryFunctionConcept) |

117 | __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) |

118 | #endif |

119 | |

120 | public: |

121 | class value_compare |

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

123 | { |

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

125 | protected: |

126 | _Compare comp; |

127 | |

128 | value_compare(_Compare __c) |

129 | : comp(__c) { } |

130 | |

131 | public: |

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

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

134 | }; |

135 | |

136 | private: |

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

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

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

140 | |

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

142 | key_compare, _Pair_alloc_type> _Rep_type; |

143 | |

144 | /// The actual tree structure. |

145 | _Rep_type _M_t; |

146 | |

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

148 | |

149 | public: |

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

151 | // "functionally equivalent" |

152 | typedef typename _Alloc_traits::pointer pointer; |

153 | typedef typename _Alloc_traits::const_pointer const_pointer; |

154 | typedef typename _Alloc_traits::reference reference; |

155 | typedef typename _Alloc_traits::const_reference const_reference; |

156 | typedef typename _Rep_type::iterator iterator; |

157 | typedef typename _Rep_type::const_iterator const_iterator; |

158 | typedef typename _Rep_type::size_type size_type; |

159 | typedef typename _Rep_type::difference_type difference_type; |

160 | typedef typename _Rep_type::reverse_iterator reverse_iterator; |

161 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

162 | |

163 | #if __cplusplus > 201402L |

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

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

166 | #endif |

167 | |

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

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

170 | |

171 | /** |

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

173 | */ |

174 | #if __cplusplus < 201103L |

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

176 | #else |

177 | map() = default; |

178 | #endif |

179 | |

180 | /** |

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

182 | * @param __comp A comparison object. |

183 | * @param __a An allocator object. |

184 | */ |

185 | explicit |

186 | map(const _Compare& __comp, |

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

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

189 | |

190 | /** |

191 | * @brief %Map copy constructor. |

192 | * |

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

194 | */ |

195 | #if __cplusplus < 201103L |

196 | map(const map& __x) |

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

198 | #else |

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

200 | |

201 | /** |

202 | * @brief %Map move constructor. |

203 | * |

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

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

206 | */ |

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

208 | |

209 | /** |

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

211 | * @param __l An initializer_list. |

212 | * @param __comp A comparison object. |

213 | * @param __a An allocator object. |

214 | * |

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

216 | * initializer_list @a __l. |

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

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

219 | */ |

220 | map(initializer_list<value_type> __l, |

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

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

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

224 | { _M_t._M_insert_unique(__l.begin(), __l.end()); } |

225 | |

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

227 | explicit |

228 | map(const allocator_type& __a) |

229 | : _M_t(_Compare(), _Pair_alloc_type(__a)) { } |

230 | |

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

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

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

234 | |

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

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

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

238 | && _Alloc_traits::_S_always_equal()) |

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

240 | |

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

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

243 | : _M_t(_Compare(), _Pair_alloc_type(__a)) |

244 | { _M_t._M_insert_unique(__l.begin(), __l.end()); } |

245 | |

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

247 | template<typename _InputIterator> |

248 | map(_InputIterator __first, _InputIterator __last, |

249 | const allocator_type& __a) |

250 | : _M_t(_Compare(), _Pair_alloc_type(__a)) |

251 | { _M_t._M_insert_unique(__first, __last); } |

252 | #endif |

253 | |

254 | /** |

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

256 | * @param __first An input iterator. |

257 | * @param __last An input iterator. |

258 | * |

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

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

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

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

263 | */ |

264 | template<typename _InputIterator> |

265 | map(_InputIterator __first, _InputIterator __last) |

266 | : _M_t() |

267 | { _M_t._M_insert_unique(__first, __last); } |

268 | |

269 | /** |

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

271 | * @param __first An input iterator. |

272 | * @param __last An input iterator. |

273 | * @param __comp A comparison functor. |

274 | * @param __a An allocator object. |

275 | * |

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

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

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

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

280 | */ |

281 | template<typename _InputIterator> |

282 | map(_InputIterator __first, _InputIterator __last, |

283 | const _Compare& __comp, |

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

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

286 | { _M_t._M_insert_unique(__first, __last); } |

287 | |

288 | #if __cplusplus >= 201103L |

289 | /** |

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

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

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

293 | */ |

294 | ~map() = default; |

295 | #endif |

296 | |

297 | /** |

298 | * @brief %Map assignment operator. |

299 | * |

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

301 | */ |

302 | #if __cplusplus < 201103L |

303 | map& |

304 | operator=(const map& __x) |

305 | { |

306 | _M_t = __x._M_t; |

307 | return *this; |

308 | } |

309 | #else |

310 | map& |

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

312 | |

313 | /// Move assignment operator. |

314 | map& |

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

316 | |

317 | /** |

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

319 | * @param __l An initializer_list. |

320 | * |

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

322 | * initializer list @a __l. |

323 | * |

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

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

326 | * of elements assigned. |

327 | */ |

328 | map& |

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

330 | { |

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

332 | return *this; |

333 | } |

334 | #endif |

335 | |

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

337 | allocator_type |

338 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

340 | |

341 | // iterators |

342 | /** |

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

344 | * %map. |

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

346 | */ |

347 | iterator |

348 | begin() _GLIBCXX_NOEXCEPT |

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

350 | |

351 | /** |

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

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

354 | * keys. |

355 | */ |

356 | const_iterator |

357 | begin() const _GLIBCXX_NOEXCEPT |

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

359 | |

360 | /** |

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

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

363 | * according to the keys. |

364 | */ |

365 | iterator |

366 | end() _GLIBCXX_NOEXCEPT |

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

368 | |

369 | /** |

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

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

372 | * the keys. |

373 | */ |

374 | const_iterator |

375 | end() const _GLIBCXX_NOEXCEPT |

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

377 | |

378 | /** |

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

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

381 | * keys. |

382 | */ |

383 | reverse_iterator |

384 | rbegin() _GLIBCXX_NOEXCEPT |

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

386 | |

387 | /** |

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

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

390 | * according to the keys. |

391 | */ |

392 | const_reverse_iterator |

393 | rbegin() const _GLIBCXX_NOEXCEPT |

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

395 | |

396 | /** |

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

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

399 | * according to the keys. |

400 | */ |

401 | reverse_iterator |

402 | rend() _GLIBCXX_NOEXCEPT |

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

404 | |

405 | /** |

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

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

408 | * order according to the keys. |

409 | */ |

410 | const_reverse_iterator |

411 | rend() const _GLIBCXX_NOEXCEPT |

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

413 | |

414 | #if __cplusplus >= 201103L |

415 | /** |

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

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

418 | * keys. |

419 | */ |

420 | const_iterator |

421 | cbegin() const noexcept |

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

423 | |

424 | /** |

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

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

427 | * the keys. |

428 | */ |

429 | const_iterator |

430 | cend() const noexcept |

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

432 | |

433 | /** |

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

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

436 | * according to the keys. |

437 | */ |

438 | const_reverse_iterator |

439 | crbegin() const noexcept |

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

441 | |

442 | /** |

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

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

445 | * order according to the keys. |

446 | */ |

447 | const_reverse_iterator |

448 | crend() const noexcept |

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

450 | #endif |

451 | |

452 | // capacity |

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

454 | * end().) |

455 | */ |

456 | bool |

457 | empty() const _GLIBCXX_NOEXCEPT |

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

459 | |

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

461 | size_type |

462 | size() const _GLIBCXX_NOEXCEPT |

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

464 | |

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

466 | size_type |

467 | max_size() const _GLIBCXX_NOEXCEPT |

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

469 | |

470 | // [23.3.1.2] element access |

471 | /** |

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

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

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

475 | * |

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

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

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

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

480 | * |

481 | * Lookup requires logarithmic time. |

482 | */ |

483 | mapped_type& |

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

485 | { |

486 | // concept requirements |

487 | __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) |

488 | |

489 | iterator __i = lower_bound(__k); |

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

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

492 | #if __cplusplus >= 201103L |

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

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

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

496 | #else |

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

498 | #endif |

499 | return (*__i).second; |

500 | } |

501 | |

502 | #if __cplusplus >= 201103L |

503 | mapped_type& |

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

505 | { |

506 | // concept requirements |

507 | __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>) |

508 | |

509 | iterator __i = lower_bound(__k); |

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

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

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

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

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

515 | return (*__i).second; |

516 | } |

517 | #endif |

518 | |

519 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

521 | /** |

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

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

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

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

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

527 | */ |

528 | mapped_type& |

529 | at(const key_type& __k) |

530 | { |

531 | iterator __i = lower_bound(__k); |

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

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

534 | return (*__i).second; |

535 | } |

536 | |

537 | const mapped_type& |

538 | at(const key_type& __k) const |

539 | { |

540 | const_iterator __i = lower_bound(__k); |

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

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

543 | return (*__i).second; |

544 | } |

545 | |

546 | // modifiers |

547 | #if __cplusplus >= 201103L |

548 | /** |

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

550 | * |

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

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

553 | * part of the pair constructor). |

554 | * |

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

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

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

558 | * |

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

560 | * the %map. |

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

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

563 | * |

564 | * Insertion requires logarithmic time. |

565 | */ |

566 | template<typename... _Args> |

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

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

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

570 | |

571 | /** |

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

573 | * |

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

575 | * should be inserted. |

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

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

578 | * part of the pair constructor). |

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

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

581 | * std::pair). |

582 | * |

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

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

585 | * does. |

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

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

588 | * cause no gains in efficiency. |

589 | * |

590 | * See |

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

592 | * for more on @a hinting. |

593 | * |

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

595 | */ |

596 | template<typename... _Args> |

597 | iterator |

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

599 | { |

600 | return _M_t._M_emplace_hint_unique(__pos, |

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

602 | } |

603 | #endif |

604 | |

605 | #if __cplusplus > 201402L |

606 | /// Extract a node. |

607 | node_type |

608 | extract(const_iterator __pos) |

609 | { |

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

611 | return _M_t.extract(__pos); |

612 | } |

613 | |

614 | /// Extract a node. |

615 | node_type |

616 | extract(const key_type& __x) |

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

618 | |

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

620 | insert_return_type |

621 | insert(node_type&& __nh) |

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

623 | |

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

625 | iterator |

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

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

628 | |

629 | template<typename, typename> |

630 | friend class _Rb_tree_merge_helper; |

631 | |

632 | template<typename _C2> |

633 | void |

634 | merge(map<_Key, _Tp, _C2, _Alloc>& __source) |

635 | { |

636 | using _Merge_helper = _Rb_tree_merge_helper<map, _C2>; |

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

638 | } |

639 | |

640 | template<typename _C2> |

641 | void |

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

643 | { merge(__source); } |

644 | |

645 | template<typename _C2> |

646 | void |

647 | merge(multimap<_Key, _Tp, _C2, _Alloc>& __source) |

648 | { |

649 | using _Merge_helper = _Rb_tree_merge_helper<map, _C2>; |

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

651 | } |

652 | |

653 | template<typename _C2> |

654 | void |

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

656 | { merge(__source); } |

657 | #endif // C++17 |

658 | |

659 | #if __cplusplus > 201402L |

660 | #define __cpp_lib_map_try_emplace 201411 |

661 | /** |

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

663 | * |

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

665 | * the map. |

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

667 | * instance. |

668 | * |

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

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

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

672 | * |

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

674 | * the %map. |

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

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

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

678 | * |

679 | * Insertion requires logarithmic time. |

680 | */ |

681 | template <typename... _Args> |

682 | pair<iterator, bool> |

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

684 | { |

685 | iterator __i = lower_bound(__k); |

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

687 | { |

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

689 | std::forward_as_tuple(__k), |

690 | std::forward_as_tuple( |

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

692 | return {__i, true}; |

693 | } |

694 | return {__i, false}; |

695 | } |

696 | |

697 | // move-capable overload |

698 | template <typename... _Args> |

699 | pair<iterator, bool> |

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

701 | { |

702 | iterator __i = lower_bound(__k); |

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

704 | { |

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

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

707 | std::forward_as_tuple( |

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

709 | return {__i, true}; |

710 | } |

711 | return {__i, false}; |

712 | } |

713 | |

714 | /** |

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

716 | * |

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

718 | * pair should be inserted. |

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

720 | * the map. |

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

722 | * instance. |

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

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

725 | * std::pair). |

726 | * |

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

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

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

730 | * this function has no effect. |

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

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

733 | * cause no gains in efficiency. |

734 | * |

735 | * See |

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

737 | * for more on @a hinting. |

738 | * |

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

740 | */ |

741 | template <typename... _Args> |

742 | iterator |

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

744 | _Args&&... __args) |

745 | { |

746 | iterator __i; |

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

748 | if (__true_hint.second) |

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

750 | std::piecewise_construct, |

751 | std::forward_as_tuple(__k), |

752 | std::forward_as_tuple( |

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

754 | else |

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

756 | return __i; |

757 | } |

758 | |

759 | // move-capable overload |

760 | template <typename... _Args> |

761 | iterator |

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

763 | { |

764 | iterator __i; |

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

766 | if (__true_hint.second) |

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

768 | std::piecewise_construct, |

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

770 | std::forward_as_tuple( |

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

772 | else |

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

774 | return __i; |

775 | } |

776 | #endif |

777 | |

778 | /** |

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

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

781 | * creation of pairs). |

782 | * |

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

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

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

786 | * |

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

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

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

790 | * |

791 | * Insertion requires logarithmic time. |

792 | * @{ |

793 | */ |

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

795 | insert(const value_type& __x) |

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

797 | |

798 | #if __cplusplus >= 201103L |

799 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

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

802 | insert(value_type&& __x) |

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

804 | |

805 | template<typename _Pair, typename = typename |

806 | std::enable_if<std::is_constructible<value_type, |

807 | _Pair&&>::value>::type> |

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

809 | insert(_Pair&& __x) |

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

811 | #endif |

812 | // @} |

813 | |

814 | #if __cplusplus >= 201103L |

815 | /** |

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

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

818 | * inserted. |

819 | * |

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

821 | */ |

822 | void |

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

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

825 | #endif |

826 | |

827 | /** |

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

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

830 | * pair should be inserted. |

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

832 | * of pairs). |

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

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

835 | * |

836 | |

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

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

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

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

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

842 | * cause no gains in efficiency. |

843 | * |

844 | * See |

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

846 | * for more on @a hinting. |

847 | * |

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

849 | * @{ |

850 | */ |

851 | iterator |

852 | #if __cplusplus >= 201103L |

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

854 | #else |

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

856 | #endif |

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

858 | |

859 | #if __cplusplus >= 201103L |

860 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

862 | iterator |

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

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

865 | |

866 | template<typename _Pair, typename = typename |

867 | std::enable_if<std::is_constructible<value_type, |

868 | _Pair&&>::value>::type> |

869 | iterator |

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

871 | { return _M_t._M_insert_unique_(__position, |

872 | std::forward<_Pair>(__x)); } |

873 | #endif |

874 | // @} |

875 | |

876 | /** |

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

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

879 | * inserted. |

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

881 | * |

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

883 | */ |

884 | template<typename _InputIterator> |

885 | void |

886 | insert(_InputIterator __first, _InputIterator __last) |

887 | { _M_t._M_insert_unique(__first, __last); } |

888 | |

889 | #if __cplusplus > 201402L |

890 | #define __cpp_lib_map_insertion 201411 |

891 | /** |

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

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

894 | * the map. |

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

896 | * instance. |

897 | * |

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

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

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

901 | * |

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

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

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

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

906 | * is assigned from __obj. |

907 | * |

908 | * Insertion requires logarithmic time. |

909 | */ |

910 | template <typename _Obj> |

911 | pair<iterator, bool> |

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

913 | { |

914 | iterator __i = lower_bound(__k); |

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

916 | { |

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

918 | std::forward_as_tuple(__k), |

919 | std::forward_as_tuple( |

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

921 | return {__i, true}; |

922 | } |

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

924 | return {__i, false}; |

925 | } |

926 | |

927 | // move-capable overload |

928 | template <typename _Obj> |

929 | pair<iterator, bool> |

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

931 | { |

932 | iterator __i = lower_bound(__k); |

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

934 | { |

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

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

937 | std::forward_as_tuple( |

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

939 | return {__i, true}; |

940 | } |

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

942 | return {__i, false}; |

943 | } |

944 | |

945 | /** |

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

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

948 | * pair should be inserted. |

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

950 | * the map. |

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

952 | * instance. |

953 | * |

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

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

956 | * |

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

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

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

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

961 | * is assigned from __obj. |

962 | * |

963 | * Insertion requires logarithmic time. |

964 | */ |

965 | template <typename _Obj> |

966 | iterator |

967 | insert_or_assign(const_iterator __hint, |

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

969 | { |

970 | iterator __i; |

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

972 | if (__true_hint.second) |

973 | { |

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

975 | std::piecewise_construct, |

976 | std::forward_as_tuple(__k), |

977 | std::forward_as_tuple( |

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

979 | } |

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

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

982 | return __i; |

983 | } |

984 | |

985 | // move-capable overload |

986 | template <typename _Obj> |

987 | iterator |

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

989 | { |

990 | iterator __i; |

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

992 | if (__true_hint.second) |

993 | { |

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

995 | std::piecewise_construct, |

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

997 | std::forward_as_tuple( |

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

999 | } |

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

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

1002 | return __i; |

1003 | } |

1004 | #endif |

1005 | |

1006 | #if __cplusplus >= 201103L |

1007 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1009 | /** |

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

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

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

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

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

1015 | * |

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

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

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

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

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

1021 | * |

1022 | * @{ |

1023 | */ |

1024 | iterator |

1025 | erase(const_iterator __position) |

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

1027 | |

1028 | // LWG 2059 |

1029 | _GLIBCXX_ABI_TAG_CXX11 |

1030 | iterator |

1031 | erase(iterator __position) |

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

1033 | // @} |

1034 | #else |

1035 | /** |

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

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

1038 | * |

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

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

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

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

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

1044 | */ |

1045 | void |

1046 | erase(iterator __position) |

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

1048 | #endif |

1049 | |

1050 | /** |

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

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

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

1054 | * |

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

1056 | * a %map. |

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

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

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

1060 | */ |

1061 | size_type |

1062 | erase(const key_type& __x) |

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

1064 | |

1065 | #if __cplusplus >= 201103L |

1066 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1068 | /** |

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

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

1071 | * erased. |

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

1073 | * be erased. |

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

1075 | * |

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

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

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

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

1080 | */ |

1081 | iterator |

1082 | erase(const_iterator __first, const_iterator __last) |

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

1084 | #else |

1085 | /** |

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

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

1088 | * erased. |

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

1090 | * be erased. |

1091 | * |

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

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

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

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

1096 | */ |

1097 | void |

1098 | erase(iterator __first, iterator __last) |

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

1100 | #endif |

1101 | |

1102 | /** |

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

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

1105 | * |

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

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

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

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

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

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

1112 | * |

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

1114 | */ |

1115 | void |

1116 | swap(map& __x) |

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

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

1119 | |

1120 | /** |

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

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

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

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

1125 | */ |

1126 | void |

1127 | clear() _GLIBCXX_NOEXCEPT |

1128 | { _M_t.clear(); } |

1129 | |

1130 | // observers |

1131 | /** |

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

1133 | * constructed. |

1134 | */ |

1135 | key_compare |

1136 | key_comp() const |

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

1138 | |

1139 | /** |

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

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

1142 | */ |

1143 | value_compare |

1144 | value_comp() const |

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

1146 | |

1147 | // [23.3.1.3] map operations |

1148 | |

1149 | //@{ |

1150 | /** |

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

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

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

1154 | * found. |

1155 | * |

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

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

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

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

1160 | */ |

1161 | |

1162 | iterator |

1163 | find(const key_type& __x) |

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

1165 | |

1166 | #if __cplusplus > 201103L |

1167 | template<typename _Kt> |

1168 | auto |

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

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

1171 | #endif |

1172 | //@} |

1173 | |

1174 | //@{ |

1175 | /** |

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

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

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

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

1180 | * |

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

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

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

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

1185 | */ |

1186 | |

1187 | const_iterator |

1188 | find(const key_type& __x) const |

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

1190 | |

1191 | #if __cplusplus > 201103L |

1192 | template<typename _Kt> |

1193 | auto |

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

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

1196 | #endif |

1197 | //@} |

1198 | |

1199 | //@{ |

1200 | /** |

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

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

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

1204 | * |

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

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

1207 | */ |

1208 | size_type |

1209 | count(const key_type& __x) const |

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

1211 | |

1212 | #if __cplusplus > 201103L |

1213 | template<typename _Kt> |

1214 | auto |

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

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

1217 | #endif |

1218 | //@} |

1219 | |

1220 | //@{ |

1221 | /** |

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

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

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

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

1226 | * |

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

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

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

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

1231 | */ |

1232 | iterator |

1233 | lower_bound(const key_type& __x) |

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

1235 | |

1236 | #if __cplusplus > 201103L |

1237 | template<typename _Kt> |

1238 | auto |

1239 | lower_bound(const _Kt& __x) |

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

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

1242 | #endif |

1243 | //@} |

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 Read-only (constant) iterator pointing to first element |

1250 | * equal to or greater 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 | const_iterator |

1258 | lower_bound(const key_type& __x) const |

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

1260 | |

1261 | #if __cplusplus > 201103L |

1262 | template<typename _Kt> |

1263 | auto |

1264 | lower_bound(const _Kt& __x) const |

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

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

1267 | #endif |

1268 | //@} |

1269 | |

1270 | //@{ |

1271 | /** |

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

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

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

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

1276 | */ |

1277 | iterator |

1278 | upper_bound(const key_type& __x) |

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

1280 | |

1281 | #if __cplusplus > 201103L |

1282 | template<typename _Kt> |

1283 | auto |

1284 | upper_bound(const _Kt& __x) |

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

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

1287 | #endif |

1288 | //@} |

1289 | |

1290 | //@{ |

1291 | /** |

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

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

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

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

1296 | */ |

1297 | const_iterator |

1298 | upper_bound(const key_type& __x) const |

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

1300 | |

1301 | #if __cplusplus > 201103L |

1302 | template<typename _Kt> |

1303 | auto |

1304 | upper_bound(const _Kt& __x) const |

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

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

1307 | #endif |

1308 | //@} |

1309 | |

1310 | //@{ |

1311 | /** |

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

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

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

1315 | * matching given key. |

1316 | * |

1317 | * This function is equivalent to |

1318 | * @code |

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

1320 | * c.upper_bound(val)) |

1321 | * @endcode |

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

1323 | * |

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

1325 | */ |

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

1327 | equal_range(const key_type& __x) |

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

1329 | |

1330 | #if __cplusplus > 201103L |

1331 | template<typename _Kt> |

1332 | auto |

1333 | equal_range(const _Kt& __x) |

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

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

1336 | #endif |

1337 | //@} |

1338 | |

1339 | //@{ |

1340 | /** |

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

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

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

1344 | * to the subsequence matching given key. |

1345 | * |

1346 | * This function is equivalent to |

1347 | * @code |

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

1349 | * c.upper_bound(val)) |

1350 | * @endcode |

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

1352 | * |

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

1354 | */ |

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

1356 | equal_range(const key_type& __x) const |

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

1358 | |

1359 | #if __cplusplus > 201103L |

1360 | template<typename _Kt> |

1361 | auto |

1362 | equal_range(const _Kt& __x) const |

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

1364 | _M_t._M_equal_range_tr(__x))) |

1365 | { |

1366 | return pair<const_iterator, const_iterator>( |

1367 | _M_t._M_equal_range_tr(__x)); |

1368 | } |

1369 | #endif |

1370 | //@} |

1371 | |

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

1373 | friend bool |

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

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

1376 | |

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

1378 | friend bool |

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

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

1381 | }; |

1382 | |

1383 | /** |

1384 | * @brief Map equality comparison. |

1385 | * @param __x A %map. |

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

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

1388 | * |

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

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

1391 | * and if corresponding elements compare equal. |

1392 | */ |

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

1394 | inline bool |

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

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

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

1398 | |

1399 | /** |

1400 | * @brief Map ordering relation. |

1401 | * @param __x A %map. |

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

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

1404 | * |

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

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

1407 | * |

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

1409 | */ |

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

1411 | inline bool |

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

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

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

1415 | |

1416 | /// Based on operator== |

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

1418 | inline bool |

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

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

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

1422 | |

1423 | /// Based on operator< |

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

1425 | inline bool |

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

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

1428 | { return __y < __x; } |

1429 | |

1430 | /// Based on operator< |

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

1432 | inline bool |

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

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

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

1436 | |

1437 | /// Based on operator< |

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

1439 | inline bool |

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

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

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

1443 | |

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

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

1446 | inline void |

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

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

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

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

1451 | |

1452 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1453 | |

1454 | #if __cplusplus > 201402L |

1455 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

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

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

1458 | typename _Cmp2> |

1459 | struct |

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

1461 | _Cmp2> |

1462 | { |

1463 | private: |

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

1465 | |

1466 | static auto& |

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

1468 | { return __map._M_t; } |

1469 | |

1470 | static auto& |

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

1472 | { return __map._M_t; } |

1473 | }; |

1474 | _GLIBCXX_END_NAMESPACE_VERSION |

1475 | #endif // C++17 |

1476 | |

1477 | } // namespace std |

1478 | |

1479 | #endif /* _STL_MAP_H */ |

1480 |