1 | // unordered_map 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_map.h |

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

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

28 | */ |

29 | |

30 | #ifndef _UNORDERED_MAP_H |

31 | #define _UNORDERED_MAP_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_map. |

39 | template<bool _Cache> |

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

41 | |

42 | template<typename _Key, |

43 | typename _Tp, |

44 | typename _Hash = hash<_Key>, |

45 | typename _Pred = std::equal_to<_Key>, |

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

47 | typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> |

48 | using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, |

49 | _Alloc, __detail::_Select1st, |

50 | _Pred, _Hash, |

51 | __detail::_Mod_range_hashing, |

52 | __detail::_Default_ranged_hash, |

53 | __detail::_Prime_rehash_policy, _Tr>; |

54 | |

55 | /// Base types for unordered_multimap. |

56 | template<bool _Cache> |

57 | using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; |

58 | |

59 | template<typename _Key, |

60 | typename _Tp, |

61 | typename _Hash = hash<_Key>, |

62 | typename _Pred = std::equal_to<_Key>, |

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

64 | typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> |

65 | using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, |

66 | _Alloc, __detail::_Select1st, |

67 | _Pred, _Hash, |

68 | __detail::_Mod_range_hashing, |

69 | __detail::_Default_ranged_hash, |

70 | __detail::_Prime_rehash_policy, _Tr>; |

71 | |

72 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

73 | class unordered_multimap; |

74 | |

75 | /** |

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

77 | * at most one of each key value) that associates values of another type |

78 | * with the keys. |

79 | * |

80 | * @ingroup unordered_associative_containers |

81 | * |

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

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

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

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

86 | * to equal_to<_Value>. |

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

88 | * std::allocator<std::pair<const _Key, _Tp>>. |

89 | * |

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

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

92 | * |

93 | * The resulting value type of the container is std::pair<const _Key, _Tp>. |

94 | * |

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

96 | * alias __umap_hashtable. |

97 | */ |

98 | template<typename _Key, typename _Tp, |

99 | typename _Hash = hash<_Key>, |

100 | typename _Pred = equal_to<_Key>, |

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

102 | class unordered_map |

103 | { |

104 | typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; |

105 | _Hashtable _M_h; |

106 | |

107 | public: |

108 | // typedefs: |

109 | //@{ |

110 | /// Public typedefs. |

111 | typedef typename _Hashtable::key_type key_type; |

112 | typedef typename _Hashtable::value_type value_type; |

113 | typedef typename _Hashtable::mapped_type mapped_type; |

114 | typedef typename _Hashtable::hasher hasher; |

115 | typedef typename _Hashtable::key_equal key_equal; |

116 | typedef typename _Hashtable::allocator_type allocator_type; |

117 | //@} |

118 | |

119 | //@{ |

120 | /// Iterator-related typedefs. |

121 | typedef typename _Hashtable::pointer pointer; |

122 | typedef typename _Hashtable::const_pointer const_pointer; |

123 | typedef typename _Hashtable::reference reference; |

124 | typedef typename _Hashtable::const_reference const_reference; |

125 | typedef typename _Hashtable::iterator iterator; |

126 | typedef typename _Hashtable::const_iterator const_iterator; |

127 | typedef typename _Hashtable::local_iterator local_iterator; |

128 | typedef typename _Hashtable::const_local_iterator const_local_iterator; |

129 | typedef typename _Hashtable::size_type size_type; |

130 | typedef typename _Hashtable::difference_type difference_type; |

131 | //@} |

132 | |

133 | #if __cplusplus > 201402L |

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

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

136 | #endif |

137 | |

138 | //construct/destroy/copy |

139 | |

140 | /// Default constructor. |

141 | unordered_map() = default; |

142 | |

143 | /** |

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

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

146 | * @param __hf A hash functor. |

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

148 | * @param __a An allocator object. |

149 | */ |

150 | explicit |

151 | unordered_map(size_type __n, |

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

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

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

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

156 | { } |

157 | |

158 | /** |

159 | * @brief Builds an %unordered_map from a range. |

160 | * @param __first An input iterator. |

161 | * @param __last An input iterator. |

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

163 | * @param __hf A hash functor. |

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

165 | * @param __a An allocator object. |

166 | * |

167 | * Create an %unordered_map consisting of copies of the elements from |

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

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

170 | */ |

171 | template<typename _InputIterator> |

172 | unordered_map(_InputIterator __first, _InputIterator __last, |

173 | size_type __n = 0, |

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

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

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

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

178 | { } |

179 | |

180 | /// Copy constructor. |

181 | unordered_map(const unordered_map&) = default; |

182 | |

183 | /// Move constructor. |

184 | unordered_map(unordered_map&&) = default; |

185 | |

186 | /** |

187 | * @brief Creates an %unordered_map with no elements. |

188 | * @param __a An allocator object. |

189 | */ |

190 | explicit |

191 | unordered_map(const allocator_type& __a) |

192 | : _M_h(__a) |

193 | { } |

194 | |

195 | /* |

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

197 | * @param __uset Input %unordered_map to copy. |

198 | * @param __a An allocator object. |

199 | */ |

200 | unordered_map(const unordered_map& __umap, |

201 | const allocator_type& __a) |

202 | : _M_h(__umap._M_h, __a) |

203 | { } |

204 | |

205 | /* |

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

207 | * @param __uset Input %unordered_map to move. |

208 | * @param __a An allocator object. |

209 | */ |

210 | unordered_map(unordered_map&& __umap, |

211 | const allocator_type& __a) |

212 | : _M_h(std::move(__umap._M_h), __a) |

213 | { } |

214 | |

215 | /** |

216 | * @brief Builds an %unordered_map from an initializer_list. |

217 | * @param __l An initializer_list. |

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

219 | * @param __hf A hash functor. |

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

221 | * @param __a An allocator object. |

222 | * |

223 | * Create an %unordered_map consisting of copies of the elements in the |

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

225 | */ |

226 | unordered_map(initializer_list<value_type> __l, |

227 | size_type __n = 0, |

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

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

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

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

232 | { } |

233 | |

234 | unordered_map(size_type __n, const allocator_type& __a) |

235 | : unordered_map(__n, hasher(), key_equal(), __a) |

236 | { } |

237 | |

238 | unordered_map(size_type __n, const hasher& __hf, |

239 | const allocator_type& __a) |

240 | : unordered_map(__n, __hf, key_equal(), __a) |

241 | { } |

242 | |

243 | template<typename _InputIterator> |

244 | unordered_map(_InputIterator __first, _InputIterator __last, |

245 | size_type __n, |

246 | const allocator_type& __a) |

247 | : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) |

248 | { } |

249 | |

250 | template<typename _InputIterator> |

251 | unordered_map(_InputIterator __first, _InputIterator __last, |

252 | size_type __n, const hasher& __hf, |

253 | const allocator_type& __a) |

254 | : unordered_map(__first, __last, __n, __hf, key_equal(), __a) |

255 | { } |

256 | |

257 | unordered_map(initializer_list<value_type> __l, |

258 | size_type __n, |

259 | const allocator_type& __a) |

260 | : unordered_map(__l, __n, hasher(), key_equal(), __a) |

261 | { } |

262 | |

263 | unordered_map(initializer_list<value_type> __l, |

264 | size_type __n, const hasher& __hf, |

265 | const allocator_type& __a) |

266 | : unordered_map(__l, __n, __hf, key_equal(), __a) |

267 | { } |

268 | |

269 | /// Copy assignment operator. |

270 | unordered_map& |

271 | operator=(const unordered_map&) = default; |

272 | |

273 | /// Move assignment operator. |

274 | unordered_map& |

275 | operator=(unordered_map&&) = default; |

276 | |

277 | /** |

278 | * @brief %Unordered_map list assignment operator. |

279 | * @param __l An initializer_list. |

280 | * |

281 | * This function fills an %unordered_map with copies of the elements in |

282 | * the initializer list @a __l. |

283 | * |

284 | * Note that the assignment completely changes the %unordered_map and |

285 | * that the resulting %unordered_map's size is the same as the number |

286 | * of elements assigned. |

287 | */ |

288 | unordered_map& |

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

290 | { |

291 | _M_h = __l; |

292 | return *this; |

293 | } |

294 | |

295 | /// Returns the allocator object used by the %unordered_map. |

296 | allocator_type |

297 | get_allocator() const noexcept |

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

299 | |

300 | // size and capacity: |

301 | |

302 | /// Returns true if the %unordered_map is empty. |

303 | bool |

304 | empty() const noexcept |

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

306 | |

307 | /// Returns the size of the %unordered_map. |

308 | size_type |

309 | size() const noexcept |

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

311 | |

312 | /// Returns the maximum size of the %unordered_map. |

313 | size_type |

314 | max_size() const noexcept |

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

316 | |

317 | // iterators. |

318 | |

319 | /** |

320 | * Returns a read/write iterator that points to the first element in the |

321 | * %unordered_map. |

322 | */ |

323 | iterator |

324 | begin() noexcept |

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

326 | |

327 | //@{ |

328 | /** |

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

330 | * element in the %unordered_map. |

331 | */ |

332 | const_iterator |

333 | begin() const noexcept |

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

335 | |

336 | const_iterator |

337 | cbegin() const noexcept |

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

339 | //@} |

340 | |

341 | /** |

342 | * Returns a read/write iterator that points one past the last element in |

343 | * the %unordered_map. |

344 | */ |

345 | iterator |

346 | end() noexcept |

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

348 | |

349 | //@{ |

350 | /** |

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

352 | * element in the %unordered_map. |

353 | */ |

354 | const_iterator |

355 | end() const noexcept |

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

357 | |

358 | const_iterator |

359 | cend() const noexcept |

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

361 | //@} |

362 | |

363 | // modifiers. |

364 | |

365 | /** |

366 | * @brief Attempts to build and insert a std::pair into the |

367 | * %unordered_map. |

368 | * |

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

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

371 | * part of the pair constructor). |

372 | * |

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

374 | * to the possibly inserted pair, and the second is a bool that |

375 | * is true if the pair was actually inserted. |

376 | * |

377 | * This function attempts to build and insert a (key, value) %pair into |

378 | * the %unordered_map. |

379 | * An %unordered_map relies on unique keys and thus a %pair is only |

380 | * inserted if its first element (the key) is not already present in the |

381 | * %unordered_map. |

382 | * |

383 | * Insertion requires amortized constant time. |

384 | */ |

385 | template<typename... _Args> |

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

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

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

389 | |

390 | /** |

391 | * @brief Attempts to build and insert a std::pair into the |

392 | * %unordered_map. |

393 | * |

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

395 | * should be inserted. |

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

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

398 | * part of the pair constructor). |

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

400 | * std::pair built from @a __args (may or may not be that |

401 | * std::pair). |

402 | * |

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

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

405 | * does. |

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

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

408 | * cause no gains in efficiency. |

409 | * |

410 | * See |

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

412 | * for more on @a hinting. |

413 | * |

414 | * Insertion requires amortized constant time. |

415 | */ |

416 | template<typename... _Args> |

417 | iterator |

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

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

420 | |

421 | #if __cplusplus > 201402L |

422 | /// Extract a node. |

423 | node_type |

424 | extract(const_iterator __pos) |

425 | { |

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

427 | return _M_h.extract(__pos); |

428 | } |

429 | |

430 | /// Extract a node. |

431 | node_type |

432 | extract(const key_type& __key) |

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

434 | |

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

436 | insert_return_type |

437 | insert(node_type&& __nh) |

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

439 | |

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

441 | iterator |

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

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

444 | |

445 | #define __cpp_lib_unordered_map_try_emplace 201411 |

446 | /** |

447 | * @brief Attempts to build and insert a std::pair into the |

448 | * %unordered_map. |

449 | * |

450 | * @param __k Key to use for finding a possibly existing pair in |

451 | * the unordered_map. |

452 | * @param __args Arguments used to generate the .second for a |

453 | * new pair instance. |

454 | * |

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

456 | * to the possibly inserted pair, and the second is a bool that |

457 | * is true if the pair was actually inserted. |

458 | * |

459 | * This function attempts to build and insert a (key, value) %pair into |

460 | * the %unordered_map. |

461 | * An %unordered_map relies on unique keys and thus a %pair is only |

462 | * inserted if its first element (the key) is not already present in the |

463 | * %unordered_map. |

464 | * If a %pair is not inserted, this function has no effect. |

465 | * |

466 | * Insertion requires amortized constant time. |

467 | */ |

468 | template <typename... _Args> |

469 | pair<iterator, bool> |

470 | try_emplace(const key_type& __k, _Args&&... __args) |

471 | { |

472 | iterator __i = find(__k); |

473 | if (__i == end()) |

474 | { |

475 | __i = emplace(std::piecewise_construct, |

476 | std::forward_as_tuple(__k), |

477 | std::forward_as_tuple( |

478 | std::forward<_Args>(__args)...)) |

479 | .first; |

480 | return {__i, true}; |

481 | } |

482 | return {__i, false}; |

483 | } |

484 | |

485 | // move-capable overload |

486 | template <typename... _Args> |

487 | pair<iterator, bool> |

488 | try_emplace(key_type&& __k, _Args&&... __args) |

489 | { |

490 | iterator __i = find(__k); |

491 | if (__i == end()) |

492 | { |

493 | __i = emplace(std::piecewise_construct, |

494 | std::forward_as_tuple(std::move(__k)), |

495 | std::forward_as_tuple( |

496 | std::forward<_Args>(__args)...)) |

497 | .first; |

498 | return {__i, true}; |

499 | } |

500 | return {__i, false}; |

501 | } |

502 | |

503 | /** |

504 | * @brief Attempts to build and insert a std::pair into the |

505 | * %unordered_map. |

506 | * |

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

508 | * should be inserted. |

509 | * @param __k Key to use for finding a possibly existing pair in |

510 | * the unordered_map. |

511 | * @param __args Arguments used to generate the .second for a |

512 | * new pair instance. |

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

514 | * std::pair built from @a __args (may or may not be that |

515 | * std::pair). |

516 | * |

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

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

519 | * does. However, if insertion did not take place, |

520 | * this function has no effect. |

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

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

523 | * cause no gains in efficiency. |

524 | * |

525 | * See |

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

527 | * for more on @a hinting. |

528 | * |

529 | * Insertion requires amortized constant time. |

530 | */ |

531 | template <typename... _Args> |

532 | iterator |

533 | try_emplace(const_iterator __hint, const key_type& __k, |

534 | _Args&&... __args) |

535 | { |

536 | iterator __i = find(__k); |

537 | if (__i == end()) |

538 | __i = emplace_hint(__hint, std::piecewise_construct, |

539 | std::forward_as_tuple(__k), |

540 | std::forward_as_tuple( |

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

542 | return __i; |

543 | } |

544 | |

545 | // move-capable overload |

546 | template <typename... _Args> |

547 | iterator |

548 | try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) |

549 | { |

550 | iterator __i = find(__k); |

551 | if (__i == end()) |

552 | __i = emplace_hint(__hint, std::piecewise_construct, |

553 | std::forward_as_tuple(std::move(__k)), |

554 | std::forward_as_tuple( |

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

556 | return __i; |

557 | } |

558 | #endif // C++17 |

559 | |

560 | //@{ |

561 | /** |

562 | * @brief Attempts to insert a std::pair into the %unordered_map. |

563 | |

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

565 | * creation of pairs). |

566 | * |

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

568 | * points to the possibly inserted pair, and the second is |

569 | * a bool that is true if the pair was actually inserted. |

570 | * |

571 | * This function attempts to insert a (key, value) %pair into the |

572 | * %unordered_map. An %unordered_map relies on unique keys and thus a |

573 | * %pair is only inserted if its first element (the key) is not already |

574 | * present in the %unordered_map. |

575 | * |

576 | * Insertion requires amortized constant time. |

577 | */ |

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

579 | insert(const value_type& __x) |

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

581 | |

582 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

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

585 | insert(value_type&& __x) |

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

587 | |

588 | template<typename _Pair> |

589 | __enable_if_t<is_constructible<value_type, _Pair&&>::value, |

590 | pair<iterator, bool>> |

591 | insert(_Pair&& __x) |

592 | { return _M_h.emplace(std::forward<_Pair>(__x)); } |

593 | //@} |

594 | |

595 | //@{ |

596 | /** |

597 | * @brief Attempts to insert a std::pair into the %unordered_map. |

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

599 | * pair should be inserted. |

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

601 | * of pairs). |

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

603 | * @a __x (may or may not be the %pair passed in). |

604 | * |

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

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

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

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

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

610 | * |

611 | * See |

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

613 | * for more on @a hinting. |

614 | * |

615 | * Insertion requires amortized constant time. |

616 | */ |

617 | iterator |

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

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

620 | |

621 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

623 | iterator |

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

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

626 | |

627 | template<typename _Pair> |

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

629 | insert(const_iterator __hint, _Pair&& __x) |

630 | { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); } |

631 | //@} |

632 | |

633 | /** |

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

635 | * elements. |

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

637 | * inserted. |

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

639 | * |

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

641 | */ |

642 | template<typename _InputIterator> |

643 | void |

644 | insert(_InputIterator __first, _InputIterator __last) |

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

646 | |

647 | /** |

648 | * @brief Attempts to insert a list of elements into the %unordered_map. |

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

650 | * to be inserted. |

651 | * |

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

653 | */ |

654 | void |

655 | insert(initializer_list<value_type> __l) |

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

657 | |

658 | |

659 | #if __cplusplus > 201402L |

660 | #define __cpp_lib_unordered_map_insertion 201411 |

661 | /** |

662 | * @brief Attempts to insert a std::pair into the %unordered_map. |

663 | * @param __k Key to use for finding a possibly existing pair in |

664 | * the map. |

665 | * @param __obj Argument used to generate the .second for a pair |

666 | * instance. |

667 | * |

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

669 | * points to the possibly inserted pair, and the second is |

670 | * a bool that is true if the pair was actually inserted. |

671 | * |

672 | * This function attempts to insert a (key, value) %pair into the |

673 | * %unordered_map. An %unordered_map relies on unique keys and thus a |

674 | * %pair is only inserted if its first element (the key) is not already |

675 | * present in the %unordered_map. |

676 | * If the %pair was already in the %unordered_map, the .second of |

677 | * the %pair is assigned from __obj. |

678 | * |

679 | * Insertion requires amortized constant time. |

680 | */ |

681 | template <typename _Obj> |

682 | pair<iterator, bool> |

683 | insert_or_assign(const key_type& __k, _Obj&& __obj) |

684 | { |

685 | iterator __i = find(__k); |

686 | if (__i == end()) |

687 | { |

688 | __i = emplace(std::piecewise_construct, |

689 | std::forward_as_tuple(__k), |

690 | std::forward_as_tuple(std::forward<_Obj>(__obj))) |

691 | .first; |

692 | return {__i, true}; |

693 | } |

694 | (*__i).second = std::forward<_Obj>(__obj); |

695 | return {__i, false}; |

696 | } |

697 | |

698 | // move-capable overload |

699 | template <typename _Obj> |

700 | pair<iterator, bool> |

701 | insert_or_assign(key_type&& __k, _Obj&& __obj) |

702 | { |

703 | iterator __i = find(__k); |

704 | if (__i == end()) |

705 | { |

706 | __i = emplace(std::piecewise_construct, |

707 | std::forward_as_tuple(std::move(__k)), |

708 | std::forward_as_tuple(std::forward<_Obj>(__obj))) |

709 | .first; |

710 | return {__i, true}; |

711 | } |

712 | (*__i).second = std::forward<_Obj>(__obj); |

713 | return {__i, false}; |

714 | } |

715 | |

716 | /** |

717 | * @brief Attempts to insert a std::pair into the %unordered_map. |

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

719 | * pair should be inserted. |

720 | * @param __k Key to use for finding a possibly existing pair in |

721 | * the unordered_map. |

722 | * @param __obj Argument used to generate the .second for a pair |

723 | * instance. |

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

725 | * @a __x (may or may not be the %pair passed in). |

726 | * |

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

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

729 | * does. |

730 | * If the %pair was already in the %unordered map, the .second of |

731 | * the %pair is assigned from __obj. |

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

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

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

735 | * |

736 | * See |

737 | |

738 | * for more on @a hinting. |

739 | * |

740 | * Insertion requires amortized constant time. |

741 | */ |

742 | template <typename _Obj> |

743 | iterator |

744 | insert_or_assign(const_iterator __hint, const key_type& __k, |

745 | _Obj&& __obj) |

746 | { |

747 | iterator __i = find(__k); |

748 | if (__i == end()) |

749 | { |

750 | return emplace_hint(__hint, std::piecewise_construct, |

751 | std::forward_as_tuple(__k), |

752 | std::forward_as_tuple( |

753 | std::forward<_Obj>(__obj))); |

754 | } |

755 | (*__i).second = std::forward<_Obj>(__obj); |

756 | return __i; |

757 | } |

758 | |

759 | // move-capable overload |

760 | template <typename _Obj> |

761 | iterator |

762 | insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) |

763 | { |

764 | iterator __i = find(__k); |

765 | if (__i == end()) |

766 | { |

767 | return emplace_hint(__hint, std::piecewise_construct, |

768 | std::forward_as_tuple(std::move(__k)), |

769 | std::forward_as_tuple( |

770 | std::forward<_Obj>(__obj))); |

771 | } |

772 | (*__i).second = std::forward<_Obj>(__obj); |

773 | return __i; |

774 | } |

775 | #endif |

776 | |

777 | //@{ |

778 | /** |

779 | * @brief Erases an element from an %unordered_map. |

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

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

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

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

784 | * |

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

786 | * from an %unordered_map. |

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

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

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

790 | */ |

791 | iterator |

792 | erase(const_iterator __position) |

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

794 | |

795 | // LWG 2059. |

796 | iterator |

797 | erase(iterator __position) |

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

799 | //@} |

800 | |

801 | /** |

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

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

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

805 | * |

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

807 | * an %unordered_map. For an %unordered_map the result of this function |

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

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

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

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

812 | */ |

813 | size_type |

814 | erase(const key_type& __x) |

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

816 | |

817 | /** |

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

819 | * %unordered_map. |

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

821 | * erased. |

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

823 | * be erased. |

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

825 | * |

826 | * This function erases a sequence of elements from an %unordered_map. |

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

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

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

830 | */ |

831 | iterator |

832 | erase(const_iterator __first, const_iterator __last) |

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

834 | |

835 | /** |

836 | * Erases all elements in an %unordered_map. |

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

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

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

840 | */ |

841 | void |

842 | clear() noexcept |

843 | { _M_h.clear(); } |

844 | |

845 | /** |

846 | * @brief Swaps data with another %unordered_map. |

847 | * @param __x An %unordered_map of the same element and allocator |

848 | * types. |

849 | * |

850 | * This exchanges the elements between two %unordered_map in constant |

851 | * time. |

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

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

854 | */ |

855 | void |

856 | swap(unordered_map& __x) |

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

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

859 | |

860 | #if __cplusplus > 201402L |

861 | template<typename, typename, typename> |

862 | friend class std::_Hash_merge_helper; |

863 | |

864 | template<typename _H2, typename _P2> |

865 | void |

866 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) |

867 | { |

868 | using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; |

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

870 | } |

871 | |

872 | template<typename _H2, typename _P2> |

873 | void |

874 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) |

875 | { merge(__source); } |

876 | |

877 | template<typename _H2, typename _P2> |

878 | void |

879 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) |

880 | { |

881 | using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; |

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

883 | } |

884 | |

885 | template<typename _H2, typename _P2> |

886 | void |

887 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) |

888 | { merge(__source); } |

889 | #endif // C++17 |

890 | |

891 | // observers. |

892 | |

893 | /// Returns the hash functor object with which the %unordered_map was |

894 | /// constructed. |

895 | hasher |

896 | hash_function() const |

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

898 | |

899 | /// Returns the key comparison object with which the %unordered_map was |

900 | /// constructed. |

901 | key_equal |

902 | key_eq() const |

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

904 | |

905 | // lookup. |

906 | |

907 | //@{ |

908 | /** |

909 | * @brief Tries to locate an element in an %unordered_map. |

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

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

912 | * found. |

913 | * |

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

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

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

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

918 | */ |

919 | iterator |

920 | find(const key_type& __x) |

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

922 | |

923 | const_iterator |

924 | find(const key_type& __x) const |

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

926 | //@} |

927 | |

928 | /** |

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

930 | * @param __x Key to count. |

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

932 | * |

933 | * This function only makes sense for %unordered_multimap; for |

934 | * %unordered_map the result will either be 0 (not present) or 1 |

935 | * (present). |

936 | */ |

937 | size_type |

938 | count(const key_type& __x) const |

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

940 | |

941 | //@{ |

942 | /** |

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

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

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

946 | * matching given key. |

947 | * |

948 | * This function probably only makes sense for %unordered_multimap. |

949 | */ |

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

951 | equal_range(const key_type& __x) |

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

953 | |

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

955 | equal_range(const key_type& __x) const |

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

957 | //@} |

958 | |

959 | //@{ |

960 | /** |

961 | * @brief Subscript ( @c [] ) access to %unordered_map data. |

962 | * @param __k The key for which data should be retrieved. |

963 | * @return A reference to the data of the (key,data) %pair. |

964 | * |

965 | * Allows for easy lookup with the subscript ( @c [] )operator. Returns |

966 | * data associated with the key specified in subscript. If the key does |

967 | * not exist, a pair with that key is created using default values, which |

968 | * is then returned. |

969 | * |

970 | * Lookup requires constant time. |

971 | */ |

972 | mapped_type& |

973 | operator[](const key_type& __k) |

974 | { return _M_h[__k]; } |

975 | |

976 | mapped_type& |

977 | operator[](key_type&& __k) |

978 | { return _M_h[std::move(__k)]; } |

979 | //@} |

980 | |

981 | //@{ |

982 | /** |

983 | * @brief Access to %unordered_map data. |

984 | * @param __k The key for which data should be retrieved. |

985 | * @return A reference to the data whose key is equal to @a __k, if |

986 | * such a data is present in the %unordered_map. |

987 | * @throw std::out_of_range If no such data is present. |

988 | */ |

989 | mapped_type& |

990 | at(const key_type& __k) |

991 | { return _M_h.at(__k); } |

992 | |

993 | const mapped_type& |

994 | at(const key_type& __k) const |

995 | { return _M_h.at(__k); } |

996 | //@} |

997 | |

998 | // bucket interface. |

999 | |

1000 | /// Returns the number of buckets of the %unordered_map. |

1001 | size_type |

1002 | bucket_count() const noexcept |

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

1004 | |

1005 | /// Returns the maximum number of buckets of the %unordered_map. |

1006 | size_type |

1007 | max_bucket_count() const noexcept |

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

1009 | |

1010 | /* |

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

1012 | * @param __n A bucket index. |

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

1014 | */ |

1015 | size_type |

1016 | bucket_size(size_type __n) const |

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

1018 | |

1019 | /* |

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

1021 | * @param __key A key instance. |

1022 | * @return The key bucket index. |

1023 | */ |

1024 | size_type |

1025 | bucket(const key_type& __key) const |

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

1027 | |

1028 | /** |

1029 | * @brief Returns a read/write iterator pointing to the first bucket |

1030 | * element. |

1031 | * @param __n The bucket index. |

1032 | * @return A read/write local iterator. |

1033 | */ |

1034 | local_iterator |

1035 | begin(size_type __n) |

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

1037 | |

1038 | //@{ |

1039 | /** |

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

1041 | * bucket element. |

1042 | * @param __n The bucket index. |

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

1044 | */ |

1045 | const_local_iterator |

1046 | begin(size_type __n) const |

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

1048 | |

1049 | const_local_iterator |

1050 | cbegin(size_type __n) const |

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

1052 | //@} |

1053 | |

1054 | /** |

1055 | * @brief Returns a read/write iterator pointing to one past the last |

1056 | * bucket elements. |

1057 | * @param __n The bucket index. |

1058 | * @return A read/write local iterator. |

1059 | */ |

1060 | local_iterator |

1061 | end(size_type __n) |

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

1063 | |

1064 | //@{ |

1065 | /** |

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

1067 | * the last bucket elements. |

1068 | * @param __n The bucket index. |

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

1070 | */ |

1071 | const_local_iterator |

1072 | end(size_type __n) const |

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

1074 | |

1075 | const_local_iterator |

1076 | cend(size_type __n) const |

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

1078 | //@} |

1079 | |

1080 | // hash policy. |

1081 | |

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

1083 | float |

1084 | load_factor() const noexcept |

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

1086 | |

1087 | /// Returns a positive number that the %unordered_map tries to keep the |

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

1089 | float |

1090 | max_load_factor() const noexcept |

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

1092 | |

1093 | /** |

1094 | * @brief Change the %unordered_map maximum load factor. |

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

1096 | */ |

1097 | void |

1098 | max_load_factor(float __z) |

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

1100 | |

1101 | /** |

1102 | * @brief May rehash the %unordered_map. |

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

1104 | * |

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

1106 | * %unordered_map maximum load factor. |

1107 | */ |

1108 | void |

1109 | rehash(size_type __n) |

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

1111 | |

1112 | /** |

1113 | * @brief Prepare the %unordered_map for a specified number of |

1114 | * elements. |

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

1116 | * |

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

1118 | */ |

1119 | void |

1120 | reserve(size_type __n) |

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

1122 | |

1123 | template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, |

1124 | typename _Alloc1> |

1125 | friend bool |

1126 | operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, |

1127 | const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); |

1128 | }; |

1129 | |

1130 | #if __cpp_deduction_guides >= 201606 |

1131 | |

1132 | template<typename _InputIterator, |

1133 | typename _Hash = hash<__iter_key_t<_InputIterator>>, |

1134 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, |

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

1136 | typename = _RequireInputIter<_InputIterator>, |

1137 | typename = _RequireAllocator<_Allocator>> |

1138 | unordered_map(_InputIterator, _InputIterator, |

1139 | typename unordered_map<int, int>::size_type = {}, |

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

1141 | -> unordered_map<__iter_key_t<_InputIterator>, |

1142 | __iter_val_t<_InputIterator>, |

1143 | _Hash, _Pred, _Allocator>; |

1144 | |

1145 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, |

1146 | typename _Pred = equal_to<_Key>, |

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

1148 | typename = _RequireAllocator<_Allocator>> |

1149 | unordered_map(initializer_list<pair<_Key, _Tp>>, |

1150 | typename unordered_map<int, int>::size_type = {}, |

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

1152 | -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; |

1153 | |

1154 | template<typename _InputIterator, typename _Allocator, |

1155 | typename = _RequireInputIter<_InputIterator>, |

1156 | typename = _RequireAllocator<_Allocator>> |

1157 | unordered_map(_InputIterator, _InputIterator, |

1158 | typename unordered_map<int, int>::size_type, _Allocator) |

1159 | -> unordered_map<__iter_key_t<_InputIterator>, |

1160 | __iter_val_t<_InputIterator>, |

1161 | hash<__iter_key_t<_InputIterator>>, |

1162 | equal_to<__iter_key_t<_InputIterator>>, |

1163 | _Allocator>; |

1164 | |

1165 | template<typename _InputIterator, typename _Allocator, |

1166 | typename = _RequireInputIter<_InputIterator>, |

1167 | typename = _RequireAllocator<_Allocator>> |

1168 | unordered_map(_InputIterator, _InputIterator, _Allocator) |

1169 | -> unordered_map<__iter_key_t<_InputIterator>, |

1170 | __iter_val_t<_InputIterator>, |

1171 | hash<__iter_key_t<_InputIterator>>, |

1172 | equal_to<__iter_key_t<_InputIterator>>, |

1173 | _Allocator>; |

1174 | |

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

1176 | typename = _RequireInputIter<_InputIterator>, |

1177 | typename = _RequireAllocator<_Allocator>> |

1178 | unordered_map(_InputIterator, _InputIterator, |

1179 | typename unordered_map<int, int>::size_type, |

1180 | _Hash, _Allocator) |

1181 | -> unordered_map<__iter_key_t<_InputIterator>, |

1182 | __iter_val_t<_InputIterator>, _Hash, |

1183 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; |

1184 | |

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

1186 | typename = _RequireAllocator<_Allocator>> |

1187 | unordered_map(initializer_list<pair<_Key, _Tp>>, |

1188 | typename unordered_map<int, int>::size_type, |

1189 | _Allocator) |

1190 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; |

1191 | |

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

1193 | typename = _RequireAllocator<_Allocator>> |

1194 | unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) |

1195 | -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; |

1196 | |

1197 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, |

1198 | typename = _RequireAllocator<_Allocator>> |

1199 | unordered_map(initializer_list<pair<_Key, _Tp>>, |

1200 | typename unordered_map<int, int>::size_type, |

1201 | _Hash, _Allocator) |

1202 | -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; |

1203 | |

1204 | #endif |

1205 | |

1206 | /** |

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

1208 | * (possibly containing multiple of each key value) that associates |

1209 | * values of another type with the keys. |

1210 | * |

1211 | * @ingroup unordered_associative_containers |

1212 | * |

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

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

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

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

1217 | * to equal_to<_Value>. |

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

1219 | * std::allocator<std::pair<const _Key, _Tp>>. |

1220 | * |

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

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

1223 | * |

1224 | * The resulting value type of the container is std::pair<const _Key, _Tp>. |

1225 | * |

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

1227 | * alias __ummap_hashtable. |

1228 | */ |

1229 | template<typename _Key, typename _Tp, |

1230 | typename _Hash = hash<_Key>, |

1231 | typename _Pred = equal_to<_Key>, |

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

1233 | class unordered_multimap |

1234 | { |

1235 | typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; |

1236 | _Hashtable _M_h; |

1237 | |

1238 | public: |

1239 | // typedefs: |

1240 | //@{ |

1241 | /// Public typedefs. |

1242 | typedef typename _Hashtable::key_type key_type; |

1243 | typedef typename _Hashtable::value_type value_type; |

1244 | typedef typename _Hashtable::mapped_type mapped_type; |

1245 | typedef typename _Hashtable::hasher hasher; |

1246 | typedef typename _Hashtable::key_equal key_equal; |

1247 | typedef typename _Hashtable::allocator_type allocator_type; |

1248 | //@} |

1249 | |

1250 | //@{ |

1251 | /// Iterator-related typedefs. |

1252 | typedef typename _Hashtable::pointer pointer; |

1253 | typedef typename _Hashtable::const_pointer const_pointer; |

1254 | typedef typename _Hashtable::reference reference; |

1255 | typedef typename _Hashtable::const_reference const_reference; |

1256 | typedef typename _Hashtable::iterator iterator; |

1257 | typedef typename _Hashtable::const_iterator const_iterator; |

1258 | typedef typename _Hashtable::local_iterator local_iterator; |

1259 | typedef typename _Hashtable::const_local_iterator const_local_iterator; |

1260 | typedef typename _Hashtable::size_type size_type; |

1261 | typedef typename _Hashtable::difference_type difference_type; |

1262 | //@} |

1263 | |

1264 | #if __cplusplus > 201402L |

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

1266 | #endif |

1267 | |

1268 | //construct/destroy/copy |

1269 | |

1270 | /// Default constructor. |

1271 | unordered_multimap() = default; |

1272 | |

1273 | /** |

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

1275 | * @param __n Mnimal initial number of buckets. |

1276 | * @param __hf A hash functor. |

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

1278 | * @param __a An allocator object. |

1279 | */ |

1280 | explicit |

1281 | unordered_multimap(size_type __n, |

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

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

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

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

1286 | { } |

1287 | |

1288 | /** |

1289 | * @brief Builds an %unordered_multimap from a range. |

1290 | * @param __first An input iterator. |

1291 | * @param __last An input iterator. |

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

1293 | * @param __hf A hash functor. |

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

1295 | * @param __a An allocator object. |

1296 | * |

1297 | * Create an %unordered_multimap consisting of copies of the elements |

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

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

1300 | */ |

1301 | template<typename _InputIterator> |

1302 | unordered_multimap(_InputIterator __first, _InputIterator __last, |

1303 | size_type __n = 0, |

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

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

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

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

1308 | { } |

1309 | |

1310 | /// Copy constructor. |

1311 | unordered_multimap(const unordered_multimap&) = default; |

1312 | |

1313 | /// Move constructor. |

1314 | unordered_multimap(unordered_multimap&&) = default; |

1315 | |

1316 | /** |

1317 | * @brief Creates an %unordered_multimap with no elements. |

1318 | * @param __a An allocator object. |

1319 | */ |

1320 | explicit |

1321 | unordered_multimap(const allocator_type& __a) |

1322 | : _M_h(__a) |

1323 | { } |

1324 | |

1325 | /* |

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

1327 | * @param __uset Input %unordered_multimap to copy. |

1328 | * @param __a An allocator object. |

1329 | */ |

1330 | unordered_multimap(const unordered_multimap& __ummap, |

1331 | const allocator_type& __a) |

1332 | : _M_h(__ummap._M_h, __a) |

1333 | { } |

1334 | |

1335 | /* |

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

1337 | * @param __uset Input %unordered_multimap to move. |

1338 | * @param __a An allocator object. |

1339 | */ |

1340 | unordered_multimap(unordered_multimap&& __ummap, |

1341 | const allocator_type& __a) |

1342 | : _M_h(std::move(__ummap._M_h), __a) |

1343 | { } |

1344 | |

1345 | /** |

1346 | * @brief Builds an %unordered_multimap from an initializer_list. |

1347 | * @param __l An initializer_list. |

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

1349 | * @param __hf A hash functor. |

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

1351 | * @param __a An allocator object. |

1352 | * |

1353 | * Create an %unordered_multimap consisting of copies of the elements in |

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

1355 | */ |

1356 | unordered_multimap(initializer_list<value_type> __l, |

1357 | size_type __n = 0, |

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

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

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

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

1362 | { } |

1363 | |

1364 | unordered_multimap(size_type __n, const allocator_type& __a) |

1365 | : unordered_multimap(__n, hasher(), key_equal(), __a) |

1366 | { } |

1367 | |

1368 | unordered_multimap(size_type __n, const hasher& __hf, |

1369 | const allocator_type& __a) |

1370 | : unordered_multimap(__n, __hf, key_equal(), __a) |

1371 | { } |

1372 | |

1373 | template<typename _InputIterator> |

1374 | unordered_multimap(_InputIterator __first, _InputIterator __last, |

1375 | size_type __n, |

1376 | const allocator_type& __a) |

1377 | : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) |

1378 | { } |

1379 | |

1380 | template<typename _InputIterator> |

1381 | unordered_multimap(_InputIterator __first, _InputIterator __last, |

1382 | size_type __n, const hasher& __hf, |

1383 | const allocator_type& __a) |

1384 | : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) |

1385 | { } |

1386 | |

1387 | unordered_multimap(initializer_list<value_type> __l, |

1388 | size_type __n, |

1389 | const allocator_type& __a) |

1390 | : unordered_multimap(__l, __n, hasher(), key_equal(), __a) |

1391 | { } |

1392 | |

1393 | unordered_multimap(initializer_list<value_type> __l, |

1394 | size_type __n, const hasher& __hf, |

1395 | const allocator_type& __a) |

1396 | : unordered_multimap(__l, __n, __hf, key_equal(), __a) |

1397 | { } |

1398 | |

1399 | /// Copy assignment operator. |

1400 | unordered_multimap& |

1401 | operator=(const unordered_multimap&) = default; |

1402 | |

1403 | /// Move assignment operator. |

1404 | unordered_multimap& |

1405 | operator=(unordered_multimap&&) = default; |

1406 | |

1407 | /** |

1408 | * @brief %Unordered_multimap list assignment operator. |

1409 | * @param __l An initializer_list. |

1410 | * |

1411 | * This function fills an %unordered_multimap with copies of the |

1412 | * elements in the initializer list @a __l. |

1413 | * |

1414 | * Note that the assignment completely changes the %unordered_multimap |

1415 | * and that the resulting %unordered_multimap's size is the same as the |

1416 | * number of elements assigned. |

1417 | */ |

1418 | unordered_multimap& |

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

1420 | { |

1421 | _M_h = __l; |

1422 | return *this; |

1423 | } |

1424 | |

1425 | /// Returns the allocator object used by the %unordered_multimap. |

1426 | allocator_type |

1427 | get_allocator() const noexcept |

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

1429 | |

1430 | // size and capacity: |

1431 | |

1432 | /// Returns true if the %unordered_multimap is empty. |

1433 | bool |

1434 | empty() const noexcept |

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

1436 | |

1437 | /// Returns the size of the %unordered_multimap. |

1438 | size_type |

1439 | size() const noexcept |

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

1441 | |

1442 | /// Returns the maximum size of the %unordered_multimap. |

1443 | size_type |

1444 | max_size() const noexcept |

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

1446 | |

1447 | // iterators. |

1448 | |

1449 | /** |

1450 | * Returns a read/write iterator that points to the first element in the |

1451 | * %unordered_multimap. |

1452 | */ |

1453 | iterator |

1454 | begin() noexcept |

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

1456 | |

1457 | //@{ |

1458 | /** |

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

1460 | * element in the %unordered_multimap. |

1461 | */ |

1462 | const_iterator |

1463 | begin() const noexcept |

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

1465 | |

1466 | const_iterator |

1467 | cbegin() const noexcept |

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

1469 | //@} |

1470 | |

1471 | /** |

1472 | * Returns a read/write iterator that points one past the last element in |

1473 | * the %unordered_multimap. |

1474 | */ |

1475 | iterator |

1476 | end() noexcept |

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

1478 | |

1479 | //@{ |

1480 | /** |

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

1482 | * element in the %unordered_multimap. |

1483 | */ |

1484 | const_iterator |

1485 | end() const noexcept |

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

1487 | |

1488 | const_iterator |

1489 | cend() const noexcept |

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

1491 | //@} |

1492 | |

1493 | // modifiers. |

1494 | |

1495 | /** |

1496 | * @brief Attempts to build and insert a std::pair into the |

1497 | * %unordered_multimap. |

1498 | * |

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

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

1501 | * part of the pair constructor). |

1502 | * |

1503 | * @return An iterator that points to the inserted pair. |

1504 | * |

1505 | * This function attempts to build and insert a (key, value) %pair into |

1506 | * the %unordered_multimap. |

1507 | * |

1508 | * Insertion requires amortized constant time. |

1509 | */ |

1510 | template<typename... _Args> |

1511 | iterator |

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

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

1514 | |

1515 | /** |

1516 | * @brief Attempts to build and insert a std::pair into the |

1517 | * %unordered_multimap. |

1518 | * |

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

1520 | * should be inserted. |

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

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

1523 | * part of the pair constructor). |

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

1525 | * std::pair built from @a __args. |

1526 | * |

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

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

1529 | * cause no gains in efficiency. |

1530 | * |

1531 | * See |

1532 | |

1533 | * for more on @a hinting. |

1534 | * |

1535 | * Insertion requires amortized constant time. |

1536 | */ |

1537 | template<typename... _Args> |

1538 | iterator |

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

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

1541 | |

1542 | //@{ |

1543 | /** |

1544 | * @brief Inserts a std::pair into the %unordered_multimap. |

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

1546 | * creation of pairs). |

1547 | * |

1548 | * @return An iterator that points to the inserted pair. |

1549 | * |

1550 | * Insertion requires amortized constant time. |

1551 | */ |

1552 | iterator |

1553 | insert(const value_type& __x) |

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

1555 | |

1556 | iterator |

1557 | insert(value_type&& __x) |

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

1559 | |

1560 | template<typename _Pair> |

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

1562 | insert(_Pair&& __x) |

1563 | { return _M_h.emplace(std::forward<_Pair>(__x)); } |

1564 | //@} |

1565 | |

1566 | //@{ |

1567 | /** |

1568 | * @brief Inserts a std::pair into the %unordered_multimap. |

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

1570 | * pair should be inserted. |

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

1572 | * of pairs). |

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

1574 | * @a __x (may or may not be the %pair passed in). |

1575 | * |

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

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

1578 | * cause no gains in efficiency. |

1579 | * |

1580 | * See |

1581 | |

1582 | * for more on @a hinting. |

1583 | * |

1584 | * Insertion requires amortized constant time. |

1585 | */ |

1586 | iterator |

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

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

1589 | |

1590 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1592 | iterator |

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

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

1595 | |

1596 | template<typename _Pair> |

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

1598 | insert(const_iterator __hint, _Pair&& __x) |

1599 | { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); } |

1600 | //@} |

1601 | |

1602 | /** |

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

1604 | * elements. |

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

1606 | * inserted. |

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

1608 | * |

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

1610 | */ |

1611 | template<typename _InputIterator> |

1612 | void |

1613 | insert(_InputIterator __first, _InputIterator __last) |

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

1615 | |

1616 | /** |

1617 | * @brief Attempts to insert a list of elements into the |

1618 | * %unordered_multimap. |

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

1620 | * to be inserted. |

1621 | * |

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

1623 | */ |

1624 | void |

1625 | insert(initializer_list<value_type> __l) |

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

1627 | |

1628 | #if __cplusplus > 201402L |

1629 | /// Extract a node. |

1630 | node_type |

1631 | extract(const_iterator __pos) |

1632 | { |

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

1634 | return _M_h.extract(__pos); |

1635 | } |

1636 | |

1637 | /// Extract a node. |

1638 | node_type |

1639 | extract(const key_type& __key) |

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

1641 | |

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

1643 | iterator |

1644 | insert(node_type&& __nh) |

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

1646 | |

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

1648 | iterator |

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

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

1651 | #endif // C++17 |

1652 | |

1653 | //@{ |

1654 | /** |

1655 | * @brief Erases an element from an %unordered_multimap. |

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

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

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

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

1660 | * |

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

1662 | * from an %unordered_multimap. |

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

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

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

1666 | */ |

1667 | iterator |

1668 | erase(const_iterator __position) |

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

1670 | |

1671 | // LWG 2059. |

1672 | iterator |

1673 | erase(iterator __position) |

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

1675 | //@} |

1676 | |

1677 | /** |

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

1679 | * @param __x Key of elements to be erased. |

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

1681 | * |

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

1683 | * an %unordered_multimap. |

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

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

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

1687 | */ |

1688 | size_type |

1689 | erase(const key_type& __x) |

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

1691 | |

1692 | /** |

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

1694 | * %unordered_multimap. |

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

1696 | * erased. |

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

1698 | * be erased. |

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

1700 | * |

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

1702 | * %unordered_multimap. |

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

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

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

1706 | */ |

1707 | iterator |

1708 | erase(const_iterator __first, const_iterator __last) |

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

1710 | |

1711 | /** |

1712 | * Erases all elements in an %unordered_multimap. |

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

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

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

1716 | */ |

1717 | void |

1718 | clear() noexcept |

1719 | { _M_h.clear(); } |

1720 | |

1721 | /** |

1722 | * @brief Swaps data with another %unordered_multimap. |

1723 | * @param __x An %unordered_multimap of the same element and allocator |

1724 | * types. |

1725 | * |

1726 | * This exchanges the elements between two %unordered_multimap in |

1727 | * constant time. |

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

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

1730 | */ |

1731 | void |

1732 | swap(unordered_multimap& __x) |

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

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

1735 | |

1736 | #if __cplusplus > 201402L |

1737 | template<typename, typename, typename> |

1738 | friend class std::_Hash_merge_helper; |

1739 | |

1740 | template<typename _H2, typename _P2> |

1741 | void |

1742 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) |

1743 | { |

1744 | using _Merge_helper |

1745 | = _Hash_merge_helper<unordered_multimap, _H2, _P2>; |

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

1747 | } |

1748 | |

1749 | template<typename _H2, typename _P2> |

1750 | void |

1751 | merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) |

1752 | { merge(__source); } |

1753 | |

1754 | template<typename _H2, typename _P2> |

1755 | void |

1756 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) |

1757 | { |

1758 | using _Merge_helper |

1759 | = _Hash_merge_helper<unordered_multimap, _H2, _P2>; |

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

1761 | } |

1762 | |

1763 | template<typename _H2, typename _P2> |

1764 | void |

1765 | merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) |

1766 | { merge(__source); } |

1767 | #endif // C++17 |

1768 | |

1769 | // observers. |

1770 | |

1771 | /// Returns the hash functor object with which the %unordered_multimap |

1772 | /// was constructed. |

1773 | hasher |

1774 | hash_function() const |

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

1776 | |

1777 | /// Returns the key comparison object with which the %unordered_multimap |

1778 | /// was constructed. |

1779 | key_equal |

1780 | key_eq() const |

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

1782 | |

1783 | // lookup. |

1784 | |

1785 | //@{ |

1786 | /** |

1787 | * @brief Tries to locate an element in an %unordered_multimap. |

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

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

1790 | * found. |

1791 | * |

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

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

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

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

1796 | */ |

1797 | iterator |

1798 | find(const key_type& __x) |

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

1800 | |

1801 | const_iterator |

1802 | find(const key_type& __x) const |

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

1804 | //@} |

1805 | |

1806 | /** |

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

1808 | * @param __x Key to count. |

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

1810 | */ |

1811 | size_type |

1812 | count(const key_type& __x) const |

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

1814 | |

1815 | //@{ |

1816 | /** |

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

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

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

1820 | * matching given key. |

1821 | */ |

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

1823 | equal_range(const key_type& __x) |

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

1825 | |

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

1827 | equal_range(const key_type& __x) const |

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

1829 | //@} |

1830 | |

1831 | // bucket interface. |

1832 | |

1833 | /// Returns the number of buckets of the %unordered_multimap. |

1834 | size_type |

1835 | bucket_count() const noexcept |

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

1837 | |

1838 | /// Returns the maximum number of buckets of the %unordered_multimap. |

1839 | size_type |

1840 | max_bucket_count() const noexcept |

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

1842 | |

1843 | /* |

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

1845 | * @param __n A bucket index. |

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

1847 | */ |

1848 | size_type |

1849 | bucket_size(size_type __n) const |

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

1851 | |

1852 | /* |

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

1854 | * @param __key A key instance. |

1855 | * @return The key bucket index. |

1856 | */ |

1857 | size_type |

1858 | bucket(const key_type& __key) const |

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

1860 | |

1861 | /** |

1862 | * @brief Returns a read/write iterator pointing to the first bucket |

1863 | * element. |

1864 | * @param __n The bucket index. |

1865 | * @return A read/write local iterator. |

1866 | */ |

1867 | local_iterator |

1868 | begin(size_type __n) |

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

1870 | |

1871 | //@{ |

1872 | /** |

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

1874 | * bucket element. |

1875 | * @param __n The bucket index. |

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

1877 | */ |

1878 | const_local_iterator |

1879 | begin(size_type __n) const |

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

1881 | |

1882 | const_local_iterator |

1883 | cbegin(size_type __n) const |

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

1885 | //@} |

1886 | |

1887 | /** |

1888 | * @brief Returns a read/write iterator pointing to one past the last |

1889 | * bucket elements. |

1890 | * @param __n The bucket index. |

1891 | * @return A read/write local iterator. |

1892 | */ |

1893 | local_iterator |

1894 | end(size_type __n) |

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

1896 | |

1897 | //@{ |

1898 | /** |

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

1900 | * the last bucket elements. |

1901 | * @param __n The bucket index. |

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

1903 | */ |

1904 | const_local_iterator |

1905 | end(size_type __n) const |

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

1907 | |

1908 | const_local_iterator |

1909 | cend(size_type __n) const |

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

1911 | //@} |

1912 | |

1913 | // hash policy. |

1914 | |

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

1916 | float |

1917 | load_factor() const noexcept |

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

1919 | |

1920 | /// Returns a positive number that the %unordered_multimap tries to keep |

1921 | /// the load factor less than or equal to. |

1922 | float |

1923 | max_load_factor() const noexcept |

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

1925 | |

1926 | /** |

1927 | * @brief Change the %unordered_multimap maximum load factor. |

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

1929 | */ |

1930 | void |

1931 | max_load_factor(float __z) |

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

1933 | |

1934 | /** |

1935 | * @brief May rehash the %unordered_multimap. |

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

1937 | * |

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

1939 | * %unordered_multimap maximum load factor. |

1940 | */ |

1941 | void |

1942 | rehash(size_type __n) |

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

1944 | |

1945 | /** |

1946 | * @brief Prepare the %unordered_multimap for a specified number of |

1947 | * elements. |

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

1949 | * |

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

1951 | */ |

1952 | void |

1953 | reserve(size_type __n) |

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

1955 | |

1956 | template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, |

1957 | typename _Alloc1> |

1958 | friend bool |

1959 | operator==(const unordered_multimap<_Key1, _Tp1, |

1960 | _Hash1, _Pred1, _Alloc1>&, |

1961 | const unordered_multimap<_Key1, _Tp1, |

1962 | _Hash1, _Pred1, _Alloc1>&); |

1963 | }; |

1964 | |

1965 | #if __cpp_deduction_guides >= 201606 |

1966 | |

1967 | template<typename _InputIterator, |

1968 | typename _Hash = hash<__iter_key_t<_InputIterator>>, |

1969 | typename _Pred = equal_to<__iter_key_t<_InputIterator>>, |

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

1971 | typename = _RequireInputIter<_InputIterator>, |

1972 | typename = _RequireAllocator<_Allocator>> |

1973 | unordered_multimap(_InputIterator, _InputIterator, |

1974 | unordered_multimap<int, int>::size_type = {}, |

1975 | _Hash = _Hash(), _Pred = _Pred(), |

1976 | _Allocator = _Allocator()) |

1977 | -> unordered_multimap<__iter_key_t<_InputIterator>, |

1978 | __iter_val_t<_InputIterator>, _Hash, _Pred, |

1979 | _Allocator>; |

1980 | |

1981 | template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, |

1982 | typename _Pred = equal_to<_Key>, |

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

1984 | typename = _RequireAllocator<_Allocator>> |

1985 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, |

1986 | unordered_multimap<int, int>::size_type = {}, |

1987 | _Hash = _Hash(), _Pred = _Pred(), |

1988 | _Allocator = _Allocator()) |

1989 | -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; |

1990 | |

1991 | template<typename _InputIterator, typename _Allocator, |

1992 | typename = _RequireInputIter<_InputIterator>, |

1993 | typename = _RequireAllocator<_Allocator>> |

1994 | unordered_multimap(_InputIterator, _InputIterator, |

1995 | unordered_multimap<int, int>::size_type, _Allocator) |

1996 | -> unordered_multimap<__iter_key_t<_InputIterator>, |

1997 | __iter_val_t<_InputIterator>, |

1998 | hash<__iter_key_t<_InputIterator>>, |

1999 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; |

2000 | |

2001 | template<typename _InputIterator, typename _Allocator, |

2002 | typename = _RequireInputIter<_InputIterator>, |

2003 | typename = _RequireAllocator<_Allocator>> |

2004 | unordered_multimap(_InputIterator, _InputIterator, _Allocator) |

2005 | -> unordered_multimap<__iter_key_t<_InputIterator>, |

2006 | __iter_val_t<_InputIterator>, |

2007 | hash<__iter_key_t<_InputIterator>>, |

2008 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; |

2009 | |

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

2011 | typename = _RequireInputIter<_InputIterator>, |

2012 | typename = _RequireAllocator<_Allocator>> |

2013 | unordered_multimap(_InputIterator, _InputIterator, |

2014 | unordered_multimap<int, int>::size_type, _Hash, |

2015 | _Allocator) |

2016 | -> unordered_multimap<__iter_key_t<_InputIterator>, |

2017 | __iter_val_t<_InputIterator>, _Hash, |

2018 | equal_to<__iter_key_t<_InputIterator>>, _Allocator>; |

2019 | |

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

2021 | typename = _RequireAllocator<_Allocator>> |

2022 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, |

2023 | unordered_multimap<int, int>::size_type, |

2024 | _Allocator) |

2025 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; |

2026 | |

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

2028 | typename = _RequireAllocator<_Allocator>> |

2029 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) |

2030 | -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; |

2031 | |

2032 | template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, |

2033 | typename = _RequireAllocator<_Allocator>> |

2034 | unordered_multimap(initializer_list<pair<_Key, _Tp>>, |

2035 | unordered_multimap<int, int>::size_type, |

2036 | _Hash, _Allocator) |

2037 | -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; |

2038 | |

2039 | #endif |

2040 | |

2041 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2042 | inline void |

2043 | swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2044 | unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

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

2047 | |

2048 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2049 | inline void |

2050 | swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2051 | unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

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

2054 | |

2055 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2056 | inline bool |

2057 | operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2058 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

2060 | |

2061 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2062 | inline bool |

2063 | operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2064 | const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

2066 | |

2067 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2068 | inline bool |

2069 | operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2070 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

2072 | |

2073 | template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |

2074 | inline bool |

2075 | operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, |

2076 | const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) |

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

2078 | |

2079 | _GLIBCXX_END_NAMESPACE_CONTAINER |

2080 | |

2081 | #if __cplusplus > 201402L |

2082 | // Allow std::unordered_map access to internals of compatible maps. |

2083 | template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, |

2084 | typename _Alloc, typename _Hash2, typename _Eq2> |

2085 | struct _Hash_merge_helper< |

2086 | _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, |

2087 | _Hash2, _Eq2> |

2088 | { |

2089 | private: |

2090 | template<typename... _Tp> |

2091 | using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; |

2092 | template<typename... _Tp> |

2093 | using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; |

2094 | |

2095 | friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; |

2096 | |

2097 | static auto& |

2098 | _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) |

2099 | { return __map._M_h; } |

2100 | |

2101 | static auto& |

2102 | _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) |

2103 | { return __map._M_h; } |

2104 | }; |

2105 | |

2106 | // Allow std::unordered_multimap access to internals of compatible maps. |

2107 | template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, |

2108 | typename _Alloc, typename _Hash2, typename _Eq2> |

2109 | struct _Hash_merge_helper< |

2110 | _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, |

2111 | _Hash2, _Eq2> |

2112 | { |

2113 | private: |

2114 | template<typename... _Tp> |

2115 | using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; |

2116 | template<typename... _Tp> |

2117 | using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; |

2118 | |

2119 | friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; |

2120 | |

2121 | static auto& |

2122 | _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) |

2123 | { return __map._M_h; } |

2124 | |

2125 | static auto& |

2126 | _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) |

2127 | { return __map._M_h; } |

2128 | }; |

2129 | #endif // C++17 |

2130 | |

2131 | _GLIBCXX_END_NAMESPACE_VERSION |

2132 | } // namespace std |

2133 | |

2134 | #endif /* _UNORDERED_MAP_H */ |

2135 |