contiguous_iterator.h (4559B)
1 // Copyright 2020 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_CONTAINERS_CONTIGUOUS_ITERATOR_H_ 6 #define BASE_CONTAINERS_CONTIGUOUS_ITERATOR_H_ 7 8 #include <array> 9 #include <iterator> 10 #include <string> 11 #include <type_traits> 12 #include <vector> 13 14 #include "base/containers/checked_iterators.h" 15 16 namespace base { 17 18 namespace internal { 19 20 template <typename T> 21 struct PointsToObject : std::true_type {}; 22 // std::iter_value_t is not defined for `T*` where T is not an object type. 23 template <typename T> 24 struct PointsToObject<T*> : std::is_object<T> {}; 25 26 // A pointer is a contiguous iterator. 27 // Reference: https://wg21.link/iterator.traits#5 28 template <typename T> 29 struct IsPointer : std::is_pointer<T> {}; 30 31 template <typename T, typename StringT = std::basic_string<iter_value_t<T>>> 32 struct IsStringIterImpl 33 : std::disjunction<std::is_same<T, typename StringT::const_iterator>, 34 std::is_same<T, typename StringT::iterator>> {}; 35 36 // An iterator to std::basic_string is contiguous. 37 // Reference: https://wg21.link/basic.string.general#2 38 // 39 // Note: Requires indirection via `IsStringIterImpl` to avoid triggering a 40 // `static_assert(is_trivial_v<value_type>)` inside libc++'s std::basic_string. 41 template <typename T> 42 struct IsStringIter 43 : std::conjunction< 44 std::disjunction<std::is_same<iter_value_t<T>, char>, 45 std::is_same<iter_value_t<T>, wchar_t>, 46 #if !defined(MOZ_SANDBOX) 47 std::is_same<iter_value_t<T>, char8_t>, 48 #endif 49 std::is_same<iter_value_t<T>, char16_t>, 50 std::is_same<iter_value_t<T>, char32_t>>, 51 IsStringIterImpl<T>> {}; 52 53 // An iterator to std::array is contiguous. 54 // Reference: https://wg21.link/array.overview#1 55 template <typename T, typename ArrayT = std::array<iter_value_t<T>, 1>> 56 struct IsArrayIter 57 : std::disjunction<std::is_same<T, typename ArrayT::const_iterator>, 58 std::is_same<T, typename ArrayT::iterator>> {}; 59 60 // An iterator to a non-bool std::vector is contiguous. 61 // Reference: https://wg21.link/vector.overview#2 62 template <typename T, typename VectorT = std::vector<iter_value_t<T>>> 63 struct IsVectorIter 64 : std::conjunction< 65 std::negation<std::is_same<iter_value_t<T>, bool>>, 66 std::disjunction<std::is_same<T, typename VectorT::const_iterator>, 67 std::is_same<T, typename VectorT::iterator>>> {}; 68 69 // The result of passing a std::valarray to std::begin is a contiguous iterator. 70 // Note: Since all common standard library implementations (i.e. libc++, 71 // stdlibc++ and MSVC's STL) just use a pointer here, we perform a similar 72 // optimization. The corresponding unittest still ensures that this is working 73 // as intended. 74 // Reference: https://wg21.link/valarray.range#1 75 template <typename T> 76 struct IsValueArrayIter : std::is_pointer<T> {}; 77 78 // base's CheckedContiguousIterator is a contiguous iterator. 79 template <typename T, typename ValueT = iter_value_t<T>> 80 struct IsCheckedContiguousIter 81 : std::disjunction< 82 std::is_same<T, base::CheckedContiguousConstIterator<ValueT>>, 83 std::is_same<T, base::CheckedContiguousIterator<ValueT>>> {}; 84 85 // Check that the iterator points to an actual object, and is one of the 86 // iterator types mentioned above. 87 template <typename T, bool B = PointsToObject<T>::value> 88 struct IsContiguousIteratorImpl : std::false_type {}; 89 template <typename T> 90 struct IsContiguousIteratorImpl<T, true> 91 : std::disjunction<IsPointer<T>, 92 IsStringIter<T>, 93 IsArrayIter<T>, 94 IsVectorIter<T>, 95 IsValueArrayIter<T>, 96 IsCheckedContiguousIter<T>> {}; 97 98 } // namespace internal 99 100 // IsContiguousIterator is a type trait that determines whether a given type is 101 // a contiguous iterator. It is similar to C++20's contiguous_iterator concept, 102 // but due to a lack of the corresponding contiguous_iterator_tag relies on 103 // explicitly instantiating the type with iterators that are supposed to be 104 // contiguous iterators. 105 // References: 106 // - https://wg21.link/iterator.concept.contiguous 107 // - https://wg21.link/std.iterator.tags#lib:contiguous_iterator_tag 108 // - https://wg21.link/n4284 109 template <typename T> 110 struct IsContiguousIterator 111 : internal::IsContiguousIteratorImpl<remove_cvref_t<T>> {}; 112 113 } // namespace base 114 115 #endif // BASE_CONTAINERS_CONTIGUOUS_ITERATOR_H_