1 | // Set 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_set.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_SET_H |

57 | #define _STL_SET_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 multiset; |

71 | |

72 | /** |

73 | * @brief A standard container made up of unique keys, which can be |

74 | * retrieved in logarithmic time. |

75 | * |

76 | * @ingroup associative_containers |

77 | * |

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

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

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

81 | * |

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

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

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

85 | * |

86 | * Sets support bidirectional iterators. |

87 | * |

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

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

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

91 | */ |

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

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

94 | class set |

95 | { |

96 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

97 | // concept requirements |

98 | typedef typename _Alloc::value_type _Alloc_value_type; |

99 | # if __cplusplus < 201103L |

100 | __glibcxx_class_requires(_Key, _SGIAssignableConcept) |

101 | # endif |

102 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, |

103 | _BinaryFunctionConcept) |

104 | __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) |

105 | #endif |

106 | |

107 | #if __cplusplus >= 201103L |

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

109 | "std::set must have a non-const, non-volatile value_type"); |

110 | # ifdef __STRICT_ANSI__ |

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

112 | "std::set must have the same value_type as its allocator"); |

113 | # endif |

114 | #endif |

115 | |

116 | public: |

117 | // typedefs: |

118 | //@{ |

119 | /// Public 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 | |

127 | private: |

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 | _Rep_type _M_t; // Red-black tree representing set. |

134 | |

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

136 | |

137 | public: |

138 | //@{ |

139 | /// Iterator-related typedefs. |

140 | typedef typename _Alloc_traits::pointer pointer; |

141 | typedef typename _Alloc_traits::const_pointer const_pointer; |

142 | typedef typename _Alloc_traits::reference reference; |

143 | typedef typename _Alloc_traits::const_reference const_reference; |

144 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

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

147 | typedef typename _Rep_type::const_iterator iterator; |

148 | typedef typename _Rep_type::const_iterator const_iterator; |

149 | typedef typename _Rep_type::const_reverse_iterator reverse_iterator; |

150 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

151 | typedef typename _Rep_type::size_type size_type; |

152 | typedef typename _Rep_type::difference_type difference_type; |

153 | //@} |

154 | |

155 | #if __cplusplus > 201402L |

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

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

158 | #endif |

159 | |

160 | // allocation/deallocation |

161 | /** |

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

163 | */ |

164 | #if __cplusplus < 201103L |

165 | set() : _M_t() { } |

166 | #else |

167 | set() = default; |

168 | #endif |

169 | |

170 | /** |

171 | * @brief Creates a %set with no elements. |

172 | * @param __comp Comparator to use. |

173 | * @param __a An allocator object. |

174 | */ |

175 | explicit |

176 | set(const _Compare& __comp, |

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

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

179 | |

180 | /** |

181 | * @brief Builds a %set from a range. |

182 | * @param __first An input iterator. |

183 | * @param __last An input iterator. |

184 | * |

185 | * Create a %set consisting of copies of the elements from |

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

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

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

189 | */ |

190 | template<typename _InputIterator> |

191 | set(_InputIterator __first, _InputIterator __last) |

192 | : _M_t() |

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

194 | |

195 | /** |

196 | * @brief Builds a %set from a range. |

197 | * @param __first An input iterator. |

198 | * @param __last An input iterator. |

199 | * @param __comp A comparison functor. |

200 | * @param __a An allocator object. |

201 | * |

202 | * Create a %set consisting of copies of the elements from |

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

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

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

206 | */ |

207 | template<typename _InputIterator> |

208 | set(_InputIterator __first, _InputIterator __last, |

209 | const _Compare& __comp, |

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

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

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

213 | |

214 | /** |

215 | * @brief %Set copy constructor. |

216 | * |

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

218 | */ |

219 | #if __cplusplus < 201103L |

220 | set(const set& __x) |

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

222 | #else |

223 | set(const set&) = default; |

224 | |

225 | /** |

226 | * @brief %Set move constructor |

227 | * |

228 | * The newly-created %set contains the exact contents of the moved |

229 | * instance. The moved instance is a valid, but unspecified, %set. |

230 | */ |

231 | set(set&&) = default; |

232 | |

233 | /** |

234 | * @brief Builds a %set from an initializer_list. |

235 | * @param __l An initializer_list. |

236 | * @param __comp A comparison functor. |

237 | * @param __a An allocator object. |

238 | * |

239 | * Create a %set consisting of copies of the elements in the list. |

240 | * This is linear in N if the list is already sorted, and NlogN |

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

242 | */ |

243 | set(initializer_list<value_type> __l, |

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

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

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

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

248 | |

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

250 | explicit |

251 | set(const allocator_type& __a) |

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

253 | |

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

255 | set(const set& __x, const allocator_type& __a) |

256 | : _M_t(__x._M_t, _Key_alloc_type(__a)) { } |

257 | |

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

259 | set(set&& __x, const allocator_type& __a) |

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

261 | && _Alloc_traits::_S_always_equal()) |

262 | : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { } |

263 | |

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

265 | set(initializer_list<value_type> __l, const allocator_type& __a) |

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

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

268 | |

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

270 | template<typename _InputIterator> |

271 | set(_InputIterator __first, _InputIterator __last, |

272 | const allocator_type& __a) |

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

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

275 | |

276 | /** |

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

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

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

280 | */ |

281 | ~set() = default; |

282 | #endif |

283 | |

284 | /** |

285 | * @brief %Set assignment operator. |

286 | * |

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

288 | */ |

289 | #if __cplusplus < 201103L |

290 | set& |

291 | operator=(const set& __x) |

292 | { |

293 | _M_t = __x._M_t; |

294 | return *this; |

295 | } |

296 | #else |

297 | set& |

298 | operator=(const set&) = default; |

299 | |

300 | /// Move assignment operator. |

301 | set& |

302 | operator=(set&&) = default; |

303 | |

304 | /** |

305 | * @brief %Set list assignment operator. |

306 | * @param __l An initializer_list. |

307 | * |

308 | * This function fills a %set with copies of the elements in the |

309 | * initializer list @a __l. |

310 | * |

311 | * Note that the assignment completely changes the %set and |

312 | * that the resulting %set's size is the same as the number |

313 | * of elements assigned. |

314 | */ |

315 | set& |

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

317 | { |

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

319 | return *this; |

320 | } |

321 | #endif |

322 | |

323 | // accessors: |

324 | |

325 | /// Returns the comparison object with which the %set was constructed. |

326 | key_compare |

327 | key_comp() const |

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

329 | /// Returns the comparison object with which the %set was constructed. |

330 | value_compare |

331 | value_comp() const |

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

333 | /// Returns the allocator object with which the %set was constructed. |

334 | allocator_type |

335 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

337 | |

338 | /** |

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

340 | * element in the %set. Iteration is done in ascending order according |

341 | * to the keys. |

342 | */ |

343 | iterator |

344 | begin() const _GLIBCXX_NOEXCEPT |

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

346 | |

347 | /** |

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

349 | * element in the %set. Iteration is done in ascending order according |

350 | * to the keys. |

351 | */ |

352 | iterator |

353 | end() const _GLIBCXX_NOEXCEPT |

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

355 | |

356 | /** |

357 | * Returns a read-only (constant) iterator that points to the last |

358 | * element in the %set. Iteration is done in descending order according |

359 | * to the keys. |

360 | */ |

361 | reverse_iterator |

362 | rbegin() const _GLIBCXX_NOEXCEPT |

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

364 | |

365 | /** |

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

367 | * last pair in the %set. Iteration is done in descending order |

368 | * according to the keys. |

369 | */ |

370 | reverse_iterator |

371 | rend() const _GLIBCXX_NOEXCEPT |

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

373 | |

374 | #if __cplusplus >= 201103L |

375 | /** |

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

377 | * element in the %set. Iteration is done in ascending order according |

378 | * to the keys. |

379 | */ |

380 | iterator |

381 | cbegin() const noexcept |

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

383 | |

384 | /** |

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

386 | * element in the %set. Iteration is done in ascending order according |

387 | * to the keys. |

388 | */ |

389 | iterator |

390 | cend() const noexcept |

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

392 | |

393 | /** |

394 | * Returns a read-only (constant) iterator that points to the last |

395 | * element in the %set. Iteration is done in descending order according |

396 | * to the keys. |

397 | */ |

398 | reverse_iterator |

399 | crbegin() const noexcept |

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

401 | |

402 | /** |

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

404 | * last pair in the %set. Iteration is done in descending order |

405 | * according to the keys. |

406 | */ |

407 | reverse_iterator |

408 | crend() const noexcept |

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

410 | #endif |

411 | |

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

413 | bool |

414 | empty() const _GLIBCXX_NOEXCEPT |

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

416 | |

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

418 | size_type |

419 | size() const _GLIBCXX_NOEXCEPT |

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

421 | |

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

423 | size_type |

424 | max_size() const _GLIBCXX_NOEXCEPT |

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

426 | |

427 | /** |

428 | * @brief Swaps data with another %set. |

429 | * @param __x A %set of the same element and allocator types. |

430 | * |

431 | * This exchanges the elements between two sets in constant |

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

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

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

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

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

437 | * |

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

439 | */ |

440 | void |

441 | swap(set& __x) |

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

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

444 | |

445 | // insert/erase |

446 | #if __cplusplus >= 201103L |

447 | /** |

448 | * @brief Attempts to build and insert an element into the %set. |

449 | * @param __args Arguments used to generate an element. |

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

451 | * to the possibly inserted element, and the second is a bool |

452 | * that is true if the element was actually inserted. |

453 | * |

454 | * This function attempts to build and insert an element into the %set. |

455 | * A %set relies on unique keys and thus an element is only inserted if |

456 | * it is not already present in the %set. |

457 | * |

458 | * Insertion requires logarithmic time. |

459 | */ |

460 | template<typename... _Args> |

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

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

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

464 | |

465 | /** |

466 | * @brief Attempts to insert an element into the %set. |

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

468 | * element should be inserted. |

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

470 | * inserted. |

471 | * @return An iterator that points to the element with key equivalent to |

472 | * the one generated from @a __args (may or may not be the |

473 | * element itself). |

474 | * |

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

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

477 | * does. Note that the first parameter is only a hint and can |

478 | * potentially improve the performance of the insertion process. A bad |

479 | * hint would cause no gains in efficiency. |

480 | * |

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

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

483 | * |

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

485 | */ |

486 | template<typename... _Args> |

487 | iterator |

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

489 | { |

490 | return _M_t._M_emplace_hint_unique(__pos, |

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

492 | } |

493 | #endif |

494 | |

495 | /** |

496 | * @brief Attempts to insert an element into the %set. |

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

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

499 | * to the possibly inserted element, and the second is a bool |

500 | * that is true if the element was actually inserted. |

501 | * |

502 | * This function attempts to insert an element into the %set. A %set |

503 | * relies on unique keys and thus an element is only inserted if it is |

504 | * not already present in the %set. |

505 | * |

506 | * Insertion requires logarithmic time. |

507 | */ |

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

509 | insert(const value_type& __x) |

510 | { |

511 | std::pair<typename _Rep_type::iterator, bool> __p = |

512 | _M_t._M_insert_unique(__x); |

513 | return std::pair<iterator, bool>(__p.first, __p.second); |

514 | } |

515 | |

516 | #if __cplusplus >= 201103L |

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

518 | insert(value_type&& __x) |

519 | { |

520 | std::pair<typename _Rep_type::iterator, bool> __p = |

521 | _M_t._M_insert_unique(std::move(__x)); |

522 | return std::pair<iterator, bool>(__p.first, __p.second); |

523 | } |

524 | #endif |

525 | |

526 | /** |

527 | * @brief Attempts to insert an element into the %set. |

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

529 | * element should be inserted. |

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

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

532 | * @a __x (may or may not be the element passed in). |

533 | * |

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

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

536 | * does. Note that the first parameter is only a hint and can |

537 | * potentially improve the performance of the insertion process. A bad |

538 | * hint would cause no gains in efficiency. |

539 | * |

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

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

542 | * |

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

544 | */ |

545 | iterator |

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

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

548 | |

549 | #if __cplusplus >= 201103L |

550 | iterator |

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

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

553 | #endif |

554 | |

555 | /** |

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

557 | * of elements. |

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

559 | * inserted. |

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

561 | * |

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

563 | */ |

564 | template<typename _InputIterator> |

565 | void |

566 | insert(_InputIterator __first, _InputIterator __last) |

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

568 | |

569 | #if __cplusplus >= 201103L |

570 | /** |

571 | * @brief Attempts to insert a list of elements into the %set. |

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

573 | * to be inserted. |

574 | * |

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

576 | */ |

577 | void |

578 | insert(initializer_list<value_type> __l) |

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

580 | #endif |

581 | |

582 | #if __cplusplus > 201402L |

583 | /// Extract a node. |

584 | node_type |

585 | extract(const_iterator __pos) |

586 | { |

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

588 | return _M_t.extract(__pos); |

589 | } |

590 | |

591 | /// Extract a node. |

592 | node_type |

593 | extract(const key_type& __x) |

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

595 | |

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

597 | insert_return_type |

598 | insert(node_type&& __nh) |

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

600 | |

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

602 | iterator |

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

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

605 | |

606 | template<typename, typename> |

607 | friend class std::_Rb_tree_merge_helper; |

608 | |

609 | template<typename _Compare1> |

610 | void |

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

612 | { |

613 | using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; |

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

615 | } |

616 | |

617 | template<typename _Compare1> |

618 | void |

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

620 | { merge(__source); } |

621 | |

622 | template<typename _Compare1> |

623 | void |

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

625 | { |

626 | using _Merge_helper = _Rb_tree_merge_helper<set, _Compare1>; |

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

628 | } |

629 | |

630 | template<typename _Compare1> |

631 | void |

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

633 | { merge(__source); } |

634 | #endif // C++17 |

635 | |

636 | #if __cplusplus >= 201103L |

637 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

639 | /** |

640 | * @brief Erases an element from a %set. |

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

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

643 | * @a __position prior to the element being erased. If no such |

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

645 | * |

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

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

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

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

650 | * responsibility. |

651 | */ |

652 | _GLIBCXX_ABI_TAG_CXX11 |

653 | iterator |

654 | erase(const_iterator __position) |

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

656 | #else |

657 | /** |

658 | * @brief Erases an element from a %set. |

659 | * @param position An iterator pointing to the element to be erased. |

660 | * |

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

662 | * from a %set. Note that this function only erases the element, and |

663 | * that if the element is itself a pointer, the pointed-to memory is not |

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

665 | * responsibility. |

666 | */ |

667 | void |

668 | erase(iterator __position) |

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

670 | #endif |

671 | |

672 | /** |

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

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

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

676 | * |

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

678 | * a %set. |

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

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

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

682 | */ |

683 | size_type |

684 | erase(const key_type& __x) |

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

686 | |

687 | #if __cplusplus >= 201103L |

688 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

690 | /** |

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

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

693 | * erased. |

694 | |

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

696 | * be erased. |

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

698 | * |

699 | * This function erases a sequence of elements from a %set. |

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

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

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

703 | */ |

704 | _GLIBCXX_ABI_TAG_CXX11 |

705 | iterator |

706 | erase(const_iterator __first, const_iterator __last) |

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

708 | #else |

709 | /** |

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

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

712 | * erased. |

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

714 | * be erased. |

715 | * |

716 | * This function erases a sequence of elements from a %set. |

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

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

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

720 | */ |

721 | void |

722 | erase(iterator __first, iterator __last) |

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

724 | #endif |

725 | |

726 | /** |

727 | * Erases all elements in a %set. Note that this function only erases |

728 | * the elements, and that if the elements themselves are pointers, the |

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

730 | * the user's responsibility. |

731 | */ |

732 | void |

733 | clear() _GLIBCXX_NOEXCEPT |

734 | { _M_t.clear(); } |

735 | |

736 | // set operations: |

737 | |

738 | //@{ |

739 | /** |

740 | * @brief Finds the number of elements. |

741 | * @param __x Element to located. |

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

743 | * |

744 | * This function only makes sense for multisets; for set the result will |

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

746 | */ |

747 | size_type |

748 | count(const key_type& __x) const |

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

750 | |

751 | #if __cplusplus > 201103L |

752 | template<typename _Kt> |

753 | auto |

754 | count(const _Kt& __x) const |

755 | -> decltype(_M_t._M_count_tr(__x)) |

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

757 | #endif |

758 | //@} |

759 | |

760 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

762 | //@{ |

763 | /** |

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

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

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

767 | * found. |

768 | * |

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

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

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

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

773 | */ |

774 | iterator |

775 | find(const key_type& __x) |

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

777 | |

778 | const_iterator |

779 | find(const key_type& __x) const |

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

781 | |

782 | #if __cplusplus > 201103L |

783 | template<typename _Kt> |

784 | auto |

785 | find(const _Kt& __x) |

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

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

788 | |

789 | template<typename _Kt> |

790 | auto |

791 | find(const _Kt& __x) const |

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

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

794 | #endif |

795 | //@} |

796 | |

797 | //@{ |

798 | /** |

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

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

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

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

803 | * |

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

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

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

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

808 | */ |

809 | iterator |

810 | lower_bound(const key_type& __x) |

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

812 | |

813 | const_iterator |

814 | lower_bound(const key_type& __x) const |

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

816 | |

817 | #if __cplusplus > 201103L |

818 | template<typename _Kt> |

819 | auto |

820 | lower_bound(const _Kt& __x) |

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

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

823 | |

824 | template<typename _Kt> |

825 | auto |

826 | lower_bound(const _Kt& __x) const |

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

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

829 | #endif |

830 | //@} |

831 | |

832 | //@{ |

833 | /** |

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

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

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

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

838 | */ |

839 | iterator |

840 | upper_bound(const key_type& __x) |

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

842 | |

843 | const_iterator |

844 | upper_bound(const key_type& __x) const |

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

846 | |

847 | #if __cplusplus > 201103L |

848 | template<typename _Kt> |

849 | auto |

850 | upper_bound(const _Kt& __x) |

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

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

853 | |

854 | template<typename _Kt> |

855 | auto |

856 | upper_bound(const _Kt& __x) const |

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

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

859 | #endif |

860 | //@} |

861 | |

862 | //@{ |

863 | /** |

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

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

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

867 | * matching given key. |

868 | * |

869 | * This function is equivalent to |

870 | * @code |

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

872 | * c.upper_bound(val)) |

873 | * @endcode |

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

875 | * |

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

877 | */ |

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

879 | equal_range(const key_type& __x) |

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

881 | |

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

883 | equal_range(const key_type& __x) const |

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

885 | |

886 | #if __cplusplus > 201103L |

887 | template<typename _Kt> |

888 | auto |

889 | equal_range(const _Kt& __x) |

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

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

892 | |

893 | template<typename _Kt> |

894 | auto |

895 | equal_range(const _Kt& __x) const |

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

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

898 | #endif |

899 | //@} |

900 | |

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

902 | friend bool |

903 | operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); |

904 | |

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

906 | friend bool |

907 | operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); |

908 | }; |

909 | |

910 | #if __cpp_deduction_guides >= 201606 |

911 | |

912 | template<typename _InputIterator, |

913 | typename _Compare = |

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

915 | typename _Allocator = |

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

917 | typename = _RequireInputIter<_InputIterator>, |

918 | typename = _RequireAllocator<_Allocator>> |

919 | set(_InputIterator, _InputIterator, |

920 | _Compare = _Compare(), _Allocator = _Allocator()) |

921 | -> set<typename iterator_traits<_InputIterator>::value_type, |

922 | _Compare, _Allocator>; |

923 | |

924 | template<typename _Key, typename _Compare = less<_Key>, |

925 | typename _Allocator = allocator<_Key>, |

926 | typename = _RequireAllocator<_Allocator>> |

927 | set(initializer_list<_Key>, |

928 | _Compare = _Compare(), _Allocator = _Allocator()) |

929 | -> set<_Key, _Compare, _Allocator>; |

930 | |

931 | template<typename _InputIterator, typename _Allocator, |

932 | typename = _RequireInputIter<_InputIterator>, |

933 | typename = _RequireAllocator<_Allocator>> |

934 | set(_InputIterator, _InputIterator, _Allocator) |

935 | -> set<typename iterator_traits<_InputIterator>::value_type, |

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

937 | _Allocator>; |

938 | |

939 | template<typename _Key, typename _Allocator, |

940 | typename = _RequireAllocator<_Allocator>> |

941 | set(initializer_list<_Key>, _Allocator) |

942 | -> set<_Key, less<_Key>, _Allocator>; |

943 | |

944 | #endif |

945 | |

946 | /** |

947 | * @brief Set equality comparison. |

948 | * @param __x A %set. |

949 | * @param __y A %set of the same type as @a x. |

950 | * @return True iff the size and elements of the sets are equal. |

951 | * |

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

953 | * Sets are considered equivalent if their sizes are equal, and if |

954 | * corresponding elements compare equal. |

955 | */ |

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

957 | inline bool |

958 | operator==(const set<_Key, _Compare, _Alloc>& __x, |

959 | const set<_Key, _Compare, _Alloc>& __y) |

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

961 | |

962 | /** |

963 | * @brief Set ordering relation. |

964 | * @param __x A %set. |

965 | * @param __y A %set of the same type as @a x. |

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

967 | * |

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

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

970 | * |

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

972 | */ |

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

974 | inline bool |

975 | operator<(const set<_Key, _Compare, _Alloc>& __x, |

976 | const set<_Key, _Compare, _Alloc>& __y) |

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

978 | |

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

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

981 | inline bool |

982 | operator!=(const set<_Key, _Compare, _Alloc>& __x, |

983 | const set<_Key, _Compare, _Alloc>& __y) |

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

985 | |

986 | /// Returns y < x. |

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

988 | inline bool |

989 | operator>(const set<_Key, _Compare, _Alloc>& __x, |

990 | const set<_Key, _Compare, _Alloc>& __y) |

991 | { return __y < __x; } |

992 | |

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

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

995 | inline bool |

996 | operator<=(const set<_Key, _Compare, _Alloc>& __x, |

997 | const set<_Key, _Compare, _Alloc>& __y) |

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

999 | |

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

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

1002 | inline bool |

1003 | operator>=(const set<_Key, _Compare, _Alloc>& __x, |

1004 | const set<_Key, _Compare, _Alloc>& __y) |

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

1006 | |

1007 | /// See std::set::swap(). |

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

1009 | inline void |

1010 | swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) |

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

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

1013 | |

1014 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1015 | |

1016 | #if __cplusplus > 201402L |

1017 | // Allow std::set access to internals of compatible sets. |

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

1019 | struct |

1020 | _Rb_tree_merge_helper<_GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>, _Cmp2> |

1021 | { |

1022 | private: |

1023 | friend class _GLIBCXX_STD_C::set<_Val, _Cmp1, _Alloc>; |

1024 | |

1025 | static auto& |

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

1027 | { return __set._M_t; } |

1028 | |

1029 | static auto& |

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

1031 | { return __set._M_t; } |

1032 | }; |

1033 | #endif // C++17 |

1034 | |

1035 | _GLIBCXX_END_NAMESPACE_VERSION |

1036 | } //namespace std |

1037 | #endif /* _STL_SET_H */ |

1038 |