contiguous_iterator.h 4.1 KB

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