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

2 | |

3 | // Copyright (C) 2001-2018 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_multimap.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_MULTIMAP_H |

57 | #define _STL_MULTIMAP_H 1 |

58 | |

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

60 | #if __cplusplus >= 201103L |

61 | #include <initializer_list> |

62 | #endif |

63 | |

64 | namespace std _GLIBCXX_VISIBILITY(default) |

65 | { |

66 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

67 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

68 | |

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

70 | class map; |

71 | |

72 | /** |

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

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

75 | * |

76 | * @ingroup associative_containers |

77 | * |

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

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

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

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

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

83 | * |

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

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

86 | * <a href="tables.html#69">associative container</a> (using equivalent |

87 | * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type |

88 | * is T, and the value_type is std::pair<const Key,T>. |

89 | * |

90 | * Multimaps support bidirectional iterators. |

91 | * |

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

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

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

95 | */ |

96 | template <typename _Key, typename _Tp, |

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

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

99 | class multimap |

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 | #if __cplusplus >= 201103L && defined(__STRICT_ANSI__) |

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

122 | "std::multimap must have the same value_type as its allocator"); |

123 | #endif |

124 | |

125 | public: |

126 | class value_compare |

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

128 | { |

129 | friend class multimap<_Key, _Tp, _Compare, _Alloc>; |

130 | protected: |

131 | _Compare comp; |

132 | |

133 | value_compare(_Compare __c) |

134 | : comp(__c) { } |

135 | |

136 | public: |

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

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

139 | }; |

140 | |

141 | private: |

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

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

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

145 | |

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

147 | key_compare, _Pair_alloc_type> _Rep_type; |

148 | /// The actual tree structure. |

149 | _Rep_type _M_t; |

150 | |

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

152 | |

153 | public: |

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

155 | // "functionally equivalent" |

156 | typedef typename _Alloc_traits::pointer pointer; |

157 | typedef typename _Alloc_traits::const_pointer const_pointer; |

158 | typedef typename _Alloc_traits::reference reference; |

159 | typedef typename _Alloc_traits::const_reference const_reference; |

160 | typedef typename _Rep_type::iterator iterator; |

161 | typedef typename _Rep_type::const_iterator const_iterator; |

162 | typedef typename _Rep_type::size_type size_type; |

163 | typedef typename _Rep_type::difference_type difference_type; |

164 | typedef typename _Rep_type::reverse_iterator reverse_iterator; |

165 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

166 | |

167 | #if __cplusplus > 201402L |

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

169 | #endif |

170 | |

171 | // [23.3.2] construct/copy/destroy |

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

173 | |

174 | /** |

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

176 | */ |

177 | #if __cplusplus < 201103L |

178 | multimap() : _M_t() { } |

179 | #else |

180 | multimap() = default; |

181 | #endif |

182 | |

183 | /** |

184 | * @brief Creates a %multimap with no elements. |

185 | * @param __comp A comparison object. |

186 | * @param __a An allocator object. |

187 | */ |

188 | explicit |

189 | multimap(const _Compare& __comp, |

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

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

192 | |

193 | /** |

194 | * @brief %Multimap copy constructor. |

195 | * |

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

197 | */ |

198 | #if __cplusplus < 201103L |

199 | multimap(const multimap& __x) |

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

201 | #else |

202 | multimap(const multimap&) = default; |

203 | |

204 | /** |

205 | * @brief %Multimap move constructor. |

206 | * |

207 | * The newly-created %multimap contains the exact contents of the |

208 | * moved instance. The moved instance is a valid, but unspecified |

209 | * %multimap. |

210 | */ |

211 | multimap(multimap&&) = default; |

212 | |

213 | /** |

214 | * @brief Builds a %multimap from an initializer_list. |

215 | * @param __l An initializer_list. |

216 | * @param __comp A comparison functor. |

217 | * @param __a An allocator object. |

218 | * |

219 | * Create a %multimap consisting of copies of the elements from |

220 | * the initializer_list. This is linear in N if the list is already |

221 | * sorted, and NlogN otherwise (where N is @a __l.size()). |

222 | */ |

223 | multimap(initializer_list<value_type> __l, |

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

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

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

227 | { _M_t._M_insert_equal(__l.begin(), __l.end()); } |

228 | |

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

230 | explicit |

231 | multimap(const allocator_type& __a) |

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

233 | |

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

235 | multimap(const multimap& __m, const allocator_type& __a) |

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

237 | |

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

239 | multimap(multimap&& __m, const allocator_type& __a) |

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

241 | && _Alloc_traits::_S_always_equal()) |

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

243 | |

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

245 | multimap(initializer_list<value_type> __l, const allocator_type& __a) |

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

247 | { _M_t._M_insert_equal(__l.begin(), __l.end()); } |

248 | |

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

250 | template<typename _InputIterator> |

251 | multimap(_InputIterator __first, _InputIterator __last, |

252 | const allocator_type& __a) |

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

254 | { _M_t._M_insert_equal(__first, __last); } |

255 | #endif |

256 | |

257 | /** |

258 | * @brief Builds a %multimap from a range. |

259 | * @param __first An input iterator. |

260 | * @param __last An input iterator. |

261 | * |

262 | * Create a %multimap consisting of copies of the elements from |

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

264 | * and NlogN otherwise (where N is distance(__first,__last)). |

265 | */ |

266 | template<typename _InputIterator> |

267 | multimap(_InputIterator __first, _InputIterator __last) |

268 | : _M_t() |

269 | { _M_t._M_insert_equal(__first, __last); } |

270 | |

271 | /** |

272 | * @brief Builds a %multimap from a range. |

273 | * @param __first An input iterator. |

274 | * @param __last An input iterator. |

275 | * @param __comp A comparison functor. |

276 | * @param __a An allocator object. |

277 | * |

278 | * Create a %multimap consisting of copies of the elements from |

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

280 | * and NlogN otherwise (where N is distance(__first,__last)). |

281 | */ |

282 | template<typename _InputIterator> |

283 | multimap(_InputIterator __first, _InputIterator __last, |

284 | const _Compare& __comp, |

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

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

287 | { _M_t._M_insert_equal(__first, __last); } |

288 | |

289 | #if __cplusplus >= 201103L |

290 | /** |

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

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

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

294 | */ |

295 | ~multimap() = default; |

296 | #endif |

297 | |

298 | /** |

299 | * @brief %Multimap assignment operator. |

300 | * |

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

302 | */ |

303 | #if __cplusplus < 201103L |

304 | multimap& |

305 | operator=(const multimap& __x) |

306 | { |

307 | _M_t = __x._M_t; |

308 | return *this; |

309 | } |

310 | #else |

311 | multimap& |

312 | operator=(const multimap&) = default; |

313 | |

314 | /// Move assignment operator. |

315 | multimap& |

316 | operator=(multimap&&) = default; |

317 | |

318 | /** |

319 | * @brief %Multimap list assignment operator. |

320 | * @param __l An initializer_list. |

321 | * |

322 | * This function fills a %multimap with copies of the elements |

323 | * in the initializer list @a __l. |

324 | * |

325 | * Note that the assignment completely changes the %multimap and |

326 | * that the resulting %multimap's size is the same as the number |

327 | * of elements assigned. |

328 | */ |

329 | multimap& |

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

331 | { |

332 | _M_t._M_assign_equal(__l.begin(), __l.end()); |

333 | return *this; |

334 | } |

335 | #endif |

336 | |

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

338 | allocator_type |

339 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

341 | |

342 | // iterators |

343 | /** |

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

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

346 | * keys. |

347 | */ |

348 | iterator |

349 | begin() _GLIBCXX_NOEXCEPT |

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

351 | |

352 | /** |

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

354 | * in the %multimap. Iteration is done in ascending order according to |

355 | * the keys. |

356 | */ |

357 | const_iterator |

358 | begin() const _GLIBCXX_NOEXCEPT |

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

360 | |

361 | /** |

362 | * Returns a read/write iterator that points one past the last pair in |

363 | * the %multimap. Iteration is done in ascending order according to the |

364 | * keys. |

365 | */ |

366 | iterator |

367 | end() _GLIBCXX_NOEXCEPT |

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

369 | |

370 | /** |

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

372 | * pair in the %multimap. Iteration is done in ascending order according |

373 | * to the keys. |

374 | */ |

375 | const_iterator |

376 | end() const _GLIBCXX_NOEXCEPT |

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

378 | |

379 | /** |

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

381 | * the %multimap. Iteration is done in descending order according to the |

382 | * keys. |

383 | */ |

384 | reverse_iterator |

385 | rbegin() _GLIBCXX_NOEXCEPT |

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

387 | |

388 | /** |

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

390 | * last pair in the %multimap. Iteration is done in descending order |

391 | * according to the keys. |

392 | */ |

393 | const_reverse_iterator |

394 | rbegin() const _GLIBCXX_NOEXCEPT |

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

396 | |

397 | /** |

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

399 | * first pair in the %multimap. Iteration is done in descending order |

400 | * according to the keys. |

401 | */ |

402 | reverse_iterator |

403 | rend() _GLIBCXX_NOEXCEPT |

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

405 | |

406 | /** |

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

408 | * before the first pair in the %multimap. Iteration is done in |

409 | * descending order according to the keys. |

410 | */ |

411 | const_reverse_iterator |

412 | rend() const _GLIBCXX_NOEXCEPT |

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

414 | |

415 | #if __cplusplus >= 201103L |

416 | /** |

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

418 | * in the %multimap. Iteration is done in ascending order according to |

419 | * the keys. |

420 | */ |

421 | const_iterator |

422 | cbegin() const noexcept |

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

424 | |

425 | /** |

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

427 | * pair in the %multimap. Iteration is done in ascending order according |

428 | * to the keys. |

429 | */ |

430 | const_iterator |

431 | cend() const noexcept |

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

433 | |

434 | /** |

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

436 | * last pair in the %multimap. Iteration is done in descending order |

437 | * according to the keys. |

438 | */ |

439 | const_reverse_iterator |

440 | crbegin() const noexcept |

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

442 | |

443 | /** |

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

445 | * before the first pair in the %multimap. Iteration is done in |

446 | * descending order according to the keys. |

447 | */ |

448 | const_reverse_iterator |

449 | crend() const noexcept |

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

451 | #endif |

452 | |

453 | // capacity |

454 | /** Returns true if the %multimap is empty. */ |

455 | bool |

456 | empty() const _GLIBCXX_NOEXCEPT |

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

458 | |

459 | /** Returns the size of the %multimap. */ |

460 | size_type |

461 | size() const _GLIBCXX_NOEXCEPT |

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

463 | |

464 | /** Returns the maximum size of the %multimap. */ |

465 | size_type |

466 | max_size() const _GLIBCXX_NOEXCEPT |

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

468 | |

469 | // modifiers |

470 | #if __cplusplus >= 201103L |

471 | /** |

472 | * @brief Build and insert a std::pair into the %multimap. |

473 | * |

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

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

476 | * part of the pair constructor). |

477 | * |

478 | * @return An iterator that points to the inserted (key,value) pair. |

479 | * |

480 | * This function builds and inserts a (key, value) %pair into the |

481 | * %multimap. |

482 | * Contrary to a std::map the %multimap does not rely on unique keys and |

483 | * thus multiple pairs with the same key can be inserted. |

484 | * |

485 | * Insertion requires logarithmic time. |

486 | */ |

487 | template<typename... _Args> |

488 | iterator |

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

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

491 | |

492 | /** |

493 | * @brief Builds and inserts a std::pair into the %multimap. |

494 | * |

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

496 | * should be inserted. |

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

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

499 | * part of the pair constructor). |

500 | * @return An iterator that points to the inserted (key,value) pair. |

501 | * |

502 | * This function inserts a (key, value) pair into the %multimap. |

503 | * Contrary to a std::map the %multimap does not rely on unique keys and |

504 | * thus multiple pairs with the same key can be inserted. |

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

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

507 | * cause no gains in efficiency. |

508 | * |

509 | * For more on @a hinting, see: |

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

511 | * |

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

513 | */ |

514 | template<typename... _Args> |

515 | iterator |

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

517 | { |

518 | return _M_t._M_emplace_hint_equal(__pos, |

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

520 | } |

521 | #endif |

522 | |

523 | /** |

524 | * @brief Inserts a std::pair into the %multimap. |

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

526 | * of pairs). |

527 | * @return An iterator that points to the inserted (key,value) pair. |

528 | * |

529 | * This function inserts a (key, value) pair into the %multimap. |

530 | * Contrary to a std::map the %multimap does not rely on unique keys and |

531 | * thus multiple pairs with the same key can be inserted. |

532 | * |

533 | * Insertion requires logarithmic time. |

534 | * @{ |

535 | */ |

536 | iterator |

537 | insert(const value_type& __x) |

538 | { return _M_t._M_insert_equal(__x); } |

539 | |

540 | #if __cplusplus >= 201103L |

541 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

543 | iterator |

544 | insert(value_type&& __x) |

545 | { return _M_t._M_insert_equal(std::move(__x)); } |

546 | |

547 | template<typename _Pair> |

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

549 | insert(_Pair&& __x) |

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

551 | #endif |

552 | // @} |

553 | |

554 | /** |

555 | * @brief Inserts a std::pair into the %multimap. |

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

557 | * pair should be inserted. |

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

559 | * of pairs). |

560 | * @return An iterator that points to the inserted (key,value) pair. |

561 | * |

562 | * This function inserts a (key, value) pair into the %multimap. |

563 | * Contrary to a std::map the %multimap does not rely on unique keys and |

564 | * thus multiple pairs with the same key can be inserted. |

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

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

567 | * cause no gains in efficiency. |

568 | * |

569 | * For more on @a hinting, see: |

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

571 | * |

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

573 | * @{ |

574 | */ |

575 | iterator |

576 | #if __cplusplus >= 201103L |

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

578 | #else |

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

580 | #endif |

581 | { return _M_t._M_insert_equal_(__position, __x); } |

582 | |

583 | #if __cplusplus >= 201103L |

584 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

586 | iterator |

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

588 | { return _M_t._M_insert_equal_(__position, std::move(__x)); } |

589 | |

590 | template<typename _Pair> |

591 | __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> |

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

593 | { |

594 | return _M_t._M_emplace_hint_equal(__position, |

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

596 | } |

597 | #endif |

598 | // @} |

599 | |

600 | /** |

601 | * @brief A template function that attempts to insert a range |

602 | * of elements. |

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

604 | * inserted. |

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

606 | * |

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

608 | */ |

609 | template<typename _InputIterator> |

610 | void |

611 | insert(_InputIterator __first, _InputIterator __last) |

612 | { _M_t._M_insert_equal(__first, __last); } |

613 | |

614 | #if __cplusplus >= 201103L |

615 | /** |

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

617 | * @param __l A std::initializer_list<value_type> of pairs to be |

618 | * inserted. |

619 | * |

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

621 | */ |

622 | void |

623 | insert(initializer_list<value_type> __l) |

624 | { this->insert(__l.begin(), __l.end()); } |

625 | #endif |

626 | |

627 | #if __cplusplus > 201402L |

628 | /// Extract a node. |

629 | node_type |

630 | extract(const_iterator __pos) |

631 | { |

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

633 | return _M_t.extract(__pos); |

634 | } |

635 | |

636 | /// Extract a node. |

637 | node_type |

638 | extract(const key_type& __x) |

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

640 | |

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

642 | iterator |

643 | insert(node_type&& __nh) |

644 | { return _M_t._M_reinsert_node_equal(std::move(__nh)); } |

645 | |

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

647 | iterator |

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

649 | { return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); } |

650 | |

651 | template<typename, typename> |

652 | friend class std::_Rb_tree_merge_helper; |

653 | |

654 | template<typename _C2> |

655 | void |

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

657 | { |

658 | using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>; |

659 | _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); |

660 | } |

661 | |

662 | template<typename _C2> |

663 | void |

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

665 | { merge(__source); } |

666 | |

667 | template<typename _C2> |

668 | void |

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

670 | { |

671 | using _Merge_helper = _Rb_tree_merge_helper<multimap, _C2>; |

672 | _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source)); |

673 | } |

674 | |

675 | template<typename _C2> |

676 | void |

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

678 | { merge(__source); } |

679 | #endif // C++17 |

680 | |

681 | #if __cplusplus >= 201103L |

682 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

684 | /** |

685 | * @brief Erases an element from a %multimap. |

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

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

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

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

690 | * |

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

692 | * from a %multimap. Note that this function only erases the element, |

693 | * and that if the element is itself a pointer, the pointed-to memory is |

694 | * not touched in any way. Managing the pointer is the user's |

695 | * responsibility. |

696 | * |

697 | * @{ |

698 | */ |

699 | iterator |

700 | erase(const_iterator __position) |

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

702 | |

703 | // LWG 2059. |

704 | _GLIBCXX_ABI_TAG_CXX11 |

705 | iterator |

706 | erase(iterator __position) |

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

708 | // @} |

709 | #else |

710 | /** |

711 | * @brief Erases an element from a %multimap. |

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

713 | * |

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

715 | * from a %multimap. Note that this function only erases the element, |

716 | * and that if the element is itself a pointer, the pointed-to memory is |

717 | * not touched in any way. Managing the pointer is the user's |

718 | * responsibility. |

719 | */ |

720 | void |

721 | erase(iterator __position) |

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

723 | #endif |

724 | |

725 | /** |

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

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

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

729 | * |

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

731 | * %multimap. |

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

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

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

735 | */ |

736 | size_type |

737 | erase(const key_type& __x) |

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

739 | |

740 | #if __cplusplus >= 201103L |

741 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

743 | /** |

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

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

746 | * erased. |

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

748 | * erased . |

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

750 | * |

751 | * This function erases a sequence of elements from a %multimap. |

752 | * Note that this function only erases the elements, and that if |

753 | * the elements themselves are pointers, the pointed-to memory is not |

754 | * touched in any way. Managing the pointer is the user's |

755 | * responsibility. |

756 | */ |

757 | iterator |

758 | erase(const_iterator __first, const_iterator __last) |

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

760 | #else |

761 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

763 | /** |

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

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

766 | * erased. |

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

768 | * be erased. |

769 | * |

770 | * This function erases a sequence of elements from a %multimap. |

771 | * Note that this function only erases the elements, and that if |

772 | * the elements themselves are pointers, the pointed-to memory is not |

773 | * touched in any way. Managing the pointer is the user's |

774 | * responsibility. |

775 | */ |

776 | void |

777 | erase(iterator __first, iterator __last) |

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

779 | #endif |

780 | |

781 | /** |

782 | * @brief Swaps data with another %multimap. |

783 | * @param __x A %multimap of the same element and allocator types. |

784 | * |

785 | * This exchanges the elements between two multimaps in constant time. |

786 | * (It is only swapping a pointer, an integer, and an instance of |

787 | * the @c Compare type (which itself is often stateless and empty), so it |

788 | * should be quite fast.) |

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

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

791 | * |

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

793 | */ |

794 | void |

795 | swap(multimap& __x) |

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

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

798 | |

799 | /** |

800 | * Erases all elements in a %multimap. Note that this function only |

801 | * erases the elements, and that if the elements themselves are pointers, |

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

803 | * is the user's responsibility. |

804 | */ |

805 | void |

806 | clear() _GLIBCXX_NOEXCEPT |

807 | { _M_t.clear(); } |

808 | |

809 | // observers |

810 | /** |

811 | * Returns the key comparison object out of which the %multimap |

812 | * was constructed. |

813 | */ |

814 | key_compare |

815 | key_comp() const |

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

817 | |

818 | /** |

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

820 | * object out of which the %multimap was constructed. |

821 | */ |

822 | value_compare |

823 | value_comp() const |

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

825 | |

826 | // multimap operations |

827 | |

828 | //@{ |

829 | /** |

830 | * @brief Tries to locate an element in a %multimap. |

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

832 | * @return Iterator pointing to sought-after element, |

833 | * or end() if not found. |

834 | * |

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

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

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

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

839 | */ |

840 | iterator |

841 | find(const key_type& __x) |

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

843 | |

844 | #if __cplusplus > 201103L |

845 | template<typename _Kt> |

846 | auto |

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

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

849 | #endif |

850 | //@} |

851 | |

852 | //@{ |

853 | /** |

854 | * @brief Tries to locate an element in a %multimap. |

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

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

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

858 | * |

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

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

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

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

863 | */ |

864 | const_iterator |

865 | find(const key_type& __x) const |

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

867 | |

868 | #if __cplusplus > 201103L |

869 | template<typename _Kt> |

870 | auto |

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

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

873 | #endif |

874 | //@} |

875 | |

876 | //@{ |

877 | /** |

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

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

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

881 | */ |

882 | size_type |

883 | count(const key_type& __x) const |

884 | { return _M_t.count(__x); } |

885 | |

886 | #if __cplusplus > 201103L |

887 | template<typename _Kt> |

888 | auto |

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

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

891 | #endif |

892 | //@} |

893 | |

894 | //@{ |

895 | /** |

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

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

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

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

900 | * |

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

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

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

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

905 | */ |

906 | iterator |

907 | lower_bound(const key_type& __x) |

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

909 | |

910 | #if __cplusplus > 201103L |

911 | template<typename _Kt> |

912 | auto |

913 | lower_bound(const _Kt& __x) |

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

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

916 | #endif |

917 | //@} |

918 | |

919 | //@{ |

920 | /** |

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

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

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

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

925 | * |

926 | * This function returns the first element of a subsequence of |

927 | * elements that matches the given key. If unsuccessful the |

928 | * iterator will point to the next greatest element or, if no |

929 | * such greater element exists, to end(). |

930 | */ |

931 | const_iterator |

932 | lower_bound(const key_type& __x) const |

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

934 | |

935 | #if __cplusplus > 201103L |

936 | template<typename _Kt> |

937 | auto |

938 | lower_bound(const _Kt& __x) const |

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

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

941 | #endif |

942 | //@} |

943 | |

944 | //@{ |

945 | /** |

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

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

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

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

950 | */ |

951 | iterator |

952 | upper_bound(const key_type& __x) |

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

954 | |

955 | #if __cplusplus > 201103L |

956 | template<typename _Kt> |

957 | auto |

958 | upper_bound(const _Kt& __x) |

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

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

961 | #endif |

962 | //@} |

963 | |

964 | //@{ |

965 | /** |

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

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

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

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

970 | */ |

971 | const_iterator |

972 | upper_bound(const key_type& __x) const |

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

974 | |

975 | #if __cplusplus > 201103L |

976 | template<typename _Kt> |

977 | auto |

978 | upper_bound(const _Kt& __x) const |

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

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

981 | #endif |

982 | //@} |

983 | |

984 | //@{ |

985 | /** |

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

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

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

989 | * matching given key. |

990 | * |

991 | * This function is equivalent to |

992 | * @code |

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

994 | * c.upper_bound(val)) |

995 | * @endcode |

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

997 | */ |

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

999 | equal_range(const key_type& __x) |

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

1001 | |

1002 | #if __cplusplus > 201103L |

1003 | template<typename _Kt> |

1004 | auto |

1005 | equal_range(const _Kt& __x) |

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

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

1008 | #endif |

1009 | //@} |

1010 | |

1011 | //@{ |

1012 | /** |

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

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

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

1016 | * to the subsequence matching given key. |

1017 | * |

1018 | * This function is equivalent to |

1019 | * @code |

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

1021 | * c.upper_bound(val)) |

1022 | * @endcode |

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

1024 | */ |

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

1026 | equal_range(const key_type& __x) const |

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

1028 | |

1029 | #if __cplusplus > 201103L |

1030 | template<typename _Kt> |

1031 | auto |

1032 | equal_range(const _Kt& __x) const |

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

1034 | _M_t._M_equal_range_tr(__x))) |

1035 | { |

1036 | return pair<const_iterator, const_iterator>( |

1037 | _M_t._M_equal_range_tr(__x)); |

1038 | } |

1039 | #endif |

1040 | //@} |

1041 | |

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

1043 | friend bool |

1044 | operator==(const multimap<_K1, _T1, _C1, _A1>&, |

1045 | const multimap<_K1, _T1, _C1, _A1>&); |

1046 | |

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

1048 | friend bool |

1049 | operator<(const multimap<_K1, _T1, _C1, _A1>&, |

1050 | const multimap<_K1, _T1, _C1, _A1>&); |

1051 | }; |

1052 | |

1053 | #if __cpp_deduction_guides >= 201606 |

1054 | |

1055 | template<typename _InputIterator, |

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

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

1058 | typename = _RequireInputIter<_InputIterator>, |

1059 | typename = _RequireAllocator<_Allocator>> |

1060 | multimap(_InputIterator, _InputIterator, |

1061 | _Compare = _Compare(), _Allocator = _Allocator()) |

1062 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |

1063 | _Compare, _Allocator>; |

1064 | |

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

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

1067 | typename = _RequireAllocator<_Allocator>> |

1068 | multimap(initializer_list<pair<_Key, _Tp>>, |

1069 | _Compare = _Compare(), _Allocator = _Allocator()) |

1070 | -> multimap<_Key, _Tp, _Compare, _Allocator>; |

1071 | |

1072 | template<typename _InputIterator, typename _Allocator, |

1073 | typename = _RequireInputIter<_InputIterator>, |

1074 | typename = _RequireAllocator<_Allocator>> |

1075 | multimap(_InputIterator, _InputIterator, _Allocator) |

1076 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |

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

1078 | |

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

1080 | typename = _RequireAllocator<_Allocator>> |

1081 | multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) |

1082 | -> multimap<_Key, _Tp, less<_Key>, _Allocator>; |

1083 | |

1084 | #endif |

1085 | |

1086 | /** |

1087 | * @brief Multimap equality comparison. |

1088 | * @param __x A %multimap. |

1089 | * @param __y A %multimap of the same type as @a __x. |

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

1091 | * |

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

1093 | * multimaps. Multimaps are considered equivalent if their sizes are equal, |

1094 | * and if corresponding elements compare equal. |

1095 | */ |

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

1097 | inline bool |

1098 | operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1099 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

1101 | |

1102 | /** |

1103 | * @brief Multimap ordering relation. |

1104 | * @param __x A %multimap. |

1105 | * @param __y A %multimap of the same type as @a __x. |

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

1107 | * |

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

1109 | * multimaps. The elements must be comparable with @c <. |

1110 | * |

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

1112 | */ |

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

1114 | inline bool |

1115 | operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1116 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

1118 | |

1119 | /// Based on operator== |

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

1121 | inline bool |

1122 | operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1123 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

1125 | |

1126 | /// Based on operator< |

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

1128 | inline bool |

1129 | operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1130 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

1131 | { return __y < __x; } |

1132 | |

1133 | /// Based on operator< |

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

1135 | inline bool |

1136 | operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1137 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

1139 | |

1140 | /// Based on operator< |

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

1142 | inline bool |

1143 | operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1144 | const multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

1146 | |

1147 | /// See std::multimap::swap(). |

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

1149 | inline void |

1150 | swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, |

1151 | multimap<_Key, _Tp, _Compare, _Alloc>& __y) |

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

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

1154 | |

1155 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1156 | |

1157 | #if __cplusplus > 201402L |

1158 | // Allow std::multimap access to internals of compatible maps. |

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

1160 | typename _Cmp2> |

1161 | struct |

1162 | _Rb_tree_merge_helper<_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>, |

1163 | _Cmp2> |

1164 | { |

1165 | private: |

1166 | friend class _GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp1, _Alloc>; |

1167 | |

1168 | static auto& |

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

1170 | { return __map._M_t; } |

1171 | |

1172 | static auto& |

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

1174 | { return __map._M_t; } |

1175 | }; |

1176 | #endif // C++17 |

1177 | |

1178 | _GLIBCXX_END_NAMESPACE_VERSION |

1179 | } // namespace std |

1180 | |

1181 | #endif /* _STL_MULTIMAP_H */ |

1182 |