300 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// UNSUPPORTED: c++03, c++11, c++14, c++17, c++2012 13// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>14// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>15// constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++2316 17// template<input_range R, class T, class Proj = identity>18// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>19// constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++2320 21#include <algorithm>22#include <array>23#include <cassert>24#include <list>25#include <ranges>26#include <string>27#include <vector>28 29#include "almost_satisfies_types.h"30#include "boolean_testable.h"31#include "test_iterators.h"32 33struct NotEqualityComparable {};34 35template <class Iter, class Sent = Iter>36concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); };37 38static_assert(HasContainsIt<int*>);39static_assert(HasContainsIt<int*, int*>);40static_assert(!HasContainsIt<NotEqualityComparable*>);41static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>);42static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>);43static_assert(!HasContainsIt<InputIteratorNotInputOrOutputIterator>);44static_assert(!HasContainsIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);45static_assert(!HasContainsIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);46static_assert(!HasContainsIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);47 48static_assert(!HasContainsIt<int*, int>);49static_assert(!HasContainsIt<int, int*>);50 51template <class Range, class ValT>52concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); };53 54static_assert(!HasContainsR<int, int>);55static_assert(HasContainsR<int[1], int>);56static_assert(!HasContainsR<NotEqualityComparable[1], NotEqualityComparable>);57static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>);58static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>);59static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>);60static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>);61static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>);62 63template <class Iter, class Sent = Iter>64constexpr void test_iterators() {65 using ValueT = std::iter_value_t<Iter>;66 { // simple tests67 ValueT a[] = {1, 2, 3, 4, 5, 6};68 {69 std::same_as<bool> decltype(auto) ret = std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3);70 assert(ret);71 }72 {73 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));74 std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole, 3);75 assert(ret);76 }77 }78 79 { // check that a range with a single element works80 ValueT a[] = {32};81 {82 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 1)), 32);83 assert(ret);84 }85 {86 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 1)));87 bool ret = std::ranges::contains(whole, 32);88 assert(ret);89 }90 }91 92 { // check that an empty range works93 std::array<ValueT, 0> a = {};94 {95 bool ret = std::ranges::contains(Iter(a.data()), Sent(Iter(a.data())), 1);96 assert(!ret);97 }98 {99 auto whole = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data())));100 bool ret = std::ranges::contains(whole, 1);101 assert(!ret);102 }103 }104 105 { // check that the first element matches106 ValueT a[] = {32, 3, 2, 1, 0, 23, 21, 9, 40, 100};107 {108 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 10)), 32);109 assert(ret);110 }111 {112 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 10)));113 bool ret = std::ranges::contains(whole, 32);114 assert(ret);115 }116 }117 118 { // check that the last element matches119 ValueT a[] = {3, 22, 1, 43, 99, 0, 56, 100, 32};120 {121 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 9)), 32);122 assert(ret);123 }124 {125 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));126 bool ret = std::ranges::contains(whole, 32);127 assert(ret);128 }129 }130 131 { // no match132 ValueT a[] = {13, 1, 21, 4, 5};133 {134 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10);135 assert(!ret);136 }137 {138 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));139 bool ret = std::ranges::contains(whole, 10);140 assert(!ret);141 }142 }143 144 { // check that the projections are used145 int a[] = {1, 9, 0, 13, 25};146 {147 bool ret = std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; });148 assert(ret);149 }150 {151 auto range = std::ranges::subrange(a, a + 5);152 bool ret = std::ranges::contains(range, -13, [&](int i) { return i * -1; });153 assert(ret);154 }155 }156}157 158constexpr bool test() {159 types::for_each(types::type_list<char, long long>{}, []<class T> {160 types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> {161 if constexpr (std::forward_iterator<Iter>)162 test_iterators<Iter>();163 test_iterators<Iter, sentinel_wrapper<Iter>>();164 test_iterators<Iter, sized_sentinel<Iter>>();165 });166 });167 168 { // count invocations of the projection for contiguous iterators169 int a[] = {1, 9, 0, 13, 25};170 int projection_count = 0;171 {172 bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) {173 ++projection_count;174 return i;175 });176 assert(ret);177 assert(projection_count == 3);178 projection_count = 0;179 }180 {181 bool ret = std::ranges::contains(a, 0, [&](int i) {182 ++projection_count;183 return i;184 });185 assert(ret);186 assert(projection_count == 3);187 }188 }189 190 { // check invocations of the projection for std::string191 const std::string str{"hello world"};192 const std::string str1{"hi world"};193 int projection_count = 0;194 {195 std::string a[] = {str1, str1, str, str1, str1};196 auto whole =197 std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5)));198 bool ret = std::ranges::contains(whole.begin(), whole.end(), +"hello world", [&](const std::string i) {199 ++projection_count;200 return i;201 });202 assert(ret);203 assert(projection_count == 3);204 projection_count = 0;205 }206 {207 std::string a[] = {str1, str1, str, str1, str1};208 auto whole =209 std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5)));210 bool ret = std::ranges::contains(whole, +"hello world", [&](const std::string i) {211 ++projection_count;212 return i;213 });214 assert(ret);215 assert(projection_count == 3);216 }217 }218 219 { // check invocations of the projection for non-contiguous iterators220 std::vector<bool> whole{false, false, true, false};221 int projection_count = 0;222 {223 bool ret = std::ranges::contains(whole.begin(), whole.end(), true, [&](bool b) {224 ++projection_count;225 return b;226 });227 assert(ret);228 assert(projection_count == 3);229 projection_count = 0;230 }231 {232 bool ret = std::ranges::contains(whole, true, [&](bool b) {233 ++projection_count;234 return b;235 });236 assert(ret);237 assert(projection_count == 3);238 }239 }240 241 { // check invocations of the projection for views::transform242 int a[] = {1, 2, 3, 4, 5};243 int projection_count = 0;244 auto square_number = a | std::views::transform([](int x) { return x * x; });245 {246 bool ret = std::ranges::contains(square_number.begin(), square_number.end(), 16, [&](int i) {247 ++projection_count;248 return i;249 });250 assert(ret);251 assert(projection_count == 4);252 projection_count = 0;253 }254 {255 bool ret = std::ranges::contains(square_number, 16, [&](int i) {256 ++projection_count;257 return i;258 });259 assert(ret);260 assert(projection_count == 4);261 }262 }263 264 return true;265}266 267// test for non-contiguous containers268bool test_nonconstexpr() {269 std::list<int> a = {7, 5, 0, 16, 8};270 int projection_count = 0;271 {272 bool ret = std::ranges::contains(a.begin(), a.end(), 0, [&](int i) {273 ++projection_count;274 return i;275 });276 assert(ret);277 assert(projection_count == 3);278 projection_count = 0;279 }280 {281 bool ret = std::ranges::contains(a, 0, [&](int i) {282 ++projection_count;283 return i;284 });285 assert(ret);286 assert(projection_count == 3);287 }288 289 return true;290}291 292int main(int, char**) {293 test();294 static_assert(test());295 296 assert(test_nonconstexpr());297 298 return 0;299}300