1 | // Multiset 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 |

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_multiset.h |

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

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

54 | */ |

55 | |

56 | #ifndef _STL_MULTISET_H |

57 | #define _STL_MULTISET_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 _Compare, typename _Alloc> |

70 | class set; |

71 | |

72 | /** |

73 | * @brief A standard container made up of elements, which can be retrieved |

74 | * in logarithmic time. |

75 | * |

76 | * @ingroup associative_containers |

77 | * |

78 | * |

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

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

81 | * @tparam _Alloc Allocator type, defaults to allocator<_Key>. |

82 | * |

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

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

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

86 | * keys). For a @c multiset<Key> the key_type and value_type are Key. |

87 | * |

88 | * Multisets support bidirectional iterators. |

89 | * |

90 | * The private tree data is declared exactly the same way for set and |

91 | * multiset; the distinction is made entirely in how the tree functions are |

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

93 | */ |

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

95 | typename _Alloc = std::allocator<_Key> > |

96 | class multiset |

97 | { |

98 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

99 | // concept requirements |

100 | typedef typename _Alloc::value_type _Alloc_value_type; |

101 | # if __cplusplus < 201103L |

102 | __glibcxx_class_requires(_Key, _SGIAssignableConcept) |

103 | # endif |

104 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, |

105 | _BinaryFunctionConcept) |

106 | __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) |

107 | #endif |

108 | |

109 | #if __cplusplus >= 201103L |

110 | static_assert(is_same<typename remove_cv<_Key>::type, _Key>::value, |

111 | "std::multiset must have a non-const, non-volatile value_type"); |

112 | # ifdef __STRICT_ANSI__ |

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

114 | "std::multiset must have the same value_type as its allocator"); |

115 | # endif |

116 | #endif |

117 | |

118 | public: |

119 | // typedefs: |

120 | typedef _Key key_type; |

121 | typedef _Key value_type; |

122 | typedef _Compare key_compare; |

123 | typedef _Compare value_compare; |

124 | typedef _Alloc allocator_type; |

125 | |

126 | private: |

127 | /// This turns a red-black tree into a [multi]set. |

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

129 | rebind<_Key>::other _Key_alloc_type; |

130 | |

131 | typedef _Rb_tree<key_type, value_type, _Identity<value_type>, |

132 | key_compare, _Key_alloc_type> _Rep_type; |

133 | /// The actual tree structure. |

134 | _Rep_type _M_t; |

135 | |

136 | typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits; |

137 | |

138 | public: |

139 | typedef typename _Alloc_traits::pointer pointer; |

140 | typedef typename _Alloc_traits::const_pointer const_pointer; |

141 | typedef typename _Alloc_traits::reference reference; |

142 | typedef typename _Alloc_traits::const_reference const_reference; |

143 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

144 | // DR 103. set::iterator is required to be modifiable, |

145 | // but this allows modification of keys. |

146 | typedef typename _Rep_type::const_iterator iterator; |

147 | typedef typename _Rep_type::const_iterator const_iterator; |

148 | typedef typename _Rep_type::const_reverse_iterator reverse_iterator; |

149 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

150 | typedef typename _Rep_type::size_type size_type; |

151 | typedef typename _Rep_type::difference_type difference_type; |

152 | |

153 | #if __cplusplus > 201402L |

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

155 | #endif |

156 | |

157 | // allocation/deallocation |

158 | /** |

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

160 | */ |

161 | #if __cplusplus < 201103L |

162 | multiset() : _M_t() { } |

163 | #else |

164 | multiset() = default; |

165 | #endif |

166 | |

167 | /** |

168 | * @brief Creates a %multiset with no elements. |

169 | * @param __comp Comparator to use. |

170 | * @param __a An allocator object. |

171 | */ |

172 | explicit |

173 | multiset(const _Compare& __comp, |

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

175 | : _M_t(__comp, _Key_alloc_type(__a)) { } |

176 | |

177 | /** |

178 | * @brief Builds a %multiset from a range. |

179 | * @param __first An input iterator. |

180 | * @param __last An input iterator. |

181 | * |

182 | * Create a %multiset consisting of copies of the elements from |

183 | * [first,last). This is linear in N if the range is already sorted, |

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

185 | */ |

186 | template<typename _InputIterator> |

187 | multiset(_InputIterator __first, _InputIterator __last) |

188 | : _M_t() |

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

190 | |

191 | /** |

192 | * @brief Builds a %multiset from a range. |

193 | * @param __first An input iterator. |

194 | * @param __last An input iterator. |

195 | * @param __comp A comparison functor. |

196 | * @param __a An allocator object. |

197 | * |

198 | * Create a %multiset consisting of copies of the elements from |

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

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

201 | */ |

202 | template<typename _InputIterator> |

203 | multiset(_InputIterator __first, _InputIterator __last, |

204 | const _Compare& __comp, |

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

206 | : _M_t(__comp, _Key_alloc_type(__a)) |

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

208 | |

209 | /** |

210 | * @brief %Multiset copy constructor. |

211 | * |

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

213 | */ |

214 | #if __cplusplus < 201103L |

215 | multiset(const multiset& __x) |

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

217 | #else |

218 | multiset(const multiset&) = default; |

219 | |

220 | /** |

221 | * @brief %Multiset move constructor. |

222 | * |

223 | * The newly-created %multiset contains the exact contents of the |

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

225 | * %multiset. |

226 | */ |

227 | multiset(multiset&&) = default; |

228 | |

229 | /** |

230 | * @brief Builds a %multiset from an initializer_list. |

231 | * @param __l An initializer_list. |

232 | * @param __comp A comparison functor. |

233 | * @param __a An allocator object. |

234 | * |

235 | * Create a %multiset consisting of copies of the elements from |

236 | * the list. This is linear in N if the list is already sorted, |

237 | * and NlogN otherwise (where N is @a __l.size()). |

238 | */ |

239 | multiset(initializer_list<value_type> __l, |

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

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

242 | : _M_t(__comp, _Key_alloc_type(__a)) |

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

244 | |

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

246 | explicit |

247 | multiset(const allocator_type& __a) |

248 | : _M_t(_Compare(), _Key_alloc_type(__a)) { } |

249 | |

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

251 | multiset(const multiset& __m, const allocator_type& __a) |

252 | : _M_t(__m._M_t, _Key_alloc_type(__a)) { } |

253 | |

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

255 | multiset(multiset&& __m, const allocator_type& __a) |

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

257 | && _Alloc_traits::_S_always_equal()) |

258 | : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { } |

259 | |

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

261 | multiset(initializer_list<value_type> __l, const allocator_type& __a) |

262 | : _M_t(_Compare(), _Key_alloc_type(__a)) |

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

264 | |

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

266 | template<typename _InputIterator> |

267 | multiset(_InputIterator __first, _InputIterator __last, |

268 | const allocator_type& __a) |

269 | : _M_t(_Compare(), _Key_alloc_type(__a)) |

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

271 | |

272 | /** |

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

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

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

276 | */ |

277 | ~multiset() = default; |

278 | #endif |

279 | |

280 | /** |

281 | * @brief %Multiset assignment operator. |

282 | * |

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

284 | */ |

285 | #if __cplusplus < 201103L |

286 | multiset& |

287 | operator=(const multiset& __x) |

288 | { |

289 | _M_t = __x._M_t; |

290 | return *this; |

291 | } |

292 | #else |

293 | multiset& |

294 | operator=(const multiset&) = default; |

295 | |

296 | /// Move assignment operator. |

297 | multiset& |

298 | operator=(multiset&&) = default; |

299 | |

300 | /** |

301 | * @brief %Multiset list assignment operator. |

302 | * @param __l An initializer_list. |

303 | * |

304 | * This function fills a %multiset with copies of the elements in the |

305 | * initializer list @a __l. |

306 | * |

307 | * Note that the assignment completely changes the %multiset and |

308 | * that the resulting %multiset's size is the same as the number |

309 | * of elements assigned. |

310 | */ |

311 | multiset& |

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

313 | { |

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

315 | return *this; |

316 | } |

317 | #endif |

318 | |

319 | // accessors: |

320 | |

321 | /// Returns the comparison object. |

322 | key_compare |

323 | key_comp() const |

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

325 | /// Returns the comparison object. |

326 | value_compare |

327 | value_comp() const |

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

329 | /// Returns the memory allocation object. |

330 | allocator_type |

331 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

333 | |

334 | /** |

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

336 | * element in the %multiset. Iteration is done in ascending order |

337 | * according to the keys. |

338 | */ |

339 | iterator |

340 | begin() const _GLIBCXX_NOEXCEPT |

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

342 | |

343 | /** |

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

345 | * element in the %multiset. Iteration is done in ascending order |

346 | * according to the keys. |

347 | */ |

348 | iterator |

349 | end() const _GLIBCXX_NOEXCEPT |

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

351 | |

352 | /** |

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

354 | * last element in the %multiset. Iteration is done in descending order |

355 | * according to the keys. |

356 | */ |

357 | reverse_iterator |

358 | rbegin() const _GLIBCXX_NOEXCEPT |

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

360 | |

361 | /** |

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

363 | * last element in the %multiset. Iteration is done in descending order |

364 | * according to the keys. |

365 | */ |

366 | reverse_iterator |

367 | rend() const _GLIBCXX_NOEXCEPT |

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

369 | |

370 | #if __cplusplus >= 201103L |

371 | /** |

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

373 | * element in the %multiset. Iteration is done in ascending order |

374 | * according to the keys. |

375 | */ |

376 | iterator |

377 | cbegin() const noexcept |

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

379 | |

380 | /** |

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

382 | * element in the %multiset. Iteration is done in ascending order |

383 | * according to the keys. |

384 | */ |

385 | iterator |

386 | cend() const noexcept |

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

388 | |

389 | /** |

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

391 | * last element in the %multiset. Iteration is done in descending order |

392 | * according to the keys. |

393 | */ |

394 | reverse_iterator |

395 | crbegin() const noexcept |

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

397 | |

398 | /** |

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

400 | * last element in the %multiset. Iteration is done in descending order |

401 | * according to the keys. |

402 | */ |

403 | reverse_iterator |

404 | crend() const noexcept |

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

406 | #endif |

407 | |

408 | /// Returns true if the %set is empty. |

409 | bool |

410 | empty() const _GLIBCXX_NOEXCEPT |

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

412 | |

413 | /// Returns the size of the %set. |

414 | size_type |

415 | size() const _GLIBCXX_NOEXCEPT |

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

417 | |

418 | /// Returns the maximum size of the %set. |

419 | size_type |

420 | max_size() const _GLIBCXX_NOEXCEPT |

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

422 | |

423 | /** |

424 | * @brief Swaps data with another %multiset. |

425 | * @param __x A %multiset of the same element and allocator types. |

426 | * |

427 | * This exchanges the elements between two multisets in constant time. |

428 | * (It is only swapping a pointer, an integer, and an instance of the @c |

429 | * Compare type (which itself is often stateless and empty), so it should |

430 | * be quite fast.) |

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

432 | * std::swap(s1,s2) will feed to this function. |

433 | * |

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

435 | */ |

436 | void |

437 | swap(multiset& __x) |

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

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

440 | |

441 | // insert/erase |

442 | #if __cplusplus >= 201103L |

443 | /** |

444 | * @brief Builds and inserts an element into the %multiset. |

445 | * @param __args Arguments used to generate the element instance to be |

446 | * inserted. |

447 | * @return An iterator that points to the inserted element. |

448 | * |

449 | * This function inserts an element into the %multiset. Contrary |

450 | * to a std::set the %multiset does not rely on unique keys and thus |

451 | * multiple copies of the same element can be inserted. |

452 | * |

453 | * Insertion requires logarithmic time. |

454 | */ |

455 | template<typename... _Args> |

456 | iterator |

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

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

459 | |

460 | /** |

461 | * @brief Builds and inserts an element into the %multiset. |

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

463 | * element should be inserted. |

464 | * @param __args Arguments used to generate the element instance to be |

465 | * inserted. |

466 | * @return An iterator that points to the inserted element. |

467 | * |

468 | * This function inserts an element into the %multiset. Contrary |

469 | * to a std::set the %multiset does not rely on unique keys and thus |

470 | * multiple copies of the same element can be inserted. |

471 | * |

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

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

474 | * cause no gains in efficiency. |

475 | * |

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

477 | * for more on @a hinting. |

478 | * |

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

480 | */ |

481 | template<typename... _Args> |

482 | iterator |

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

484 | { |

485 | return _M_t._M_emplace_hint_equal(__pos, |

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

487 | } |

488 | #endif |

489 | |

490 | /** |

491 | * @brief Inserts an element into the %multiset. |

492 | * @param __x Element to be inserted. |

493 | * @return An iterator that points to the inserted element. |

494 | * |

495 | * This function inserts an element into the %multiset. Contrary |

496 | * to a std::set the %multiset does not rely on unique keys and thus |

497 | * multiple copies of the same element can be inserted. |

498 | * |

499 | * Insertion requires logarithmic time. |

500 | */ |

501 | iterator |

502 | insert(const value_type& __x) |

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

504 | |

505 | #if __cplusplus >= 201103L |

506 | iterator |

507 | insert(value_type&& __x) |

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

509 | #endif |

510 | |

511 | /** |

512 | * @brief Inserts an element into the %multiset. |

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

514 | * element should be inserted. |

515 | * @param __x Element to be inserted. |

516 | * @return An iterator that points to the inserted element. |

517 | * |

518 | * This function inserts an element into the %multiset. Contrary |

519 | * to a std::set the %multiset does not rely on unique keys and thus |

520 | * multiple copies of the same element can be inserted. |

521 | * |

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

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

524 | * cause no gains in efficiency. |

525 | * |

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

527 | * for more on @a hinting. |

528 | * |

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

530 | */ |

531 | iterator |

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

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

534 | |

535 | #if __cplusplus >= 201103L |

536 | iterator |

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

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

539 | #endif |

540 | |

541 | /** |

542 | * @brief A template function that tries to insert a range of elements. |

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

544 | * inserted. |

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

546 | * |

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

548 | */ |

549 | template<typename _InputIterator> |

550 | void |

551 | insert(_InputIterator __first, _InputIterator __last) |

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

553 | |

554 | #if __cplusplus >= 201103L |

555 | /** |

556 | * @brief Attempts to insert a list of elements into the %multiset. |

557 | * @param __l A std::initializer_list<value_type> of elements |

558 | * to be inserted. |

559 | * |

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

561 | */ |

562 | void |

563 | insert(initializer_list<value_type> __l) |

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

565 | #endif |

566 | |

567 | #if __cplusplus > 201402L |

568 | /// Extract a node. |

569 | node_type |

570 | extract(const_iterator __pos) |

571 | { |

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

573 | return _M_t.extract(__pos); |

574 | } |

575 | |

576 | /// Extract a node. |

577 | node_type |

578 | extract(const key_type& __x) |

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

580 | |

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

582 | iterator |

583 | insert(node_type&& __nh) |

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

585 | |

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

587 | iterator |

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

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

590 | |

591 | template<typename, typename> |

592 | friend class std::_Rb_tree_merge_helper; |

593 | |

594 | template<typename _Compare1> |

595 | void |

596 | merge(multiset<_Key, _Compare1, _Alloc>& __source) |

597 | { |

598 | using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; |

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

600 | } |

601 | |

602 | template<typename _Compare1> |

603 | void |

604 | merge(multiset<_Key, _Compare1, _Alloc>&& __source) |

605 | { merge(__source); } |

606 | |

607 | template<typename _Compare1> |

608 | void |

609 | merge(set<_Key, _Compare1, _Alloc>& __source) |

610 | { |

611 | using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>; |

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

613 | } |

614 | |

615 | template<typename _Compare1> |

616 | void |

617 | merge(set<_Key, _Compare1, _Alloc>&& __source) |

618 | { merge(__source); } |

619 | #endif // C++17 |

620 | |

621 | #if __cplusplus >= 201103L |

622 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

624 | /** |

625 | * @brief Erases an element from a %multiset. |

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

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

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

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

630 | * |

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

632 | * from a %multiset. Note that this function only erases the element, |

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

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

635 | * responsibility. |

636 | */ |

637 | _GLIBCXX_ABI_TAG_CXX11 |

638 | iterator |

639 | erase(const_iterator __position) |

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

641 | #else |

642 | /** |

643 | * @brief Erases an element from a %multiset. |

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

645 | * |

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

647 | * from a %multiset. Note that this function only erases the element, |

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

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

650 | * responsibility. |

651 | */ |

652 | void |

653 | erase(iterator __position) |

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

655 | #endif |

656 | |

657 | /** |

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

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

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

661 | * |

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

663 | * %multiset. |

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

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

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

667 | */ |

668 | size_type |

669 | erase(const key_type& __x) |

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

671 | |

672 | #if __cplusplus >= 201103L |

673 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

675 | /** |

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

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

678 | * erased. |

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

680 | * be erased. |

681 | * @return The iterator @a last. |

682 | * |

683 | * This function erases a sequence of elements from a %multiset. |

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

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

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

687 | * responsibility. |

688 | */ |

689 | _GLIBCXX_ABI_TAG_CXX11 |

690 | iterator |

691 | erase(const_iterator __first, const_iterator __last) |

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

693 | #else |

694 | /** |

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

696 | * @param first Iterator pointing to the start of the range to be |

697 | * erased. |

698 | * @param last Iterator pointing to the end of the range to be erased. |

699 | * |

700 | * This function erases a sequence of elements from a %multiset. |

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

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

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

704 | * responsibility. |

705 | */ |

706 | void |

707 | erase(iterator __first, iterator __last) |

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

709 | #endif |

710 | |

711 | /** |

712 | * Erases all elements in a %multiset. Note that this function only |

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

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

715 | * is the user's responsibility. |

716 | */ |

717 | void |

718 | clear() _GLIBCXX_NOEXCEPT |

719 | { _M_t.clear(); } |

720 | |

721 | // multiset operations: |

722 | |

723 | //@{ |

724 | /** |

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

726 | * @param __x Key of elements to be located. |

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

728 | */ |

729 | size_type |

730 | count(const key_type& __x) const |

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

732 | |

733 | #if __cplusplus > 201103L |

734 | template<typename _Kt> |

735 | auto |

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

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

738 | #endif |

739 | //@} |

740 | |

741 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

742 | // 214. set::find() missing const overload |

743 | //@{ |

744 | /** |

745 | * @brief Tries to locate an element in a %set. |

746 | * @param __x Element to be located. |

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

748 | * found. |

749 | * |

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

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

752 | * pointing to the sought after element. If unsuccessful it returns the |

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

754 | */ |

755 | iterator |

756 | find(const key_type& __x) |

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

758 | |

759 | const_iterator |

760 | find(const key_type& __x) const |

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

762 | |

763 | #if __cplusplus > 201103L |

764 | template<typename _Kt> |

765 | auto |

766 | find(const _Kt& __x) |

767 | -> decltype(iterator{_M_t._M_find_tr(__x)}) |

768 | { return iterator{_M_t._M_find_tr(__x)}; } |

769 | |

770 | template<typename _Kt> |

771 | auto |

772 | find(const _Kt& __x) const |

773 | -> decltype(const_iterator{_M_t._M_find_tr(__x)}) |

774 | { return const_iterator{_M_t._M_find_tr(__x)}; } |

775 | #endif |

776 | //@} |

777 | |

778 | //@{ |

779 | /** |

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

781 | * @param __x Key to be located. |

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

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

784 | * |

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

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

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

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

789 | */ |

790 | iterator |

791 | lower_bound(const key_type& __x) |

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

793 | |

794 | const_iterator |

795 | lower_bound(const key_type& __x) const |

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

797 | |

798 | #if __cplusplus > 201103L |

799 | template<typename _Kt> |

800 | auto |

801 | lower_bound(const _Kt& __x) |

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

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

804 | |

805 | template<typename _Kt> |

806 | auto |

807 | lower_bound(const _Kt& __x) const |

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

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

810 | #endif |

811 | //@} |

812 | |

813 | //@{ |

814 | /** |

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

816 | * @param __x Key to be located. |

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

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

819 | */ |

820 | iterator |

821 | upper_bound(const key_type& __x) |

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

823 | |

824 | const_iterator |

825 | upper_bound(const key_type& __x) const |

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

827 | |

828 | #if __cplusplus > 201103L |

829 | template<typename _Kt> |

830 | auto |

831 | upper_bound(const _Kt& __x) |

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

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

834 | |

835 | template<typename _Kt> |

836 | auto |

837 | upper_bound(const _Kt& __x) const |

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

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

840 | #endif |

841 | //@} |

842 | |

843 | //@{ |

844 | /** |

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

846 | * @param __x Key to be located. |

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

848 | * matching given key. |

849 | * |

850 | * This function is equivalent to |

851 | * @code |

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

853 | * c.upper_bound(val)) |

854 | * @endcode |

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

856 | * |

857 | * This function probably only makes sense for multisets. |

858 | */ |

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

860 | equal_range(const key_type& __x) |

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

862 | |

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

864 | equal_range(const key_type& __x) const |

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

866 | |

867 | #if __cplusplus > 201103L |

868 | template<typename _Kt> |

869 | auto |

870 | equal_range(const _Kt& __x) |

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

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

873 | |

874 | template<typename _Kt> |

875 | auto |

876 | equal_range(const _Kt& __x) const |

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

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

879 | #endif |

880 | //@} |

881 | |

882 | template<typename _K1, typename _C1, typename _A1> |

883 | friend bool |

884 | operator==(const multiset<_K1, _C1, _A1>&, |

885 | const multiset<_K1, _C1, _A1>&); |

886 | |

887 | template<typename _K1, typename _C1, typename _A1> |

888 | friend bool |

889 | operator< (const multiset<_K1, _C1, _A1>&, |

890 | const multiset<_K1, _C1, _A1>&); |

891 | }; |

892 | |

893 | #if __cpp_deduction_guides >= 201606 |

894 | |

895 | template<typename _InputIterator, |

896 | typename _Compare = |

897 | less<typename iterator_traits<_InputIterator>::value_type>, |

898 | typename _Allocator = |

899 | allocator<typename iterator_traits<_InputIterator>::value_type>, |

900 | typename = _RequireInputIter<_InputIterator>, |

901 | typename = _RequireAllocator<_Allocator>> |

902 | multiset(_InputIterator, _InputIterator, |

903 | _Compare = _Compare(), _Allocator = _Allocator()) |

904 | -> multiset<typename iterator_traits<_InputIterator>::value_type, |

905 | _Compare, _Allocator>; |

906 | |

907 | template<typename _Key, |

908 | typename _Compare = less<_Key>, |

909 | typename _Allocator = allocator<_Key>, |

910 | typename = _RequireAllocator<_Allocator>> |

911 | multiset(initializer_list<_Key>, |

912 | _Compare = _Compare(), _Allocator = _Allocator()) |

913 | -> multiset<_Key, _Compare, _Allocator>; |

914 | |

915 | template<typename _InputIterator, typename _Allocator, |

916 | typename = _RequireInputIter<_InputIterator>, |

917 | typename = _RequireAllocator<_Allocator>> |

918 | multiset(_InputIterator, _InputIterator, _Allocator) |

919 | -> multiset<typename iterator_traits<_InputIterator>::value_type, |

920 | less<typename iterator_traits<_InputIterator>::value_type>, |

921 | _Allocator>; |

922 | |

923 | template<typename _Key, typename _Allocator, |

924 | typename = _RequireAllocator<_Allocator>> |

925 | multiset(initializer_list<_Key>, _Allocator) |

926 | -> multiset<_Key, less<_Key>, _Allocator>; |

927 | |

928 | #endif |

929 | |

930 | /** |

931 | * @brief Multiset equality comparison. |

932 | * @param __x A %multiset. |

933 | * @param __y A %multiset of the same type as @a __x. |

934 | * @return True iff the size and elements of the multisets are equal. |

935 | * |

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

937 | * multisets. |

938 | * Multisets are considered equivalent if their sizes are equal, and if |

939 | * corresponding elements compare equal. |

940 | */ |

941 | template<typename _Key, typename _Compare, typename _Alloc> |

942 | inline bool |

943 | operator==(const multiset<_Key, _Compare, _Alloc>& __x, |

944 | const multiset<_Key, _Compare, _Alloc>& __y) |

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

946 | |

947 | /** |

948 | * @brief Multiset ordering relation. |

949 | * @param __x A %multiset. |

950 | * @param __y A %multiset of the same type as @a __x. |

951 | * @return True iff @a __x is lexicographically less than @a __y. |

952 | * |

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

954 | * sets. The elements must be comparable with @c <. |

955 | * |

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

957 | */ |

958 | template<typename _Key, typename _Compare, typename _Alloc> |

959 | inline bool |

960 | operator<(const multiset<_Key, _Compare, _Alloc>& __x, |

961 | const multiset<_Key, _Compare, _Alloc>& __y) |

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

963 | |

964 | /// Returns !(x == y). |

965 | template<typename _Key, typename _Compare, typename _Alloc> |

966 | inline bool |

967 | operator!=(const multiset<_Key, _Compare, _Alloc>& __x, |

968 | const multiset<_Key, _Compare, _Alloc>& __y) |

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

970 | |

971 | /// Returns y < x. |

972 | template<typename _Key, typename _Compare, typename _Alloc> |

973 | inline bool |

974 | operator>(const multiset<_Key,_Compare,_Alloc>& __x, |

975 | const multiset<_Key,_Compare,_Alloc>& __y) |

976 | { return __y < __x; } |

977 | |

978 | /// Returns !(y < x) |

979 | template<typename _Key, typename _Compare, typename _Alloc> |

980 | inline bool |

981 | operator<=(const multiset<_Key, _Compare, _Alloc>& __x, |

982 | const multiset<_Key, _Compare, _Alloc>& __y) |

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

984 | |

985 | /// Returns !(x < y) |

986 | template<typename _Key, typename _Compare, typename _Alloc> |

987 | inline bool |

988 | operator>=(const multiset<_Key, _Compare, _Alloc>& __x, |

989 | const multiset<_Key, _Compare, _Alloc>& __y) |

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

991 | |

992 | /// See std::multiset::swap(). |

993 | template<typename _Key, typename _Compare, typename _Alloc> |

994 | inline void |

995 | swap(multiset<_Key, _Compare, _Alloc>& __x, |

996 | multiset<_Key, _Compare, _Alloc>& __y) |

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

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

999 | |

1000 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1001 | |

1002 | #if __cplusplus > 201402L |

1003 | // Allow std::multiset access to internals of compatible sets. |

1004 | template<typename _Val, typename _Cmp1, typename _Alloc, typename _Cmp2> |

1005 | struct |

1006 | _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>, |

1007 | _Cmp2> |

1008 | { |

1009 | private: |

1010 | friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>; |

1011 | |

1012 | static auto& |

1013 | _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set) |

1014 | { return __set._M_t; } |

1015 | |

1016 | static auto& |

1017 | _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) |

1018 | { return __set._M_t; } |

1019 | }; |

1020 | |

1021 | #endif // C++17 |

1022 | |

1023 | _GLIBCXX_END_NAMESPACE_VERSION |

1024 | } // namespace std |

1025 | |

1026 | #endif /* _STL_MULTISET_H */ |

1027 |