138 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// template<ForwardIterator Iter1, ForwardIterator Iter2>12// requires HasEqualTo<Iter1::value_type, Iter2::value_type>13// constexpr Iter1 // constexpr after C++1714// search(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2);15//16// template<class ForwardIterator, class Searcher>17// ForwardIterator search(ForwardIterator first, ForwardIterator last,18// const Searcher& searcher); // C++1719 20#include <algorithm>21#include <cassert>22 23#include "test_macros.h"24#include "test_iterators.h"25 26struct MySearcherC {27 template <typename Iterator>28 std::pair<Iterator, Iterator> TEST_CONSTEXPR operator()(Iterator b, Iterator e) const {29 return std::make_pair(b, e);30 }31};32 33#if TEST_STD_VER > 1734TEST_CONSTEXPR bool test_constexpr() {35 int ia[] = {0, 1, 2, 3};36 int ib[] = {0, 1, 5, 3};37 int ic[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};38 return (std::search(std::begin(ic), std::end(ic), std::begin(ia), std::end(ia)) == ic + 3) &&39 (std::search(std::begin(ic), std::end(ic), std::begin(ib), std::end(ib)) == std::end(ic)) &&40 (std::search(std::begin(ic), std::end(ic), MySearcherC()) == std::begin(ic));41}42#endif43 44int searcher_called = 0;45 46struct MySearcher {47 template <typename Iterator>48 std::pair<Iterator, Iterator> operator()(Iterator b, Iterator e) const {49 ++searcher_called;50 return std::make_pair(b, e);51 }52};53 54namespace User {55struct S {56 S(int x) : x_(x) {}57 int x_;58};59bool operator==(S lhs, S rhs) { return lhs.x_ == rhs.x_; }60template <class T, class U>61void make_pair(T&&, U&&) = delete;62} // namespace User63 64template <class Iter1, class Iter2>65void test() {66 int ia[] = {0, 1, 2, 3, 4, 5};67 const unsigned sa = sizeof(ia) / sizeof(ia[0]);68 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia), Iter2(ia)) == Iter1(ia));69 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia), Iter2(ia + 1)) == Iter1(ia));70 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + 1), Iter2(ia + 2)) == Iter1(ia + 1));71 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + 2), Iter2(ia + 2)) == Iter1(ia));72 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + 2), Iter2(ia + 3)) == Iter1(ia + 2));73 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + 2), Iter2(ia + 3)) == Iter1(ia + 2));74 assert(std::search(Iter1(ia), Iter1(ia), Iter2(ia + 2), Iter2(ia + 3)) == Iter1(ia));75 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + sa - 1), Iter2(ia + sa)) == Iter1(ia + sa - 1));76 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia + sa - 3), Iter2(ia + sa)) == Iter1(ia + sa - 3));77 assert(std::search(Iter1(ia), Iter1(ia + sa), Iter2(ia), Iter2(ia + sa)) == Iter1(ia));78 assert(std::search(Iter1(ia), Iter1(ia + sa - 1), Iter2(ia), Iter2(ia + sa)) == Iter1(ia + sa - 1));79 assert(std::search(Iter1(ia), Iter1(ia + 1), Iter2(ia), Iter2(ia + sa)) == Iter1(ia + 1));80 int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};81 const unsigned sb = sizeof(ib) / sizeof(ib[0]);82 int ic[] = {1};83 assert(std::search(Iter1(ib), Iter1(ib + sb), Iter2(ic), Iter2(ic + 1)) == Iter1(ib + 1));84 int id[] = {1, 2};85 assert(std::search(Iter1(ib), Iter1(ib + sb), Iter2(id), Iter2(id + 2)) == Iter1(ib + 1));86 int ie[] = {1, 2, 3};87 assert(std::search(Iter1(ib), Iter1(ib + sb), Iter2(ie), Iter2(ie + 3)) == Iter1(ib + 4));88 int ig[] = {1, 2, 3, 4};89 assert(std::search(Iter1(ib), Iter1(ib + sb), Iter2(ig), Iter2(ig + 4)) == Iter1(ib + 8));90 int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};91 const unsigned sh = sizeof(ih) / sizeof(ih[0]);92 int ii[] = {1, 1, 2};93 assert(std::search(Iter1(ih), Iter1(ih + sh), Iter2(ii), Iter2(ii + 3)) == Iter1(ih + 3));94 int ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};95 const unsigned sj = sizeof(ij) / sizeof(ij[0]);96 int ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};97 const unsigned sk = sizeof(ik) / sizeof(ik[0]);98 assert(std::search(Iter1(ij), Iter1(ij + sj), Iter2(ik), Iter2(ik + sk)) == Iter1(ij + 6));99}100 101template <class Iter>102void adl_test() {103 User::S ua[] = {1};104 assert(std::search(Iter(ua), Iter(ua), Iter(ua), Iter(ua)) == Iter(ua));105}106 107int main(int, char**) {108 test<forward_iterator<const int*>, forward_iterator<const int*> >();109 test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();110 test<forward_iterator<const int*>, random_access_iterator<const int*> >();111 test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();112 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*> >();113 test<bidirectional_iterator<const int*>, random_access_iterator<const int*> >();114 test<random_access_iterator<const int*>, forward_iterator<const int*> >();115 test<random_access_iterator<const int*>, bidirectional_iterator<const int*> >();116 test<random_access_iterator<const int*>, random_access_iterator<const int*> >();117 118 adl_test<forward_iterator<User::S*> >();119 adl_test<random_access_iterator<User::S*> >();120 121#if TEST_STD_VER > 14122 {123 typedef int* RI;124 static_assert((std::is_same<RI, decltype(std::search(RI(), RI(), MySearcher()))>::value), "");125 126 RI it(nullptr);127 assert(it == std::search(it, it, MySearcher()));128 assert(searcher_called == 1);129 }130#endif131 132#if TEST_STD_VER > 17133 static_assert(test_constexpr());134#endif135 136 return 0;137}138