1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// 2dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 3dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// The LLVM Compiler Infrastructure 4dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 5dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// This file is distributed under the University of Illinois Open Source 6dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// License. See LICENSE.TXT for details. 7dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 8dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 9dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 10dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#ifndef LLVM_ADT_ITERATOR_H 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define LLVM_ADT_ITERATOR_H 12dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 13dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <iterator> 14dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <cstddef> 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 16dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace llvm { 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief CRTP base class which implements the entire standard iterator facade 19dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// in terms of a minimal subset of the interface. 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Use this when it is reasonable to implement most of the iterator 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// functionality in terms of a core subset. If you need special behavior or 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// there are performance implications for this, you may want to override the 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// relevant members instead. 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Note, one abstraction that this does *not* provide is implementing 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// subtraction in terms of addition by negating the difference. Negation isn't 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// always information preserving, and I can see very reasonable iterator 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// designs where this doesn't work well. It doesn't really force much added 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// boilerplate anyways. 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Another abstraction that this doesn't provide is implementing increment in 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// terms of addition of one. These aren't equivalent for all iterator 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// categories, and respecting that adds a lot of complexity for little gain. 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <typename DerivedT, typename IteratorCategoryT, typename T, 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename ReferenceT = T &> 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass iterator_facade_base 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReferenceT> { 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesprotected: 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines enum { 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess = 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value, 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsBidirectional = 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinespublic: 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT operator+(DifferenceTypeT n) const { 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '+' operator is only defined for random access iterators."); 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT tmp = *static_cast<const DerivedT *>(this); 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines tmp += n; 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return tmp; 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '+' operator is only defined for random access iterators."); 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return i + n; 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT operator-(DifferenceTypeT n) const { 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '-' operator is only defined for random access iterators."); 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT tmp = *static_cast<const DerivedT *>(this); 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines tmp -= n; 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return tmp; 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator++() { 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return static_cast<DerivedT *>(this)->operator+=(1); 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT operator++(int) { 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT tmp = *static_cast<DerivedT *>(this); 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++*static_cast<DerivedT *>(this); 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return tmp; 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator--() { 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsBidirectional, 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The decrement operator is only defined for bidirectional iterators."); 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return static_cast<DerivedT *>(this)->operator-=(1); 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT operator--(int) { 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsBidirectional, 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The decrement operator is only defined for bidirectional iterators."); 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT tmp = *static_cast<DerivedT *>(this); 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines --*static_cast<DerivedT *>(this); 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return tmp; 94dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator!=(const DerivedT &RHS) const { 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return !static_cast<const DerivedT *>(this)->operator==(RHS); 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator>(const DerivedT &RHS) const { 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Relational operators are only defined for random access iterators."); 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return !static_cast<const DerivedT *>(this)->operator<(RHS) && 105dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines !static_cast<const DerivedT *>(this)->operator==(RHS); 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 107dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator<=(const DerivedT &RHS) const { 108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Relational operators are only defined for random access iterators."); 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return !static_cast<const DerivedT *>(this)->operator>(RHS); 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator>=(const DerivedT &RHS) const { 114dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRandomAccess, 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Relational operators are only defined for random access iterators."); 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return !static_cast<const DerivedT *>(this)->operator<(RHS); 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PointerT operator->() const { 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return &static_cast<const DerivedT *>(this)->operator*(); 122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReferenceT operator[](DifferenceTypeT n) const { 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert(IsRandomAccess, 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Subscripting is only defined for random access iterators."); 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *static_cast<const DerivedT *>(this)->operator+(n); 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief CRTP base class for adapting an iterator to a different type. 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// This class can be used through CRTP to adapt one iterator into another. 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Typically this is done through providing in the derived class a custom \c 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// operator* implementation. Other methods can be overridden as well. 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate < 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename DerivedT, typename WrappedIteratorT, 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename IteratorCategoryT = 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename std::iterator_traits<WrappedIteratorT>::iterator_category, 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename DifferenceTypeT = 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename std::iterator_traits<WrappedIteratorT>::difference_type, 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename PointerT = T *, typename ReferenceT = T &, 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Don't provide these, they are mostly to act as aliases below. 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass iterator_adaptor_base 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : public iterator_facade_base<DerivedT, IteratorCategoryT, T, 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DifferenceTypeT, PointerT, ReferenceT> { 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef typename iterator_adaptor_base::iterator_facade_base BaseT; 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesprotected: 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines WrappedIteratorT I; 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines iterator_adaptor_base() {} 154dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines template <typename U> 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit iterator_adaptor_base( 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines U &&u, 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename std::enable_if< 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines !std::is_base_of<typename std::remove_cv< 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename std::remove_reference<U>::type>::type, 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT>::value, 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines int>::type = 0) 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : I(std::forward<U &&>(u)) {} 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinespublic: 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef DifferenceTypeT difference_type; 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator+=(difference_type n) { 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BaseT::IsRandomAccess, 171dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '+=' operator is only defined for random access iterators."); 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I += n; 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *static_cast<DerivedT *>(this); 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 175dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator-=(difference_type n) { 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BaseT::IsRandomAccess, 178dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '-=' operator is only defined for random access iterators."); 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I -= n; 180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *static_cast<DerivedT *>(this); 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines using BaseT::operator-; 183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines difference_type operator-(const DerivedT &RHS) const { 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BaseT::IsRandomAccess, 186dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The '-' operator is only defined for random access iterators."); 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I - RHS.I; 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 190dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // We have to explicitly provide ++ and -- rather than letting the facade 191dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // forward to += because WrappedIteratorT might not support +=. 192dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines using BaseT::operator++; 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator++() { 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++I; 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *static_cast<DerivedT *>(this); 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines using BaseT::operator--; 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DerivedT &operator--() { 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BaseT::IsBidirectional, 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The decrement operator is only defined for bidirectional iterators."); 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines --I; 203dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *static_cast<DerivedT *>(this); 204dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 205dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator==(const DerivedT &RHS) const { return I == RHS.I; } 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator<(const DerivedT &RHS) const { 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static_assert( 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BaseT::IsRandomAccess, 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Relational operators are only defined for random access iterators."); 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I < RHS.I; 212dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReferenceT operator*() const { return *I; } 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 217dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief An iterator type that allows iterating over the pointees via some 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// other iterator. 219dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// The typical usage of this is to expose a type that iterates over Ts, but 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// which is implemented with some iterator over T*s: 222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \code 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator; 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \endcode 226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <typename WrappedIteratorT, 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename T = typename std::remove_reference< 228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines decltype(**std::declval<WrappedIteratorT>())>::type> 229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstruct pointee_iterator 230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : iterator_adaptor_base< 231dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines pointee_iterator<WrappedIteratorT>, WrappedIteratorT, 232dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename std::iterator_traits<WrappedIteratorT>::iterator_category, 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines T> { 234dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines pointee_iterator() {} 235dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines template <typename U> 236dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines pointee_iterator(U &&u) 237dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 239dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines T &operator*() const { return **this->I; } 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 245