libstdc++: stl_map.h Source File (original) (raw)

56#ifndef _STL_MAP_H

57#define _STL_MAP_H 1

61#if __cplusplus >= 201103L

64#endif

66namespace std _GLIBCXX_VISIBILITY(default)

67{

68_GLIBCXX_BEGIN_NAMESPACE_VERSION

69_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

71 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>

72 class multimap;

100 template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,

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

103 {

104 public:

105 typedef _Key key_type;

106 typedef _Tp mapped_type;

108 typedef _Compare key_compare;

109 typedef _Alloc allocator_type;

110

111 private:

112#ifdef _GLIBCXX_CONCEPT_CHECKS

113

114 typedef typename _Alloc::value_type _Alloc_value_type;

115# if __cplusplus < 201103L

116 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

117# endif

118 __glibcxx_class_requires4(_Compare, bool, _Key, _Key,

119 _BinaryFunctionConcept)

120 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)

121#endif

122

123#if __cplusplus >= 201103L

124#if __cplusplus > 201703L || defined __STRICT_ANSI__

126 "std::map must have the same value_type as its allocator");

127#endif

128#endif

129

130 public:

131#pragma GCC diagnostic push

132#pragma GCC diagnostic ignored "-Wdeprecated-declarations"

133 class value_compare

135 {

136 friend class map<_Key, _Tp, _Compare, _Alloc>;

137 protected:

138 _Compare comp;

139

140 value_compare(_Compare __c)

141 : comp(__c) { }

142

143 public:

145 { return comp(__x.first, __y.first); }

146 };

147#pragma GCC diagnostic pop

148

149 private:

150

152 rebind<value_type>::other _Pair_alloc_type;

153

154 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,

155 key_compare, _Pair_alloc_type> _Rep_type;

156

157

158 _Rep_type _M_t;

159

161

162#if __cplusplus >= 201703L

163 template<typename _Up, typename _Vp = remove_reference_t<_Up>>

164 static constexpr bool __usable_key

165 = __or_v<is_same<const _Vp, const _Key>,

167#endif

168

169 public:

170

171

172 typedef typename _Alloc_traits::pointer pointer;

173 typedef typename _Alloc_traits::const_pointer const_pointer;

174 typedef typename _Alloc_traits::reference reference;

175 typedef typename _Alloc_traits::const_reference const_reference;

176 typedef typename _Rep_type::iterator iterator;

177 typedef typename _Rep_type::const_iterator const_iterator;

178 typedef typename _Rep_type::size_type size_type;

179 typedef typename _Rep_type::difference_type difference_type;

182

183#if __cplusplus > 201402L

186#endif

187

188

189

190

191

192

193

194#if __cplusplus < 201103L

195 map() : _M_t() { }

196#else

198#endif

199

200

201

202

203

204

205 explicit

206 map(const _Compare& __comp,

207 const allocator_type& __a = allocator_type())

208 : _M_t(__comp, _Pair_alloc_type(__a)) { }

209

210

211

212

213

214

215#if __cplusplus < 201103L

217 : _M_t(__x._M_t) { }

218#else

220

221

222

223

224

225

226

228

229

230

231

232

233

234

235

236

237

238

239

241 const _Compare& __comp = _Compare(),

242 const allocator_type& __a = allocator_type())

243 : _M_t(__comp, _Pair_alloc_type(__a))

244 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }

245

246

247 explicit

248 map(const allocator_type& __a)

249 : _M_t(_Pair_alloc_type(__a)) { }

250

251

252 map(const map& __m, const __type_identity_t<allocator_type>& __a)

253 : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }

254

255

256 map(map&& __m, const __type_identity_t<allocator_type>& __a)

258 && _Alloc_traits::_S_always_equal())

259 : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }

260

261

263 : _M_t(_Pair_alloc_type(__a))

264 { _M_t._M_insert_range_unique(__l.begin(), __l.end()); }

265

266

267 template<typename _InputIterator>

268 map(_InputIterator __first, _InputIterator __last,

269 const allocator_type& __a)

270 : _M_t(_Pair_alloc_type(__a))

271 { _M_t._M_insert_range_unique(__first, __last); }

272#endif

273

274

275

276

277

278

279

280

281

282

283

284 template<typename _InputIterator>

285 map(_InputIterator __first, _InputIterator __last)

286 : _M_t()

287 { _M_t._M_insert_range_unique(__first, __last); }

288

289

290

291

292

293

294

295

296

297

298

299

300

301 template<typename _InputIterator>

302 map(_InputIterator __first, _InputIterator __last,

303 const _Compare& __comp,

304 const allocator_type& __a = allocator_type())

305 : _M_t(__comp, _Pair_alloc_type(__a))

306 { _M_t._M_insert_range_unique(__first, __last); }

307

308#if __cplusplus >= 201103L

309

310

311

312

313

315#endif

316

317

318

319

320

321

322#if __cplusplus < 201103L

325 {

326 _M_t = __x._M_t;

327 return *this;

328 }

329#else

332

333

336

337

338

339

340

341

342

343

344

345

346

347

350 {

351 _M_t._M_assign_unique(__l.begin(), __l.end());

352 return *this;

353 }

354#endif

355

356

357 allocator_type

359 { return allocator_type(_M_t.get_allocator()); }

360

361

362

363

364

365

366

369 { return _M_t.begin(); }

370

371

372

373

374

375

376 const_iterator

377 begin() const _GLIBCXX_NOEXCEPT

378 { return _M_t.begin(); }

379

380

381

382

383

384

386 end() _GLIBCXX_NOEXCEPT

387 { return _M_t.end(); }

388

389

390

391

392

393

394 const_iterator

395 end() const _GLIBCXX_NOEXCEPT

396 { return _M_t.end(); }

397

398

399

400

401

402

405 { return _M_t.rbegin(); }

406

407

408

409

410

411

412 const_reverse_iterator

414 { return _M_t.rbegin(); }

415

416

417

418

419

420

423 { return _M_t.rend(); }

424

425

426

427

428

429

430 const_reverse_iterator

431 rend() const _GLIBCXX_NOEXCEPT

432 { return _M_t.rend(); }

433

434#if __cplusplus >= 201103L

435

436

437

438

439

440 const_iterator

442 { return _M_t.begin(); }

443

444

445

446

447

448

449 const_iterator

451 { return _M_t.end(); }

452

453

454

455

456

457

458 const_reverse_iterator

460 { return _M_t.rbegin(); }

461

462

463

464

465

466

467 const_reverse_iterator

469 { return _M_t.rend(); }

470#endif

471

472

473

474

475

476 _GLIBCXX_NODISCARD bool

477 empty() const _GLIBCXX_NOEXCEPT

478 { return _M_t.empty(); }

479

480

481 size_type

482 size() const _GLIBCXX_NOEXCEPT

483 { return _M_t.size(); }

484

485

486 size_type

488 { return _M_t.max_size(); }

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503 mapped_type&

505 {

506

507 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)

508

510

511 if (__i == end() || key_comp()(__k, (*__i).first))

512#if __cplusplus >= 201103L

516#else

518#endif

519 return (*__i).second;

520 }

521

522#if __cplusplus >= 201103L

523 mapped_type&

525 {

526

527 __glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)

528

530

531 if (__i == end() || key_comp()(__k, (*__i).first))

535 return (*__i).second;

536 }

537#endif

538

539

540

541

542

543

544

545

546

547

548 mapped_type&

549 at(const key_type& __k)

550 {

552 if (__i == end() || key_comp()(__k, (*__i).first))

553 __throw_out_of_range(__N("map::at"));

554 return (*__i).second;

555 }

556

557 const mapped_type&

558 at(const key_type& __k) const

559 {

561 if (__i == end() || key_comp()(__k, (*__i).first))

562 __throw_out_of_range(__N("map::at"));

563 return (*__i).second;

564 }

565

566

567#if __cplusplus >= 201103L

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586 template<typename... _Args>

589 {

590#if __cplusplus >= 201703L

591 if constexpr (sizeof...(_Args) == 2)

592 if constexpr (is_same_v<allocator_type, allocator<value_type>>)

593 {

594 auto&& [__a, __v] = pair<_Args&...>(__args...);

595 if constexpr (__usable_key<decltype(__a)>)

596 {

597 const key_type& __k = __a;

599 if (__i == end() || key_comp()(__k, (*__i).first))

600 {

601 __i = emplace_hint(__i, std::forward<_Args>(__args)...);

602 return {__i, true};

603 }

604 return {__i, false};

605 }

606 }

607#endif

608 return _M_t._M_emplace_unique(std::forward<_Args>(__args)...);

609 }

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636 template<typename... _Args>

639 {

640 return _M_t._M_emplace_hint_unique(__pos,

641 std::forward<_Args>(__args)...);

642 }

643#endif

644

645#if __cplusplus > 201402L

646

647 node_type

649 {

650 __glibcxx_assert(__pos != end());

651 return _M_t.extract(__pos);

652 }

653

654

655 node_type

657 { return _M_t.extract(__x); }

658

659

660 insert_return_type

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

663

664

666 insert(const_iterator __hint, node_type&& __nh)

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

668

669 template<typename, typename>

670 friend struct std::_Rb_tree_merge_helper;

671

672 template<typename _Cmp2>

673 void

675 {

676 using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>;

677 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));

678 }

679

680 template<typename _Cmp2>

681 void

682 merge(map<_Key, _Tp, _Cmp2, _Alloc>&& __source)

683 { merge(__source); }

684

685 template<typename _Cmp2>

686 void

687 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>& __source)

688 {

689 using _Merge_helper = _Rb_tree_merge_helper<map, _Cmp2>;

690 _M_t._M_merge_unique(_Merge_helper::_S_get_tree(__source));

691 }

692

693 template<typename _Cmp2>

694 void

695 merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source)

696 { merge(__source); }

697#endif

698

699#ifdef __glibcxx_map_try_emplace

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720 template <typename... _Args>

721 pair<iterator, bool>

723 {

725 if (__i == end() || key_comp()(__k, (*__i).first))

726 {

730 std::forward<_Args>(__args)...));

731 return {__i, true};

732 }

733 return {__i, false};

734 }

735

736

737 template <typename... _Args>

739 try_emplace(key_type&& __k, _Args&&... __args)

740 {

742 if (__i == end() || key_comp()(__k, (*__i).first))

743 {

747 std::forward<_Args>(__args)...));

748 return {__i, true};

749 }

750 return {__i, false};

751 }

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780 template <typename... _Args>

781 iterator

782 try_emplace(const_iterator __hint, const key_type& __k,

783 _Args&&... __args)

784 {

785 iterator __i;

786 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);

787 if (__true_hint.second)

788 __i = emplace_hint(iterator(__true_hint.second),

792 std::forward<_Args>(__args)...));

793 else

794 __i = iterator(__true_hint.first);

795 return __i;

796 }

797

798

799 template <typename... _Args>

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

802 {

804 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);

805 if (__true_hint.second)

810 std::forward<_Args>(__args)...));

811 else

812 __i = iterator(__true_hint.first);

813 return __i;

814 }

815#endif

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

835 { return _M_t._M_insert_unique(__x); }

836

837#if __cplusplus >= 201103L

838

839

842 { return _M_t._M_insert_unique(std::move(__x)); }

843

844 template<typename _Pair>

845 __enable_if_t<is_constructible<value_type, _Pair>::value,

848 {

849#if __cplusplus >= 201703L

851 if constexpr (__is_pair<remove_const_t<_P2>>)

853 if constexpr (__usable_key<typename _P2::first_type>)

854 {

855 const key_type& __k = __x.first;

857 if (__i == end() || key_comp()(__k, (*__i).first))

858 {

859 __i = emplace_hint(__i, std::forward<_Pair>(__x));

860 return {__i, true};

861 }

862 return {__i, false};

863 }

864#endif

865 return _M_t._M_emplace_unique(std::forward<_Pair>(__x));

866 }

867#endif

868

869

870#if __cplusplus >= 201103L

871

872

873

874

875

876

877

878 void

880 { insert(__list.begin(), __list.end()); }

881#endif

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

908#if __cplusplus >= 201103L

910#else

912#endif

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

914

915#if __cplusplus >= 201103L

916

917

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

921

922 template<typename _Pair>

923 __enable_if_t<is_constructible<value_type, _Pair>::value, iterator>

924 insert(const_iterator __position, _Pair&& __x)

925 {

926 return _M_t._M_emplace_hint_unique(__position,

927 std::forward<_Pair>(__x));

928 }

929#endif

930

931

932

933

934

935

936

937

938

939

940 template<typename _InputIterator>

941 void

942 insert(_InputIterator __first, _InputIterator __last)

943 { _M_t._M_insert_range_unique(__first, __last); }

944

945#if __cplusplus > 201402L

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965 template <typename _Obj>

968 {

970 if (__i == end() || key_comp()(__k, (*__i).first))

971 {

975 std::forward<_Obj>(__obj)));

976 return {__i, true};

977 }

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

979 return {__i, false};

980 }

981

982

983 template <typename _Obj>

986 {

988 if (__i == end() || key_comp()(__k, (*__i).first))

989 {

993 std::forward<_Obj>(__obj)));

994 return {__i, true};

995 }

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

997 return {__i, false};

998 }

999

1000

1001

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1012

1013

1014

1015

1016

1017

1018

1019

1020 template <typename _Obj>

1021 iterator

1023 const key_type& __k, _Obj&& __obj)

1024 {

1025 iterator __i;

1026 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);

1027 if (__true_hint.second)

1028 {

1029 return emplace_hint(iterator(__true_hint.second),

1033 std::forward<_Obj>(__obj)));

1034 }

1035 __i = iterator(__true_hint.first);

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

1037 return __i;

1038 }

1039

1040

1041 template <typename _Obj>

1043 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)

1044 {

1046 auto __true_hint = _M_t._M_get_insert_hint_unique_pos(__hint, __k);

1047 if (__true_hint.second)

1048 {

1053 std::forward<_Obj>(__obj)));

1054 }

1055 __i = iterator(__true_hint.first);

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

1057 return __i;

1058 }

1059#endif

1060

1061#if __cplusplus >= 201103L

1062

1063

1064

1065

1066

1067

1068

1069

1070

1071

1072

1073

1074

1075

1076

1077

1078

1079 iterator

1080 erase(const_iterator __position)

1081 { return _M_t.erase(__position); }

1082

1083

1084 _GLIBCXX_ABI_TAG_CXX11

1087 { return _M_t.erase(__position); }

1088

1089#else

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1100 void

1102 { _M_t.erase(__position); }

1103#endif

1104

1105

1106

1107

1108

1109

1110

1111

1112

1113

1114

1115

1116 size_type

1118 { return _M_t.erase(__x); }

1119

1120#if __cplusplus >= 201103L

1121

1122

1123

1124

1125

1126

1127

1128

1129

1130

1131

1132

1133

1134

1135

1137 erase(const_iterator __first, const_iterator __last)

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

1139#else

1140

1141

1142

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152 void

1154 { _M_t.erase(__first, __last); }

1155#endif

1156

1157

1158

1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169

1170 void

1172 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)

1173 { _M_t.swap(__x._M_t); }

1174

1175

1176

1177

1178

1179

1180

1181 void

1183 { _M_t.clear(); }

1184

1185

1186

1187

1188

1189

1190 key_compare

1192 { return _M_t.key_comp(); }

1193

1194

1195

1196

1197

1198 value_compare

1200 { return value_compare(_M_t.key_comp()); }

1201

1202

1203

1204

1205

1206

1207

1208

1209

1210

1211

1212

1213

1214

1215

1216

1219 { return _M_t.find(__x); }

1220

1221#if __cplusplus > 201103L

1222 template<typename _Kt>

1223 auto

1224 find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))

1225 { return _M_t._M_find_tr(__x); }

1226#endif

1227

1228

1229

1230

1231

1232

1233

1234

1235

1236

1237

1238

1239

1240

1241

1242 const_iterator

1243 find(const key_type& __x) const

1244 { return _M_t.find(__x); }

1245

1246#if __cplusplus > 201103L

1247 template<typename _Kt>

1248 auto

1249 find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))

1250 { return _M_t._M_find_tr(__x); }

1251#endif

1252

1253

1254

1255

1256

1257

1258

1259

1260

1261

1262

1263 size_type

1264 count(const key_type& __x) const

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

1266

1267#if __cplusplus > 201103L

1268 template<typename _Kt>

1269 auto

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

1271 { return _M_t._M_count_tr(__x); }

1272#endif

1273

1274

1275#if __cplusplus > 201703L

1276

1277

1278

1279

1280

1281

1282 bool

1284 { return _M_t.find(__x) != _M_t.end(); }

1285

1286 template<typename _Kt>

1287 auto

1289 -> decltype(_M_t._M_find_tr(__x), void(), true)

1290 { return _M_t._M_find_tr(__x) != _M_t.end(); }

1291

1292#endif

1293

1294

1295

1296

1297

1298

1299

1300

1301

1302

1303

1304

1305

1308 { return _M_t.lower_bound(__x); }

1309

1310#if __cplusplus > 201103L

1311 template<typename _Kt>

1312 auto

1314 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))

1315 { return iterator(_M_t._M_lower_bound_tr(__x)); }

1316#endif

1317

1318

1319

1320

1321

1322

1323

1324

1325

1326

1327

1328

1329

1330

1331 const_iterator

1333 { return _M_t.lower_bound(__x); }

1334

1335#if __cplusplus > 201103L

1336 template<typename _Kt>

1337 auto

1339 -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))

1340 { return const_iterator(_M_t._M_lower_bound_tr(__x)); }

1341#endif

1342

1343

1344

1345

1346

1347

1348

1349

1350

1353 { return _M_t.upper_bound(__x); }

1354

1355#if __cplusplus > 201103L

1356 template<typename _Kt>

1357 auto

1359 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))

1360 { return iterator(_M_t._M_upper_bound_tr(__x)); }

1361#endif

1362

1363

1364

1365

1366

1367

1368

1369

1370

1371 const_iterator

1373 { return _M_t.upper_bound(__x); }

1374

1375#if __cplusplus > 201103L

1376 template<typename _Kt>

1377 auto

1379 -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))

1380 { return const_iterator(_M_t._M_upper_bound_tr(__x)); }

1381#endif

1382

1383

1384

1385

1386

1387

1388

1389

1390

1391

1392

1393

1394

1395

1396

1397

1398

1399

1402 { return _M_t.equal_range(__x); }

1403

1404#if __cplusplus > 201103L

1405 template<typename _Kt>

1406 auto

1410#endif

1411

1412

1413

1414

1415

1416

1417

1418

1419

1420

1421

1422

1423

1424

1425

1426

1427

1428

1431 { return _M_t.equal_range(__x); }

1432

1433#if __cplusplus > 201103L

1434 template<typename _Kt>

1435 auto

1438 _M_t._M_equal_range_tr(__x)))

1439 {

1441 _M_t._M_equal_range_tr(__x));

1442 }

1443#endif

1444

1445

1446 template<typename _K1, typename _T1, typename _C1, typename _A1>

1447 friend bool

1450

1451#if __cpp_lib_three_way_comparison

1452 template<typename _K1, typename _T1, typename _C1, typename _A1>

1453 friend __detail::__synth3way_t<pair<const _K1, _T1>>

1456#else

1457 template<typename _K1, typename _T1, typename _C1, typename _A1>

1458 friend bool

1461#endif

1462 };

1463

1464

1465#if __cpp_deduction_guides >= 201606

1466

1467 template<typename _InputIterator,

1468 typename _Compare = less<__iter_key_t<_InputIterator>>,

1469 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,

1470 typename = _RequireInputIter<_InputIterator>,

1471 typename = _RequireNotAllocator<_Compare>,

1472 typename = _RequireAllocator<_Allocator>>

1473 map(_InputIterator, _InputIterator,

1474 _Compare = _Compare(), _Allocator = _Allocator())

1475 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,

1476 _Compare, _Allocator>;

1477

1478 template<typename _Key, typename _Tp, typename _Compare = less<_Key>,

1479 typename _Allocator = allocator<pair<const _Key, _Tp>>,

1480 typename = _RequireNotAllocator<_Compare>,

1481 typename = _RequireAllocator<_Allocator>>

1482 map(initializer_list<pair<_Key, _Tp>>,

1483 _Compare = _Compare(), _Allocator = _Allocator())

1484 -> map<_Key, _Tp, _Compare, _Allocator>;

1485

1486 template <typename _InputIterator, typename _Allocator,

1487 typename = _RequireInputIter<_InputIterator>,

1488 typename = _RequireAllocator<_Allocator>>

1489 map(_InputIterator, _InputIterator, _Allocator)

1490 -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,

1491 less<__iter_key_t<_InputIterator>>, _Allocator>;

1492

1493 template<typename _Key, typename _Tp, typename _Allocator,

1494 typename = _RequireAllocator<_Allocator>>

1495 map(initializer_list<pair<_Key, _Tp>>, _Allocator)

1496 -> map<_Key, _Tp, less<_Key>, _Allocator>;

1497

1498#endif

1499

1500

1501

1502

1503

1504

1505

1506

1507

1508

1509

1510 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1511 inline bool

1514 { return __x._M_t == __y._M_t; }

1515

1516#if __cpp_lib_three_way_comparison

1517

1518

1519

1520

1521

1522

1523

1524

1525

1526

1527

1528

1529

1530

1531 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1532 inline __detail::__synth3way_t<pair<const _Key, _Tp>>

1533 operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1534 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1535 { return __x._M_t <=> __y._M_t; }

1536#else

1537

1538

1539

1540

1541

1542

1543

1544

1545

1546

1547

1548 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1549 inline bool

1550 operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1551 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1552 { return __x._M_t < __y._M_t; }

1553

1554

1555 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1556 inline bool

1557 operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1558 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1559 { return !(__x == __y); }

1560

1561

1562 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1563 inline bool

1564 operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1565 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1566 { return __y < __x; }

1567

1568

1569 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1570 inline bool

1571 operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1572 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1573 { return !(__y < __x); }

1574

1575

1576 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1577 inline bool

1578 operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,

1579 const map<_Key, _Tp, _Compare, _Alloc>& __y)

1580 { return !(__x < __y); }

1581#endif

1582

1583

1584 template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>

1585 inline void

1588 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))

1589 { __x.swap(__y); }

1590

1591_GLIBCXX_END_NAMESPACE_CONTAINER

1592

1593#if __cplusplus > 201402L

1594

1595 template<typename _Key, typename _Val, typename _Cmp1, typename _Alloc,

1596 typename _Cmp2>

1597 struct

1598 _Rb_tree_merge_helper<_GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>,

1599 _Cmp2>

1600 {

1601 private:

1602 friend class _GLIBCXX_STD_C::map<_Key, _Val, _Cmp1, _Alloc>;

1603

1604 static auto&

1605 _S_get_tree(_GLIBCXX_STD_C::map<_Key, _Val, _Cmp2, _Alloc>& __map)

1606 { return __map._M_t; }

1607

1608 static auto&

1609 _S_get_tree(_GLIBCXX_STD_C::multimap<_Key, _Val, _Cmp2, _Alloc>& __map)

1610 { return __map._M_t; }

1611 };

1612#endif

1613

1614_GLIBCXX_END_NAMESPACE_VERSION

1615}

1616

1617#endif

constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)

constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)

constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)

constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)

typename remove_reference< _Tp >::type remove_reference_t

Alias template for remove_reference.

constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept

Create a tuple of lvalue or rvalue references to the arguments.

constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept

Convert a value to an rvalue.

constexpr piecewise_construct_t piecewise_construct

Tag for piecewise construction of std::pair objects.

ISO C++ entities toplevel namespace is std.

Primary class template, tuple.

is_nothrow_copy_constructible

The standard allocator, as per C++03 [20.4.1].

Node handle type for maps.

Return type of insert(node_handle&&) on unique maps/sets.

Struct holding two objects of arbitrary type.

_T1 first

The first member.

constexpr void swap(pair &__p) noexcept(__and_< __is_nothrow_swappable< _T1 >, __is_nothrow_swappable< _T2 > >::value)

Swap the first members and then the second members.

A standard container made up of (key,value) pairs, which can be retrieved based on a key,...

iterator emplace_hint(const_iterator __pos, _Args &&... __args)

Attempts to build and insert a std::pair into the map.

const_iterator find(const key_type &__x) const

Tries to locate an element in a map.

map(_InputIterator __first, _InputIterator __last, const allocator_type &__a)

Allocator-extended range constructor.

__enable_if_t< is_constructible< value_type, _Pair >::value, iterator > insert(const_iterator __position, _Pair &&__x)

Attempts to insert a std::pair into the map.

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

Finds the number of elements with given key.

auto equal_range(const _Kt &__x) const -> decltype(pair< const_iterator, const_iterator >(_M_t._M_equal_range_tr(__x)))

Finds a subsequence matching given key.

bool empty() const noexcept

const_reverse_iterator rend() const noexcept

bool contains(const key_type &__x) const

Finds whether an element with the given key exists.

map(const map &__m, const __type_identity_t< allocator_type > &__a)

Allocator-extended copy constructor.

value_compare value_comp() const

auto lower_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))

Finds the beginning of a subsequence matching given key.

pair< iterator, bool > try_emplace(const key_type &__k, _Args &&... __args)

Attempts to build and insert a std::pair into the map.

void insert(_InputIterator __first, _InputIterator __last)

Template function that attempts to insert a range of elements.

iterator upper_bound(const key_type &__x)

Finds the end of a subsequence matching given key.

std::pair< iterator, iterator > equal_range(const key_type &__x)

Finds a subsequence matching given key.

map(initializer_list< value_type > __l, const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())

Builds a map from an initializer_list.

insert_return_type insert(node_type &&__nh)

Re-insert an extracted node.

auto find(const _Kt &__x) -> decltype(_M_t._M_find_tr(__x))

Tries to locate an element in a map.

iterator try_emplace(const_iterator __hint, const key_type &__k, _Args &&... __args)

Attempts to build and insert a std::pair into the map.

std::pair< iterator, bool > insert(const value_type &__x)

Attempts to insert a std::pair into the map.

map(map &&)=default

Map move constructor.

size_type count(const key_type &__x) const

Finds the number of elements with given key.

const_reverse_iterator rbegin() const noexcept

reverse_iterator rbegin() noexcept

iterator insert_or_assign(const_iterator __hint, const key_type &__k, _Obj &&__obj)

Attempts to insert or assign a std::pair into the map.

const_iterator end() const noexcept

const_iterator cend() const noexcept

mapped_type & at(const key_type &__k)

Access to map data.

auto upper_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))

Finds the end of a subsequence matching given key.

key_compare key_comp() const

map(map &&__m, const __type_identity_t< allocator_type > &__a) noexcept(is_nothrow_copy_constructible< _Compare >::value &&_Alloc_traits::_S_always_equal())

Allocator-extended move constructor.

auto lower_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))

Finds the beginning of a subsequence matching given key.

map(_InputIterator __first, _InputIterator __last)

Builds a map from a range.

const_reverse_iterator crbegin() const noexcept

pair< iterator, bool > insert_or_assign(const key_type &__k, _Obj &&__obj)

Attempts to insert or assign a std::pair into the map.

void swap(map &__x) noexcept(/*conditional */)

Swaps data with another map.

size_type erase(const key_type &__x)

Erases elements according to the provided key.

iterator insert(const_iterator __hint, node_type &&__nh)

Re-insert an extracted node.

map(initializer_list< value_type > __l, const allocator_type &__a)

Allocator-extended initialier-list constructor.

map(const map &)=default

Map copy constructor.

node_type extract(const_iterator __pos)

Extract a node.

map(const allocator_type &__a)

Allocator-extended default constructor.

node_type extract(const key_type &__x)

Extract a node.

iterator insert(const_iterator __position, value_type &&__x)

Attempts to insert a std::pair into the map.

iterator insert(const_iterator __position, const value_type &__x)

Attempts to insert a std::pair into the map.

map(const _Compare &__comp, const allocator_type &__a=allocator_type())

Creates a map with no elements.

reverse_iterator rend() noexcept

iterator erase(const_iterator __first, const_iterator __last)

Erases a [first,last) range of elements from a map.

void insert(std::initializer_list< value_type > __list)

Attempts to insert a list of std::pairs into the map.

map & operator=(const map &)=default

Map assignment operator.

const_iterator lower_bound(const key_type &__x) const

Finds the beginning of a subsequence matching given key.

size_type size() const noexcept

std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const

Finds a subsequence matching given key.

auto upper_bound(const _Kt &__x) const -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x)))

Finds the end of a subsequence matching given key.

iterator find(const key_type &__x)

Tries to locate an element in a map.

map(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())

Builds a map from a range.

__enable_if_t< is_constructible< value_type, _Pair >::value, pair< iterator, bool > > insert(_Pair &&__x)

Attempts to insert a std::pair into the map.

iterator erase(const_iterator __position)

Erases an element from a map.

auto find(const _Kt &__x) const -> decltype(_M_t._M_find_tr(__x))

Tries to locate an element in a map.

mapped_type & operator[](const key_type &__k)

Subscript ( [] ) access to map data.

auto contains(const _Kt &__x) const -> decltype(_M_t._M_find_tr(__x), void(), true)

Finds whether an element with the given key exists.

iterator lower_bound(const key_type &__x)

Finds the beginning of a subsequence matching given key.

const_reverse_iterator crend() const noexcept

allocator_type get_allocator() const noexcept

Get a copy of the memory allocation object.

map & operator=(initializer_list< value_type > __l)

Map list assignment operator.

_GLIBCXX_ABI_TAG_CXX11 iterator erase(iterator __position)

Erases an element from a map.

auto equal_range(const _Kt &__x) -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))

Finds a subsequence matching given key.

std::pair< iterator, bool > emplace(_Args &&... __args)

Attempts to build and insert a std::pair into the map.

const_iterator cbegin() const noexcept

size_type max_size() const noexcept

const_iterator begin() const noexcept

iterator begin() noexcept

map & operator=(map &&)=default

Move assignment operator.

std::pair< iterator, bool > insert(value_type &&__x)

Attempts to insert a std::pair into the map.

map()=default

Default constructor creates no elements.

const_iterator upper_bound(const key_type &__x) const

Finds the end of a subsequence matching given key.

Uniform interface to C++98 and C++11 allocators.