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

2 | |

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

4 | // |

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

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

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

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

9 | // any later version. |

10 | |

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

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

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

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

15 | |

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

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

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

19 | |

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

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

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

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

24 | |

25 | /* |

26 | * |

27 | * Copyright (c) 1994 |

28 | * Hewlett-Packard Company |

29 | * |

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

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

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

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

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

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

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

37 | * |

38 | * |

39 | * Copyright (c) 1996,1997 |

40 | * Silicon Graphics Computer Systems, Inc. |

41 | * |

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

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

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

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

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

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

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

49 | */ |

50 | |

51 | /** @file bits/stl_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_CONTAINER |

67 | |

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

69 | class multiset; |

70 | |

71 | /** |

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

73 | * retrieved in logarithmic time. |

74 | * |

75 | * @ingroup associative_containers |

76 | * |

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

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

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

80 | * |

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

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

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

84 | * |

85 | * Sets support bidirectional iterators. |

86 | * |

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

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

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

90 | */ |

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

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

93 | class set |

94 | { |

95 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

96 | // concept requirements |

97 | typedef typename _Alloc::value_type _Alloc_value_type; |

98 | # if __cplusplus < 201103L |

99 | __glibcxx_class_requires(_Key, _SGIAssignableConcept) |

100 | # endif |

101 | __glibcxx_class_requires4(_Compare, bool, _Key, _Key, |

102 | _BinaryFunctionConcept) |

103 | __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) |

104 | #endif |

105 | |

106 | public: |

107 | // typedefs: |

108 | //@{ |

109 | /// Public typedefs. |

110 | typedef _Key key_type; |

111 | typedef _Key value_type; |

112 | typedef _Compare key_compare; |

113 | typedef _Compare value_compare; |

114 | typedef _Alloc allocator_type; |

115 | //@} |

116 | |

117 | private: |

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

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

120 | |

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

122 | key_compare, _Key_alloc_type> _Rep_type; |

123 | _Rep_type _M_t; // Red-black tree representing set. |

124 | |

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

126 | |

127 | public: |

128 | //@{ |

129 | /// Iterator-related typedefs. |

130 | typedef typename _Alloc_traits::pointer pointer; |

131 | typedef typename _Alloc_traits::const_pointer const_pointer; |

132 | typedef typename _Alloc_traits::reference reference; |

133 | typedef typename _Alloc_traits::const_reference const_reference; |

134 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

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

137 | typedef typename _Rep_type::const_iterator iterator; |

138 | typedef typename _Rep_type::const_iterator const_iterator; |

139 | typedef typename _Rep_type::const_reverse_iterator reverse_iterator; |

140 | typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; |

141 | typedef typename _Rep_type::size_type size_type; |

142 | typedef typename _Rep_type::difference_type difference_type; |

143 | //@} |

144 | |

145 | #if __cplusplus > 201402L |

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

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

148 | #endif |

149 | |

150 | // allocation/deallocation |

151 | /** |

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

153 | */ |

154 | #if __cplusplus < 201103L |

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

156 | #else |

157 | set() = default; |

158 | #endif |

159 | |

160 | /** |

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

162 | * @param __comp Comparator to use. |

163 | * @param __a An allocator object. |

164 | */ |

165 | explicit |

166 | set(const _Compare& __comp, |

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

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

169 | |

170 | /** |

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

172 | * @param __first An input iterator. |

173 | * @param __last An input iterator. |

174 | * |

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

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

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

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

179 | */ |

180 | template<typename _InputIterator> |

181 | set(_InputIterator __first, _InputIterator __last) |

182 | : _M_t() |

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

184 | |

185 | /** |

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

187 | * @param __first An input iterator. |

188 | * @param __last An input iterator. |

189 | * @param __comp A comparison functor. |

190 | * @param __a An allocator object. |

191 | * |

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

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

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

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

196 | */ |

197 | template<typename _InputIterator> |

198 | set(_InputIterator __first, _InputIterator __last, |

199 | const _Compare& __comp, |

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

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

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

203 | |

204 | /** |

205 | * @brief %Set copy constructor. |

206 | * |

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

208 | */ |

209 | #if __cplusplus < 201103L |

210 | set(const set& __x) |

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

212 | #else |

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

214 | |

215 | /** |

216 | * @brief %Set move constructor |

217 | * |

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

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

220 | */ |

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

222 | |

223 | /** |

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

225 | * @param __l An initializer_list. |

226 | * @param __comp A comparison functor. |

227 | * @param __a An allocator object. |

228 | * |

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

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

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

232 | */ |

233 | set(initializer_list<value_type> __l, |

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

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

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

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

238 | |

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

240 | explicit |

241 | set(const allocator_type& __a) |

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

243 | |

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

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

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

247 | |

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

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

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

251 | && _Alloc_traits::_S_always_equal()) |

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

253 | |

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

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

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

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

258 | |

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

260 | template<typename _InputIterator> |

261 | set(_InputIterator __first, _InputIterator __last, |

262 | const allocator_type& __a) |

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

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

265 | |

266 | /** |

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

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

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

270 | */ |

271 | ~set() = default; |

272 | #endif |

273 | |

274 | /** |

275 | * @brief %Set assignment operator. |

276 | * |

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

278 | */ |

279 | #if __cplusplus < 201103L |

280 | set& |

281 | operator=(const set& __x) |

282 | { |

283 | _M_t = __x._M_t; |

284 | return *this; |

285 | } |

286 | #else |

287 | set& |

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

289 | |

290 | /// Move assignment operator. |

291 | set& |

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

293 | |

294 | /** |

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

296 | * @param __l An initializer_list. |

297 | * |

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

299 | * initializer list @a __l. |

300 | * |

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

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

303 | * of elements assigned. |

304 | */ |

305 | set& |

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

307 | { |

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

309 | return *this; |

310 | } |

311 | #endif |

312 | |

313 | // accessors: |

314 | |

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

316 | key_compare |

317 | key_comp() const |

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

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

320 | value_compare |

321 | value_comp() const |

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

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

324 | allocator_type |

325 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

327 | |

328 | /** |

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

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

331 | * to the keys. |

332 | */ |

333 | iterator |

334 | begin() const _GLIBCXX_NOEXCEPT |

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

336 | |

337 | /** |

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

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

340 | * to the keys. |

341 | */ |

342 | iterator |

343 | end() const _GLIBCXX_NOEXCEPT |

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

345 | |

346 | /** |

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

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

349 | * to the keys. |

350 | */ |

351 | reverse_iterator |

352 | rbegin() const _GLIBCXX_NOEXCEPT |

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

354 | |

355 | /** |

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

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

358 | * according to the keys. |

359 | */ |

360 | reverse_iterator |

361 | rend() const _GLIBCXX_NOEXCEPT |

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

363 | |

364 | #if __cplusplus >= 201103L |

365 | /** |

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

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

368 | * to the keys. |

369 | */ |

370 | iterator |

371 | cbegin() const noexcept |

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

373 | |

374 | /** |

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

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

377 | * to the keys. |

378 | */ |

379 | iterator |

380 | cend() const noexcept |

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

382 | |

383 | /** |

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

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

386 | * to the keys. |

387 | */ |

388 | reverse_iterator |

389 | crbegin() const noexcept |

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

391 | |

392 | /** |

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

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

395 | * according to the keys. |

396 | */ |

397 | reverse_iterator |

398 | crend() const noexcept |

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

400 | #endif |

401 | |

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

403 | bool |

404 | empty() const _GLIBCXX_NOEXCEPT |

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

406 | |

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

408 | size_type |

409 | size() const _GLIBCXX_NOEXCEPT |

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

411 | |

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

413 | size_type |

414 | max_size() const _GLIBCXX_NOEXCEPT |

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

416 | |

417 | /** |

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

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

420 | * |

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

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

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

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

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

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

427 | * |

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

429 | */ |

430 | void |

431 | swap(set& __x) |

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

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

434 | |

435 | // insert/erase |

436 | #if __cplusplus >= 201103L |

437 | /** |

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

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

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

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

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

443 | * |

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

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

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

447 | * |

448 | * Insertion requires logarithmic time. |

449 | */ |

450 | template<typename... _Args> |

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

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

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

454 | |

455 | /** |

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

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

458 | * element should be inserted. |

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

460 | * inserted. |

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

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

463 | * element itself). |

464 | * |

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

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

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

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

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

470 | * |

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

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

473 | * |

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

475 | */ |

476 | template<typename... _Args> |

477 | iterator |

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

479 | { |

480 | return _M_t._M_emplace_hint_unique(__pos, |

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

482 | } |

483 | #endif |

484 | |

485 | /** |

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

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

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

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

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

491 | * |

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

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

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

495 | * |

496 | * Insertion requires logarithmic time. |

497 | */ |

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

499 | insert(const value_type& __x) |

500 | { |

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

502 | _M_t._M_insert_unique(__x); |

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

504 | } |

505 | |

506 | #if __cplusplus >= 201103L |

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

508 | insert(value_type&& __x) |

509 | { |

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

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

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

513 | } |

514 | #endif |

515 | |

516 | /** |

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

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

519 | * element should be inserted. |

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

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

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

523 | * |

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

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

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

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

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

529 | * |

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

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

532 | * |

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

534 | */ |

535 | iterator |

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

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

538 | |

539 | #if __cplusplus >= 201103L |

540 | iterator |

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

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

543 | #endif |

544 | |

545 | /** |

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

547 | * of elements. |

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

549 | * inserted. |

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

551 | * |

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

553 | */ |

554 | template<typename _InputIterator> |

555 | void |

556 | insert(_InputIterator __first, _InputIterator __last) |

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

558 | |

559 | #if __cplusplus >= 201103L |

560 | /** |

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

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

563 | * to be inserted. |

564 | * |

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

566 | */ |

567 | void |

568 | insert(initializer_list<value_type> __l) |

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

570 | #endif |

571 | |

572 | #if __cplusplus > 201402L |

573 | /// Extract a node. |

574 | node_type |

575 | extract(const_iterator __pos) |

576 | { |

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

578 | return _M_t.extract(__pos); |

579 | } |

580 | |

581 | /// Extract a node. |

582 | node_type |

583 | extract(const key_type& __x) |

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

585 | |

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

587 | insert_return_type |

588 | insert(node_type&& __nh) |

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

590 | |

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

592 | iterator |

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

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

595 | |

596 | template<typename, typename> |

597 | friend class _Rb_tree_merge_helper; |

598 | |

599 | template<typename _Compare1> |

600 | void |

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

602 | { |

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

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

605 | } |

606 | |

607 | template<typename _Compare1> |

608 | void |

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

610 | { merge(__source); } |

611 | |

612 | template<typename _Compare1> |

613 | void |

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

615 | { |

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

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

618 | } |

619 | |

620 | template<typename _Compare1> |

621 | void |

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

623 | { merge(__source); } |

624 | #endif // C++17 |

625 | |

626 | #if __cplusplus >= 201103L |

627 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

629 | /** |

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

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

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

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

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

635 | * |

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

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

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

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

640 | * responsibility. |

641 | */ |

642 | _GLIBCXX_ABI_TAG_CXX11 |

643 | iterator |

644 | erase(const_iterator __position) |

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

646 | #else |

647 | /** |

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

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

650 | * |

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

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

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

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

655 | * responsibility. |

656 | */ |

657 | void |

658 | erase(iterator __position) |

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

660 | #endif |

661 | |

662 | /** |

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

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

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

666 | * |

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

668 | * a %set. |

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

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

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

672 | */ |

673 | size_type |

674 | erase(const key_type& __x) |

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

676 | |

677 | #if __cplusplus >= 201103L |

678 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

680 | /** |

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

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

683 | * erased. |

684 | |

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

686 | * be erased. |

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

688 | * |

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

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

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

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

693 | */ |

694 | _GLIBCXX_ABI_TAG_CXX11 |

695 | iterator |

696 | erase(const_iterator __first, const_iterator __last) |

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

698 | #else |

699 | /** |

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

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

702 | * erased. |

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

704 | * be erased. |

705 | * |

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

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

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

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

710 | */ |

711 | void |

712 | erase(iterator __first, iterator __last) |

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

714 | #endif |

715 | |

716 | /** |

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

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

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

720 | * the user's responsibility. |

721 | */ |

722 | void |

723 | clear() _GLIBCXX_NOEXCEPT |

724 | { _M_t.clear(); } |

725 | |

726 | // set operations: |

727 | |

728 | //@{ |

729 | /** |

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

731 | * @param __x Element to located. |

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

733 | * |

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

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

736 | */ |

737 | size_type |

738 | count(const key_type& __x) const |

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

740 | |

741 | #if __cplusplus > 201103L |

742 | template<typename _Kt> |

743 | auto |

744 | count(const _Kt& __x) const |

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

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

747 | #endif |

748 | //@} |

749 | |

750 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

752 | //@{ |

753 | /** |

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

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

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

757 | * found. |

758 | * |

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

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

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

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

763 | */ |

764 | iterator |

765 | find(const key_type& __x) |

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

767 | |

768 | const_iterator |

769 | find(const key_type& __x) const |

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

771 | |

772 | #if __cplusplus > 201103L |

773 | template<typename _Kt> |

774 | auto |

775 | find(const _Kt& __x) |

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

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

778 | |

779 | template<typename _Kt> |

780 | auto |

781 | find(const _Kt& __x) const |

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

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

784 | #endif |

785 | //@} |

786 | |

787 | //@{ |

788 | /** |

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

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

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

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

793 | * |

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

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

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

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

798 | */ |

799 | iterator |

800 | lower_bound(const key_type& __x) |

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

802 | |

803 | const_iterator |

804 | lower_bound(const key_type& __x) const |

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

806 | |

807 | #if __cplusplus > 201103L |

808 | template<typename _Kt> |

809 | auto |

810 | lower_bound(const _Kt& __x) |

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

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

813 | |

814 | template<typename _Kt> |

815 | auto |

816 | lower_bound(const _Kt& __x) const |

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

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

819 | #endif |

820 | //@} |

821 | |

822 | //@{ |

823 | /** |

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

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

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

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

828 | */ |

829 | iterator |

830 | upper_bound(const key_type& __x) |

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

832 | |

833 | const_iterator |

834 | upper_bound(const key_type& __x) const |

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

836 | |

837 | #if __cplusplus > 201103L |

838 | template<typename _Kt> |

839 | auto |

840 | upper_bound(const _Kt& __x) |

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

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

843 | |

844 | template<typename _Kt> |

845 | auto |

846 | upper_bound(const _Kt& __x) const |

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

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

849 | #endif |

850 | //@} |

851 | |

852 | //@{ |

853 | /** |

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

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

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

857 | * matching given key. |

858 | * |

859 | * This function is equivalent to |

860 | * @code |

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

862 | * c.upper_bound(val)) |

863 | * @endcode |

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

865 | * |

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

867 | */ |

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

869 | equal_range(const key_type& __x) |

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

871 | |

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

873 | equal_range(const key_type& __x) const |

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

875 | |

876 | #if __cplusplus > 201103L |

877 | template<typename _Kt> |

878 | auto |

879 | equal_range(const _Kt& __x) |

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

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

882 | |

883 | template<typename _Kt> |

884 | auto |

885 | equal_range(const _Kt& __x) const |

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

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

888 | #endif |

889 | //@} |

890 | |

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

892 | friend bool |

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

894 | |

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

896 | friend bool |

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

898 | }; |

899 | |

900 | |

901 | /** |

902 | * @brief Set equality comparison. |

903 | * @param __x A %set. |

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

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

906 | * |

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

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

909 | * corresponding elements compare equal. |

910 | */ |

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

912 | inline bool |

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

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

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

916 | |

917 | /** |

918 | * @brief Set ordering relation. |

919 | * @param __x A %set. |

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

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

922 | * |

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

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

925 | * |

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

927 | */ |

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

929 | inline bool |

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

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

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

933 | |

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

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

936 | inline bool |

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

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

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

940 | |

941 | /// Returns y < x. |

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

943 | inline bool |

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

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

946 | { return __y < __x; } |

947 | |

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

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

950 | inline bool |

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

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

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

954 | |

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

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 < __y); } |

961 | |

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

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

964 | inline void |

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

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

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

968 | |

969 | _GLIBCXX_END_NAMESPACE_CONTAINER |

970 | |

971 | #if __cplusplus > 201402L |

972 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

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

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

975 | struct |

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

977 | { |

978 | private: |

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

980 | |

981 | static auto& |

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

983 | { return __set._M_t; } |

984 | |

985 | static auto& |

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

987 | { return __set._M_t; } |

988 | }; |

989 | _GLIBCXX_END_NAMESPACE_VERSION |

990 | #endif // C++17 |

991 | |

992 | } //namespace std |

993 | #endif /* _STL_SET_H */ |

994 |