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

2 | |

3 | // Copyright (C) 2010-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 | /** @file bits/unordered_set.h |

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

27 | * Do not attempt to use it directly. @headername{unordered_set} |

28 | */ |

29 | |

30 | #ifndef _UNORDERED_SET_H |

31 | #define _UNORDERED_SET_H |

32 | |

33 | namespace std _GLIBCXX_VISIBILITY(default) |

34 | { |

35 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

36 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

37 | |

38 | /// Base types for unordered_set. |

39 | template<bool _Cache> |

40 | using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; |

41 | |

42 | template<typename _Value, |

43 | typename _Hash = hash<_Value>, |

44 | typename _Pred = std::equal_to<_Value>, |

45 | typename _Alloc = std::allocator<_Value>, |

46 | typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> |

47 | using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, |

48 | __detail::_Identity, _Pred, _Hash, |

49 | __detail::_Mod_range_hashing, |

50 | __detail::_Default_ranged_hash, |

51 | __detail::_Prime_rehash_policy, _Tr>; |

52 | |

53 | /// Base types for unordered_multiset. |

54 | template<bool _Cache> |

55 | using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; |

56 | |

57 | template<typename _Value, |

58 | typename _Hash = hash<_Value>, |

59 | typename _Pred = std::equal_to<_Value>, |

60 | typename _Alloc = std::allocator<_Value>, |

61 | typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> |

62 | using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, |

63 | __detail::_Identity, |

64 | _Pred, _Hash, |

65 | __detail::_Mod_range_hashing, |

66 | __detail::_Default_ranged_hash, |

67 | __detail::_Prime_rehash_policy, _Tr>; |

68 | |

69 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

70 | class unordered_multiset; |

71 | |

72 | /** |

73 | * @brief A standard container composed of unique keys (containing |

74 | * at most one of each key value) in which the elements' keys are |

75 | * the elements themselves. |

76 | * |

77 | * @ingroup unordered_associative_containers |

78 | * |

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

80 | * @tparam _Hash Hashing function object type, defaults to hash<_Value>. |

81 | |

82 | * @tparam _Pred Predicate function object type, defaults to |

83 | * equal_to<_Value>. |

84 | * |

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

86 | * |

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

88 | * <a href="tables.html#xx">unordered associative container</a> |

89 | * |

90 | * Base is _Hashtable, dispatched at compile time via template |

91 | * alias __uset_hashtable. |

92 | */ |

93 | template<typename _Value, |

94 | typename _Hash = hash<_Value>, |

95 | typename _Pred = equal_to<_Value>, |

96 | typename _Alloc = allocator<_Value>> |

97 | class unordered_set |

98 | { |

99 | typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; |

100 | _Hashtable _M_h; |

101 | |

102 | public: |

103 | // typedefs: |

104 | //@{ |

105 | /// Public typedefs. |

106 | typedef typename _Hashtable::key_type key_type; |

107 | typedef typename _Hashtable::value_type value_type; |

108 | typedef typename _Hashtable::hasher hasher; |

109 | typedef typename _Hashtable::key_equal key_equal; |

110 | typedef typename _Hashtable::allocator_type allocator_type; |

111 | //@} |

112 | |

113 | //@{ |

114 | /// Iterator-related typedefs. |

115 | typedef typename _Hashtable::pointer pointer; |

116 | typedef typename _Hashtable::const_pointer const_pointer; |

117 | typedef typename _Hashtable::reference reference; |

118 | typedef typename _Hashtable::const_reference const_reference; |

119 | typedef typename _Hashtable::iterator iterator; |

120 | typedef typename _Hashtable::const_iterator const_iterator; |

121 | typedef typename _Hashtable::local_iterator local_iterator; |

122 | typedef typename _Hashtable::const_local_iterator const_local_iterator; |

123 | typedef typename _Hashtable::size_type size_type; |

124 | typedef typename _Hashtable::difference_type difference_type; |

125 | //@} |

126 | |

127 | #if __cplusplus > 201402L |

128 | using node_type = typename _Hashtable::node_type; |

129 | using insert_return_type = typename _Hashtable::insert_return_type; |

130 | #endif |

131 | |

132 | // construct/destroy/copy |

133 | |

134 | /// Default constructor. |

135 | unordered_set() = default; |

136 | |

137 | /** |

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

139 | * @param __n Minimal initial number of buckets. |

140 | * @param __hf A hash functor. |

141 | * @param __eql A key equality functor. |

142 | * @param __a An allocator object. |

143 | */ |

144 | explicit |

145 | unordered_set(size_type __n, |

146 | const hasher& __hf = hasher(), |

147 | const key_equal& __eql = key_equal(), |

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

149 | : _M_h(__n, __hf, __eql, __a) |

150 | { } |

151 | |

152 | /** |

153 | * @brief Builds an %unordered_set from a range. |

154 | * @param __first An input iterator. |

155 | * @param __last An input iterator. |

156 | * @param __n Minimal initial number of buckets. |

157 | * @param __hf A hash functor. |

158 | * @param __eql A key equality functor. |

159 | * @param __a An allocator object. |

160 | * |

161 | * Create an %unordered_set consisting of copies of the elements from |

162 | * [__first,__last). This is linear in N (where N is |

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

164 | */ |

165 | template<typename _InputIterator> |

166 | unordered_set(_InputIterator __first, _InputIterator __last, |

167 | size_type __n = 0, |

168 | const hasher& __hf = hasher(), |

169 | const key_equal& __eql = key_equal(), |

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

171 | : _M_h(__first, __last, __n, __hf, __eql, __a) |

172 | { } |

173 | |

174 | /// Copy constructor. |

175 | unordered_set(const unordered_set&) = default; |

176 | |

177 | /// Move constructor. |

178 | unordered_set(unordered_set&&) = default; |

179 | |

180 | /** |

181 | * @brief Creates an %unordered_set with no elements. |

182 | * @param __a An allocator object. |

183 | */ |

184 | explicit |

185 | unordered_set(const allocator_type& __a) |

186 | : _M_h(__a) |

187 | { } |

188 | |

189 | /* |

190 | * @brief Copy constructor with allocator argument. |

191 | * @param __uset Input %unordered_set to copy. |

192 | * @param __a An allocator object. |

193 | */ |

194 | unordered_set(const unordered_set& __uset, |

195 | const allocator_type& __a) |

196 | : _M_h(__uset._M_h, __a) |

197 | { } |

198 | |

199 | /* |

200 | * @brief Move constructor with allocator argument. |

201 | * @param __uset Input %unordered_set to move. |

202 | * @param __a An allocator object. |

203 | */ |

204 | unordered_set(unordered_set&& __uset, |

205 | const allocator_type& __a) |

206 | : _M_h(std::move(__uset._M_h), __a) |

207 | { } |

208 | |

209 | /** |

210 | * @brief Builds an %unordered_set from an initializer_list. |

211 | * @param __l An initializer_list. |

212 | * @param __n Minimal initial number of buckets. |

213 | * @param __hf A hash functor. |

214 | * @param __eql A key equality functor. |

215 | * @param __a An allocator object. |

216 | * |

217 | * Create an %unordered_set consisting of copies of the elements in the |

218 | * list. This is linear in N (where N is @a __l.size()). |

219 | */ |

220 | unordered_set(initializer_list<value_type> __l, |

221 | size_type __n = 0, |

222 | const hasher& __hf = hasher(), |

223 | const key_equal& __eql = key_equal(), |

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

225 | : _M_h(__l, __n, __hf, __eql, __a) |

226 | { } |

227 | |

228 | unordered_set(size_type __n, const allocator_type& __a) |

229 | : unordered_set(__n, hasher(), key_equal(), __a) |

230 | { } |

231 | |

232 | unordered_set(size_type __n, const hasher& __hf, |

233 | const allocator_type& __a) |

234 | : unordered_set(__n, __hf, key_equal(), __a) |

235 | { } |

236 | |

237 | template<typename _InputIterator> |

238 | unordered_set(_InputIterator __first, _InputIterator __last, |

239 | size_type __n, |

240 | const allocator_type& __a) |

241 | : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) |

242 | { } |

243 | |

244 | template<typename _InputIterator> |

245 | unordered_set(_InputIterator __first, _InputIterator __last, |

246 | size_type __n, const hasher& __hf, |

247 | const allocator_type& __a) |

248 | : unordered_set(__first, __last, __n, __hf, key_equal(), __a) |

249 | { } |

250 | |

251 | unordered_set(initializer_list<value_type> __l, |

252 | size_type __n, |

253 | const allocator_type& __a) |

254 | : unordered_set(__l, __n, hasher(), key_equal(), __a) |

255 | { } |

256 | |

257 | unordered_set(initializer_list<value_type> __l, |

258 | size_type __n, const hasher& __hf, |

259 | const allocator_type& __a) |

260 | : unordered_set(__l, __n, __hf, key_equal(), __a) |

261 | { } |

262 | |

263 | /// Copy assignment operator. |

264 | unordered_set& |

265 | operator=(const unordered_set&) = default; |

266 | |

267 | /// Move assignment operator. |

268 | unordered_set& |

269 | operator=(unordered_set&&) = default; |

270 | |

271 | /** |

272 | * @brief %Unordered_set list assignment operator. |

273 | * @param __l An initializer_list. |

274 | * |

275 | * This function fills an %unordered_set with copies of the elements in |

276 | * the initializer list @a __l. |

277 | * |

278 | * Note that the assignment completely changes the %unordered_set and |

279 | * that the resulting %unordered_set's size is the same as the number |

280 | * of elements assigned. |

281 | */ |

282 | unordered_set& |

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

284 | { |

285 | _M_h = __l; |

286 | return *this; |

287 | } |

288 | |

289 | /// Returns the allocator object used by the %unordered_set. |

290 | allocator_type |

291 | get_allocator() const noexcept |

292 | { return _M_h.get_allocator(); } |

293 | |

294 | // size and capacity: |

295 | |

296 | /// Returns true if the %unordered_set is empty. |

297 | bool |

298 | empty() const noexcept |

299 | { return _M_h.empty(); } |

300 | |

301 | /// Returns the size of the %unordered_set. |

302 | size_type |

303 | size() const noexcept |

304 | { return _M_h.size(); } |

305 | |

306 | /// Returns the maximum size of the %unordered_set. |

307 | size_type |

308 | max_size() const noexcept |

309 | { return _M_h.max_size(); } |

310 | |

311 | // iterators. |

312 | |

313 | //@{ |

314 | /** |

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

316 | * element in the %unordered_set. |

317 | */ |

318 | iterator |

319 | begin() noexcept |

320 | { return _M_h.begin(); } |

321 | |

322 | const_iterator |

323 | begin() const noexcept |

324 | { return _M_h.begin(); } |

325 | //@} |

326 | |

327 | //@{ |

328 | /** |

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

330 | * element in the %unordered_set. |

331 | */ |

332 | iterator |

333 | end() noexcept |

334 | { return _M_h.end(); } |

335 | |

336 | const_iterator |

337 | end() const noexcept |

338 | { return _M_h.end(); } |

339 | //@} |

340 | |

341 | /** |

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

343 | * element in the %unordered_set. |

344 | */ |

345 | const_iterator |

346 | cbegin() const noexcept |

347 | { return _M_h.begin(); } |

348 | |

349 | /** |

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

351 | * element in the %unordered_set. |

352 | */ |

353 | const_iterator |

354 | cend() const noexcept |

355 | { return _M_h.end(); } |

356 | |

357 | // modifiers. |

358 | |

359 | /** |

360 | * @brief Attempts to build and insert an element into the |

361 | * %unordered_set. |

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

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

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

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

366 | * |

367 | * This function attempts to build and insert an element into the |

368 | * %unordered_set. An %unordered_set relies on unique keys and thus an |

369 | * element is only inserted if it is not already present in the |

370 | * %unordered_set. |

371 | * |

372 | * Insertion requires amortized constant time. |

373 | */ |

374 | template<typename... _Args> |

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

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

377 | { return _M_h.emplace(std::forward<_Args>(__args)...); } |

378 | |

379 | /** |

380 | * @brief Attempts to insert an element into the %unordered_set. |

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

382 | * element should be inserted. |

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

384 | * inserted. |

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

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

387 | * element itself). |

388 | * |

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

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

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

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

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

394 | * |

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

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

397 | * |

398 | * Insertion requires amortized constant time. |

399 | */ |

400 | template<typename... _Args> |

401 | iterator |

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

403 | { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } |

404 | |

405 | //@{ |

406 | /** |

407 | * @brief Attempts to insert an element into the %unordered_set. |

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

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

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

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

412 | * |

413 | * This function attempts to insert an element into the %unordered_set. |

414 | * An %unordered_set relies on unique keys and thus an element is only |

415 | * inserted if it is not already present in the %unordered_set. |

416 | * |

417 | * Insertion requires amortized constant time. |

418 | */ |

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

420 | insert(const value_type& __x) |

421 | { return _M_h.insert(__x); } |

422 | |

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

424 | insert(value_type&& __x) |

425 | { return _M_h.insert(std::move(__x)); } |

426 | //@} |

427 | |

428 | //@{ |

429 | /** |

430 | * @brief Attempts to insert an element into the %unordered_set. |

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

432 | * element should be inserted. |

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

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

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

436 | * |

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

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

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

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

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

442 | * |

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

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

445 | * |

446 | * Insertion requires amortized constant. |

447 | */ |

448 | iterator |

449 | insert(const_iterator __hint, const value_type& __x) |

450 | { return _M_h.insert(__hint, __x); } |

451 | |

452 | iterator |

453 | insert(const_iterator __hint, value_type&& __x) |

454 | { return _M_h.insert(__hint, std::move(__x)); } |

455 | //@} |

456 | |

457 | /** |

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

459 | * elements. |

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

461 | * inserted. |

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

463 | * |

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

465 | */ |

466 | template<typename _InputIterator> |

467 | void |

468 | insert(_InputIterator __first, _InputIterator __last) |

469 | { _M_h.insert(__first, __last); } |

470 | |

471 | /** |

472 | * @brief Attempts to insert a list of elements into the %unordered_set. |

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

474 | * to be inserted. |

475 | * |

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

477 | */ |

478 | void |

479 | insert(initializer_list<value_type> __l) |

480 | { _M_h.insert(__l); } |

481 | |

482 | #if __cplusplus > 201402L |

483 | /// Extract a node. |

484 | node_type |

485 | extract(const_iterator __pos) |

486 | { |

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

488 | return _M_h.extract(__pos); |

489 | } |

490 | |

491 | /// Extract a node. |

492 | node_type |

493 | extract(const key_type& __key) |

494 | { return _M_h.extract(__key); } |

495 | |

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

497 | insert_return_type |

498 | insert(node_type&& __nh) |

499 | { return _M_h._M_reinsert_node(std::move(__nh)); } |

500 | |

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

502 | iterator |

503 | insert(const_iterator, node_type&& __nh) |

504 | { return _M_h._M_reinsert_node(std::move(__nh)).position; } |

505 | #endif // C++17 |

506 | |

507 | //@{ |

508 | /** |

509 | * @brief Erases an element from an %unordered_set. |

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

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

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

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

514 | * |

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

516 | * from an %unordered_set. Note that this function only erases the |

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

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

519 | * responsibility. |

520 | */ |

521 | iterator |

522 | erase(const_iterator __position) |

523 | { return _M_h.erase(__position); } |

524 | |

525 | // LWG 2059. |

526 | iterator |

527 | erase(iterator __position) |

528 | { return _M_h.erase(__position); } |

529 | //@} |

530 | |

531 | /** |

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

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

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

535 | * |

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

537 | * an %unordered_set. For an %unordered_set the result of this function |

538 | * can only be 0 (not present) or 1 (present). |

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

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

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

542 | */ |

543 | size_type |

544 | erase(const key_type& __x) |

545 | { return _M_h.erase(__x); } |

546 | |

547 | /** |

548 | * @brief Erases a [__first,__last) range of elements from an |

549 | * %unordered_set. |

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

551 | * erased. |

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

553 | * be erased. |

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

555 | * |

556 | * This function erases a sequence of elements from an %unordered_set. |

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

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

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

560 | */ |

561 | iterator |

562 | erase(const_iterator __first, const_iterator __last) |

563 | { return _M_h.erase(__first, __last); } |

564 | |

565 | /** |

566 | * Erases all elements in an %unordered_set. Note that this function only |

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

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

569 | * is the user's responsibility. |

570 | */ |

571 | void |

572 | clear() noexcept |

573 | { _M_h.clear(); } |

574 | |

575 | /** |

576 | * @brief Swaps data with another %unordered_set. |

577 | * @param __x An %unordered_set of the same element and allocator |

578 | * types. |

579 | * |

580 | * This exchanges the elements between two sets in constant time. |

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

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

583 | */ |

584 | void |

585 | swap(unordered_set& __x) |

586 | noexcept( noexcept(_M_h.swap(__x._M_h)) ) |

587 | { _M_h.swap(__x._M_h); } |

588 | |

589 | #if __cplusplus > 201402L |

590 | template<typename, typename, typename> |

591 | friend class std::_Hash_merge_helper; |

592 | |

593 | template<typename _H2, typename _P2> |

594 | void |

595 | merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) |

596 | { |

597 | using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; |

598 | _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); |

599 | } |

600 | |

601 | template<typename _H2, typename _P2> |

602 | void |

603 | merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) |

604 | { merge(__source); } |

605 | |

606 | template<typename _H2, typename _P2> |

607 | void |

608 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) |

609 | { |

610 | using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; |

611 | _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); |

612 | } |

613 | |

614 | template<typename _H2, typename _P2> |

615 | void |

616 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) |

617 | { merge(__source); } |

618 | #endif // C++17 |

619 | |

620 | // observers. |

621 | |

622 | /// Returns the hash functor object with which the %unordered_set was |

623 | /// constructed. |

624 | hasher |

625 | hash_function() const |

626 | { return _M_h.hash_function(); } |

627 | |

628 | /// Returns the key comparison object with which the %unordered_set was |

629 | /// constructed. |

630 | key_equal |

631 | key_eq() const |

632 | { return _M_h.key_eq(); } |

633 | |

634 | // lookup. |

635 | |

636 | //@{ |

637 | /** |

638 | * @brief Tries to locate an element in an %unordered_set. |

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

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

641 | * found. |

642 | * |

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

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

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

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

647 | */ |

648 | iterator |

649 | find(const key_type& __x) |

650 | { return _M_h.find(__x); } |

651 | |

652 | const_iterator |

653 | find(const key_type& __x) const |

654 | { return _M_h.find(__x); } |

655 | //@} |

656 | |

657 | /** |

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

659 | * @param __x Element to located. |

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

661 | * |

662 | * This function only makes sense for unordered_multisets; for |

663 | * unordered_set the result will either be 0 (not present) or 1 |

664 | * (present). |

665 | */ |

666 | size_type |

667 | count(const key_type& __x) const |

668 | { return _M_h.count(__x); } |

669 | |

670 | //@{ |

671 | /** |

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

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

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

675 | * matching given key. |

676 | * |

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

678 | */ |

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

680 | equal_range(const key_type& __x) |

681 | { return _M_h.equal_range(__x); } |

682 | |

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

684 | equal_range(const key_type& __x) const |

685 | { return _M_h.equal_range(__x); } |

686 | //@} |

687 | |

688 | // bucket interface. |

689 | |

690 | /// Returns the number of buckets of the %unordered_set. |

691 | size_type |

692 | bucket_count() const noexcept |

693 | { return _M_h.bucket_count(); } |

694 | |

695 | /// Returns the maximum number of buckets of the %unordered_set. |

696 | size_type |

697 | max_bucket_count() const noexcept |

698 | { return _M_h.max_bucket_count(); } |

699 | |

700 | /* |

701 | * @brief Returns the number of elements in a given bucket. |

702 | * @param __n A bucket index. |

703 | * @return The number of elements in the bucket. |

704 | */ |

705 | size_type |

706 | bucket_size(size_type __n) const |

707 | { return _M_h.bucket_size(__n); } |

708 | |

709 | /* |

710 | * @brief Returns the bucket index of a given element. |

711 | * @param __key A key instance. |

712 | * @return The key bucket index. |

713 | */ |

714 | size_type |

715 | bucket(const key_type& __key) const |

716 | { return _M_h.bucket(__key); } |

717 | |

718 | //@{ |

719 | /** |

720 | * @brief Returns a read-only (constant) iterator pointing to the first |

721 | * bucket element. |

722 | * @param __n The bucket index. |

723 | * @return A read-only local iterator. |

724 | */ |

725 | local_iterator |

726 | begin(size_type __n) |

727 | { return _M_h.begin(__n); } |

728 | |

729 | const_local_iterator |

730 | begin(size_type __n) const |

731 | { return _M_h.begin(__n); } |

732 | |

733 | const_local_iterator |

734 | cbegin(size_type __n) const |

735 | { return _M_h.cbegin(__n); } |

736 | //@} |

737 | |

738 | //@{ |

739 | /** |

740 | * @brief Returns a read-only (constant) iterator pointing to one past |

741 | * the last bucket elements. |

742 | * @param __n The bucket index. |

743 | * @return A read-only local iterator. |

744 | */ |

745 | local_iterator |

746 | end(size_type __n) |

747 | { return _M_h.end(__n); } |

748 | |

749 | const_local_iterator |

750 | end(size_type __n) const |

751 | { return _M_h.end(__n); } |

752 | |

753 | const_local_iterator |

754 | cend(size_type __n) const |

755 | { return _M_h.cend(__n); } |

756 | //@} |

757 | |

758 | // hash policy. |

759 | |

760 | /// Returns the average number of elements per bucket. |

761 | float |

762 | load_factor() const noexcept |

763 | { return _M_h.load_factor(); } |

764 | |

765 | /// Returns a positive number that the %unordered_set tries to keep the |

766 | /// load factor less than or equal to. |

767 | float |

768 | max_load_factor() const noexcept |

769 | { return _M_h.max_load_factor(); } |

770 | |

771 | /** |

772 | * @brief Change the %unordered_set maximum load factor. |

773 | * @param __z The new maximum load factor. |

774 | */ |

775 | void |

776 | max_load_factor(float __z) |

777 | { _M_h.max_load_factor(__z); } |

778 | |

779 | /** |

780 | * @brief May rehash the %unordered_set. |

781 | * @param __n The new number of buckets. |

782 | * |

783 | * Rehash will occur only if the new number of buckets respect the |

784 | * %unordered_set maximum load factor. |

785 | */ |

786 | void |

787 | rehash(size_type __n) |

788 | { _M_h.rehash(__n); } |

789 | |

790 | /** |

791 | * @brief Prepare the %unordered_set for a specified number of |

792 | * elements. |

793 | * @param __n Number of elements required. |

794 | * |

795 | * Same as rehash(ceil(n / max_load_factor())). |

796 | */ |

797 | void |

798 | reserve(size_type __n) |

799 | { _M_h.reserve(__n); } |

800 | |

801 | template<typename _Value1, typename _Hash1, typename _Pred1, |

802 | typename _Alloc1> |

803 | friend bool |

804 | operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&, |

805 | const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&); |

806 | }; |

807 | |

808 | #if __cpp_deduction_guides >= 201606 |

809 | |

810 | template<typename _InputIterator, |

811 | typename _Hash = |

812 | hash<typename iterator_traits<_InputIterator>::value_type>, |

813 | typename _Pred = |

814 | equal_to<typename iterator_traits<_InputIterator>::value_type>, |

815 | typename _Allocator = |

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

817 | typename = _RequireInputIter<_InputIterator>, |

818 | typename = _RequireAllocator<_Allocator>> |

819 | unordered_set(_InputIterator, _InputIterator, |

820 | unordered_set<int>::size_type = {}, |

821 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |

822 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, |

823 | _Hash, _Pred, _Allocator>; |

824 | |

825 | template<typename _Tp, typename _Hash = hash<_Tp>, |

826 | typename _Pred = equal_to<_Tp>, |

827 | typename _Allocator = allocator<_Tp>, |

828 | typename = _RequireAllocator<_Allocator>> |

829 | unordered_set(initializer_list<_Tp>, |

830 | unordered_set<int>::size_type = {}, |

831 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |

832 | -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; |

833 | |

834 | template<typename _InputIterator, typename _Allocator, |

835 | typename = _RequireInputIter<_InputIterator>, |

836 | typename = _RequireAllocator<_Allocator>> |

837 | unordered_set(_InputIterator, _InputIterator, |

838 | unordered_set<int>::size_type, _Allocator) |

839 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, |

840 | hash< |

841 | typename iterator_traits<_InputIterator>::value_type>, |

842 | equal_to< |

843 | typename iterator_traits<_InputIterator>::value_type>, |

844 | _Allocator>; |

845 | |

846 | template<typename _InputIterator, typename _Hash, typename _Allocator, |

847 | typename = _RequireInputIter<_InputIterator>, |

848 | typename = _RequireAllocator<_Allocator>> |

849 | unordered_set(_InputIterator, _InputIterator, |

850 | unordered_set<int>::size_type, |

851 | _Hash, _Allocator) |

852 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, |

853 | _Hash, |

854 | equal_to< |

855 | typename iterator_traits<_InputIterator>::value_type>, |

856 | _Allocator>; |

857 | |

858 | template<typename _Tp, typename _Allocator, |

859 | typename = _RequireAllocator<_Allocator>> |

860 | unordered_set(initializer_list<_Tp>, |

861 | unordered_set<int>::size_type, _Allocator) |

862 | -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; |

863 | |

864 | template<typename _Tp, typename _Hash, typename _Allocator, |

865 | typename = _RequireAllocator<_Allocator>> |

866 | unordered_set(initializer_list<_Tp>, |

867 | unordered_set<int>::size_type, _Hash, _Allocator) |

868 | -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; |

869 | |

870 | #endif |

871 | |

872 | /** |

873 | * @brief A standard container composed of equivalent keys |

874 | * (possibly containing multiple of each key value) in which the |

875 | * elements' keys are the elements themselves. |

876 | * |

877 | * @ingroup unordered_associative_containers |

878 | * |

879 | * @tparam _Value Type of key objects. |

880 | * @tparam _Hash Hashing function object type, defaults to hash<_Value>. |

881 | * @tparam _Pred Predicate function object type, defaults |

882 | * to equal_to<_Value>. |

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

884 | * |

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

886 | * <a href="tables.html#xx">unordered associative container</a> |

887 | * |

888 | * Base is _Hashtable, dispatched at compile time via template |

889 | * alias __umset_hashtable. |

890 | */ |

891 | template<typename _Value, |

892 | typename _Hash = hash<_Value>, |

893 | typename _Pred = equal_to<_Value>, |

894 | typename _Alloc = allocator<_Value>> |

895 | class unordered_multiset |

896 | { |

897 | typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; |

898 | _Hashtable _M_h; |

899 | |

900 | public: |

901 | // typedefs: |

902 | //@{ |

903 | /// Public typedefs. |

904 | typedef typename _Hashtable::key_type key_type; |

905 | typedef typename _Hashtable::value_type value_type; |

906 | typedef typename _Hashtable::hasher hasher; |

907 | typedef typename _Hashtable::key_equal key_equal; |

908 | typedef typename _Hashtable::allocator_type allocator_type; |

909 | //@} |

910 | |

911 | //@{ |

912 | /// Iterator-related typedefs. |

913 | typedef typename _Hashtable::pointer pointer; |

914 | typedef typename _Hashtable::const_pointer const_pointer; |

915 | typedef typename _Hashtable::reference reference; |

916 | typedef typename _Hashtable::const_reference const_reference; |

917 | typedef typename _Hashtable::iterator iterator; |

918 | typedef typename _Hashtable::const_iterator const_iterator; |

919 | typedef typename _Hashtable::local_iterator local_iterator; |

920 | typedef typename _Hashtable::const_local_iterator const_local_iterator; |

921 | typedef typename _Hashtable::size_type size_type; |

922 | typedef typename _Hashtable::difference_type difference_type; |

923 | //@} |

924 | |

925 | #if __cplusplus > 201402L |

926 | using node_type = typename _Hashtable::node_type; |

927 | #endif |

928 | |

929 | // construct/destroy/copy |

930 | |

931 | /// Default constructor. |

932 | unordered_multiset() = default; |

933 | |

934 | /** |

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

936 | * @param __n Minimal initial number of buckets. |

937 | * @param __hf A hash functor. |

938 | * @param __eql A key equality functor. |

939 | * @param __a An allocator object. |

940 | */ |

941 | explicit |

942 | unordered_multiset(size_type __n, |

943 | const hasher& __hf = hasher(), |

944 | const key_equal& __eql = key_equal(), |

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

946 | : _M_h(__n, __hf, __eql, __a) |

947 | { } |

948 | |

949 | /** |

950 | * @brief Builds an %unordered_multiset from a range. |

951 | * @param __first An input iterator. |

952 | * @param __last An input iterator. |

953 | * @param __n Minimal initial number of buckets. |

954 | * @param __hf A hash functor. |

955 | * @param __eql A key equality functor. |

956 | * @param __a An allocator object. |

957 | * |

958 | * Create an %unordered_multiset consisting of copies of the elements |

959 | * from [__first,__last). This is linear in N (where N is |

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

961 | */ |

962 | template<typename _InputIterator> |

963 | unordered_multiset(_InputIterator __first, _InputIterator __last, |

964 | size_type __n = 0, |

965 | const hasher& __hf = hasher(), |

966 | const key_equal& __eql = key_equal(), |

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

968 | : _M_h(__first, __last, __n, __hf, __eql, __a) |

969 | { } |

970 | |

971 | /// Copy constructor. |

972 | unordered_multiset(const unordered_multiset&) = default; |

973 | |

974 | /// Move constructor. |

975 | unordered_multiset(unordered_multiset&&) = default; |

976 | |

977 | /** |

978 | * @brief Builds an %unordered_multiset from an initializer_list. |

979 | * @param __l An initializer_list. |

980 | * @param __n Minimal initial number of buckets. |

981 | * @param __hf A hash functor. |

982 | * @param __eql A key equality functor. |

983 | * @param __a An allocator object. |

984 | * |

985 | * Create an %unordered_multiset consisting of copies of the elements in |

986 | * the list. This is linear in N (where N is @a __l.size()). |

987 | */ |

988 | unordered_multiset(initializer_list<value_type> __l, |

989 | size_type __n = 0, |

990 | const hasher& __hf = hasher(), |

991 | const key_equal& __eql = key_equal(), |

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

993 | : _M_h(__l, __n, __hf, __eql, __a) |

994 | { } |

995 | |

996 | /// Copy assignment operator. |

997 | unordered_multiset& |

998 | operator=(const unordered_multiset&) = default; |

999 | |

1000 | /// Move assignment operator. |

1001 | unordered_multiset& |

1002 | operator=(unordered_multiset&&) = default; |

1003 | |

1004 | /** |

1005 | * @brief Creates an %unordered_multiset with no elements. |

1006 | * @param __a An allocator object. |

1007 | */ |

1008 | explicit |

1009 | unordered_multiset(const allocator_type& __a) |

1010 | : _M_h(__a) |

1011 | { } |

1012 | |

1013 | /* |

1014 | * @brief Copy constructor with allocator argument. |

1015 | * @param __uset Input %unordered_multiset to copy. |

1016 | * @param __a An allocator object. |

1017 | */ |

1018 | unordered_multiset(const unordered_multiset& __umset, |

1019 | const allocator_type& __a) |

1020 | : _M_h(__umset._M_h, __a) |

1021 | { } |

1022 | |

1023 | /* |

1024 | * @brief Move constructor with allocator argument. |

1025 | * @param __umset Input %unordered_multiset to move. |

1026 | * @param __a An allocator object. |

1027 | */ |

1028 | unordered_multiset(unordered_multiset&& __umset, |

1029 | const allocator_type& __a) |

1030 | : _M_h(std::move(__umset._M_h), __a) |

1031 | { } |

1032 | |

1033 | unordered_multiset(size_type __n, const allocator_type& __a) |

1034 | : unordered_multiset(__n, hasher(), key_equal(), __a) |

1035 | { } |

1036 | |

1037 | unordered_multiset(size_type __n, const hasher& __hf, |

1038 | const allocator_type& __a) |

1039 | : unordered_multiset(__n, __hf, key_equal(), __a) |

1040 | { } |

1041 | |

1042 | template<typename _InputIterator> |

1043 | unordered_multiset(_InputIterator __first, _InputIterator __last, |

1044 | size_type __n, |

1045 | const allocator_type& __a) |

1046 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) |

1047 | { } |

1048 | |

1049 | template<typename _InputIterator> |

1050 | unordered_multiset(_InputIterator __first, _InputIterator __last, |

1051 | size_type __n, const hasher& __hf, |

1052 | const allocator_type& __a) |

1053 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) |

1054 | { } |

1055 | |

1056 | unordered_multiset(initializer_list<value_type> __l, |

1057 | size_type __n, |

1058 | const allocator_type& __a) |

1059 | : unordered_multiset(__l, __n, hasher(), key_equal(), __a) |

1060 | { } |

1061 | |

1062 | unordered_multiset(initializer_list<value_type> __l, |

1063 | size_type __n, const hasher& __hf, |

1064 | const allocator_type& __a) |

1065 | : unordered_multiset(__l, __n, __hf, key_equal(), __a) |

1066 | { } |

1067 | |

1068 | /** |

1069 | * @brief %Unordered_multiset list assignment operator. |

1070 | * @param __l An initializer_list. |

1071 | * |

1072 | * This function fills an %unordered_multiset with copies of the elements |

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

1074 | * |

1075 | * Note that the assignment completely changes the %unordered_multiset |

1076 | * and that the resulting %unordered_multiset's size is the same as the |

1077 | * number of elements assigned. |

1078 | */ |

1079 | unordered_multiset& |

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

1081 | { |

1082 | _M_h = __l; |

1083 | return *this; |

1084 | } |

1085 | |

1086 | /// Returns the allocator object used by the %unordered_multiset. |

1087 | allocator_type |

1088 | get_allocator() const noexcept |

1089 | { return _M_h.get_allocator(); } |

1090 | |

1091 | // size and capacity: |

1092 | |

1093 | /// Returns true if the %unordered_multiset is empty. |

1094 | bool |

1095 | empty() const noexcept |

1096 | { return _M_h.empty(); } |

1097 | |

1098 | /// Returns the size of the %unordered_multiset. |

1099 | size_type |

1100 | size() const noexcept |

1101 | { return _M_h.size(); } |

1102 | |

1103 | /// Returns the maximum size of the %unordered_multiset. |

1104 | size_type |

1105 | max_size() const noexcept |

1106 | { return _M_h.max_size(); } |

1107 | |

1108 | // iterators. |

1109 | |

1110 | //@{ |

1111 | /** |

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

1113 | * element in the %unordered_multiset. |

1114 | */ |

1115 | iterator |

1116 | begin() noexcept |

1117 | { return _M_h.begin(); } |

1118 | |

1119 | const_iterator |

1120 | begin() const noexcept |

1121 | { return _M_h.begin(); } |

1122 | //@} |

1123 | |

1124 | //@{ |

1125 | /** |

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

1127 | * element in the %unordered_multiset. |

1128 | */ |

1129 | iterator |

1130 | end() noexcept |

1131 | { return _M_h.end(); } |

1132 | |

1133 | const_iterator |

1134 | end() const noexcept |

1135 | { return _M_h.end(); } |

1136 | //@} |

1137 | |

1138 | /** |

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

1140 | * element in the %unordered_multiset. |

1141 | */ |

1142 | const_iterator |

1143 | cbegin() const noexcept |

1144 | { return _M_h.begin(); } |

1145 | |

1146 | /** |

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

1148 | * element in the %unordered_multiset. |

1149 | */ |

1150 | const_iterator |

1151 | cend() const noexcept |

1152 | { return _M_h.end(); } |

1153 | |

1154 | // modifiers. |

1155 | |

1156 | /** |

1157 | * @brief Builds and insert an element into the %unordered_multiset. |

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

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

1160 | * |

1161 | * Insertion requires amortized constant time. |

1162 | */ |

1163 | template<typename... _Args> |

1164 | iterator |

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

1166 | { return _M_h.emplace(std::forward<_Args>(__args)...); } |

1167 | |

1168 | /** |

1169 | * @brief Inserts an element into the %unordered_multiset. |

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

1171 | * element should be inserted. |

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

1173 | * inserted. |

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

1175 | * |

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

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

1178 | * cause no gains in efficiency. |

1179 | * |

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

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

1182 | * |

1183 | * Insertion requires amortized constant time. |

1184 | */ |

1185 | template<typename... _Args> |

1186 | iterator |

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

1188 | { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } |

1189 | |

1190 | //@{ |

1191 | /** |

1192 | * @brief Inserts an element into the %unordered_multiset. |

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

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

1195 | * |

1196 | * Insertion requires amortized constant time. |

1197 | */ |

1198 | iterator |

1199 | insert(const value_type& __x) |

1200 | { return _M_h.insert(__x); } |

1201 | |

1202 | iterator |

1203 | insert(value_type&& __x) |

1204 | { return _M_h.insert(std::move(__x)); } |

1205 | //@} |

1206 | |

1207 | //@{ |

1208 | /** |

1209 | * @brief Inserts an element into the %unordered_multiset. |

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

1211 | * element should be inserted. |

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

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

1214 | * |

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

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

1217 | * cause no gains in efficiency. |

1218 | * |

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

1220 | |

1221 | * |

1222 | * Insertion requires amortized constant. |

1223 | */ |

1224 | iterator |

1225 | insert(const_iterator __hint, const value_type& __x) |

1226 | { return _M_h.insert(__hint, __x); } |

1227 | |

1228 | iterator |

1229 | insert(const_iterator __hint, value_type&& __x) |

1230 | { return _M_h.insert(__hint, std::move(__x)); } |

1231 | //@} |

1232 | |

1233 | /** |

1234 | * @brief A template function that inserts a range of elements. |

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

1236 | * inserted. |

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

1238 | * |

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

1240 | */ |

1241 | template<typename _InputIterator> |

1242 | void |

1243 | insert(_InputIterator __first, _InputIterator __last) |

1244 | { _M_h.insert(__first, __last); } |

1245 | |

1246 | /** |

1247 | * @brief Inserts a list of elements into the %unordered_multiset. |

1248 | * @param __l A std::initializer_list<value_type> of elements to be |

1249 | * inserted. |

1250 | * |

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

1252 | */ |

1253 | void |

1254 | insert(initializer_list<value_type> __l) |

1255 | { _M_h.insert(__l); } |

1256 | |

1257 | #if __cplusplus > 201402L |

1258 | /// Extract a node. |

1259 | node_type |

1260 | extract(const_iterator __pos) |

1261 | { |

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

1263 | return _M_h.extract(__pos); |

1264 | } |

1265 | |

1266 | /// Extract a node. |

1267 | node_type |

1268 | extract(const key_type& __key) |

1269 | { return _M_h.extract(__key); } |

1270 | |

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

1272 | iterator |

1273 | insert(node_type&& __nh) |

1274 | { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } |

1275 | |

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

1277 | iterator |

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

1279 | { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } |

1280 | #endif // C++17 |

1281 | |

1282 | //@{ |

1283 | /** |

1284 | * @brief Erases an element from an %unordered_multiset. |

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

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

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

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

1289 | * |

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

1291 | * from an %unordered_multiset. |

1292 | * |

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

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

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

1296 | */ |

1297 | iterator |

1298 | erase(const_iterator __position) |

1299 | { return _M_h.erase(__position); } |

1300 | |

1301 | // LWG 2059. |

1302 | iterator |

1303 | erase(iterator __position) |

1304 | { return _M_h.erase(__position); } |

1305 | //@} |

1306 | |

1307 | |

1308 | /** |

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

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

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

1312 | * |

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

1314 | * an %unordered_multiset. |

1315 | * |

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

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

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

1319 | */ |

1320 | size_type |

1321 | erase(const key_type& __x) |

1322 | { return _M_h.erase(__x); } |

1323 | |

1324 | /** |

1325 | * @brief Erases a [__first,__last) range of elements from an |

1326 | * %unordered_multiset. |

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

1328 | * erased. |

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

1330 | * be erased. |

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

1332 | * |

1333 | * This function erases a sequence of elements from an |

1334 | * %unordered_multiset. |

1335 | * |

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

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

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

1339 | */ |

1340 | iterator |

1341 | erase(const_iterator __first, const_iterator __last) |

1342 | { return _M_h.erase(__first, __last); } |

1343 | |

1344 | /** |

1345 | * Erases all elements in an %unordered_multiset. |

1346 | * |

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

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

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

1350 | */ |

1351 | void |

1352 | clear() noexcept |

1353 | { _M_h.clear(); } |

1354 | |

1355 | /** |

1356 | * @brief Swaps data with another %unordered_multiset. |

1357 | * @param __x An %unordered_multiset of the same element and allocator |

1358 | * types. |

1359 | * |

1360 | * This exchanges the elements between two sets in constant time. |

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

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

1363 | */ |

1364 | void |

1365 | swap(unordered_multiset& __x) |

1366 | noexcept( noexcept(_M_h.swap(__x._M_h)) ) |

1367 | { _M_h.swap(__x._M_h); } |

1368 | |

1369 | #if __cplusplus > 201402L |

1370 | template<typename, typename, typename> |

1371 | friend class std::_Hash_merge_helper; |

1372 | |

1373 | template<typename _H2, typename _P2> |

1374 | void |

1375 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) |

1376 | { |

1377 | using _Merge_helper |

1378 | = _Hash_merge_helper<unordered_multiset, _H2, _P2>; |

1379 | _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); |

1380 | } |

1381 | |

1382 | template<typename _H2, typename _P2> |

1383 | void |

1384 | merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) |

1385 | { merge(__source); } |

1386 | |

1387 | template<typename _H2, typename _P2> |

1388 | void |

1389 | merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) |

1390 | { |

1391 | using _Merge_helper |

1392 | = _Hash_merge_helper<unordered_multiset, _H2, _P2>; |

1393 | _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); |

1394 | } |

1395 | |

1396 | template<typename _H2, typename _P2> |

1397 | void |

1398 | merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) |

1399 | { merge(__source); } |

1400 | #endif // C++17 |

1401 | |

1402 | // observers. |

1403 | |

1404 | /// Returns the hash functor object with which the %unordered_multiset |

1405 | /// was constructed. |

1406 | hasher |

1407 | hash_function() const |

1408 | { return _M_h.hash_function(); } |

1409 | |

1410 | /// Returns the key comparison object with which the %unordered_multiset |

1411 | /// was constructed. |

1412 | key_equal |

1413 | key_eq() const |

1414 | { return _M_h.key_eq(); } |

1415 | |

1416 | // lookup. |

1417 | |

1418 | //@{ |

1419 | /** |

1420 | * @brief Tries to locate an element in an %unordered_multiset. |

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

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

1423 | * found. |

1424 | * |

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

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

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

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

1429 | */ |

1430 | iterator |

1431 | find(const key_type& __x) |

1432 | { return _M_h.find(__x); } |

1433 | |

1434 | const_iterator |

1435 | find(const key_type& __x) const |

1436 | { return _M_h.find(__x); } |

1437 | //@} |

1438 | |

1439 | /** |

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

1441 | * @param __x Element to located. |

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

1443 | */ |

1444 | size_type |

1445 | count(const key_type& __x) const |

1446 | { return _M_h.count(__x); } |

1447 | |

1448 | //@{ |

1449 | /** |

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

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

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

1453 | * matching given key. |

1454 | */ |

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

1456 | equal_range(const key_type& __x) |

1457 | { return _M_h.equal_range(__x); } |

1458 | |

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

1460 | equal_range(const key_type& __x) const |

1461 | { return _M_h.equal_range(__x); } |

1462 | //@} |

1463 | |

1464 | // bucket interface. |

1465 | |

1466 | /// Returns the number of buckets of the %unordered_multiset. |

1467 | size_type |

1468 | bucket_count() const noexcept |

1469 | { return _M_h.bucket_count(); } |

1470 | |

1471 | /// Returns the maximum number of buckets of the %unordered_multiset. |

1472 | size_type |

1473 | max_bucket_count() const noexcept |

1474 | { return _M_h.max_bucket_count(); } |

1475 | |

1476 | /* |

1477 | * @brief Returns the number of elements in a given bucket. |

1478 | * @param __n A bucket index. |

1479 | * @return The number of elements in the bucket. |

1480 | */ |

1481 | size_type |

1482 | bucket_size(size_type __n) const |

1483 | { return _M_h.bucket_size(__n); } |

1484 | |

1485 | /* |

1486 | * @brief Returns the bucket index of a given element. |

1487 | * @param __key A key instance. |

1488 | * @return The key bucket index. |

1489 | */ |

1490 | size_type |

1491 | bucket(const key_type& __key) const |

1492 | { return _M_h.bucket(__key); } |

1493 | |

1494 | //@{ |

1495 | /** |

1496 | * @brief Returns a read-only (constant) iterator pointing to the first |

1497 | * bucket element. |

1498 | * @param __n The bucket index. |

1499 | * @return A read-only local iterator. |

1500 | */ |

1501 | local_iterator |

1502 | begin(size_type __n) |

1503 | { return _M_h.begin(__n); } |

1504 | |

1505 | const_local_iterator |

1506 | begin(size_type __n) const |

1507 | { return _M_h.begin(__n); } |

1508 | |

1509 | const_local_iterator |

1510 | cbegin(size_type __n) const |

1511 | { return _M_h.cbegin(__n); } |

1512 | //@} |

1513 | |

1514 | //@{ |

1515 | /** |

1516 | * @brief Returns a read-only (constant) iterator pointing to one past |

1517 | * the last bucket elements. |

1518 | * @param __n The bucket index. |

1519 | * @return A read-only local iterator. |

1520 | */ |

1521 | local_iterator |

1522 | end(size_type __n) |

1523 | { return _M_h.end(__n); } |

1524 | |

1525 | const_local_iterator |

1526 | end(size_type __n) const |

1527 | { return _M_h.end(__n); } |

1528 | |

1529 | const_local_iterator |

1530 | cend(size_type __n) const |

1531 | { return _M_h.cend(__n); } |

1532 | //@} |

1533 | |

1534 | // hash policy. |

1535 | |

1536 | /// Returns the average number of elements per bucket. |

1537 | float |

1538 | load_factor() const noexcept |

1539 | { return _M_h.load_factor(); } |

1540 | |

1541 | /// Returns a positive number that the %unordered_multiset tries to keep the |

1542 | /// load factor less than or equal to. |

1543 | float |

1544 | max_load_factor() const noexcept |

1545 | { return _M_h.max_load_factor(); } |

1546 | |

1547 | /** |

1548 | * @brief Change the %unordered_multiset maximum load factor. |

1549 | * @param __z The new maximum load factor. |

1550 | */ |

1551 | void |

1552 | max_load_factor(float __z) |

1553 | { _M_h.max_load_factor(__z); } |

1554 | |

1555 | /** |

1556 | * @brief May rehash the %unordered_multiset. |

1557 | * @param __n The new number of buckets. |

1558 | * |

1559 | * Rehash will occur only if the new number of buckets respect the |

1560 | * %unordered_multiset maximum load factor. |

1561 | */ |

1562 | void |

1563 | rehash(size_type __n) |

1564 | { _M_h.rehash(__n); } |

1565 | |

1566 | /** |

1567 | * @brief Prepare the %unordered_multiset for a specified number of |

1568 | * elements. |

1569 | * @param __n Number of elements required. |

1570 | * |

1571 | * Same as rehash(ceil(n / max_load_factor())). |

1572 | */ |

1573 | void |

1574 | reserve(size_type __n) |

1575 | { _M_h.reserve(__n); } |

1576 | |

1577 | template<typename _Value1, typename _Hash1, typename _Pred1, |

1578 | typename _Alloc1> |

1579 | friend bool |

1580 | operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&, |

1581 | const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&); |

1582 | }; |

1583 | |

1584 | |

1585 | #if __cpp_deduction_guides >= 201606 |

1586 | |

1587 | template<typename _InputIterator, |

1588 | typename _Hash = |

1589 | hash<typename iterator_traits<_InputIterator>::value_type>, |

1590 | typename _Pred = |

1591 | equal_to<typename iterator_traits<_InputIterator>::value_type>, |

1592 | typename _Allocator = |

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

1594 | typename = _RequireInputIter<_InputIterator>, |

1595 | typename = _RequireAllocator<_Allocator>> |

1596 | unordered_multiset(_InputIterator, _InputIterator, |

1597 | unordered_multiset<int>::size_type = {}, |

1598 | _Hash = _Hash(), _Pred = _Pred(), |

1599 | _Allocator = _Allocator()) |

1600 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, |

1601 | _Hash, _Pred, _Allocator>; |

1602 | |

1603 | template<typename _Tp, typename _Hash = hash<_Tp>, |

1604 | typename _Pred = equal_to<_Tp>, |

1605 | typename _Allocator = allocator<_Tp>, |

1606 | typename = _RequireAllocator<_Allocator>> |

1607 | unordered_multiset(initializer_list<_Tp>, |

1608 | unordered_multiset<int>::size_type = {}, |

1609 | _Hash = _Hash(), _Pred = _Pred(), |

1610 | _Allocator = _Allocator()) |

1611 | -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; |

1612 | |

1613 | template<typename _InputIterator, typename _Allocator, |

1614 | typename = _RequireInputIter<_InputIterator>, |

1615 | typename = _RequireAllocator<_Allocator>> |

1616 | unordered_multiset(_InputIterator, _InputIterator, |

1617 | unordered_multiset<int>::size_type, _Allocator) |

1618 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, |

1619 | hash<typename |

1620 | iterator_traits<_InputIterator>::value_type>, |

1621 | equal_to<typename |

1622 | iterator_traits<_InputIterator>::value_type>, |

1623 | _Allocator>; |

1624 | |

1625 | template<typename _InputIterator, typename _Hash, typename _Allocator, |

1626 | typename = _RequireInputIter<_InputIterator>, |

1627 | typename = _RequireAllocator<_Allocator>> |

1628 | unordered_multiset(_InputIterator, _InputIterator, |

1629 | unordered_multiset<int>::size_type, |

1630 | _Hash, _Allocator) |

1631 | -> unordered_multiset<typename |

1632 | iterator_traits<_InputIterator>::value_type, |

1633 | _Hash, |

1634 | equal_to< |

1635 | typename |

1636 | iterator_traits<_InputIterator>::value_type>, |

1637 | _Allocator>; |

1638 | |

1639 | template<typename _Tp, typename _Allocator, |

1640 | typename = _RequireAllocator<_Allocator>> |

1641 | unordered_multiset(initializer_list<_Tp>, |

1642 | unordered_multiset<int>::size_type, _Allocator) |

1643 | -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; |

1644 | |

1645 | template<typename _Tp, typename _Hash, typename _Allocator, |

1646 | typename = _RequireAllocator<_Allocator>> |

1647 | unordered_multiset(initializer_list<_Tp>, |

1648 | unordered_multiset<int>::size_type, _Hash, _Allocator) |

1649 | -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; |

1650 | |

1651 | #endif |

1652 | |

1653 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1654 | inline void |

1655 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |

1656 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |

1657 | noexcept(noexcept(__x.swap(__y))) |

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

1659 | |

1660 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1661 | inline void |

1662 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |

1663 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |

1664 | noexcept(noexcept(__x.swap(__y))) |

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

1666 | |

1667 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1668 | inline bool |

1669 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |

1670 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |

1671 | { return __x._M_h._M_equal(__y._M_h); } |

1672 | |

1673 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1674 | inline bool |

1675 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |

1676 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |

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

1678 | |

1679 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1680 | inline bool |

1681 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |

1682 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |

1683 | { return __x._M_h._M_equal(__y._M_h); } |

1684 | |

1685 | template<class _Value, class _Hash, class _Pred, class _Alloc> |

1686 | inline bool |

1687 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |

1688 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |

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

1690 | |

1691 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1692 | |

1693 | #if __cplusplus > 201402L |

1694 | // Allow std::unordered_set access to internals of compatible sets. |

1695 | template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, |

1696 | typename _Hash2, typename _Eq2> |

1697 | struct _Hash_merge_helper< |

1698 | _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2> |

1699 | { |

1700 | private: |

1701 | template<typename... _Tp> |

1702 | using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; |

1703 | template<typename... _Tp> |

1704 | using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; |

1705 | |

1706 | friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>; |

1707 | |

1708 | static auto& |

1709 | _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) |

1710 | { return __set._M_h; } |

1711 | |

1712 | static auto& |

1713 | _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) |

1714 | { return __set._M_h; } |

1715 | }; |

1716 | |

1717 | // Allow std::unordered_multiset access to internals of compatible sets. |

1718 | template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, |

1719 | typename _Hash2, typename _Eq2> |

1720 | struct _Hash_merge_helper< |

1721 | _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>, |

1722 | _Hash2, _Eq2> |

1723 | { |

1724 | private: |

1725 | template<typename... _Tp> |

1726 | using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; |

1727 | template<typename... _Tp> |

1728 | using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; |

1729 | |

1730 | friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>; |

1731 | |

1732 | static auto& |

1733 | _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) |

1734 | { return __set._M_h; } |

1735 | |

1736 | static auto& |

1737 | _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) |

1738 | { return __set._M_h; } |

1739 | }; |

1740 | #endif // C++17 |

1741 | |

1742 | _GLIBCXX_END_NAMESPACE_VERSION |

1743 | } // namespace std |

1744 | |

1745 | #endif /* _UNORDERED_SET_H */ |

1746 |