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

56#ifndef _STL_ALGO_H

57#define _STL_ALGO_H 1

64#if __cplusplus >= 201103L

66#endif

68#if _GLIBCXX_HOSTED

70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)

71# include <cstdlib>

72# endif

73#endif

77namespace std _GLIBCXX_VISIBILITY(default)

78{

79_GLIBCXX_BEGIN_NAMESPACE_VERSION

82 template<typename _Iterator, typename _Compare>

83 _GLIBCXX20_CONSTEXPR

84 void

86 _Iterator __c, _Compare __comp)

87 {

88 if (__comp(__a, __b))

89 {

90 if (__comp(__b, __c))

91 std::iter_swap(__result, __b);

92 else if (__comp(__a, __c))

93 std::iter_swap(__result, __c);

94 else

95 std::iter_swap(__result, __a);

96 }

97 else if (__comp(__a, __c))

98 std::iter_swap(__result, __a);

99 else if (__comp(__b, __c))

100 std::iter_swap(__result, __c);

101 else

102 std::iter_swap(__result, __b);

103 }

104

105

106 template<typename _InputIterator, typename _Predicate>

107 _GLIBCXX20_CONSTEXPR

108 inline _InputIterator

110 _Predicate __pred)

111 {

112 return std::__find_if(__first, __last,

113 __gnu_cxx::__ops::__negate(__pred));

114 }

115

116

117

118

119 template<typename _InputIterator, typename _Predicate, typename _Distance>

120 _GLIBCXX20_CONSTEXPR

121 _InputIterator

122 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)

123 {

124 for (; __len; --__len, (void) ++__first)

125 if (!__pred(__first))

126 break;

127 return __first;

128 }

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147 template<typename _ForwardIterator, typename _Integer,

148 typename _UnaryPredicate>

149 _GLIBCXX20_CONSTEXPR

150 _ForwardIterator

151 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,

152 _Integer __count, _UnaryPredicate __unary_pred,

154 {

155 __first = std::__find_if(__first, __last, __unary_pred);

156 while (__first != __last)

157 {

159 __n = __count;

160 _ForwardIterator __i = __first;

161 ++__i;

162 while (__i != __last && __n != 1 && __unary_pred(__i))

163 {

164 ++__i;

165 --__n;

166 }

167 if (__n == 1)

168 return __first;

169 if (__i == __last)

170 return __last;

171 __first = std::__find_if(++__i, __last, __unary_pred);

172 }

173 return __last;

174 }

175

176

177

178

179

180 template<typename _RandomAccessIter, typename _Integer,

181 typename _UnaryPredicate>

182 _GLIBCXX20_CONSTEXPR

183 _RandomAccessIter

184 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,

185 _Integer __count, _UnaryPredicate __unary_pred,

187 {

189 _DistanceType;

190

191 _DistanceType __tailSize = __last - __first;

192 _DistanceType __remainder = __count;

193

194 while (__remainder <= __tailSize)

195 {

196 __first += __remainder;

197 __tailSize -= __remainder;

198

199

200 _RandomAccessIter __backTrack = __first;

201 while (__unary_pred(--__backTrack))

202 {

203 if (--__remainder == 0)

204 return (__first - __count);

205 }

206 __remainder = __count + 1 - (__first - __backTrack);

207 }

208 return __last;

209 }

210

211 template<typename _ForwardIterator, typename _Integer,

212 typename _UnaryPredicate>

213 _GLIBCXX20_CONSTEXPR

214 _ForwardIterator

215 __search_n(_ForwardIterator __first, _ForwardIterator __last,

216 _Integer __count,

217 _UnaryPredicate __unary_pred)

218 {

219 if (__count <= 0)

220 return __first;

221

222 if (__count == 1)

223 return std::__find_if(__first, __last, __unary_pred);

224

227 }

228

229

230 template<typename _ForwardIterator1, typename _ForwardIterator2,

231 typename _BinaryPredicate>

232 _GLIBCXX20_CONSTEXPR

233 _ForwardIterator1

234 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

235 _ForwardIterator2 __first2, _ForwardIterator2 __last2,

236 forward_iterator_tag, forward_iterator_tag,

237 _BinaryPredicate __comp)

238 {

239 if (__first2 == __last2)

240 return __last1;

241

242 _ForwardIterator1 __result = __last1;

243 while (1)

244 {

245 _ForwardIterator1 __new_result

246 = std::__search(__first1, __last1, __first2, __last2, __comp);

247 if (__new_result == __last1)

248 return __result;

249 else

250 {

251 __result = __new_result;

252 __first1 = __new_result;

253 ++__first1;

254 }

255 }

256 }

257

258

259 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,

260 typename _BinaryPredicate>

261 _GLIBCXX20_CONSTEXPR

262 _BidirectionalIterator1

263 __find_end(_BidirectionalIterator1 __first1,

264 _BidirectionalIterator1 __last1,

265 _BidirectionalIterator2 __first2,

266 _BidirectionalIterator2 __last2,

267 bidirectional_iterator_tag, bidirectional_iterator_tag,

268 _BinaryPredicate __comp)

269 {

270

271 __glibcxx_function_requires(_BidirectionalIteratorConcept<

272 _BidirectionalIterator1>)

273 __glibcxx_function_requires(_BidirectionalIteratorConcept<

274 _BidirectionalIterator2>)

275

276 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;

277 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;

278

279 _RevIterator1 __rlast1(__first1);

280 _RevIterator2 __rlast2(__first2);

281 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,

282 _RevIterator2(__last2), __rlast2,

283 __comp);

284

285 if (__rresult == __rlast1)

286 return __last1;

287 else

288 {

289 _BidirectionalIterator1 __result = __rresult.base();

291 return __result;

292 }

293 }

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321 template<typename _ForwardIterator1, typename _ForwardIterator2>

322 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

323 inline _ForwardIterator1

324 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

325 _ForwardIterator2 __first2, _ForwardIterator2 __last2)

326 {

327

328 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)

329 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)

330 __glibcxx_function_requires(_EqualOpConcept<

333 __glibcxx_requires_valid_range(__first1, __last1);

334 __glibcxx_requires_valid_range(__first2, __last2);

335

336 return std::__find_end(__first1, __last1, __first2, __last2,

339 __gnu_cxx::__ops::__iter_equal_to_iter());

340 }

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370 template<typename _ForwardIterator1, typename _ForwardIterator2,

371 typename _BinaryPredicate>

372 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

373 inline _ForwardIterator1

374 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

375 _ForwardIterator2 __first2, _ForwardIterator2 __last2,

376 _BinaryPredicate __comp)

377 {

378

379 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)

380 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)

381 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

384 __glibcxx_requires_valid_range(__first1, __last1);

385 __glibcxx_requires_valid_range(__first2, __last2);

386

387 return std::__find_end(__first1, __last1, __first2, __last2,

390 __gnu_cxx::__ops::__iter_comp_iter(__comp));

391 }

392

393#if __cplusplus >= 201103L

394

395

396

397

398

399

400

401

402

403

404

405

406 template<typename _InputIterator, typename _Predicate>

407 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

408 inline bool

409 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

410 { return __last == std::find_if_not(__first, __last, __pred); }

411

412

413

414

415

416

417

418

419

420

421

422

423

424 template<typename _InputIterator, typename _Predicate>

425 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

426 inline bool

427 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

428 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443 template<typename _InputIterator, typename _Predicate>

444 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

445 inline bool

446 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

447 { return !std::none_of(__first, __last, __pred); }

448

449

450

451

452

453

454

455

456

457

458

459 template<typename _InputIterator, typename _Predicate>

460 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

461 inline _InputIterator

462 find_if_not(_InputIterator __first, _InputIterator __last,

463 _Predicate __pred)

464 {

465

466 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

467 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

469 __glibcxx_requires_valid_range(__first, __last);

471 __gnu_cxx::__ops::__pred_iter(__pred));

472 }

473

474

475

476

477

478

479

480

481

482

483

484 template<typename _InputIterator, typename _Predicate>

485 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

486 inline bool

487 is_partitioned(_InputIterator __first, _InputIterator __last,

488 _Predicate __pred)

489 {

490 __first = std::find_if_not(__first, __last, __pred);

491 if (__first == __last)

492 return true;

493 ++__first;

494 return std::none_of(__first, __last, __pred);

495 }

496

497

498

499

500

501

502

503

504

505

506 template<typename _ForwardIterator, typename _Predicate>

507 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

508 _ForwardIterator

509 partition_point(_ForwardIterator __first, _ForwardIterator __last,

510 _Predicate __pred)

511 {

512

513 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

514 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

516

517

518 __glibcxx_requires_valid_range(__first, __last);

519

521 _DistanceType;

522

523 _DistanceType __len = std::distance(__first, __last);

524

525 while (__len > 0)

526 {

527 _DistanceType __half = __len >> 1;

528 _ForwardIterator __middle = __first;

530 if (__pred(*__middle))

531 {

532 __first = __middle;

533 ++__first;

534 __len = __len - __half - 1;

535 }

536 else

537 __len = __half;

538 }

539 return __first;

540 }

541#endif

542

543 template<typename _InputIterator, typename _OutputIterator,

544 typename _Predicate>

545 _GLIBCXX20_CONSTEXPR

546 _OutputIterator

547 __remove_copy_if(_InputIterator __first, _InputIterator __last,

548 _OutputIterator __result, _Predicate __pred)

549 {

550 for (; __first != __last; ++__first)

551 if (!__pred(__first))

552 {

553 *__result = *__first;

554 ++__result;

555 }

556 return __result;

557 }

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573 template<typename _InputIterator, typename _OutputIterator, typename _Tp>

574 _GLIBCXX20_CONSTEXPR

575 inline _OutputIterator

576 remove_copy(_InputIterator __first, _InputIterator __last,

577 _OutputIterator __result, const _Tp& __value)

578 {

579

580 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

581 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

583 __glibcxx_function_requires(_EqualOpConcept<

585 __glibcxx_requires_valid_range(__first, __last);

586

587 return std::__remove_copy_if(__first, __last, __result,

588 __gnu_cxx::__ops::__iter_equals_val(__value));

589 }

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606 template<typename _InputIterator, typename _OutputIterator,

607 typename _Predicate>

608 _GLIBCXX20_CONSTEXPR

609 inline _OutputIterator

610 remove_copy_if(_InputIterator __first, _InputIterator __last,

611 _OutputIterator __result, _Predicate __pred)

612 {

613

614 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

615 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

617 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

619 __glibcxx_requires_valid_range(__first, __last);

620

621 return std::__remove_copy_if(__first, __last, __result,

622 __gnu_cxx::__ops::__pred_iter(__pred));

623 }

624

625#if __cplusplus >= 201103L

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641 template<typename _InputIterator, typename _OutputIterator,

642 typename _Predicate>

643 _GLIBCXX20_CONSTEXPR

644 _OutputIterator

645 copy_if(_InputIterator __first, _InputIterator __last,

646 _OutputIterator __result, _Predicate __pred)

647 {

648

649 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

650 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

652 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

654 __glibcxx_requires_valid_range(__first, __last);

655

656 for (; __first != __last; ++__first)

657 if (__pred(*__first))

658 {

659 *__result = *__first;

660 ++__result;

661 }

662 return __result;

663 }

664

665 template<typename _InputIterator, typename _Size, typename _OutputIterator>

666 _GLIBCXX20_CONSTEXPR

667 _OutputIterator

668 __copy_n(_InputIterator __first, _Size __n,

669 _OutputIterator __result, input_iterator_tag)

670 {

671 return std::__niter_wrap(__result,

672 __copy_n_a(__first, __n,

673 std::__niter_base(__result), true));

674 }

675

676 template<typename _RandomAccessIterator, typename _Size,

677 typename _OutputIterator>

678 _GLIBCXX20_CONSTEXPR

679 inline _OutputIterator

680 __copy_n(_RandomAccessIterator __first, _Size __n,

681 _OutputIterator __result, random_access_iterator_tag)

682 { return std::copy(__first, __first + __n, __result); }

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697 template<typename _InputIterator, typename _Size, typename _OutputIterator>

698 _GLIBCXX20_CONSTEXPR

699 inline _OutputIterator

700 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)

701 {

702

703 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

704 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

706

707 const auto __n2 = std::__size_to_integer(__n);

708 if (__n2 <= 0)

709 return __result;

710

711 __glibcxx_requires_can_increment(__first, __n2);

712 __glibcxx_requires_can_increment(__result, __n2);

713

714 return std::__copy_n(__first, __n2, __result,

716 }

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733 template<typename _InputIterator, typename _OutputIterator1,

734 typename _OutputIterator2, typename _Predicate>

735 _GLIBCXX20_CONSTEXPR

736 pair<_OutputIterator1, _OutputIterator2>

737 partition_copy(_InputIterator __first, _InputIterator __last,

738 _OutputIterator1 __out_true, _OutputIterator2 __out_false,

739 _Predicate __pred)

740 {

741

742 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

743 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,

745 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,

747 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

749 __glibcxx_requires_valid_range(__first, __last);

750

751 for (; __first != __last; ++__first)

752 if (__pred(*__first))

753 {

754 *__out_true = *__first;

755 ++__out_true;

756 }

757 else

758 {

759 *__out_false = *__first;

760 ++__out_false;

761 }

762

764 }

765#endif

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784 template<typename _ForwardIterator, typename _Tp>

785 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

786 inline _ForwardIterator

787 remove(_ForwardIterator __first, _ForwardIterator __last,

788 const _Tp& __value)

789 {

790

791 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

792 _ForwardIterator>)

793 __glibcxx_function_requires(_EqualOpConcept<

795 __glibcxx_requires_valid_range(__first, __last);

796

797 return std::__remove_if(__first, __last,

798 __gnu_cxx::__ops::__iter_equals_val(__value));

799 }

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818 template<typename _ForwardIterator, typename _Predicate>

819 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

820 inline _ForwardIterator

821 remove_if(_ForwardIterator __first, _ForwardIterator __last,

822 _Predicate __pred)

823 {

824

825 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

826 _ForwardIterator>)

827 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

829 __glibcxx_requires_valid_range(__first, __last);

830

831 return std::__remove_if(__first, __last,

832 __gnu_cxx::__ops::__pred_iter(__pred));

833 }

834

835 template<typename _ForwardIterator, typename _BinaryPredicate>

836 _GLIBCXX20_CONSTEXPR

837 _ForwardIterator

838 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,

839 _BinaryPredicate __binary_pred)

840 {

841 if (__first == __last)

842 return __last;

843 _ForwardIterator __next = __first;

844 while (++__next != __last)

845 {

846 if (__binary_pred(__first, __next))

847 return __first;

848 __first = __next;

849 }

850 return __last;

851 }

852

853 template<typename _ForwardIterator, typename _BinaryPredicate>

854 _GLIBCXX20_CONSTEXPR

855 _ForwardIterator

856 __unique(_ForwardIterator __first, _ForwardIterator __last,

857 _BinaryPredicate __binary_pred)

858 {

859

860 __first = std::__adjacent_find(__first, __last, __binary_pred);

861 if (__first == __last)

862 return __last;

863

864

865 _ForwardIterator __dest = __first;

866 ++__first;

867 while (++__first != __last)

868 if (!__binary_pred(__dest, __first))

869 *++__dest = _GLIBCXX_MOVE(*__first);

870 return ++__dest;

871 }

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887 template<typename _ForwardIterator>

888 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

889 inline _ForwardIterator

890 unique(_ForwardIterator __first, _ForwardIterator __last)

891 {

892

893 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

894 _ForwardIterator>)

895 __glibcxx_function_requires(_EqualityComparableConcept<

897 __glibcxx_requires_valid_range(__first, __last);

898

899 return std::__unique(__first, __last,

900 __gnu_cxx::__ops::__iter_equal_to_iter());

901 }

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918 template<typename _ForwardIterator, typename _BinaryPredicate>

919 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

920 inline _ForwardIterator

921 unique(_ForwardIterator __first, _ForwardIterator __last,

922 _BinaryPredicate __binary_pred)

923 {

924

925 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

926 _ForwardIterator>)

927 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

930 __glibcxx_requires_valid_range(__first, __last);

931

932 return std::__unique(__first, __last,

933 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));

934 }

935

936

937

938

939

940

941

942 template<typename _ForwardIterator, typename _OutputIterator,

943 typename _BinaryPredicate>

944 _GLIBCXX20_CONSTEXPR

945 _OutputIterator

946 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,

947 _OutputIterator __result, _BinaryPredicate __binary_pred,

949 {

950

951 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

954

955 _ForwardIterator __next = __first;

956 *__result = *__first;

957 while (++__next != __last)

958 if (!__binary_pred(__first, __next))

959 {

960 __first = __next;

961 *++__result = *__first;

962 }

963 return ++__result;

964 }

965

966

967

968

969

970

971

972 template<typename _InputIterator, typename _OutputIterator,

973 typename _BinaryPredicate>

974 _GLIBCXX20_CONSTEXPR

975 _OutputIterator

977 _OutputIterator __result, _BinaryPredicate __binary_pred,

979 {

980

981 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

984

986 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))

987 __rebound_pred

988 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);

989 *__result = __value;

990 while (++__first != __last)

991 if (!__rebound_pred(__first, __value))

992 {

993 __value = *__first;

994 *++__result = __value;

995 }

996 return ++__result;

997 }

998

999

1000

1001

1002

1003

1004

1005 template<typename _InputIterator, typename _ForwardIterator,

1006 typename _BinaryPredicate>

1007 _GLIBCXX20_CONSTEXPR

1008 _ForwardIterator

1010 _ForwardIterator __result, _BinaryPredicate __binary_pred,

1012 {

1013

1014 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

1017 *__result = *__first;

1018 while (++__first != __last)

1019 if (!__binary_pred(__result, __first))

1020 *++__result = *__first;

1021 return ++__result;

1022 }

1023

1024

1025

1026

1027

1028

1029 template<typename _BidirectionalIterator>

1030 _GLIBCXX20_CONSTEXPR

1031 void

1032 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,

1034 {

1035 while (true)

1036 if (__first == __last || __first == --__last)

1037 return;

1038 else

1039 {

1040 std::iter_swap(__first, __last);

1041 ++__first;

1042 }

1043 }

1044

1045

1046

1047

1048

1049

1050 template<typename _RandomAccessIterator>

1051 _GLIBCXX20_CONSTEXPR

1052 void

1053 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,

1055 {

1056 if (__first == __last)

1057 return;

1058 --__last;

1059 while (__first < __last)

1060 {

1061 std::iter_swap(__first, __last);

1062 ++__first;

1063 --__last;

1064 }

1065 }

1066

1067

1068

1069

1070

1071

1072

1073

1074

1075

1076

1077

1078

1079 template<typename _BidirectionalIterator>

1080 _GLIBCXX20_CONSTEXPR

1081 inline void

1082 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)

1083 {

1084

1085 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<

1086 _BidirectionalIterator>)

1087 __glibcxx_requires_valid_range(__first, __last);

1089 }

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1100

1101

1102

1103

1104

1105

1106

1107 template<typename _BidirectionalIterator, typename _OutputIterator>

1108 _GLIBCXX20_CONSTEXPR

1109 _OutputIterator

1110 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,

1111 _OutputIterator __result)

1112 {

1113

1114 __glibcxx_function_requires(_BidirectionalIteratorConcept<

1115 _BidirectionalIterator>)

1116 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

1118 __glibcxx_requires_valid_range(__first, __last);

1119

1120 while (__first != __last)

1121 {

1122 --__last;

1123 *__result = *__last;

1124 ++__result;

1125 }

1126 return __result;

1127 }

1128

1129

1130

1131

1132

1133 template<typename _EuclideanRingElement>

1134 _GLIBCXX20_CONSTEXPR

1135 _EuclideanRingElement

1136 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)

1137 {

1138 while (__n != 0)

1139 {

1140 _EuclideanRingElement __t = __m % __n;

1141 __m = __n;

1142 __n = __t;

1143 }

1144 return __m;

1145 }

1146

1147_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)

1148

1149

1150 template<typename _ForwardIterator>

1151 _GLIBCXX20_CONSTEXPR

1152 _ForwardIterator

1154 _ForwardIterator __middle,

1155 _ForwardIterator __last,

1157 {

1158 if (__first == __middle)

1159 return __last;

1160 else if (__last == __middle)

1161 return __first;

1162

1163 _ForwardIterator __first2 = __middle;

1164 do

1165 {

1166 std::iter_swap(__first, __first2);

1167 ++__first;

1168 ++__first2;

1169 if (__first == __middle)

1170 __middle = __first2;

1171 }

1172 while (__first2 != __last);

1173

1174 _ForwardIterator __ret = __first;

1175

1176 __first2 = __middle;

1177

1178 while (__first2 != __last)

1179 {

1180 std::iter_swap(__first, __first2);

1181 ++__first;

1182 ++__first2;

1183 if (__first == __middle)

1184 __middle = __first2;

1185 else if (__first2 == __last)

1186 __first2 = __middle;

1187 }

1188 return __ret;

1189 }

1190

1191

1192 template<typename _BidirectionalIterator>

1193 _GLIBCXX20_CONSTEXPR

1194 _BidirectionalIterator

1196 _BidirectionalIterator __middle,

1197 _BidirectionalIterator __last,

1199 {

1200

1201 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<

1202 _BidirectionalIterator>)

1203

1204 if (__first == __middle)

1205 return __last;

1206 else if (__last == __middle)

1207 return __first;

1208

1211

1212 while (__first != __middle && __middle != __last)

1213 {

1214 std::iter_swap(__first, --__last);

1215 ++__first;

1216 }

1217

1218 if (__first == __middle)

1219 {

1221 return __last;

1222 }

1223 else

1224 {

1226 return __first;

1227 }

1228 }

1229

1230

1231 template<typename _RandomAccessIterator>

1232 _GLIBCXX20_CONSTEXPR

1233 _RandomAccessIterator

1235 _RandomAccessIterator __middle,

1236 _RandomAccessIterator __last,

1238 {

1239

1240 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

1241 _RandomAccessIterator>)

1242

1243 if (__first == __middle)

1244 return __last;

1245 else if (__last == __middle)

1246 return __first;

1247

1249 _Distance;

1251 _ValueType;

1252

1253#if __cplusplus >= 201103L

1254 typedef typename make_unsigned<_Distance>::type _UDistance;

1255#else

1256 typedef _Distance _UDistance;

1257#endif

1258

1259 _Distance __n = __last - __first;

1260 _Distance __k = __middle - __first;

1261

1262 if (__k == __n - __k)

1263 {

1264 std::swap_ranges(__first, __middle, __middle);

1265 return __middle;

1266 }

1267

1268 _RandomAccessIterator __p = __first;

1269 _RandomAccessIterator __ret = __first + (__last - __middle);

1270

1271 for (;;)

1272 {

1273 if (__k < __n - __k)

1274 {

1275 if (__is_pod(_ValueType) && __k == 1)

1276 {

1277 _ValueType __t = _GLIBCXX_MOVE(*__p);

1278 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);

1279 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);

1280 return __ret;

1281 }

1282 _RandomAccessIterator __q = __p + __k;

1283 for (_Distance __i = 0; __i < __n - __k; ++ __i)

1284 {

1285 std::iter_swap(__p, __q);

1286 ++__p;

1287 ++__q;

1288 }

1289 __n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);

1290 if (__n == 0)

1291 return __ret;

1292 std::swap(__n, __k);

1293 __k = __n - __k;

1294 }

1295 else

1296 {

1297 __k = __n - __k;

1298 if (__is_pod(_ValueType) && __k == 1)

1299 {

1300 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));

1301 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);

1302 *__p = _GLIBCXX_MOVE(__t);

1303 return __ret;

1304 }

1305 _RandomAccessIterator __q = __p + __n;

1306 __p = __q - __k;

1307 for (_Distance __i = 0; __i < __n - __k; ++ __i)

1308 {

1309 --__p;

1310 --__q;

1311 std::iter_swap(__p, __q);

1312 }

1313 __n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);

1314 if (__n == 0)

1315 return __ret;

1316 std::swap(__n, __k);

1317 }

1318 }

1319 }

1320

1321

1322

1323

1324

1325

1326

1327

1328

1329

1330

1331

1332

1333

1334

1335

1336

1337

1338

1339

1340

1341

1342

1343

1344 template<typename _ForwardIterator>

1345 _GLIBCXX20_CONSTEXPR

1346 inline _ForwardIterator

1347 rotate(_ForwardIterator __first, _ForwardIterator __middle,

1348 _ForwardIterator __last)

1349 {

1350

1351 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

1352 _ForwardIterator>)

1353 __glibcxx_requires_valid_range(__first, __middle);

1354 __glibcxx_requires_valid_range(__middle, __last);

1355

1358 }

1359

1360_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)

1361

1362

1363

1364

1365

1366

1367

1368

1369

1370

1371

1372

1373

1374

1375

1376

1377

1378

1379

1380

1381

1382 template<typename _ForwardIterator, typename _OutputIterator>

1383 _GLIBCXX20_CONSTEXPR

1384 inline _OutputIterator

1385 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,

1386 _ForwardIterator __last, _OutputIterator __result)

1387 {

1388

1389 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

1390 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

1392 __glibcxx_requires_valid_range(__first, __middle);

1393 __glibcxx_requires_valid_range(__middle, __last);

1394

1395 return std::copy(__first, __middle,

1396 std::copy(__middle, __last, __result));

1397 }

1398

1399

1400 template<typename _ForwardIterator, typename _Predicate>

1401 _GLIBCXX20_CONSTEXPR

1402 _ForwardIterator

1403 __partition(_ForwardIterator __first, _ForwardIterator __last,

1405 {

1406 if (__first == __last)

1407 return __first;

1408

1409 while (__pred(*__first))

1410 if (++__first == __last)

1411 return __first;

1412

1413 _ForwardIterator __next = __first;

1414

1415 while (++__next != __last)

1416 if (__pred(*__next))

1417 {

1418 std::iter_swap(__first, __next);

1419 ++__first;

1420 }

1421

1422 return __first;

1423 }

1424

1425

1426 template<typename _BidirectionalIterator, typename _Predicate>

1427 _GLIBCXX20_CONSTEXPR

1428 _BidirectionalIterator

1429 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,

1431 {

1432 while (true)

1433 {

1434 while (true)

1435 if (__first == __last)

1436 return __first;

1437 else if (__pred(*__first))

1438 ++__first;

1439 else

1440 break;

1441 --__last;

1442 while (true)

1443 if (__first == __last)

1444 return __first;

1445 else if (!bool(__pred(*__last)))

1446 --__last;

1447 else

1448 break;

1449 std::iter_swap(__first, __last);

1450 ++__first;

1451 }

1452 }

1453

1454#if _GLIBCXX_HOSTED

1455

1456

1457

1458

1459

1460

1461

1462

1463 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,

1464 typename _Distance>

1465 _ForwardIterator

1467 _ForwardIterator __last,

1468 _Predicate __pred, _Distance __len,

1469 _Pointer __buffer,

1470 _Distance __buffer_size)

1471 {

1472 if (__len == 1)

1473 return __first;

1474

1475 if (__len <= __buffer_size)

1476 {

1477 _ForwardIterator __result1 = __first;

1478 _Pointer __result2 = __buffer;

1479

1480

1481

1482

1483 *__result2 = _GLIBCXX_MOVE(*__first);

1484 ++__result2;

1485 ++__first;

1486 for (; __first != __last; ++__first)

1487 if (__pred(__first))

1488 {

1489 *__result1 = _GLIBCXX_MOVE(*__first);

1490 ++__result1;

1491 }

1492 else

1493 {

1494 *__result2 = _GLIBCXX_MOVE(*__first);

1495 ++__result2;

1496 }

1497

1498 _GLIBCXX_MOVE3(__buffer, __result2, __result1);

1499 return __result1;

1500 }

1501

1502 _ForwardIterator __middle = __first;

1504 _ForwardIterator __left_split =

1506 __len / 2, __buffer,

1507 __buffer_size);

1508

1509

1510

1511 _Distance __right_len = __len - __len / 2;

1512 _ForwardIterator __right_split =

1514

1515 if (__right_len)

1516 __right_split =

1518 __right_len,

1519 __buffer, __buffer_size);

1520

1521 return std::rotate(__left_split, __middle, __right_split);

1522 }

1523

1524 template<typename _ForwardIterator, typename _Predicate>

1525 _ForwardIterator

1526 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,

1527 _Predicate __pred)

1528 {

1530

1531 if (__first == __last)

1532 return __first;

1533

1534 typedef typename iterator_traits<_ForwardIterator>::value_type

1535 _ValueType;

1536 typedef typename iterator_traits<_ForwardIterator>::difference_type

1537 _DistanceType;

1538

1539 _Temporary_buffer<_ForwardIterator, _ValueType>

1541 return

1543 _DistanceType(__buf.requested_size()),

1544 __buf.begin(),

1545 _DistanceType(__buf.size()));

1546 }

1547

1548

1549

1550

1551

1552

1553

1554

1555

1556

1557

1558

1559

1560

1561

1562

1563

1564

1565 template<typename _ForwardIterator, typename _Predicate>

1566 inline _ForwardIterator

1567 stable_partition(_ForwardIterator __first, _ForwardIterator __last,

1568 _Predicate __pred)

1569 {

1570

1571 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

1572 _ForwardIterator>)

1573 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

1575 __glibcxx_requires_valid_range(__first, __last);

1576

1577 return std::__stable_partition(__first, __last,

1578 __gnu_cxx::__ops::__pred_iter(__pred));

1579 }

1580#endif

1581

1582

1583

1584

1585 template<typename _RandomAccessIterator, typename _Compare>

1586 _GLIBCXX20_CONSTEXPR

1587 void

1588 __heap_select(_RandomAccessIterator __first,

1589 _RandomAccessIterator __middle,

1590 _RandomAccessIterator __last, _Compare __comp)

1591 {

1592 std::__make_heap(__first, __middle, __comp);

1593 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)

1594 if (__comp(__i, __first))

1595 std::__pop_heap(__first, __middle, __i, __comp);

1596 }

1597

1598

1599

1600 template<typename _InputIterator, typename _RandomAccessIterator,

1601 typename _Compare>

1602 _GLIBCXX20_CONSTEXPR

1603 _RandomAccessIterator

1604 __partial_sort_copy(_InputIterator __first, _InputIterator __last,

1605 _RandomAccessIterator __result_first,

1606 _RandomAccessIterator __result_last,

1607 _Compare __comp)

1608 {

1609 typedef typename iterator_traits<_InputIterator>::value_type

1610 _InputValueType;

1611 typedef iterator_traits<_RandomAccessIterator> _RItTraits;

1612 typedef typename _RItTraits::difference_type _DistanceType;

1613

1614 if (__result_first == __result_last)

1615 return __result_last;

1616 _RandomAccessIterator __result_real_last = __result_first;

1617 while (__first != __last && __result_real_last != __result_last)

1618 {

1619 *__result_real_last = *__first;

1620 ++__result_real_last;

1621 ++__first;

1622 }

1623

1624 std::__make_heap(__result_first, __result_real_last, __comp);

1625 while (__first != __last)

1626 {

1627 if (__comp(__first, __result_first))

1628 std::__adjust_heap(__result_first, _DistanceType(0),

1629 _DistanceType(__result_real_last

1630 - __result_first),

1631 _InputValueType(*__first), __comp);

1632 ++__first;

1633 }

1634 std::__sort_heap(__result_first, __result_real_last, __comp);

1635 return __result_real_last;

1636 }

1637

1638

1639

1640

1641

1642

1643

1644

1645

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

1656

1657

1658 template<typename _InputIterator, typename _RandomAccessIterator>

1659 _GLIBCXX20_CONSTEXPR

1660 inline _RandomAccessIterator

1661 partial_sort_copy(_InputIterator __first, _InputIterator __last,

1662 _RandomAccessIterator __result_first,

1663 _RandomAccessIterator __result_last)

1664 {

1665#ifdef _GLIBCXX_CONCEPT_CHECKS

1667 _InputValueType;

1669 _OutputValueType;

1670#endif

1671

1672

1673 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

1674 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,

1675 _OutputValueType>)

1676 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,

1677 _OutputValueType>)

1678 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)

1679 __glibcxx_requires_valid_range(__first, __last);

1680 __glibcxx_requires_irreflexive(__first, __last);

1681 __glibcxx_requires_valid_range(__result_first, __result_last);

1682

1683 return std::__partial_sort_copy(__first, __last,

1684 __result_first, __result_last,

1685 __gnu_cxx::__ops::__iter_less_iter());

1686 }

1687

1688

1689

1690

1691

1692

1693

1694

1695

1696

1697

1698

1699

1700

1701

1702

1703

1704

1705

1706

1707

1708 template<typename _InputIterator, typename _RandomAccessIterator,

1709 typename _Compare>

1710 _GLIBCXX20_CONSTEXPR

1711 inline _RandomAccessIterator

1712 partial_sort_copy(_InputIterator __first, _InputIterator __last,

1713 _RandomAccessIterator __result_first,

1714 _RandomAccessIterator __result_last,

1715 _Compare __comp)

1716 {

1717#ifdef _GLIBCXX_CONCEPT_CHECKS

1719 _InputValueType;

1721 _OutputValueType;

1722#endif

1723

1724

1725 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

1726 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

1727 _RandomAccessIterator>)

1728 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,

1729 _OutputValueType>)

1730 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

1731 _InputValueType, _OutputValueType>)

1732 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

1733 _OutputValueType, _OutputValueType>)

1734 __glibcxx_requires_valid_range(__first, __last);

1735 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

1736 __glibcxx_requires_valid_range(__result_first, __result_last);

1737

1738 return std::__partial_sort_copy(__first, __last,

1739 __result_first, __result_last,

1740 __gnu_cxx::__ops::__iter_comp_iter(__comp));

1741 }

1742

1743

1744

1745

1746 template<typename _RandomAccessIterator, typename _Compare>

1747 _GLIBCXX20_CONSTEXPR

1748 void

1749 __unguarded_linear_insert(_RandomAccessIterator __last,

1750 _Compare __comp)

1751 {

1752 typename iterator_traits<_RandomAccessIterator>::value_type

1753 __val = _GLIBCXX_MOVE(*__last);

1754 _RandomAccessIterator __next = __last;

1755 --__next;

1756 while (__comp(__val, __next))

1757 {

1758 *__last = _GLIBCXX_MOVE(*__next);

1759 __last = __next;

1760 --__next;

1761 }

1762 *__last = _GLIBCXX_MOVE(__val);

1763 }

1764

1765

1766 template<typename _RandomAccessIterator, typename _Compare>

1767 _GLIBCXX20_CONSTEXPR

1768 void

1769 __insertion_sort(_RandomAccessIterator __first,

1770 _RandomAccessIterator __last, _Compare __comp)

1771 {

1772 if (__first == __last) return;

1773

1774 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)

1775 {

1776 if (__comp(__i, __first))

1777 {

1778 typename iterator_traits<_RandomAccessIterator>::value_type

1779 __val = _GLIBCXX_MOVE(*__i);

1780 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);

1781 *__first = _GLIBCXX_MOVE(__val);

1782 }

1783 else

1784 std::__unguarded_linear_insert(__i,

1785 __gnu_cxx::__ops::__val_comp_iter(__comp));

1786 }

1787 }

1788

1789

1790 template<typename _RandomAccessIterator, typename _Compare>

1791 _GLIBCXX20_CONSTEXPR

1792 inline void

1793 __unguarded_insertion_sort(_RandomAccessIterator __first,

1794 _RandomAccessIterator __last, _Compare __comp)

1795 {

1796 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)

1797 std::__unguarded_linear_insert(__i,

1798 __gnu_cxx::__ops::__val_comp_iter(__comp));

1799 }

1800

1801

1802

1803

1804

1805 enum { _S_threshold = 16 };

1806

1807

1808 template<typename _RandomAccessIterator, typename _Compare>

1809 _GLIBCXX20_CONSTEXPR

1810 void

1811 __final_insertion_sort(_RandomAccessIterator __first,

1812 _RandomAccessIterator __last, _Compare __comp)

1813 {

1814 if (__last - __first > int(_S_threshold))

1815 {

1816 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);

1817 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,

1818 __comp);

1819 }

1820 else

1821 std::__insertion_sort(__first, __last, __comp);

1822 }

1823

1824

1825 template<typename _RandomAccessIterator, typename _Compare>

1826 _GLIBCXX20_CONSTEXPR

1827 _RandomAccessIterator

1828 __unguarded_partition(_RandomAccessIterator __first,

1829 _RandomAccessIterator __last,

1830 _RandomAccessIterator __pivot, _Compare __comp)

1831 {

1832 while (true)

1833 {

1834 while (__comp(__first, __pivot))

1835 ++__first;

1836 --__last;

1837 while (__comp(__pivot, __last))

1838 --__last;

1839 if (!(__first < __last))

1840 return __first;

1841 std::iter_swap(__first, __last);

1842 ++__first;

1843 }

1844 }

1845

1846

1847 template<typename _RandomAccessIterator, typename _Compare>

1848 _GLIBCXX20_CONSTEXPR

1849 inline _RandomAccessIterator

1850 __unguarded_partition_pivot(_RandomAccessIterator __first,

1851 _RandomAccessIterator __last, _Compare __comp)

1852 {

1853 _RandomAccessIterator __mid = __first + (__last - __first) / 2;

1855 __comp);

1856 return std::__unguarded_partition(__first + 1, __last, __first, __comp);

1857 }

1858

1859 template<typename _RandomAccessIterator, typename _Compare>

1860 _GLIBCXX20_CONSTEXPR

1861 inline void

1862 __partial_sort(_RandomAccessIterator __first,

1863 _RandomAccessIterator __middle,

1864 _RandomAccessIterator __last,

1865 _Compare __comp)

1866 {

1867 std::__heap_select(__first, __middle, __last, __comp);

1868 std::__sort_heap(__first, __middle, __comp);

1869 }

1870

1871

1872 template<typename _RandomAccessIterator, typename _Size, typename _Compare>

1873 _GLIBCXX20_CONSTEXPR

1874 void

1875 __introsort_loop(_RandomAccessIterator __first,

1876 _RandomAccessIterator __last,

1877 _Size __depth_limit, _Compare __comp)

1878 {

1879 while (__last - __first > int(_S_threshold))

1880 {

1881 if (__depth_limit == 0)

1882 {

1883 std::__partial_sort(__first, __last, __last, __comp);

1884 return;

1885 }

1886 --__depth_limit;

1887 _RandomAccessIterator __cut =

1888 std::__unguarded_partition_pivot(__first, __last, __comp);

1889 std::__introsort_loop(__cut, __last, __depth_limit, __comp);

1890 __last = __cut;

1891 }

1892 }

1893

1894

1895

1896 template<typename _RandomAccessIterator, typename _Compare>

1897 _GLIBCXX20_CONSTEXPR

1898 inline void

1899 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,

1900 _Compare __comp)

1901 {

1902 if (__first != __last)

1903 {

1904 std::__introsort_loop(__first, __last,

1905 std::__lg(__last - __first) * 2,

1906 __comp);

1907 std::__final_insertion_sort(__first, __last, __comp);

1908 }

1909 }

1910

1911 template<typename _RandomAccessIterator, typename _Size, typename _Compare>

1912 _GLIBCXX20_CONSTEXPR

1913 void

1914 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,

1915 _RandomAccessIterator __last, _Size __depth_limit,

1916 _Compare __comp)

1917 {

1918 while (__last - __first > 3)

1919 {

1920 if (__depth_limit == 0)

1921 {

1922 std::__heap_select(__first, __nth + 1, __last, __comp);

1923

1924 std::iter_swap(__first, __nth);

1925 return;

1926 }

1927 --__depth_limit;

1928 _RandomAccessIterator __cut =

1929 std::__unguarded_partition_pivot(__first, __last, __comp);

1930 if (__cut <= __nth)

1931 __first = __cut;

1932 else

1933 __last = __cut;

1934 }

1935 std::__insertion_sort(__first, __last, __comp);

1936 }

1937

1938

1939

1940

1941

1942

1943

1944

1945

1946

1947

1948

1949

1950

1951

1952

1953

1954

1955

1956

1957

1958

1959 template<typename _ForwardIterator, typename _Tp, typename _Compare>

1960 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

1961 inline _ForwardIterator

1962 lower_bound(_ForwardIterator __first, _ForwardIterator __last,

1963 const _Tp& __val, _Compare __comp)

1964 {

1965

1966 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

1967 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

1969 __glibcxx_requires_partitioned_lower_pred(__first, __last,

1970 __val, __comp);

1971

1972 return std::__lower_bound(__first, __last, __val,

1973 __gnu_cxx::__ops::__iter_comp_val(__comp));

1974 }

1975

1976 template<typename _ForwardIterator, typename _Tp, typename _Compare>

1977 _GLIBCXX20_CONSTEXPR

1978 _ForwardIterator

1979 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,

1980 const _Tp& __val, _Compare __comp)

1981 {

1982 typedef typename iterator_traits<_ForwardIterator>::difference_type

1983 _DistanceType;

1984

1985 _DistanceType __len = std::distance(__first, __last);

1986

1987 while (__len > 0)

1988 {

1989 _DistanceType __half = __len >> 1;

1990 _ForwardIterator __middle = __first;

1992 if (__comp(__val, __middle))

1993 __len = __half;

1994 else

1995 {

1996 __first = __middle;

1997 ++__first;

1998 __len = __len - __half - 1;

1999 }

2000 }

2001 return __first;

2002 }

2003

2004

2005

2006

2007

2008

2009

2010

2011

2012

2013

2014

2015 template<typename _ForwardIterator, typename _Tp>

2016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2017 inline _ForwardIterator

2018 upper_bound(_ForwardIterator __first, _ForwardIterator __last,

2019 const _Tp& __val)

2020 {

2021

2022 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2023 __glibcxx_function_requires(_LessThanOpConcept<

2025 __glibcxx_requires_partitioned_upper(__first, __last, __val);

2026

2027 return std::__upper_bound(__first, __last, __val,

2028 __gnu_cxx::__ops::__val_less_iter());

2029 }

2030

2031

2032

2033

2034

2035

2036

2037

2038

2039

2040

2041

2042

2043

2044

2045

2046 template<typename _ForwardIterator, typename _Tp, typename _Compare>

2047 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2048 inline _ForwardIterator

2049 upper_bound(_ForwardIterator __first, _ForwardIterator __last,

2050 const _Tp& __val, _Compare __comp)

2051 {

2052

2053 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2054 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2056 __glibcxx_requires_partitioned_upper_pred(__first, __last,

2057 __val, __comp);

2058

2059 return std::__upper_bound(__first, __last, __val,

2060 __gnu_cxx::__ops::__val_comp_iter(__comp));

2061 }

2062

2063 template<typename _ForwardIterator, typename _Tp,

2064 typename _CompareItTp, typename _CompareTpIt>

2065 _GLIBCXX20_CONSTEXPR

2066 pair<_ForwardIterator, _ForwardIterator>

2067 __equal_range(_ForwardIterator __first, _ForwardIterator __last,

2068 const _Tp& __val,

2069 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)

2070 {

2071 typedef typename iterator_traits<_ForwardIterator>::difference_type

2072 _DistanceType;

2073

2074 _DistanceType __len = std::distance(__first, __last);

2075

2076 while (__len > 0)

2077 {

2078 _DistanceType __half = __len >> 1;

2079 _ForwardIterator __middle = __first;

2081 if (__comp_it_val(__middle, __val))

2082 {

2083 __first = __middle;

2084 ++__first;

2085 __len = __len - __half - 1;

2086 }

2087 else if (__comp_val_it(__val, __middle))

2088 __len = __half;

2089 else

2090 {

2091 _ForwardIterator __left

2092 = std::__lower_bound(__first, __middle, __val, __comp_it_val);

2094 _ForwardIterator __right

2095 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);

2096 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);

2097 }

2098 }

2099 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);

2100 }

2101

2102

2103

2104

2105

2106

2107

2108

2109

2110

2111

2112

2113

2114

2115

2116

2117

2118

2119 template<typename _ForwardIterator, typename _Tp>

2120 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2121 inline pair<_ForwardIterator, _ForwardIterator>

2122 equal_range(_ForwardIterator __first, _ForwardIterator __last,

2123 const _Tp& __val)

2124 {

2125

2126 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2127 __glibcxx_function_requires(_LessThanOpConcept<

2129 __glibcxx_function_requires(_LessThanOpConcept<

2131 __glibcxx_requires_partitioned_lower(__first, __last, __val);

2132 __glibcxx_requires_partitioned_upper(__first, __last, __val);

2133

2134 return std::__equal_range(__first, __last, __val,

2135 __gnu_cxx::__ops::__iter_less_val(),

2136 __gnu_cxx::__ops::__val_less_iter());

2137 }

2138

2139

2140

2141

2142

2143

2144

2145

2146

2147

2148

2149

2150

2151

2152

2153

2154

2155

2156 template<typename _ForwardIterator, typename _Tp, typename _Compare>

2157 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2158 inline pair<_ForwardIterator, _ForwardIterator>

2159 equal_range(_ForwardIterator __first, _ForwardIterator __last,

2160 const _Tp& __val, _Compare __comp)

2161 {

2162

2163 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2164 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2166 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2168 __glibcxx_requires_partitioned_lower_pred(__first, __last,

2169 __val, __comp);

2170 __glibcxx_requires_partitioned_upper_pred(__first, __last,

2171 __val, __comp);

2172

2173 return std::__equal_range(__first, __last, __val,

2174 __gnu_cxx::__ops::__iter_comp_val(__comp),

2175 __gnu_cxx::__ops::__val_comp_iter(__comp));

2176 }

2177

2178

2179

2180

2181

2182

2183

2184

2185

2186

2187

2188

2189

2190 template<typename _ForwardIterator, typename _Tp>

2191 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2192 bool

2193 binary_search(_ForwardIterator __first, _ForwardIterator __last,

2194 const _Tp& __val)

2195 {

2196

2197 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2198 __glibcxx_function_requires(_LessThanOpConcept<

2200 __glibcxx_requires_partitioned_lower(__first, __last, __val);

2201 __glibcxx_requires_partitioned_upper(__first, __last, __val);

2202

2203 _ForwardIterator __i

2204 = std::__lower_bound(__first, __last, __val,

2205 __gnu_cxx::__ops::__iter_less_val());

2206 return __i != __last && !(__val < *__i);

2207 }

2208

2209

2210

2211

2212

2213

2214

2215

2216

2217

2218

2219

2220

2221

2222

2223

2224 template<typename _ForwardIterator, typename _Tp, typename _Compare>

2225 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2226 bool

2227 binary_search(_ForwardIterator __first, _ForwardIterator __last,

2228 const _Tp& __val, _Compare __comp)

2229 {

2230

2231 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

2232 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2234 __glibcxx_requires_partitioned_lower_pred(__first, __last,

2235 __val, __comp);

2236 __glibcxx_requires_partitioned_upper_pred(__first, __last,

2237 __val, __comp);

2238

2239 _ForwardIterator __i

2240 = std::__lower_bound(__first, __last, __val,

2241 __gnu_cxx::__ops::__iter_comp_val(__comp));

2242 return __i != __last && !bool(__comp(__val, *__i));

2243 }

2244

2245

2246

2247

2248 template<typename _InputIterator1, typename _InputIterator2,

2249 typename _OutputIterator, typename _Compare>

2250 void

2252 _InputIterator2 __first2, _InputIterator2 __last2,

2253 _OutputIterator __result, _Compare __comp)

2254 {

2255 while (__first1 != __last1 && __first2 != __last2)

2256 {

2257 if (__comp(__first2, __first1))

2258 {

2259 *__result = _GLIBCXX_MOVE(*__first2);

2260 ++__first2;

2261 }

2262 else

2263 {

2264 *__result = _GLIBCXX_MOVE(*__first1);

2265 ++__first1;

2266 }

2267 ++__result;

2268 }

2269 if (__first1 != __last1)

2270 _GLIBCXX_MOVE3(__first1, __last1, __result);

2271 }

2272

2273

2274 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,

2275 typename _BidirectionalIterator3, typename _Compare>

2276 void

2278 _BidirectionalIterator1 __last1,

2279 _BidirectionalIterator2 __first2,

2280 _BidirectionalIterator2 __last2,

2281 _BidirectionalIterator3 __result,

2282 _Compare __comp)

2283 {

2284 if (__first1 == __last1)

2285 {

2286 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);

2287 return;

2288 }

2289 else if (__first2 == __last2)

2290 return;

2291

2292 --__last1;

2293 --__last2;

2294 while (true)

2295 {

2296 if (__comp(__last2, __last1))

2297 {

2298 *--__result = _GLIBCXX_MOVE(*__last1);

2299 if (__first1 == __last1)

2300 {

2301 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);

2302 return;

2303 }

2304 --__last1;

2305 }

2306 else

2307 {

2308 *--__result = _GLIBCXX_MOVE(*__last2);

2309 if (__first2 == __last2)

2310 return;

2311 --__last2;

2312 }

2313 }

2314 }

2315

2316

2317 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,

2318 typename _Distance>

2319 _BidirectionalIterator1

2321 _BidirectionalIterator1 __middle,

2322 _BidirectionalIterator1 __last,

2323 _Distance __len1, _Distance __len2,

2324 _BidirectionalIterator2 __buffer,

2325 _Distance __buffer_size)

2326 {

2327 _BidirectionalIterator2 __buffer_end;

2328 if (__len1 > __len2 && __len2 <= __buffer_size)

2329 {

2330 if (__len2)

2331 {

2332 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);

2333 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);

2334 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);

2335 }

2336 else

2337 return __first;

2338 }

2339 else if (__len1 <= __buffer_size)

2340 {

2341 if (__len1)

2342 {

2343 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);

2344 _GLIBCXX_MOVE3(__middle, __last, __first);

2345 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);

2346 }

2347 else

2348 return __last;

2349 }

2350 else

2351 return std::rotate(__first, __middle, __last);

2352 }

2353

2354

2355 template<typename _BidirectionalIterator, typename _Distance,

2356 typename _Pointer, typename _Compare>

2357 void

2359 _BidirectionalIterator __middle,

2360 _BidirectionalIterator __last,

2361 _Distance __len1, _Distance __len2,

2362 _Pointer __buffer, _Compare __comp)

2363 {

2364 if (__len1 <= __len2)

2365 {

2366 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);

2368 __first, __comp);

2369 }

2370 else

2371 {

2372 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);

2374 __buffer_end, __last, __comp);

2375 }

2376 }

2377

2378 template<typename _BidirectionalIterator, typename _Distance,

2379 typename _Pointer, typename _Compare>

2380 void

2381 __merge_adaptive_resize(_BidirectionalIterator __first,

2382 _BidirectionalIterator __middle,

2383 _BidirectionalIterator __last,

2384 _Distance __len1, _Distance __len2,

2385 _Pointer __buffer, _Distance __buffer_size,

2386 _Compare __comp)

2387 {

2388 if (__len1 <= __buffer_size || __len2 <= __buffer_size)

2390 __len1, __len2, __buffer, __comp);

2391 else

2392 {

2393 _BidirectionalIterator __first_cut = __first;

2394 _BidirectionalIterator __second_cut = __middle;

2395 _Distance __len11 = 0;

2396 _Distance __len22 = 0;

2397 if (__len1 > __len2)

2398 {

2399 __len11 = __len1 / 2;

2401 __second_cut

2402 = std::__lower_bound(__middle, __last, *__first_cut,

2403 __gnu_cxx::__ops::__iter_comp_val(__comp));

2404 __len22 = std::distance(__middle, __second_cut);

2405 }

2406 else

2407 {

2408 __len22 = __len2 / 2;

2410 __first_cut

2411 = std::__upper_bound(__first, __middle, *__second_cut,

2412 __gnu_cxx::__ops::__val_comp_iter(__comp));

2414 }

2415

2416 _BidirectionalIterator __new_middle

2418 _Distance(__len1 - __len11), __len22,

2419 __buffer, __buffer_size);

2420 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,

2421 __len11, __len22,

2422 __buffer, __buffer_size, __comp);

2423 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,

2424 _Distance(__len1 - __len11),

2425 _Distance(__len2 - __len22),

2426 __buffer, __buffer_size, __comp);

2427 }

2428 }

2429

2430

2431 template<typename _BidirectionalIterator, typename _Distance,

2432 typename _Compare>

2433 void

2435 _BidirectionalIterator __middle,

2436 _BidirectionalIterator __last,

2437 _Distance __len1, _Distance __len2,

2438 _Compare __comp)

2439 {

2440 if (__len1 == 0 || __len2 == 0)

2441 return;

2442

2443 if (__len1 + __len2 == 2)

2444 {

2445 if (__comp(__middle, __first))

2446 std::iter_swap(__first, __middle);

2447 return;

2448 }

2449

2450 _BidirectionalIterator __first_cut = __first;

2451 _BidirectionalIterator __second_cut = __middle;

2452 _Distance __len11 = 0;

2453 _Distance __len22 = 0;

2454 if (__len1 > __len2)

2455 {

2456 __len11 = __len1 / 2;

2458 __second_cut

2459 = std::__lower_bound(__middle, __last, *__first_cut,

2460 __gnu_cxx::__ops::__iter_comp_val(__comp));

2461 __len22 = std::distance(__middle, __second_cut);

2462 }

2463 else

2464 {

2465 __len22 = __len2 / 2;

2467 __first_cut

2468 = std::__upper_bound(__first, __middle, *__second_cut,

2469 __gnu_cxx::__ops::__val_comp_iter(__comp));

2471 }

2472

2473 _BidirectionalIterator __new_middle

2474 = std::rotate(__first_cut, __middle, __second_cut);

2476 __len11, __len22, __comp);

2478 __len1 - __len11, __len2 - __len22, __comp);

2479 }

2480

2481 template<typename _BidirectionalIterator, typename _Compare>

2482 void

2483 __inplace_merge(_BidirectionalIterator __first,

2484 _BidirectionalIterator __middle,

2485 _BidirectionalIterator __last,

2486 _Compare __comp)

2487 {

2488 typedef typename iterator_traits<_BidirectionalIterator>::value_type

2489 _ValueType;

2490 typedef typename iterator_traits<_BidirectionalIterator>::difference_type

2491 _DistanceType;

2492

2493 if (__first == __middle || __middle == __last)

2494 return;

2495

2496 const _DistanceType __len1 = std::distance(__first, __middle);

2497 const _DistanceType __len2 = std::distance(__middle, __last);

2498

2499#if _GLIBCXX_HOSTED

2500 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;

2501

2502

2503 _TmpBuf __buf(__first, std::min(__len1, __len2));

2504

2505 if (__builtin_expect(__buf.size() == __buf.requested_size(), true))

2507 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);

2508 else if (__builtin_expect(__buf.begin() == 0, false))

2510 (__first, __middle, __last, __len1, __len2, __comp);

2511 else

2512 std::__merge_adaptive_resize

2513 (__first, __middle, __last, __len1, __len2, __buf.begin(),

2514 _DistanceType(__buf.size()), __comp);

2515#else

2517 (__first, __middle, __last, __len1, __len2, __comp);

2518#endif

2519 }

2520

2521

2522

2523

2524

2525

2526

2527

2528

2529

2530

2531

2532

2533

2534

2535

2536

2537

2538

2539 template<typename _BidirectionalIterator>

2540 inline void

2541 inplace_merge(_BidirectionalIterator __first,

2542 _BidirectionalIterator __middle,

2543 _BidirectionalIterator __last)

2544 {

2545

2546 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<

2547 _BidirectionalIterator>)

2548 __glibcxx_function_requires(_LessThanComparableConcept<

2550 __glibcxx_requires_sorted(__first, __middle);

2551 __glibcxx_requires_sorted(__middle, __last);

2552 __glibcxx_requires_irreflexive(__first, __last);

2553

2554 std::__inplace_merge(__first, __middle, __last,

2555 __gnu_cxx::__ops::__iter_less_iter());

2556 }

2557

2558

2559

2560

2561

2562

2563

2564

2565

2566

2567

2568

2569

2570

2571

2572

2573

2574

2575

2576

2577

2578

2579

2580 template<typename _BidirectionalIterator, typename _Compare>

2581 inline void

2582 inplace_merge(_BidirectionalIterator __first,

2583 _BidirectionalIterator __middle,

2584 _BidirectionalIterator __last,

2585 _Compare __comp)

2586 {

2587

2588 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<

2589 _BidirectionalIterator>)

2590 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2593 __glibcxx_requires_sorted_pred(__first, __middle, __comp);

2594 __glibcxx_requires_sorted_pred(__middle, __last, __comp);

2595 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

2596

2597 std::__inplace_merge(__first, __middle, __last,

2598 __gnu_cxx::__ops::__iter_comp_iter(__comp));

2599 }

2600

2601

2602

2603 template<typename _InputIterator, typename _OutputIterator,

2604 typename _Compare>

2605 _OutputIterator

2606 __move_merge(_InputIterator __first1, _InputIterator __last1,

2607 _InputIterator __first2, _InputIterator __last2,

2608 _OutputIterator __result, _Compare __comp)

2609 {

2610 while (__first1 != __last1 && __first2 != __last2)

2611 {

2612 if (__comp(__first2, __first1))

2613 {

2614 *__result = _GLIBCXX_MOVE(*__first2);

2615 ++__first2;

2616 }

2617 else

2618 {

2619 *__result = _GLIBCXX_MOVE(*__first1);

2620 ++__first1;

2621 }

2622 ++__result;

2623 }

2624 return _GLIBCXX_MOVE3(__first2, __last2,

2625 _GLIBCXX_MOVE3(__first1, __last1,

2626 __result));

2627 }

2628

2629 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,

2630 typename _Distance, typename _Compare>

2631 void

2632 __merge_sort_loop(_RandomAccessIterator1 __first,

2633 _RandomAccessIterator1 __last,

2634 _RandomAccessIterator2 __result, _Distance __step_size,

2635 _Compare __comp)

2636 {

2637 const _Distance __two_step = 2 * __step_size;

2638

2639 while (__last - __first >= __two_step)

2640 {

2642 __first + __step_size,

2643 __first + __two_step,

2644 __result, __comp);

2645 __first += __two_step;

2646 }

2647 __step_size = std::min(_Distance(__last - __first), __step_size);

2648

2650 __first + __step_size, __last, __result, __comp);

2651 }

2652

2653 template<typename _RandomAccessIterator, typename _Distance,

2654 typename _Compare>

2655 _GLIBCXX20_CONSTEXPR

2656 void

2657 __chunk_insertion_sort(_RandomAccessIterator __first,

2658 _RandomAccessIterator __last,

2659 _Distance __chunk_size, _Compare __comp)

2660 {

2661 while (__last - __first >= __chunk_size)

2662 {

2663 std::__insertion_sort(__first, __first + __chunk_size, __comp);

2664 __first += __chunk_size;

2665 }

2666 std::__insertion_sort(__first, __last, __comp);

2667 }

2668

2669 enum { _S_chunk_size = 7 };

2670

2671 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>

2672 void

2673 __merge_sort_with_buffer(_RandomAccessIterator __first,

2674 _RandomAccessIterator __last,

2675 _Pointer __buffer, _Compare __comp)

2676 {

2677 typedef typename iterator_traits<_RandomAccessIterator>::difference_type

2678 _Distance;

2679

2680 const _Distance __len = __last - __first;

2681 const _Pointer __buffer_last = __buffer + __len;

2682

2683 _Distance __step_size = _S_chunk_size;

2684 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);

2685

2686 while (__step_size < __len)

2687 {

2688 std::__merge_sort_loop(__first, __last, __buffer,

2689 __step_size, __comp);

2690 __step_size *= 2;

2691 std::__merge_sort_loop(__buffer, __buffer_last, __first,

2692 __step_size, __comp);

2693 __step_size *= 2;

2694 }

2695 }

2696

2697 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>

2698 void

2699 __stable_sort_adaptive(_RandomAccessIterator __first,

2700 _RandomAccessIterator __middle,

2701 _RandomAccessIterator __last,

2702 _Pointer __buffer, _Compare __comp)

2703 {

2704 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);

2705 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);

2706

2708 __middle - __first, __last - __middle,

2709 __buffer, __comp);

2710 }

2711

2712 template<typename _RandomAccessIterator, typename _Pointer,

2713 typename _Distance, typename _Compare>

2714 void

2715 __stable_sort_adaptive_resize(_RandomAccessIterator __first,

2716 _RandomAccessIterator __last,

2717 _Pointer __buffer, _Distance __buffer_size,

2718 _Compare __comp)

2719 {

2720 const _Distance __len = (__last - __first + 1) / 2;

2721 const _RandomAccessIterator __middle = __first + __len;

2722 if (__len > __buffer_size)

2723 {

2724 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,

2725 __buffer_size, __comp);

2726 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,

2727 __buffer_size, __comp);

2728 std::__merge_adaptive_resize(__first, __middle, __last,

2729 _Distance(__middle - __first),

2730 _Distance(__last - __middle),

2731 __buffer, __buffer_size,

2732 __comp);

2733 }

2734 else

2735 std::__stable_sort_adaptive(__first, __middle, __last,

2736 __buffer, __comp);

2737 }

2738

2739

2740 template<typename _RandomAccessIterator, typename _Compare>

2741 void

2743 _RandomAccessIterator __last, _Compare __comp)

2744 {

2745 if (__last - __first < 15)

2746 {

2747 std::__insertion_sort(__first, __last, __comp);

2748 return;

2749 }

2750 _RandomAccessIterator __middle = __first + (__last - __first) / 2;

2754 __middle - __first,

2755 __last - __middle,

2756 __comp);

2757 }

2758

2759

2760

2761

2762

2763

2764

2765

2766 template<typename _InputIterator1, typename _InputIterator2,

2767 typename _Compare>

2768 _GLIBCXX20_CONSTEXPR

2769 bool

2770 __includes(_InputIterator1 __first1, _InputIterator1 __last1,

2771 _InputIterator2 __first2, _InputIterator2 __last2,

2772 _Compare __comp)

2773 {

2774 while (__first1 != __last1 && __first2 != __last2)

2775 {

2776 if (__comp(__first2, __first1))

2777 return false;

2778 if (!__comp(__first1, __first2))

2779 ++__first2;

2780 ++__first1;

2781 }

2782

2783 return __first2 == __last2;

2784 }

2785

2786

2787

2788

2789

2790

2791

2792

2793

2794

2795

2796

2797

2798

2799

2800

2801

2802

2803

2804 template<typename _InputIterator1, typename _InputIterator2>

2805 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2806 inline bool

2807 includes(_InputIterator1 __first1, _InputIterator1 __last1,

2808 _InputIterator2 __first2, _InputIterator2 __last2)

2809 {

2810

2811 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

2812 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

2813 __glibcxx_function_requires(_LessThanOpConcept<

2816 __glibcxx_function_requires(_LessThanOpConcept<

2819 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

2820 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

2821 __glibcxx_requires_irreflexive2(__first1, __last1);

2822 __glibcxx_requires_irreflexive2(__first2, __last2);

2823

2824 return std::__includes(__first1, __last1, __first2, __last2,

2825 __gnu_cxx::__ops::__iter_less_iter());

2826 }

2827

2828

2829

2830

2831

2832

2833

2834

2835

2836

2837

2838

2839

2840

2841

2842

2843

2844

2845

2846

2847

2848

2849 template<typename _InputIterator1, typename _InputIterator2,

2850 typename _Compare>

2851 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

2852 inline bool

2853 includes(_InputIterator1 __first1, _InputIterator1 __last1,

2854 _InputIterator2 __first2, _InputIterator2 __last2,

2855 _Compare __comp)

2856 {

2857

2858 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

2859 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

2860 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2863 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2866 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

2867 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

2868 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

2869 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

2870

2871 return std::__includes(__first1, __last1, __first2, __last2,

2872 __gnu_cxx::__ops::__iter_comp_iter(__comp));

2873 }

2874

2875

2876

2877

2878

2879

2880

2881

2882

2883

2884

2885 template<typename _BidirectionalIterator, typename _Compare>

2886 _GLIBCXX20_CONSTEXPR

2887 bool

2888 __next_permutation(_BidirectionalIterator __first,

2889 _BidirectionalIterator __last, _Compare __comp)

2890 {

2891 if (__first == __last)

2892 return false;

2893 _BidirectionalIterator __i = __first;

2894 ++__i;

2895 if (__i == __last)

2896 return false;

2897 __i = __last;

2898 --__i;

2899

2900 for(;;)

2901 {

2902 _BidirectionalIterator __ii = __i;

2903 --__i;

2904 if (__comp(__i, __ii))

2905 {

2906 _BidirectionalIterator __j = __last;

2907 while (!__comp(__i, --__j))

2908 {}

2909 std::iter_swap(__i, __j);

2912 return true;

2913 }

2914 if (__i == __first)

2915 {

2918 return false;

2919 }

2920 }

2921 }

2922

2923

2924

2925

2926

2927

2928

2929

2930

2931

2932

2933

2934

2935 template<typename _BidirectionalIterator>

2936 _GLIBCXX20_CONSTEXPR

2937 inline bool

2938 next_permutation(_BidirectionalIterator __first,

2939 _BidirectionalIterator __last)

2940 {

2941

2942 __glibcxx_function_requires(_BidirectionalIteratorConcept<

2943 _BidirectionalIterator>)

2944 __glibcxx_function_requires(_LessThanComparableConcept<

2946 __glibcxx_requires_valid_range(__first, __last);

2947 __glibcxx_requires_irreflexive(__first, __last);

2948

2949 return std::__next_permutation

2950 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());

2951 }

2952

2953

2954

2955

2956

2957

2958

2959

2960

2961

2962

2963

2964

2965

2966

2967

2968 template<typename _BidirectionalIterator, typename _Compare>

2969 _GLIBCXX20_CONSTEXPR

2970 inline bool

2971 next_permutation(_BidirectionalIterator __first,

2972 _BidirectionalIterator __last, _Compare __comp)

2973 {

2974

2975 __glibcxx_function_requires(_BidirectionalIteratorConcept<

2976 _BidirectionalIterator>)

2977 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

2980 __glibcxx_requires_valid_range(__first, __last);

2981 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

2982

2983 return std::__next_permutation

2984 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));

2985 }

2986

2987 template<typename _BidirectionalIterator, typename _Compare>

2988 _GLIBCXX20_CONSTEXPR

2989 bool

2990 __prev_permutation(_BidirectionalIterator __first,

2991 _BidirectionalIterator __last, _Compare __comp)

2992 {

2993 if (__first == __last)

2994 return false;

2995 _BidirectionalIterator __i = __first;

2996 ++__i;

2997 if (__i == __last)

2998 return false;

2999 __i = __last;

3000 --__i;

3001

3002 for(;;)

3003 {

3004 _BidirectionalIterator __ii = __i;

3005 --__i;

3006 if (__comp(__ii, __i))

3007 {

3008 _BidirectionalIterator __j = __last;

3009 while (!__comp(--__j, __i))

3010 {}

3011 std::iter_swap(__i, __j);

3014 return true;

3015 }

3016 if (__i == __first)

3017 {

3020 return false;

3021 }

3022 }

3023 }

3024

3025

3026

3027

3028

3029

3030

3031

3032

3033

3034

3035

3036

3037

3038 template<typename _BidirectionalIterator>

3039 _GLIBCXX20_CONSTEXPR

3040 inline bool

3041 prev_permutation(_BidirectionalIterator __first,

3042 _BidirectionalIterator __last)

3043 {

3044

3045 __glibcxx_function_requires(_BidirectionalIteratorConcept<

3046 _BidirectionalIterator>)

3047 __glibcxx_function_requires(_LessThanComparableConcept<

3049 __glibcxx_requires_valid_range(__first, __last);

3050 __glibcxx_requires_irreflexive(__first, __last);

3051

3052 return std::__prev_permutation(__first, __last,

3053 __gnu_cxx::__ops::__iter_less_iter());

3054 }

3055

3056

3057

3058

3059

3060

3061

3062

3063

3064

3065

3066

3067

3068

3069

3070

3071 template<typename _BidirectionalIterator, typename _Compare>

3072 _GLIBCXX20_CONSTEXPR

3073 inline bool

3074 prev_permutation(_BidirectionalIterator __first,

3075 _BidirectionalIterator __last, _Compare __comp)

3076 {

3077

3078 __glibcxx_function_requires(_BidirectionalIteratorConcept<

3079 _BidirectionalIterator>)

3080 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

3083 __glibcxx_requires_valid_range(__first, __last);

3084 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

3085

3086 return std::__prev_permutation(__first, __last,

3087 __gnu_cxx::__ops::__iter_comp_iter(__comp));

3088 }

3089

3090

3091

3092

3093 template<typename _InputIterator, typename _OutputIterator,

3094 typename _Predicate, typename _Tp>

3095 _GLIBCXX20_CONSTEXPR

3096 _OutputIterator

3097 __replace_copy_if(_InputIterator __first, _InputIterator __last,

3098 _OutputIterator __result,

3099 _Predicate __pred, const _Tp& __new_value)

3100 {

3101 for (; __first != __last; ++__first, (void)++__result)

3102 if (__pred(__first))

3103 *__result = __new_value;

3104 else

3105 *__result = *__first;

3106 return __result;

3107 }

3108

3109

3110

3111

3112

3113

3114

3115

3116

3117

3118

3119

3120

3121

3122

3123 template<typename _InputIterator, typename _OutputIterator, typename _Tp>

3124 _GLIBCXX20_CONSTEXPR

3125 inline _OutputIterator

3126 replace_copy(_InputIterator __first, _InputIterator __last,

3127 _OutputIterator __result,

3128 const _Tp& __old_value, const _Tp& __new_value)

3129 {

3130

3131 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3132 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

3134 __glibcxx_function_requires(_EqualOpConcept<

3136 __glibcxx_requires_valid_range(__first, __last);

3137

3138 return std::__replace_copy_if(__first, __last, __result,

3139 __gnu_cxx::__ops::__iter_equals_val(__old_value),

3140 __new_value);

3141 }

3142

3143

3144

3145

3146

3147

3148

3149

3150

3151

3152

3153

3154

3155

3156

3157

3158 template<typename _InputIterator, typename _OutputIterator,

3159 typename _Predicate, typename _Tp>

3160 _GLIBCXX20_CONSTEXPR

3161 inline _OutputIterator

3162 replace_copy_if(_InputIterator __first, _InputIterator __last,

3163 _OutputIterator __result,

3164 _Predicate __pred, const _Tp& __new_value)

3165 {

3166

3167 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3168 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

3170 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

3172 __glibcxx_requires_valid_range(__first, __last);

3173

3174 return std::__replace_copy_if(__first, __last, __result,

3175 __gnu_cxx::__ops::__pred_iter(__pred),

3176 __new_value);

3177 }

3178

3179#if __cplusplus >= 201103L

3180

3181

3182

3183

3184

3185

3186

3187 template<typename _ForwardIterator>

3188 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3189 inline bool

3190 is_sorted(_ForwardIterator __first, _ForwardIterator __last)

3191 { return std::is_sorted_until(__first, __last) == __last; }

3192

3193

3194

3195

3196

3197

3198

3199

3200

3201

3202 template<typename _ForwardIterator, typename _Compare>

3203 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3204 inline bool

3205 is_sorted(_ForwardIterator __first, _ForwardIterator __last,

3206 _Compare __comp)

3207 { return std::is_sorted_until(__first, __last, __comp) == __last; }

3208

3209 template<typename _ForwardIterator, typename _Compare>

3210 _GLIBCXX20_CONSTEXPR

3211 _ForwardIterator

3212 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,

3213 _Compare __comp)

3214 {

3215 if (__first == __last)

3216 return __last;

3217

3218 _ForwardIterator __next = __first;

3219 for (++__next; __next != __last; __first = __next, (void)++__next)

3220 if (__comp(__next, __first))

3221 return __next;

3222 return __next;

3223 }

3224

3225

3226

3227

3228

3229

3230

3231

3232

3233 template<typename _ForwardIterator>

3234 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3235 inline _ForwardIterator

3236 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)

3237 {

3238

3239 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3240 __glibcxx_function_requires(_LessThanComparableConcept<

3242 __glibcxx_requires_valid_range(__first, __last);

3243 __glibcxx_requires_irreflexive(__first, __last);

3244

3245 return std::__is_sorted_until(__first, __last,

3246 __gnu_cxx::__ops::__iter_less_iter());

3247 }

3248

3249

3250

3251

3252

3253

3254

3255

3256

3257

3258 template<typename _ForwardIterator, typename _Compare>

3259 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3260 inline _ForwardIterator

3261 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,

3262 _Compare __comp)

3263 {

3264

3265 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3266 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

3269 __glibcxx_requires_valid_range(__first, __last);

3270 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

3271

3272 return std::__is_sorted_until(__first, __last,

3273 __gnu_cxx::__ops::__iter_comp_iter(__comp));

3274 }

3275

3276

3277

3278

3279

3280

3281

3282

3283

3284 template<typename _Tp>

3285 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3286 inline pair<const _Tp&, const _Tp&>

3287 minmax(const _Tp& __a, const _Tp& __b)

3288 {

3289

3290 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)

3291

3292 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)

3294 }

3295

3296

3297

3298

3299

3300

3301

3302

3303

3304

3305 template<typename _Tp, typename _Compare>

3306 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3307 inline pair<const _Tp&, const _Tp&>

3308 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)

3309 {

3312 }

3313

3314 template<typename _ForwardIterator, typename _Compare>

3315 _GLIBCXX14_CONSTEXPR

3316 pair<_ForwardIterator, _ForwardIterator>

3317 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,

3318 _Compare __comp)

3319 {

3320 _ForwardIterator __next = __first;

3321 if (__first == __last

3322 || ++__next == __last)

3323 return std::make_pair(__first, __first);

3324

3325 _ForwardIterator __min{}, __max{};

3326 if (__comp(__next, __first))

3327 {

3328 __min = __next;

3329 __max = __first;

3330 }

3331 else

3332 {

3333 __min = __first;

3334 __max = __next;

3335 }

3336

3337 __first = __next;

3338 ++__first;

3339

3340 while (__first != __last)

3341 {

3342 __next = __first;

3343 if (++__next == __last)

3344 {

3345 if (__comp(__first, __min))

3346 __min = __first;

3347 else if (!__comp(__first, __max))

3348 __max = __first;

3349 break;

3350 }

3351

3352 if (__comp(__next, __first))

3353 {

3354 if (__comp(__next, __min))

3355 __min = __next;

3356 if (!__comp(__first, __max))

3357 __max = __first;

3358 }

3359 else

3360 {

3361 if (__comp(__first, __min))

3362 __min = __first;

3363 if (!__comp(__next, __max))

3364 __max = __next;

3365 }

3366

3367 __first = __next;

3368 ++__first;

3369 }

3370

3371 return std::make_pair(__min, __max);

3372 }

3373

3374

3375

3376

3377

3378

3379

3380

3381

3382

3383

3384

3385 template<typename _ForwardIterator>

3386 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3387 inline pair<_ForwardIterator, _ForwardIterator>

3388 minmax_element(_ForwardIterator __first, _ForwardIterator __last)

3389 {

3390

3391 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3392 __glibcxx_function_requires(_LessThanComparableConcept<

3394 __glibcxx_requires_valid_range(__first, __last);

3395 __glibcxx_requires_irreflexive(__first, __last);

3396

3397 return std::__minmax_element(__first, __last,

3398 __gnu_cxx::__ops::__iter_less_iter());

3399 }

3400

3401

3402

3403

3404

3405

3406

3407

3408

3409

3410

3411

3412

3413 template<typename _ForwardIterator, typename _Compare>

3414 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3415 inline pair<_ForwardIterator, _ForwardIterator>

3416 minmax_element(_ForwardIterator __first, _ForwardIterator __last,

3417 _Compare __comp)

3418 {

3419

3420 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3421 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

3424 __glibcxx_requires_valid_range(__first, __last);

3425 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

3426

3427 return std::__minmax_element(__first, __last,

3428 __gnu_cxx::__ops::__iter_comp_iter(__comp));

3429 }

3430

3431 template<typename _Tp>

3432 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3433 inline pair<_Tp, _Tp>

3434 minmax(initializer_list<_Tp> __l)

3435 {

3436 __glibcxx_requires_irreflexive(__l.begin(), __l.end());

3437 pair<const _Tp*, const _Tp*> __p =

3438 std::__minmax_element(__l.begin(), __l.end(),

3439 __gnu_cxx::__ops::__iter_less_iter());

3440 return std::make_pair(*__p.first, *__p.second);

3441 }

3442

3443 template<typename _Tp, typename _Compare>

3444 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

3445 inline pair<_Tp, _Tp>

3446 minmax(initializer_list<_Tp> __l, _Compare __comp)

3447 {

3448 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);

3449 pair<const _Tp*, const _Tp*> __p =

3450 std::__minmax_element(__l.begin(), __l.end(),

3451 __gnu_cxx::__ops::__iter_comp_iter(__comp));

3452 return std::make_pair(*__p.first, *__p.second);

3453 }

3454

3455

3456

3457

3458

3459

3460

3461

3462

3463

3464

3465

3466

3467

3468

3469 template<typename _ForwardIterator1, typename _ForwardIterator2,

3470 typename _BinaryPredicate>

3471 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3472 inline bool

3473 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

3474 _ForwardIterator2 __first2, _BinaryPredicate __pred)

3475 {

3476

3477 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)

3478 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)

3479 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

3482 __glibcxx_requires_valid_range(__first1, __last1);

3483

3484 return std::__is_permutation(__first1, __last1, __first2,

3485 __gnu_cxx::__ops::__iter_comp_iter(__pred));

3486 }

3487

3488#if __cplusplus > 201103L

3489 template<typename _ForwardIterator1, typename _ForwardIterator2,

3490 typename _BinaryPredicate>

3491 _GLIBCXX20_CONSTEXPR

3492 bool

3493 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

3494 _ForwardIterator2 __first2, _ForwardIterator2 __last2,

3495 _BinaryPredicate __pred)

3496 {

3497 using _Cat1

3498 = typename iterator_traits<_ForwardIterator1>::iterator_category;

3499 using _Cat2

3500 = typename iterator_traits<_ForwardIterator2>::iterator_category;

3501 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;

3502 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;

3503 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();

3504 if (__ra_iters)

3505 {

3508 if (__d1 != __d2)

3509 return false;

3510 }

3511

3512

3513

3514 for (; __first1 != __last1 && __first2 != __last2;

3515 ++__first1, (void)++__first2)

3516 if (!__pred(__first1, __first2))

3517 break;

3518

3519 if (__ra_iters)

3520 {

3521 if (__first1 == __last1)

3522 return true;

3523 }

3524 else

3525 {

3528 if (__d1 == 0 && __d2 == 0)

3529 return true;

3530 if (__d1 != __d2)

3531 return false;

3532 }

3533

3534 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)

3535 {

3536 if (__scan != std::__find_if(__first1, __scan,

3537 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))

3538 continue;

3539

3540 auto __matches = std::__count_if(__first2, __last2,

3541 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));

3542 if (0 == __matches

3543 || std::__count_if(__scan, __last1,

3544 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))

3545 != __matches)

3546 return false;

3547 }

3548 return true;

3549 }

3550

3551

3552

3553

3554

3555

3556

3557

3558

3559

3560

3561

3562

3563

3564 template<typename _ForwardIterator1, typename _ForwardIterator2>

3565 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3566 inline bool

3567 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

3568 _ForwardIterator2 __first2, _ForwardIterator2 __last2)

3569 {

3570 __glibcxx_requires_valid_range(__first1, __last1);

3571 __glibcxx_requires_valid_range(__first2, __last2);

3572

3573 return

3574 std::__is_permutation(__first1, __last1, __first2, __last2,

3575 __gnu_cxx::__ops::__iter_equal_to_iter());

3576 }

3577

3578

3579

3580

3581

3582

3583

3584

3585

3586

3587

3588

3589

3590

3591

3592 template<typename _ForwardIterator1, typename _ForwardIterator2,

3593 typename _BinaryPredicate>

3594 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3595 inline bool

3596 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

3597 _ForwardIterator2 __first2, _ForwardIterator2 __last2,

3598 _BinaryPredicate __pred)

3599 {

3600 __glibcxx_requires_valid_range(__first1, __last1);

3601 __glibcxx_requires_valid_range(__first2, __last2);

3602

3603 return std::__is_permutation(__first1, __last1, __first2, __last2,

3604 __gnu_cxx::__ops::__iter_comp_iter(__pred));

3605 }

3606#endif

3607

3608#ifdef __glibcxx_clamp

3609

3610

3611

3612

3613

3614

3615

3616

3617

3618

3619

3620 template<typename _Tp>

3621 [[nodiscard]] constexpr const _Tp&

3622 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)

3623 {

3624 __glibcxx_assert(!(__hi < __lo));

3626 }

3627

3628

3629

3630

3631

3632

3633

3634

3635

3636

3637

3638

3639

3640 template<typename _Tp, typename _Compare>

3641 [[nodiscard]] constexpr const _Tp&

3642 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)

3643 {

3644 __glibcxx_assert(!__comp(__hi, __lo));

3645 return std::min(std::max(__val, __lo, __comp), __hi, __comp);

3646 }

3647#endif

3648

3649

3650

3651

3652

3653

3654

3655

3656

3657

3658

3659

3660

3661

3662

3663

3664

3665

3666

3667

3668

3669

3670 template<typename _IntType, typename _UniformRandomBitGenerator>

3671 pair<_IntType, _IntType>

3673 _UniformRandomBitGenerator&& __g)

3674 {

3675 _IntType __x

3677 return std::make_pair(__x / __b1, __x % __b1);

3678 }

3679

3680

3681

3682

3683

3684

3685

3686

3687

3688

3689

3690

3691

3692 template<typename _RandomAccessIterator,

3693 typename _UniformRandomNumberGenerator>

3694 void

3695 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,

3696 _UniformRandomNumberGenerator&& __g)

3697 {

3698

3699 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

3700 _RandomAccessIterator>)

3701 __glibcxx_requires_valid_range(__first, __last);

3702

3703 if (__first == __last)

3704 return;

3705

3707 _DistanceType;

3708

3709 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;

3711 typedef typename __distr_type::param_type __p_type;

3712

3713 typedef typename remove_reference<_UniformRandomNumberGenerator>::type

3714 _Gen;

3716 __uc_type;

3717

3718 const __uc_type __urngrange = __g.max() - __g.min();

3719 const __uc_type __urange = __uc_type(__last - __first);

3720

3721 if (__urngrange / __urange >= __urange)

3722

3723 {

3724 _RandomAccessIterator __i = __first + 1;

3725

3726

3727

3728

3729

3730 if ((__urange % 2) == 0)

3731 {

3732 __distr_type __d{0, 1};

3733 std::iter_swap(__i++, __first + __d(__g));

3734 }

3735

3736

3737

3738

3739

3740 while (__i != __last)

3741 {

3742 const __uc_type __swap_range = __uc_type(__i - __first) + 1;

3743

3746

3747 std::iter_swap(__i++, __first + __pospos.first);

3748 std::iter_swap(__i++, __first + __pospos.second);

3749 }

3750

3751 return;

3752 }

3753

3754 __distr_type __d;

3755

3756 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)

3757 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));

3758 }

3759#endif

3760

3761_GLIBCXX_BEGIN_NAMESPACE_ALGO

3762

3763

3764

3765

3766

3767

3768

3769

3770

3771

3772

3773

3774

3775 template<typename _InputIterator, typename _Function>

3776 _GLIBCXX20_CONSTEXPR

3777 _Function

3778 for_each(_InputIterator __first, _InputIterator __last, _Function __f)

3779 {

3780

3781 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3782 __glibcxx_requires_valid_range(__first, __last);

3783 for (; __first != __last; ++__first)

3784 __f(*__first);

3785 return __f;

3786 }

3787

3788#if __cplusplus >= 201703L

3789

3790

3791

3792

3793

3794

3795

3796

3797

3798

3799

3800

3801 template<typename _InputIterator, typename _Size, typename _Function>

3802 _GLIBCXX20_CONSTEXPR

3803 _InputIterator

3804 for_each_n(_InputIterator __first, _Size __n, _Function __f)

3805 {

3806 auto __n2 = std::__size_to_integer(__n);

3808 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)

3809 {

3810 if (__n2 <= 0)

3811 return __first;

3812 auto __last = __first + __n2;

3813 std::for_each(__first, __last, std::move(__f));

3814 return __last;

3815 }

3816 else

3817 {

3818 while (__n2-->0)

3819 {

3820 __f(*__first);

3821 ++__first;

3822 }

3823 return __first;

3824 }

3825 }

3826#endif

3827

3828

3829

3830

3831

3832

3833

3834

3835

3836

3837 template<typename _InputIterator, typename _Tp>

3838 _GLIBCXX20_CONSTEXPR

3839 inline _InputIterator

3840 find(_InputIterator __first, _InputIterator __last, const _Tp& __val)

3841 {

3842

3843 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3844 __glibcxx_function_requires(_EqualOpConcept<

3846 __glibcxx_requires_valid_range(__first, __last);

3847

3848#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates

3850 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)

3851 if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>

3852#if __cpp_lib_concepts

3853 || contiguous_iterator<_InputIterator>

3854#endif

3855 )

3856 {

3857

3858

3859

3860

3861 if (!(static_cast<_ValT>(__val) == __val))

3862 return __last;

3863 else if (!__is_constant_evaluated())

3864 {

3865 const void* __p0 = std::__to_address(__first);

3866 const int __ival = static_cast<int>(__val);

3867 if (auto __n = std::distance(__first, __last); __n > 0)

3868 if (auto __p1 = __builtin_memchr(__p0, __ival, __n))

3869 return __first + ((const char*)__p1 - (const char*)__p0);

3870 return __last;

3871 }

3872 }

3873#endif

3874

3875 return std::__find_if(__first, __last,

3876 __gnu_cxx::__ops::__iter_equals_val(__val));

3877 }

3878

3879

3880

3881

3882

3883

3884

3885

3886

3887

3888

3889 template<typename _InputIterator, typename _Predicate>

3890 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3891 inline _InputIterator

3892 find_if(_InputIterator __first, _InputIterator __last,

3893 _Predicate __pred)

3894 {

3895

3896 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3897 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

3899 __glibcxx_requires_valid_range(__first, __last);

3900

3901 return std::__find_if(__first, __last,

3902 __gnu_cxx::__ops::__pred_iter(__pred));

3903 }

3904

3905

3906

3907

3908

3909

3910

3911

3912

3913

3914

3915

3916

3917

3918

3919

3920

3921 template<typename _InputIterator, typename _ForwardIterator>

3922 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3923 _InputIterator

3924 find_first_of(_InputIterator __first1, _InputIterator __last1,

3925 _ForwardIterator __first2, _ForwardIterator __last2)

3926 {

3927

3928 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3929 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3930 __glibcxx_function_requires(_EqualOpConcept<

3933 __glibcxx_requires_valid_range(__first1, __last1);

3934 __glibcxx_requires_valid_range(__first2, __last2);

3935

3936 for (; __first1 != __last1; ++__first1)

3937 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)

3938 if (*__first1 == *__iter)

3939 return __first1;

3940 return __last1;

3941 }

3942

3943

3944

3945

3946

3947

3948

3949

3950

3951

3952

3953

3954

3955

3956

3957

3958

3959

3960

3961

3962 template<typename _InputIterator, typename _ForwardIterator,

3963 typename _BinaryPredicate>

3964 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3965 _InputIterator

3966 find_first_of(_InputIterator __first1, _InputIterator __last1,

3967 _ForwardIterator __first2, _ForwardIterator __last2,

3968 _BinaryPredicate __comp)

3969 {

3970

3971 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

3972 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

3973 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

3976 __glibcxx_requires_valid_range(__first1, __last1);

3977 __glibcxx_requires_valid_range(__first2, __last2);

3978

3979 for (; __first1 != __last1; ++__first1)

3980 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)

3981 if (__comp(*__first1, *__iter))

3982 return __first1;

3983 return __last1;

3984 }

3985

3986

3987

3988

3989

3990

3991

3992

3993

3994

3995 template<typename _ForwardIterator>

3996 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

3997 inline _ForwardIterator

3998 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)

3999 {

4000

4001 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

4002 __glibcxx_function_requires(_EqualityComparableConcept<

4004 __glibcxx_requires_valid_range(__first, __last);

4005

4006 return std::__adjacent_find(__first, __last,

4007 __gnu_cxx::__ops::__iter_equal_to_iter());

4008 }

4009

4010

4011

4012

4013

4014

4015

4016

4017

4018

4019

4020

4021 template<typename _ForwardIterator, typename _BinaryPredicate>

4022 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4023 inline _ForwardIterator

4024 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,

4025 _BinaryPredicate __binary_pred)

4026 {

4027

4028 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

4029 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

4032 __glibcxx_requires_valid_range(__first, __last);

4033

4034 return std::__adjacent_find(__first, __last,

4035 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));

4036 }

4037

4038

4039

4040

4041

4042

4043

4044

4045

4046

4047 template<typename _InputIterator, typename _Tp>

4048 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4049 inline typename iterator_traits<_InputIterator>::difference_type

4050 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)

4051 {

4052

4053 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

4054 __glibcxx_function_requires(_EqualOpConcept<

4056 __glibcxx_requires_valid_range(__first, __last);

4057

4058 return std::__count_if(__first, __last,

4059 __gnu_cxx::__ops::__iter_equals_val(__value));

4060 }

4061

4062

4063

4064

4065

4066

4067

4068

4069

4070

4071 template<typename _InputIterator, typename _Predicate>

4072 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4073 inline typename iterator_traits<_InputIterator>::difference_type

4074 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)

4075 {

4076

4077 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

4078 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

4080 __glibcxx_requires_valid_range(__first, __last);

4081

4082 return std::__count_if(__first, __last,

4083 __gnu_cxx::__ops::__pred_iter(__pred));

4084 }

4085

4086

4087

4088

4089

4090

4091

4092

4093

4094

4095

4096

4097

4098

4099

4100

4101

4102

4103

4104

4105

4106

4107

4108

4109

4110

4111

4112 template<typename _ForwardIterator1, typename _ForwardIterator2>

4113 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4114 inline _ForwardIterator1

4115 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

4116 _ForwardIterator2 __first2, _ForwardIterator2 __last2)

4117 {

4118

4119 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)

4120 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)

4121 __glibcxx_function_requires(_EqualOpConcept<

4124 __glibcxx_requires_valid_range(__first1, __last1);

4125 __glibcxx_requires_valid_range(__first2, __last2);

4126

4127 return std::__search(__first1, __last1, __first2, __last2,

4128 __gnu_cxx::__ops::__iter_equal_to_iter());

4129 }

4130

4131

4132

4133

4134

4135

4136

4137

4138

4139

4140

4141

4142

4143

4144

4145

4146 template<typename _ForwardIterator, typename _Integer, typename _Tp>

4147 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4148 inline _ForwardIterator

4149 search_n(_ForwardIterator __first, _ForwardIterator __last,

4150 _Integer __count, const _Tp& __val)

4151 {

4152

4153 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

4154 __glibcxx_function_requires(_EqualOpConcept<

4156 __glibcxx_requires_valid_range(__first, __last);

4157

4158 return std::__search_n(__first, __last, __count,

4159 __gnu_cxx::__ops::__iter_equals_val(__val));

4160 }

4161

4162

4163

4164

4165

4166

4167

4168

4169

4170

4171

4172

4173

4174

4175

4176

4177

4178

4179

4180 template<typename _ForwardIterator, typename _Integer, typename _Tp,

4181 typename _BinaryPredicate>

4182 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4183 inline _ForwardIterator

4184 search_n(_ForwardIterator __first, _ForwardIterator __last,

4185 _Integer __count, const _Tp& __val,

4186 _BinaryPredicate __binary_pred)

4187 {

4188

4189 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

4190 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,

4192 __glibcxx_requires_valid_range(__first, __last);

4193

4194 return std::__search_n(__first, __last, __count,

4195 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));

4196 }

4197

4198#if __cplusplus >= 201703L

4199

4200

4201

4202

4203

4204

4205

4206 template<typename _ForwardIterator, typename _Searcher>

4207 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR

4208 inline _ForwardIterator

4209 search(_ForwardIterator __first, _ForwardIterator __last,

4210 const _Searcher& __searcher)

4211 { return __searcher(__first, __last).first; }

4212#endif

4213

4214

4215

4216

4217

4218

4219

4220

4221

4222

4223

4224

4225

4226

4227

4228

4229

4230 template<typename _InputIterator, typename _OutputIterator,

4231 typename _UnaryOperation>

4232 _GLIBCXX20_CONSTEXPR

4233 _OutputIterator

4234 transform(_InputIterator __first, _InputIterator __last,

4235 _OutputIterator __result, _UnaryOperation __unary_op)

4236 {

4237

4238 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

4239 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4240

4241 __typeof__(__unary_op(*__first))>)

4242 __glibcxx_requires_valid_range(__first, __last);

4243

4244 for (; __first != __last; ++__first, (void)++__result)

4245 *__result = __unary_op(*__first);

4246 return __result;

4247 }

4248

4249

4250

4251

4252

4253

4254

4255

4256

4257

4258

4259

4260

4261

4262

4263

4264

4265

4266

4267

4268 template<typename _InputIterator1, typename _InputIterator2,

4269 typename _OutputIterator, typename _BinaryOperation>

4270 _GLIBCXX20_CONSTEXPR

4271 _OutputIterator

4272 transform(_InputIterator1 __first1, _InputIterator1 __last1,

4273 _InputIterator2 __first2, _OutputIterator __result,

4274 _BinaryOperation __binary_op)

4275 {

4276

4277 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

4278 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

4279 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4280

4281 __typeof__(__binary_op(*__first1,*__first2))>)

4282 __glibcxx_requires_valid_range(__first1, __last1);

4283

4284 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)

4285 *__result = __binary_op(*__first1, *__first2);

4286 return __result;

4287 }

4288

4289

4290

4291

4292

4293

4294

4295

4296

4297

4298

4299

4300

4301

4302 template<typename _ForwardIterator, typename _Tp>

4303 _GLIBCXX20_CONSTEXPR

4304 void

4305 replace(_ForwardIterator __first, _ForwardIterator __last,

4306 const _Tp& __old_value, const _Tp& __new_value)

4307 {

4308

4309 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

4310 _ForwardIterator>)

4311 __glibcxx_function_requires(_EqualOpConcept<

4313 __glibcxx_function_requires(_ConvertibleConcept<_Tp,

4315 __glibcxx_requires_valid_range(__first, __last);

4316

4317 for (; __first != __last; ++__first)

4318 if (*__first == __old_value)

4319 *__first = __new_value;

4320 }

4321

4322

4323

4324

4325

4326

4327

4328

4329

4330

4331

4332

4333

4334

4335 template<typename _ForwardIterator, typename _Predicate, typename _Tp>

4336 _GLIBCXX20_CONSTEXPR

4337 void

4338 replace_if(_ForwardIterator __first, _ForwardIterator __last,

4339 _Predicate __pred, const _Tp& __new_value)

4340 {

4341

4342 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

4343 _ForwardIterator>)

4344 __glibcxx_function_requires(_ConvertibleConcept<_Tp,

4346 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

4348 __glibcxx_requires_valid_range(__first, __last);

4349

4350 for (; __first != __last; ++__first)

4351 if (__pred(*__first))

4352 *__first = __new_value;

4353 }

4354

4355

4356

4357

4358

4359

4360

4361

4362

4363

4364

4365

4366

4367 template<typename _ForwardIterator, typename _Generator>

4368 _GLIBCXX20_CONSTEXPR

4369 void

4370 generate(_ForwardIterator __first, _ForwardIterator __last,

4371 _Generator __gen)

4372 {

4373

4374 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

4375 __glibcxx_function_requires(_GeneratorConcept<_Generator,

4377 __glibcxx_requires_valid_range(__first, __last);

4378

4379 for (; __first != __last; ++__first)

4380 *__first = __gen();

4381 }

4382

4383

4384

4385

4386

4387

4388

4389

4390

4391

4392

4393

4394

4395

4396

4397

4398

4399

4400 template<typename _OutputIterator, typename _Size, typename _Generator>

4401 _GLIBCXX20_CONSTEXPR

4402 _OutputIterator

4403 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)

4404 {

4405

4406 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4407

4408 __typeof__(__gen())>)

4409

4410 typedef __decltype(std::__size_to_integer(__n)) _IntSize;

4411 for (_IntSize __niter = std::__size_to_integer(__n);

4412 __niter > 0; --__niter, (void) ++__first)

4413 *__first = __gen();

4414 return __first;

4415 }

4416

4417

4418

4419

4420

4421

4422

4423

4424

4425

4426

4427

4428

4429

4430

4431

4432

4433

4434

4435 template<typename _InputIterator, typename _OutputIterator>

4436 _GLIBCXX20_CONSTEXPR

4437 inline _OutputIterator

4438 unique_copy(_InputIterator __first, _InputIterator __last,

4439 _OutputIterator __result)

4440 {

4441

4442 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

4443 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4445 __glibcxx_function_requires(_EqualityComparableConcept<

4447 __glibcxx_requires_valid_range(__first, __last);

4448

4449 if (__first == __last)

4450 return __result;

4452 __gnu_cxx::__ops::__iter_equal_to_iter(),

4455 }

4456

4457

4458

4459

4460

4461

4462

4463

4464

4465

4466

4467

4468

4469

4470

4471

4472

4473

4474

4475 template<typename _InputIterator, typename _OutputIterator,

4476 typename _BinaryPredicate>

4477 _GLIBCXX20_CONSTEXPR

4478 inline _OutputIterator

4479 unique_copy(_InputIterator __first, _InputIterator __last,

4480 _OutputIterator __result,

4481 _BinaryPredicate __binary_pred)

4482 {

4483

4484 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

4485 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4487 __glibcxx_requires_valid_range(__first, __last);

4488

4489 if (__first == __last)

4490 return __result;

4492 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),

4495 }

4496

4497#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED

4498#if _GLIBCXX_HOSTED

4499

4500

4501

4502

4503

4504

4505

4506

4507

4508

4509

4510

4511

4512

4513

4514 template<typename _RandomAccessIterator>

4515 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")

4516 inline void

4517 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)

4518 {

4519

4520 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4521 _RandomAccessIterator>)

4522 __glibcxx_requires_valid_range(__first, __last);

4523

4524 if (__first == __last)

4525 return;

4526

4527#if RAND_MAX < __INT_MAX__

4528 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))

4529 {

4530

4531

4532 unsigned __xss

4533 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);

4534 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)

4535 {

4536 __xss += !__xss;

4537 __xss ^= __xss << 13;

4538 __xss ^= __xss >> 17;

4539 __xss ^= __xss << 5;

4540 _RandomAccessIterator __j = __first

4541 + (__xss % ((__i - __first) + 1));

4542 if (__i != __j)

4543 std::iter_swap(__i, __j);

4544 }

4545 return;

4546 }

4547#endif

4548

4549 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)

4550 {

4551

4552 _RandomAccessIterator __j = __first

4553 + (std::rand() % ((__i - __first) + 1));

4554 if (__i != __j)

4555 std::iter_swap(__i, __j);

4556 }

4557 }

4558

4559

4560

4561

4562

4563

4564

4565

4566

4567

4568

4569

4570

4571

4572

4573

4574

4575

4576

4577 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>

4578 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")

4579 void

4580 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,

4581#if __cplusplus >= 201103L

4582 _RandomNumberGenerator&& __rand)

4583#else

4584 _RandomNumberGenerator& __rand)

4585#endif

4586 {

4587

4588 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4589 _RandomAccessIterator>)

4590 __glibcxx_requires_valid_range(__first, __last);

4591

4592 if (__first == __last)

4593 return;

4594 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)

4595 {

4596 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);

4597 if (__i != __j)

4598 std::iter_swap(__i, __j);

4599 }

4600 }

4601#endif

4602#endif

4603

4604

4605

4606

4607

4608

4609

4610

4611

4612

4613

4614

4615

4616

4617

4618

4619 template<typename _ForwardIterator, typename _Predicate>

4620 _GLIBCXX20_CONSTEXPR

4621 inline _ForwardIterator

4622 partition(_ForwardIterator __first, _ForwardIterator __last,

4623 _Predicate __pred)

4624 {

4625

4626 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<

4627 _ForwardIterator>)

4628 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,

4630 __glibcxx_requires_valid_range(__first, __last);

4631

4634 }

4635

4636

4637

4638

4639

4640

4641

4642

4643

4644

4645

4646

4647

4648

4649

4650

4651

4652

4653

4654 template<typename _RandomAccessIterator>

4655 _GLIBCXX20_CONSTEXPR

4656 inline void

4657 partial_sort(_RandomAccessIterator __first,

4658 _RandomAccessIterator __middle,

4659 _RandomAccessIterator __last)

4660 {

4661

4662 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4663 _RandomAccessIterator>)

4664 __glibcxx_function_requires(_LessThanComparableConcept<

4666 __glibcxx_requires_valid_range(__first, __middle);

4667 __glibcxx_requires_valid_range(__middle, __last);

4668 __glibcxx_requires_irreflexive(__first, __last);

4669

4670 std::__partial_sort(__first, __middle, __last,

4671 __gnu_cxx::__ops::__iter_less_iter());

4672 }

4673

4674

4675

4676

4677

4678

4679

4680

4681

4682

4683

4684

4685

4686

4687

4688

4689

4690

4691

4692

4693 template<typename _RandomAccessIterator, typename _Compare>

4694 _GLIBCXX20_CONSTEXPR

4695 inline void

4696 partial_sort(_RandomAccessIterator __first,

4697 _RandomAccessIterator __middle,

4698 _RandomAccessIterator __last,

4699 _Compare __comp)

4700 {

4701

4702 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4703 _RandomAccessIterator>)

4704 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

4707 __glibcxx_requires_valid_range(__first, __middle);

4708 __glibcxx_requires_valid_range(__middle, __last);

4709 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

4710

4711 std::__partial_sort(__first, __middle, __last,

4712 __gnu_cxx::__ops::__iter_comp_iter(__comp));

4713 }

4714

4715

4716

4717

4718

4719

4720

4721

4722

4723

4724

4725

4726

4727

4728

4729

4730 template<typename _RandomAccessIterator>

4731 _GLIBCXX20_CONSTEXPR

4732 inline void

4733 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,

4734 _RandomAccessIterator __last)

4735 {

4736

4737 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4738 _RandomAccessIterator>)

4739 __glibcxx_function_requires(_LessThanComparableConcept<

4741 __glibcxx_requires_valid_range(__first, __nth);

4742 __glibcxx_requires_valid_range(__nth, __last);

4743 __glibcxx_requires_irreflexive(__first, __last);

4744

4745 if (__first == __last || __nth == __last)

4746 return;

4747

4748 std::__introselect(__first, __nth, __last,

4749 std::__lg(__last - __first) * 2,

4750 __gnu_cxx::__ops::__iter_less_iter());

4751 }

4752

4753

4754

4755

4756

4757

4758

4759

4760

4761

4762

4763

4764

4765

4766

4767

4768

4769

4770 template<typename _RandomAccessIterator, typename _Compare>

4771 _GLIBCXX20_CONSTEXPR

4772 inline void

4773 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,

4774 _RandomAccessIterator __last, _Compare __comp)

4775 {

4776

4777 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4778 _RandomAccessIterator>)

4779 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

4782 __glibcxx_requires_valid_range(__first, __nth);

4783 __glibcxx_requires_valid_range(__nth, __last);

4784 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

4785

4786 if (__first == __last || __nth == __last)

4787 return;

4788

4789 std::__introselect(__first, __nth, __last,

4790 std::__lg(__last - __first) * 2,

4791 __gnu_cxx::__ops::__iter_comp_iter(__comp));

4792 }

4793

4794

4795

4796

4797

4798

4799

4800

4801

4802

4803

4804

4805

4806

4807

4808 template<typename _RandomAccessIterator>

4809 _GLIBCXX20_CONSTEXPR

4810 inline void

4811 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

4812 {

4813

4814 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4815 _RandomAccessIterator>)

4816 __glibcxx_function_requires(_LessThanComparableConcept<

4818 __glibcxx_requires_valid_range(__first, __last);

4819 __glibcxx_requires_irreflexive(__first, __last);

4820

4821 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());

4822 }

4823

4824

4825

4826

4827

4828

4829

4830

4831

4832

4833

4834

4835

4836

4837

4838

4839 template<typename _RandomAccessIterator, typename _Compare>

4840 _GLIBCXX20_CONSTEXPR

4841 inline void

4842 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,

4843 _Compare __comp)

4844 {

4845

4846 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

4847 _RandomAccessIterator>)

4848 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

4851 __glibcxx_requires_valid_range(__first, __last);

4852 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

4853

4854 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));

4855 }

4856

4857 template<typename _InputIterator1, typename _InputIterator2,

4858 typename _OutputIterator, typename _Compare>

4859 _GLIBCXX20_CONSTEXPR

4860 _OutputIterator

4861 __merge(_InputIterator1 __first1, _InputIterator1 __last1,

4862 _InputIterator2 __first2, _InputIterator2 __last2,

4863 _OutputIterator __result, _Compare __comp)

4864 {

4865 while (__first1 != __last1 && __first2 != __last2)

4866 {

4867 if (__comp(__first2, __first1))

4868 {

4869 *__result = *__first2;

4870 ++__first2;

4871 }

4872 else

4873 {

4874 *__result = *__first1;

4875 ++__first1;

4876 }

4877 ++__result;

4878 }

4879 return std::copy(__first2, __last2,

4880 std::copy(__first1, __last1, __result));

4881 }

4882

4883

4884

4885

4886

4887

4888

4889

4890

4891

4892

4893

4894

4895

4896

4897

4898

4899

4900

4901

4902 template<typename _InputIterator1, typename _InputIterator2,

4903 typename _OutputIterator>

4904 _GLIBCXX20_CONSTEXPR

4905 inline _OutputIterator

4906 merge(_InputIterator1 __first1, _InputIterator1 __last1,

4907 _InputIterator2 __first2, _InputIterator2 __last2,

4908 _OutputIterator __result)

4909 {

4910

4911 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

4912 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

4913 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4917 __glibcxx_function_requires(_LessThanOpConcept<

4920 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

4921 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

4922 __glibcxx_requires_irreflexive2(__first1, __last1);

4923 __glibcxx_requires_irreflexive2(__first2, __last2);

4924

4925 return _GLIBCXX_STD_A::__merge(__first1, __last1,

4926 __first2, __last2, __result,

4927 __gnu_cxx::__ops::__iter_less_iter());

4928 }

4929

4930

4931

4932

4933

4934

4935

4936

4937

4938

4939

4940

4941

4942

4943

4944

4945

4946

4947

4948

4949

4950

4951

4952

4953 template<typename _InputIterator1, typename _InputIterator2,

4954 typename _OutputIterator, typename _Compare>

4955 _GLIBCXX20_CONSTEXPR

4956 inline _OutputIterator

4957 merge(_InputIterator1 __first1, _InputIterator1 __last1,

4958 _InputIterator2 __first2, _InputIterator2 __last2,

4959 _OutputIterator __result, _Compare __comp)

4960 {

4961

4962 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

4963 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

4964 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4966 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

4968 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

4971 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

4972 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

4973 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

4974 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

4975

4976 return _GLIBCXX_STD_A::__merge(__first1, __last1,

4977 __first2, __last2, __result,

4978 __gnu_cxx::__ops::__iter_comp_iter(__comp));

4979 }

4980

4981 template<typename _RandomAccessIterator, typename _Compare>

4982 inline void

4983 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,

4984 _Compare __comp)

4985 {

4986 typedef typename iterator_traits<_RandomAccessIterator>::value_type

4987 _ValueType;

4988 typedef typename iterator_traits<_RandomAccessIterator>::difference_type

4989 _DistanceType;

4990

4991 if (__first == __last)

4992 return;

4993

4994#if _GLIBCXX_HOSTED

4995 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;

4996

4997

4998 _TmpBuf __buf(__first, (__last - __first + 1) / 2);

4999

5000 if (__builtin_expect(__buf.requested_size() == __buf.size(), true))

5001 std::__stable_sort_adaptive(__first,

5002 __first + _DistanceType(__buf.size()),

5003 __last, __buf.begin(), __comp);

5004 else if (__builtin_expect(__buf.begin() == 0, false))

5006 else

5007 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),

5008 _DistanceType(__buf.size()), __comp);

5009#else

5011#endif

5012 }

5013

5014

5015

5016

5017

5018

5019

5020

5021

5022

5023

5024

5025

5026

5027

5028

5029

5030

5031 template<typename _RandomAccessIterator>

5032 inline void

5033 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

5034 {

5035

5036 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

5037 _RandomAccessIterator>)

5038 __glibcxx_function_requires(_LessThanComparableConcept<

5040 __glibcxx_requires_valid_range(__first, __last);

5041 __glibcxx_requires_irreflexive(__first, __last);

5042

5043 _GLIBCXX_STD_A::__stable_sort(__first, __last,

5044 __gnu_cxx::__ops::__iter_less_iter());

5045 }

5046

5047

5048

5049

5050

5051

5052

5053

5054

5055

5056

5057

5058

5059

5060

5061

5062

5063

5064

5065 template<typename _RandomAccessIterator, typename _Compare>

5066 inline void

5067 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,

5068 _Compare __comp)

5069 {

5070

5071 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

5072 _RandomAccessIterator>)

5073 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5076 __glibcxx_requires_valid_range(__first, __last);

5077 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

5078

5079 _GLIBCXX_STD_A::__stable_sort(__first, __last,

5080 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5081 }

5082

5083 template<typename _InputIterator1, typename _InputIterator2,

5084 typename _OutputIterator,

5085 typename _Compare>

5086 _GLIBCXX20_CONSTEXPR

5087 _OutputIterator

5088 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5089 _InputIterator2 __first2, _InputIterator2 __last2,

5090 _OutputIterator __result, _Compare __comp)

5091 {

5092 while (__first1 != __last1 && __first2 != __last2)

5093 {

5094 if (__comp(__first1, __first2))

5095 {

5096 *__result = *__first1;

5097 ++__first1;

5098 }

5099 else if (__comp(__first2, __first1))

5100 {

5101 *__result = *__first2;

5102 ++__first2;

5103 }

5104 else

5105 {

5106 *__result = *__first1;

5107 ++__first1;

5108 ++__first2;

5109 }

5110 ++__result;

5111 }

5112 return std::copy(__first2, __last2,

5113 std::copy(__first1, __last1, __result));

5114 }

5115

5116

5117

5118

5119

5120

5121

5122

5123

5124

5125

5126

5127

5128

5129

5130

5131

5132

5133

5134

5135 template<typename _InputIterator1, typename _InputIterator2,

5136 typename _OutputIterator>

5137 _GLIBCXX20_CONSTEXPR

5138 inline _OutputIterator

5139 set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5140 _InputIterator2 __first2, _InputIterator2 __last2,

5141 _OutputIterator __result)

5142 {

5143

5144 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5148 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5150 __glibcxx_function_requires(_LessThanOpConcept<

5153 __glibcxx_function_requires(_LessThanOpConcept<

5156 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

5157 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

5158 __glibcxx_requires_irreflexive2(__first1, __last1);

5159 __glibcxx_requires_irreflexive2(__first2, __last2);

5160

5161 return _GLIBCXX_STD_A::__set_union(__first1, __last1,

5162 __first2, __last2, __result,

5163 __gnu_cxx::__ops::__iter_less_iter());

5164 }

5165

5166

5167

5168

5169

5170

5171

5172

5173

5174

5175

5176

5177

5178

5179

5180

5181

5182

5183

5184

5185

5186 template<typename _InputIterator1, typename _InputIterator2,

5187 typename _OutputIterator, typename _Compare>

5188 _GLIBCXX20_CONSTEXPR

5189 inline _OutputIterator

5190 set_union(_InputIterator1 __first1, _InputIterator1 __last1,

5191 _InputIterator2 __first2, _InputIterator2 __last2,

5192 _OutputIterator __result, _Compare __comp)

5193 {

5194

5195 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5196 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5197 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5199 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5201 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5204 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5207 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

5208 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

5209 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

5210 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

5211

5212 return _GLIBCXX_STD_A::__set_union(__first1, __last1,

5213 __first2, __last2, __result,

5214 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5215 }

5216

5217 template<typename _InputIterator1, typename _InputIterator2,

5218 typename _OutputIterator,

5219 typename _Compare>

5220 _GLIBCXX20_CONSTEXPR

5221 _OutputIterator

5222 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5223 _InputIterator2 __first2, _InputIterator2 __last2,

5224 _OutputIterator __result, _Compare __comp)

5225 {

5226 while (__first1 != __last1 && __first2 != __last2)

5227 if (__comp(__first1, __first2))

5228 ++__first1;

5229 else if (__comp(__first2, __first1))

5230 ++__first2;

5231 else

5232 {

5233 *__result = *__first1;

5234 ++__first1;

5235 ++__first2;

5236 ++__result;

5237 }

5238 return __result;

5239 }

5240

5241

5242

5243

5244

5245

5246

5247

5248

5249

5250

5251

5252

5253

5254

5255

5256

5257

5258

5259 template<typename _InputIterator1, typename _InputIterator2,

5260 typename _OutputIterator>

5261 _GLIBCXX20_CONSTEXPR

5262 inline _OutputIterator

5263 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5264 _InputIterator2 __first2, _InputIterator2 __last2,

5265 _OutputIterator __result)

5266 {

5267

5268 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5269 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5270 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5272 __glibcxx_function_requires(_LessThanOpConcept<

5275 __glibcxx_function_requires(_LessThanOpConcept<

5278 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

5279 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

5280 __glibcxx_requires_irreflexive2(__first1, __last1);

5281 __glibcxx_requires_irreflexive2(__first2, __last2);

5282

5283 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,

5284 __first2, __last2, __result,

5285 __gnu_cxx::__ops::__iter_less_iter());

5286 }

5287

5288

5289

5290

5291

5292

5293

5294

5295

5296

5297

5298

5299

5300

5301

5302

5303

5304

5305

5306

5307

5308

5309 template<typename _InputIterator1, typename _InputIterator2,

5310 typename _OutputIterator, typename _Compare>

5311 _GLIBCXX20_CONSTEXPR

5312 inline _OutputIterator

5313 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,

5314 _InputIterator2 __first2, _InputIterator2 __last2,

5315 _OutputIterator __result, _Compare __comp)

5316 {

5317

5318 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5319 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5320 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5322 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5325 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5328 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

5329 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

5330 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

5331 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

5332

5333 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,

5334 __first2, __last2, __result,

5335 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5336 }

5337

5338 template<typename _InputIterator1, typename _InputIterator2,

5339 typename _OutputIterator,

5340 typename _Compare>

5341 _GLIBCXX20_CONSTEXPR

5342 _OutputIterator

5343 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5344 _InputIterator2 __first2, _InputIterator2 __last2,

5345 _OutputIterator __result, _Compare __comp)

5346 {

5347 while (__first1 != __last1 && __first2 != __last2)

5348 if (__comp(__first1, __first2))

5349 {

5350 *__result = *__first1;

5351 ++__first1;

5352 ++__result;

5353 }

5354 else if (__comp(__first2, __first1))

5355 ++__first2;

5356 else

5357 {

5358 ++__first1;

5359 ++__first2;

5360 }

5361 return std::copy(__first1, __last1, __result);

5362 }

5363

5364

5365

5366

5367

5368

5369

5370

5371

5372

5373

5374

5375

5376

5377

5378

5379

5380

5381

5382

5383

5384 template<typename _InputIterator1, typename _InputIterator2,

5385 typename _OutputIterator>

5386 _GLIBCXX20_CONSTEXPR

5387 inline _OutputIterator

5388 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5389 _InputIterator2 __first2, _InputIterator2 __last2,

5390 _OutputIterator __result)

5391 {

5392

5393 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5394 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5395 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5397 __glibcxx_function_requires(_LessThanOpConcept<

5400 __glibcxx_function_requires(_LessThanOpConcept<

5403 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

5404 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

5405 __glibcxx_requires_irreflexive2(__first1, __last1);

5406 __glibcxx_requires_irreflexive2(__first2, __last2);

5407

5408 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,

5409 __first2, __last2, __result,

5410 __gnu_cxx::__ops::__iter_less_iter());

5411 }

5412

5413

5414

5415

5416

5417

5418

5419

5420

5421

5422

5423

5424

5425

5426

5427

5428

5429

5430

5431

5432

5433

5434

5435

5436 template<typename _InputIterator1, typename _InputIterator2,

5437 typename _OutputIterator, typename _Compare>

5438 _GLIBCXX20_CONSTEXPR

5439 inline _OutputIterator

5440 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5441 _InputIterator2 __first2, _InputIterator2 __last2,

5442 _OutputIterator __result, _Compare __comp)

5443 {

5444

5445 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5446 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5447 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5449 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5452 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5455 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

5456 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

5457 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

5458 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

5459

5460 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,

5461 __first2, __last2, __result,

5462 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5463 }

5464

5465 template<typename _InputIterator1, typename _InputIterator2,

5466 typename _OutputIterator,

5467 typename _Compare>

5468 _GLIBCXX20_CONSTEXPR

5469 _OutputIterator

5470 __set_symmetric_difference(_InputIterator1 __first1,

5471 _InputIterator1 __last1,

5472 _InputIterator2 __first2,

5473 _InputIterator2 __last2,

5474 _OutputIterator __result,

5475 _Compare __comp)

5476 {

5477 while (__first1 != __last1 && __first2 != __last2)

5478 if (__comp(__first1, __first2))

5479 {

5480 *__result = *__first1;

5481 ++__first1;

5482 ++__result;

5483 }

5484 else if (__comp(__first2, __first1))

5485 {

5486 *__result = *__first2;

5487 ++__first2;

5488 ++__result;

5489 }

5490 else

5491 {

5492 ++__first1;

5493 ++__first2;

5494 }

5495 return std::copy(__first2, __last2,

5496 std::copy(__first1, __last1, __result));

5497 }

5498

5499

5500

5501

5502

5503

5504

5505

5506

5507

5508

5509

5510

5511

5512

5513

5514

5515

5516

5517 template<typename _InputIterator1, typename _InputIterator2,

5518 typename _OutputIterator>

5519 _GLIBCXX20_CONSTEXPR

5520 inline _OutputIterator

5521 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5522 _InputIterator2 __first2, _InputIterator2 __last2,

5523 _OutputIterator __result)

5524 {

5525

5526 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5527 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5528 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5530 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5532 __glibcxx_function_requires(_LessThanOpConcept<

5535 __glibcxx_function_requires(_LessThanOpConcept<

5538 __glibcxx_requires_sorted_set(__first1, __last1, __first2);

5539 __glibcxx_requires_sorted_set(__first2, __last2, __first1);

5540 __glibcxx_requires_irreflexive2(__first1, __last1);

5541 __glibcxx_requires_irreflexive2(__first2, __last2);

5542

5543 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,

5544 __first2, __last2, __result,

5545 __gnu_cxx::__ops::__iter_less_iter());

5546 }

5547

5548

5549

5550

5551

5552

5553

5554

5555

5556

5557

5558

5559

5560

5561

5562

5563

5564

5565

5566

5567

5568

5569 template<typename _InputIterator1, typename _InputIterator2,

5570 typename _OutputIterator, typename _Compare>

5571 _GLIBCXX20_CONSTEXPR

5572 inline _OutputIterator

5573 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,

5574 _InputIterator2 __first2, _InputIterator2 __last2,

5575 _OutputIterator __result,

5576 _Compare __comp)

5577 {

5578

5579 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)

5580 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)

5581 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5583 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,

5585 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5588 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5591 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);

5592 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);

5593 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);

5594 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);

5595

5596 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,

5597 __first2, __last2, __result,

5598 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5599 }

5600

5601 template<typename _ForwardIterator, typename _Compare>

5602 _GLIBCXX14_CONSTEXPR

5603 _ForwardIterator

5604 __min_element(_ForwardIterator __first, _ForwardIterator __last,

5605 _Compare __comp)

5606 {

5607 if (__first == __last)

5608 return __first;

5609 _ForwardIterator __result = __first;

5610 while (++__first != __last)

5611 if (__comp(__first, __result))

5612 __result = __first;

5613 return __result;

5614 }

5615

5616

5617

5618

5619

5620

5621

5622

5623 template<typename _ForwardIterator>

5624 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

5625 _ForwardIterator

5626 inline min_element(_ForwardIterator __first, _ForwardIterator __last)

5627 {

5628

5629 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

5630 __glibcxx_function_requires(_LessThanComparableConcept<

5632 __glibcxx_requires_valid_range(__first, __last);

5633 __glibcxx_requires_irreflexive(__first, __last);

5634

5635 return _GLIBCXX_STD_A::__min_element(__first, __last,

5636 __gnu_cxx::__ops::__iter_less_iter());

5637 }

5638

5639

5640

5641

5642

5643

5644

5645

5646

5647

5648 template<typename _ForwardIterator, typename _Compare>

5649 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

5650 inline _ForwardIterator

5651 min_element(_ForwardIterator __first, _ForwardIterator __last,

5652 _Compare __comp)

5653 {

5654

5655 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

5656 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5659 __glibcxx_requires_valid_range(__first, __last);

5660 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

5661

5662 return _GLIBCXX_STD_A::__min_element(__first, __last,

5663 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5664 }

5665

5666 template<typename _ForwardIterator, typename _Compare>

5667 _GLIBCXX14_CONSTEXPR

5668 _ForwardIterator

5669 __max_element(_ForwardIterator __first, _ForwardIterator __last,

5670 _Compare __comp)

5671 {

5672 if (__first == __last) return __first;

5673 _ForwardIterator __result = __first;

5674 while (++__first != __last)

5675 if (__comp(__result, __first))

5676 __result = __first;

5677 return __result;

5678 }

5679

5680

5681

5682

5683

5684

5685

5686

5687 template<typename _ForwardIterator>

5688 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

5689 inline _ForwardIterator

5690 max_element(_ForwardIterator __first, _ForwardIterator __last)

5691 {

5692

5693 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

5694 __glibcxx_function_requires(_LessThanComparableConcept<

5696 __glibcxx_requires_valid_range(__first, __last);

5697 __glibcxx_requires_irreflexive(__first, __last);

5698

5699 return _GLIBCXX_STD_A::__max_element(__first, __last,

5700 __gnu_cxx::__ops::__iter_less_iter());

5701 }

5702

5703

5704

5705

5706

5707

5708

5709

5710

5711

5712 template<typename _ForwardIterator, typename _Compare>

5713 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR

5714 inline _ForwardIterator

5715 max_element(_ForwardIterator __first, _ForwardIterator __last,

5716 _Compare __comp)

5717 {

5718

5719 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)

5720 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,

5723 __glibcxx_requires_valid_range(__first, __last);

5724 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

5725

5726 return _GLIBCXX_STD_A::__max_element(__first, __last,

5727 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5728 }

5729

5730#if __cplusplus >= 201103L

5731

5732 template<typename _Tp>

5733 _GLIBCXX14_CONSTEXPR

5734 inline _Tp

5735 min(initializer_list<_Tp> __l)

5736 {

5737 __glibcxx_requires_irreflexive(__l.begin(), __l.end());

5738 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),

5739 __gnu_cxx::__ops::__iter_less_iter());

5740 }

5741

5742 template<typename _Tp, typename _Compare>

5743 _GLIBCXX14_CONSTEXPR

5744 inline _Tp

5745 min(initializer_list<_Tp> __l, _Compare __comp)

5746 {

5747 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);

5748 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),

5749 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5750 }

5751

5752 template<typename _Tp>

5753 _GLIBCXX14_CONSTEXPR

5754 inline _Tp

5755 max(initializer_list<_Tp> __l)

5756 {

5757 __glibcxx_requires_irreflexive(__l.begin(), __l.end());

5758 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),

5759 __gnu_cxx::__ops::__iter_less_iter());

5760 }

5761

5762 template<typename _Tp, typename _Compare>

5763 _GLIBCXX14_CONSTEXPR

5764 inline _Tp

5765 max(initializer_list<_Tp> __l, _Compare __comp)

5766 {

5767 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);

5768 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),

5769 __gnu_cxx::__ops::__iter_comp_iter(__comp));

5770 }

5771#endif

5772

5773#if __cplusplus >= 201402L

5774

5775 template<typename _InputIterator, typename _RandomAccessIterator,

5776 typename _Size, typename _UniformRandomBitGenerator>

5777 _RandomAccessIterator

5780 _Size __n, _UniformRandomBitGenerator&& __g)

5781 {

5783 using __param_type = typename __distrib_type::param_type;

5784 __distrib_type __d{};

5785 _Size __sample_sz = 0;

5786 while (__first != __last && __sample_sz != __n)

5787 {

5788 __out[__sample_sz++] = *__first;

5789 ++__first;

5790 }

5791 for (auto __pop_sz = __sample_sz; __first != __last;

5792 ++__first, (void) ++__pop_sz)

5793 {

5794 const auto __k = __d(__g, __param_type{0, __pop_sz});

5795 if (__k < __n)

5796 __out[__k] = *__first;

5797 }

5798 return __out + __sample_sz;

5799 }

5800

5801

5802 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,

5803 typename _Size, typename _UniformRandomBitGenerator>

5804 _OutputIterator

5805 __sample(_ForwardIterator __first, _ForwardIterator __last,

5807 _OutputIterator __out, _Cat,

5808 _Size __n, _UniformRandomBitGenerator&& __g)

5809 {

5811 using __param_type = typename __distrib_type::param_type;

5815

5816 if (__first == __last)

5817 return __out;

5818

5819 __distrib_type __d{};

5820 _Size __unsampled_sz = std::distance(__first, __last);

5821 __n = std::min(__n, __unsampled_sz);

5822

5823

5824

5825

5826 const __uc_type __urngrange = __g.max() - __g.min();

5827 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))

5828

5829

5830 {

5831 while (__n != 0 && __unsampled_sz >= 2)

5832 {

5835

5836 --__unsampled_sz;

5837 if (__p.first < __n)

5838 {

5839 *__out++ = *__first;

5840 --__n;

5841 }

5842

5843 ++__first;

5844

5845 if (__n == 0) break;

5846

5847 --__unsampled_sz;

5848 if (__p.second < __n)

5849 {

5850 *__out++ = *__first;

5851 --__n;

5852 }

5853

5854 ++__first;

5855 }

5856 }

5857

5858

5859

5860 for (; __n != 0; ++__first)

5861 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)

5862 {

5863 *__out++ = *__first;

5864 --__n;

5865 }

5866 return __out;

5867 }

5868#endif

5869

5870#ifdef __glibcxx_sample

5871

5872 template<typename _PopulationIterator, typename _SampleIterator,

5873 typename _Distance, typename _UniformRandomBitGenerator>

5874 _SampleIterator

5875 sample(_PopulationIterator __first, _PopulationIterator __last,

5876 _SampleIterator __out, _Distance __n,

5877 _UniformRandomBitGenerator&& __g)

5878 {

5879 using __pop_cat = typename

5881 using __samp_cat = typename

5883

5884 static_assert(

5885 __or_<is_convertible<__pop_cat, forward_iterator_tag>,

5887 "output range must use a RandomAccessIterator when input range"

5888 " does not meet the ForwardIterator requirements");

5889

5891 "sample size must be an integer type");

5892

5894 return _GLIBCXX_STD_A::

5895 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,

5896 std::forward<_UniformRandomBitGenerator>(__g));

5897 }

5898#endif

5899

5900_GLIBCXX_END_NAMESPACE_ALGO

5901_GLIBCXX_END_NAMESPACE_VERSION

5902}

5903

5904#endif

typename remove_reference< _Tp >::type remove_reference_t

Alias template for remove_reference.

typename make_unsigned< _Tp >::type make_unsigned_t

Alias template for make_unsigned.

typename common_type< _Tp... >::type common_type_t

Alias template for common_type.

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

Convert a value to an rvalue.

constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)

Apply a function to every element of a sequence.

constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)

Returns the value clamped between lo and hi.

constexpr const _Tp & max(const _Tp &, const _Tp &)

This does what you think it does.

constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)

Determines min and max at once as an ordered pair.

constexpr const _Tp & min(const _Tp &, const _Tp &)

This does what you think it does.

constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)

ISO C++ entities toplevel namespace is std.

_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)

This is a helper function for the merge routines.

_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)

Reservoir sampling algorithm.

void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)

This is a helper function for the merge routines.

constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)

Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...

constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)

void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)

This is a helper function for the merge routines.

pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)

Generate two uniformly distributed integers using a single distribution invocation.

constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)

A generalization of pointer arithmetic.

void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

This is a helper function for the stable sorting routines.

constexpr _Tp __lg(_Tp __n)

This is a helper function for the sort routines and for random.tcc.

constexpr _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)

constexpr _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)

This is a helper function...

void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)

This is a helper function for the __merge_adaptive routines.

constexpr void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)

_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)

Take a random sample from a population.

constexpr void advance(_InputIterator &__i, _Distance __n)

A generalization of pointer arithmetic.

constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)

This is a helper function for the rotate algorithm.

constexpr void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)

Swaps the median value of *__a, *__b and *__c under __comp to *__result.

constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)

void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)

This is a helper function for the __merge_adaptive routines.

_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)

This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...

constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)

Provided for stable_partition to use.

_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)

This is a helper function for the __merge_sort_loop routines.

Traits class for iterators.

Struct holding two objects of arbitrary type.

_T1 first

The first member.

_T2 second

The second member.

Marking output iterators.

Forward iterators support a superset of input iterator operations.

Bidirectional iterators support a superset of forward iterator operations.

Random-access iterators support a superset of bidirectional iterator operations.

Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...