diff options
Diffstat (limited to 'include/EASTL/iterator.h')
| -rw-r--r-- | include/EASTL/iterator.h | 1192 |
1 files changed, 1192 insertions, 0 deletions
diff --git a/include/EASTL/iterator.h b/include/EASTL/iterator.h new file mode 100644 index 0000000..d2dc899 --- /dev/null +++ b/include/EASTL/iterator.h @@ -0,0 +1,1192 @@ +/////////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +/////////////////////////////////////////////////////////////////////////////// + + +#ifndef EASTL_ITERATOR_H +#define EASTL_ITERATOR_H + + +#include <EASTL/internal/config.h> +#include <EASTL/internal/move_help.h> +#include <EASTL/initializer_list.h> + +EA_DISABLE_ALL_VC_WARNINGS(); + +#include <stddef.h> + +EA_RESTORE_ALL_VC_WARNINGS(); + +// If the user has specified that we use std iterator +// categories instead of EASTL iterator categories, +// then #include <iterator>. +#if EASTL_STD_ITERATOR_CATEGORY_ENABLED + EA_DISABLE_ALL_VC_WARNINGS(); + + #include <iterator> + + EA_RESTORE_ALL_VC_WARNINGS(); +#endif + + +EA_DISABLE_VC_WARNING(4619); // There is no warning number 'number'. +EA_DISABLE_VC_WARNING(4217); // Member template functions cannot be used for copy-assignment or copy-construction. + +#if defined(EA_PRAGMA_ONCE_SUPPORTED) + #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. +#endif + + + +namespace eastl +{ + /// iterator_status_flag + /// + /// Defines the validity status of an iterator. This is primarily used for + /// iterator validation in debug builds. These are implemented as OR-able + /// flags (as opposed to mutually exclusive values) in order to deal with + /// the nature of iterator status. In particular, an iterator may be valid + /// but not dereferencable, as in the case with an iterator to container end(). + /// An iterator may be valid but also dereferencable, as in the case with an + /// iterator to container begin(). + /// + enum iterator_status_flag + { + isf_none = 0x00, /// This is called none and not called invalid because it is not strictly the opposite of invalid. + isf_valid = 0x01, /// The iterator is valid, which means it is in the range of [begin, end]. + isf_current = 0x02, /// The iterator is valid and points to the same element it did when created. For example, if an iterator points to vector::begin() but an element is inserted at the front, the iterator is valid but not current. Modification of elements in place do not make iterators non-current. + isf_can_dereference = 0x04 /// The iterator is dereferencable, which means it is in the range of [begin, end). It may or may not be current. + }; + + + + // The following declarations are taken directly from the C++ standard document. + // input_iterator_tag, etc. + // iterator + // iterator_traits + // reverse_iterator + + // Iterator categories + // Every iterator is defined as belonging to one of the iterator categories that + // we define here. These categories come directly from the C++ standard. + #if !EASTL_STD_ITERATOR_CATEGORY_ENABLED // If we are to use our own iterator category definitions... + struct input_iterator_tag { }; + struct output_iterator_tag { }; + struct forward_iterator_tag : public input_iterator_tag { }; + struct bidirectional_iterator_tag : public forward_iterator_tag { }; + struct random_access_iterator_tag : public bidirectional_iterator_tag { }; + struct contiguous_iterator_tag : public random_access_iterator_tag { }; // Extension to the C++ standard. Contiguous ranges are more than random access, they are physically contiguous. + #endif + + + // struct iterator + template <typename Category, typename T, typename Distance = ptrdiff_t, + typename Pointer = T*, typename Reference = T&> + struct iterator + { + typedef Category iterator_category; + typedef T value_type; + typedef Distance difference_type; + typedef Pointer pointer; + typedef Reference reference; + }; + + + // struct iterator_traits + template <typename Iterator> + struct iterator_traits + { + typedef typename Iterator::iterator_category iterator_category; + typedef typename Iterator::value_type value_type; + typedef typename Iterator::difference_type difference_type; + typedef typename Iterator::pointer pointer; + typedef typename Iterator::reference reference; + }; + + template <typename T> + struct iterator_traits<T*> + { + typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category; // To consider: Change this to contiguous_iterator_tag for the case that + typedef T value_type; // EASTL_ITC_NS is "eastl" instead of "std". + typedef ptrdiff_t difference_type; + typedef T* pointer; + typedef T& reference; + }; + + template <typename T> + struct iterator_traits<const T*> + { + typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category; + typedef T value_type; + typedef ptrdiff_t difference_type; + typedef const T* pointer; + typedef const T& reference; + }; + + + + + /// is_iterator_wrapper + /// + /// Tells if an Iterator type is a wrapper type as opposed to a regular type. + /// Relies on the class declaring a typedef called wrapped_iterator_type. + /// + /// Examples of wrapping iterators: + /// reverse_iterator + /// generic_iterator + /// move_iterator + /// Examples of non-wrapping iterators: + /// iterator + /// list::iterator + /// char* + /// + /// Example behavior: + /// is_iterator_wrapper(int*)::value => false + /// is_iterator_wrapper(eastl::array<char>*)::value => false + /// is_iterator_wrapper(eastl::vector<int>::iterator)::value => false + /// is_iterator_wrapper(eastl::generic_iterator<int*>)::value => true + /// is_iterator_wrapper(eastl::move_iterator<eastl::array<int>::iterator>)::value => true + /// + template<typename Iterator> + class is_iterator_wrapper + { + template<typename> + static eastl::no_type test(...); + + template<typename U> + static eastl::yes_type test(typename U::wrapped_iterator_type*, typename eastl::enable_if<eastl::is_class<U>::value>::type* = 0); + + public: + EA_DISABLE_VC_WARNING(6334) + static const bool value = (sizeof(test<Iterator>(NULL)) == sizeof(eastl::yes_type)); + EA_RESTORE_VC_WARNING() + }; + + + /// unwrap_iterator + /// + /// Takes a wrapper Iterator (e.g. move_iterator, reverse_iterator, generic_iterator) instance + /// and returns the wrapped iterator type. If Iterator is not a wrapper (including being a pointer), + /// or is not an iterator, then this function returns it as-is. + /// unwrap_iterator unwraps only a single layer of iterator at a time. You need to call it twice, + /// for example, to unwrap two layers of iterators. + /// + /// Example usage: + /// int* pInt = unwrap_iterator(&pIntArray[15]); + /// int* pInt = unwrap_iterator(generic_iterator(&pIntArray[15])); + /// MyVector::iterator it = unwrap_iterator(myVector.begin()); + /// MyVector::iterator it = unwrap_iterator(move_iterator(myVector.begin())); + /// + template <typename Iterator, bool isWrapper> + struct is_iterator_wrapper_helper + { + typedef Iterator iterator_type; + + static iterator_type get_base(Iterator it) + { return it; } + }; + + + template <typename Iterator> + struct is_iterator_wrapper_helper<Iterator, true> + { + typedef typename Iterator::iterator_type iterator_type; + + static iterator_type get_base(Iterator it) + { return it.base(); } + }; + + template <typename Iterator> + inline typename is_iterator_wrapper_helper<Iterator, eastl::is_iterator_wrapper<Iterator>::value>::iterator_type unwrap_iterator(Iterator it) + { return eastl::is_iterator_wrapper_helper<Iterator, eastl::is_iterator_wrapper<Iterator>::value>::get_base(it); } + + + + /// reverse_iterator + /// + /// From the C++ standard: + /// Bidirectional and random access iterators have corresponding reverse + /// iterator adaptors that iterate through the data structure in the + /// opposite direction. They have the same signatures as the corresponding + /// iterators. The fundamental relation between a reverse iterator and its + /// corresponding iterator i is established by the identity: + /// &*(reverse_iterator(i)) == &*(i - 1). + /// This mapping is dictated by the fact that while there is always a pointer + /// past the end of an array, there might not be a valid pointer before the + /// beginning of an array. + /// + template <typename Iterator> + class reverse_iterator : public iterator<typename eastl::iterator_traits<Iterator>::iterator_category, + typename eastl::iterator_traits<Iterator>::value_type, + typename eastl::iterator_traits<Iterator>::difference_type, + typename eastl::iterator_traits<Iterator>::pointer, + typename eastl::iterator_traits<Iterator>::reference> + { + public: + typedef Iterator iterator_type; + typedef iterator_type wrapped_iterator_type; // This is not in the C++ Standard; it's used by use to identify it as a wrapping iterator type. + typedef typename eastl::iterator_traits<Iterator>::pointer pointer; + typedef typename eastl::iterator_traits<Iterator>::reference reference; + typedef typename eastl::iterator_traits<Iterator>::difference_type difference_type; + + protected: + Iterator mIterator; + + public: + EA_CPP14_CONSTEXPR reverse_iterator() // It's important that we construct mIterator, because if Iterator + : mIterator() { } // is a pointer, there's a difference between doing it and not. + + EA_CPP14_CONSTEXPR explicit reverse_iterator(iterator_type i) + : mIterator(i) { } + + EA_CPP14_CONSTEXPR reverse_iterator(const reverse_iterator& ri) + : mIterator(ri.mIterator) { } + + template <typename U> + EA_CPP14_CONSTEXPR reverse_iterator(const reverse_iterator<U>& ri) + : mIterator(ri.base()) { } + + // This operator= isn't in the standard, but the the C++ + // library working group has tentatively approved it, as it + // allows const and non-const reverse_iterators to interoperate. + template <typename U> + EA_CPP14_CONSTEXPR reverse_iterator<Iterator>& operator=(const reverse_iterator<U>& ri) + { mIterator = ri.base(); return *this; } + + EA_CPP14_CONSTEXPR iterator_type base() const + { return mIterator; } + + EA_CPP14_CONSTEXPR reference operator*() const + { + iterator_type i(mIterator); + return *--i; + } + + EA_CPP14_CONSTEXPR pointer operator->() const + { return &(operator*()); } + + EA_CPP14_CONSTEXPR reverse_iterator& operator++() + { --mIterator; return *this; } + + EA_CPP14_CONSTEXPR reverse_iterator operator++(int) + { + reverse_iterator ri(*this); + --mIterator; + return ri; + } + + EA_CPP14_CONSTEXPR reverse_iterator& operator--() + { ++mIterator; return *this; } + + EA_CPP14_CONSTEXPR reverse_iterator operator--(int) + { + reverse_iterator ri(*this); + ++mIterator; + return ri; + } + + EA_CPP14_CONSTEXPR reverse_iterator operator+(difference_type n) const + { return reverse_iterator(mIterator - n); } + + EA_CPP14_CONSTEXPR reverse_iterator& operator+=(difference_type n) + { mIterator -= n; return *this; } + + EA_CPP14_CONSTEXPR reverse_iterator operator-(difference_type n) const + { return reverse_iterator(mIterator + n); } + + EA_CPP14_CONSTEXPR reverse_iterator& operator-=(difference_type n) + { mIterator += n; return *this; } + + // http://cplusplus.github.io/LWG/lwg-defects.html#386, + // http://llvm.org/bugs/show_bug.cgi?id=17883 + // random_access_iterator operator[] is merely required to return something convertible to reference. + // reverse_iterator operator[] can't necessarily know what to return as the underlying iterator + // operator[] may return something other than reference. + EA_CPP14_CONSTEXPR reference operator[](difference_type n) const + { return mIterator[-n - 1]; } + }; + + + // The C++ library working group has tentatively approved the usage of two + // template parameters (Iterator1 and Iterator2) in order to allow reverse_iterators + // and const_reverse iterators to be comparable. This is a similar issue to the + // C++ defect report #179 regarding comparison of container iterators and const_iterators. + // + // libstdc++ reports that std::relops breaks the usage of two iterator types and if we + // want to support relops then we need to also make versions of each of below with + // a single template parameter to placate std::relops. But relops is hardly used due to + // the troubles it causes and so we are avoiding support here until somebody complains about it. + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator==(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() == b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator<(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() > b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator!=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() != b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator>(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() < b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator<=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() >= b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline bool + operator>=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return a.base() <= b.base(); } + + + template <typename Iterator1, typename Iterator2> + EA_CPP14_CONSTEXPR inline typename reverse_iterator<Iterator1>::difference_type + operator-(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b) + { return b.base() - a.base(); } + + + template <typename Iterator> + EA_CPP14_CONSTEXPR inline reverse_iterator<Iterator> + operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& a) + { return reverse_iterator<Iterator>(a.base() - n); } + + + /// is_reverse_iterator + /// + /// This is a type traits extension utility. + /// Given an iterator, tells if it's a reverse_iterator vs anything else. + /// If it's a reverse iterator wrapped by another iterator then value is false. + /// To consider: Detect that if it's a move_iterator<reverse_iterator> and unwrap + /// move_iterator so we can detect that underneath it's reverse_iterator. + /// + template <typename T> + struct is_reverse_iterator + : public eastl::false_type {}; + + template<typename Iterator> + struct is_reverse_iterator< eastl::reverse_iterator<Iterator> > + : public eastl::true_type {}; + + + + /// unwrap_reverse_iterator + /// + /// Returns Iterator::get_base() if it's a reverse_iterator, else returns Iterator as-is. + /// + /// Example usage: + /// vector<int> intVector; + /// eastl::reverse_iterator<vector<int>::iterator> reverseIterator(intVector.begin()); + /// vector<int>::iterator it = unwrap_reverse_iterator(reverseIterator); + /// + /// Disabled until there is considered a good use for it. + /// template <typename Iterator> + /// inline typename eastl::is_iterator_wrapper_helper<Iterator, eastl::is_reverse_iterator<Iterator>::value>::iterator_type unwrap_reverse_iterator(Iterator it) + /// { return eastl::is_iterator_wrapper_helper<Iterator, eastl::is_reverse_iterator<Iterator>::value>::get_base(it); } + + + + /// move_iterator + /// + /// From the C++11 Standard, section 24.5.3.1: + /// Class template move_iterator is an iterator adaptor with the same behavior as the underlying iterator + /// except that its dereference operator implicitly converts the value returned by the underlying iterator's + /// dereference operator to an rvalue reference. Some generic algorithms can be called with move iterators to + /// replace copying with moving. + + template<typename Iterator> + class move_iterator // Don't inherit from iterator. + { + public: + typedef Iterator iterator_type; + typedef iterator_type wrapped_iterator_type; // This is not in the C++ Standard; it's used by use to identify it as a wrapping iterator type. + typedef iterator_traits<Iterator> traits_type; + typedef typename traits_type::iterator_category iterator_category; + typedef typename traits_type::value_type value_type; + typedef typename traits_type::difference_type difference_type; + typedef Iterator pointer; + typedef value_type&& reference; + + protected: + iterator_type mIterator; + + public: + move_iterator() + : mIterator() + { + } + + explicit move_iterator(iterator_type mi) + : mIterator(mi) { } + + template<typename U> + move_iterator(const move_iterator<U>& mi) + : mIterator(mi.base()) + { + } + + iterator_type base() const + { return mIterator; } + + reference operator*() const + { return eastl::move(*mIterator); } + + pointer operator->() const + { return mIterator; } + + move_iterator& operator++() + { + ++mIterator; + return *this; + } + + move_iterator operator++(int) + { + move_iterator tempMoveIterator = *this; + ++mIterator; + return tempMoveIterator; + } + + move_iterator& operator--() + { + --mIterator; + return *this; + } + + move_iterator operator--(int) + { + move_iterator tempMoveIterator = *this; + --mIterator; + return tempMoveIterator; + } + + move_iterator operator+(difference_type n) const + { return move_iterator(mIterator + n); } + + move_iterator& operator+=(difference_type n) + { + mIterator += n; + return *this; + } + + move_iterator operator-(difference_type n) const + { return move_iterator(mIterator - n); } + + move_iterator& operator-=(difference_type n) + { + mIterator -= n; + return *this; + } + + reference operator[](difference_type n) const + { return eastl::move(mIterator[n]); } + }; + + template<typename Iterator1, typename Iterator2> + inline bool + operator==(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return a.base() == b.base(); } + + + template<typename Iterator1, typename Iterator2> + inline bool + operator!=(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return !(a == b); } + + + template<typename Iterator1, typename Iterator2> + inline bool + operator<(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return a.base() < b.base(); } + + + template<typename Iterator1, typename Iterator2> + inline bool + operator<=(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return !(b < a); } + + + template<typename Iterator1, typename Iterator2> + inline bool + operator>(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return b < a; } + + + template<typename Iterator1, typename Iterator2> + inline bool + operator>=(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) + { return !(a < b); } + + + template<typename Iterator1, typename Iterator2> + inline auto + operator-(const move_iterator<Iterator1>& a, const move_iterator<Iterator2>& b) -> decltype(a.base() - b.base()) + { return a.base() - b.base(); } + + + template<typename Iterator> + inline move_iterator<Iterator> + operator+(typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& a) + { return a + n; } + + + template<typename Iterator> + inline move_iterator<Iterator> make_move_iterator(Iterator i) + { return move_iterator<Iterator>(i); } + + + // make_move_if_noexcept_iterator returns move_iterator<Iterator> if the Iterator is of a noexcept type; + // otherwise returns Iterator as-is. The point of this is to be able to avoid moves that can generate exceptions and instead + // fall back to copies or whatever the default IteratorType::operator* returns for use by copy/move algorithms. + // To consider: merge the conditional expression usage here with the one used by move_if_noexcept, as they are the same condition. + #if EASTL_EXCEPTIONS_ENABLED + template <typename Iterator, typename IteratorType = typename eastl::conditional<eastl::is_nothrow_move_constructible<typename eastl::iterator_traits<Iterator>::value_type>::value || + !eastl::is_copy_constructible<typename eastl::iterator_traits<Iterator>::value_type>::value, + eastl::move_iterator<Iterator>, Iterator>::type> + inline IteratorType make_move_if_noexcept_iterator(Iterator i) + { return IteratorType(i); } + #else + // Else there are no exceptions and thus we always return a move_iterator. + template <typename Iterator> + inline eastl::move_iterator<Iterator> make_move_if_noexcept_iterator(Iterator i) + { return eastl::move_iterator<Iterator>(i); } + #endif + + + + /// is_move_iterator + /// + /// This is a type traits extension utility. + /// Given an iterator, tells if it's a move iterator vs anything else. + /// Example usage (though somewhat useless): + /// template <typename T> + /// bool IsMoveIterator() { return typename eastl::is_move_iterator<T>::value; } + /// + template <typename T> + struct is_move_iterator + : public eastl::false_type {}; + + template<typename Iterator> + struct is_move_iterator< eastl::move_iterator<Iterator> > + : public eastl::true_type {}; + + + /// unwrap_move_iterator + /// + /// Returns Iterator::get_base() if it's a move_iterator, else returns Iterator as-is. + /// + /// Example usage: + /// vector<int> intVector; + /// eastl::move_iterator<vector<int>::iterator> moveIterator(intVector.begin()); + /// vector<int>::iterator it = unwrap_move_iterator(moveIterator); + /// + template <typename Iterator> + inline typename eastl::is_iterator_wrapper_helper<Iterator, eastl::is_move_iterator<Iterator>::value>::iterator_type unwrap_move_iterator(Iterator it) + { return eastl::is_iterator_wrapper_helper<Iterator, eastl::is_move_iterator<Iterator>::value>::get_base(it); } + + + + + /// back_insert_iterator + /// + /// A back_insert_iterator is simply a class that acts like an iterator but when you + /// assign a value to it, it calls push_back on the container with the value. + /// + template <typename Container> + class back_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void> + { + public: + typedef back_insert_iterator<Container> this_type; + typedef Container container_type; + typedef typename Container::const_reference const_reference; + + protected: + Container& container; + + public: + //back_insert_iterator(); // Not valid. Must construct with a Container. + + //back_insert_iterator(const this_type& x) // Compiler-implemented + // : container(x.container) { } + + explicit back_insert_iterator(Container& x) + : container(x) { } + + back_insert_iterator& operator=(const_reference value) + { container.push_back(value); return *this; } + + back_insert_iterator& operator=(typename Container::value_type&& value) + { container.push_back(eastl::move(value)); return *this; } + + back_insert_iterator& operator*() + { return *this; } + + back_insert_iterator& operator++() + { return *this; } // This is by design. + + back_insert_iterator operator++(int) + { return *this; } // This is by design. + + protected: + void operator=(const this_type&){} // Declared to avoid compiler warnings about inability to generate this function. + }; + + + /// back_inserter + /// + /// Creates an instance of a back_insert_iterator. + /// + template <typename Container> + inline back_insert_iterator<Container> + back_inserter(Container& x) + { return back_insert_iterator<Container>(x); } + + + + + /// front_insert_iterator + /// + /// A front_insert_iterator is simply a class that acts like an iterator but when you + /// assign a value to it, it calls push_front on the container with the value. + /// + template <typename Container> + class front_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void> + { + public: + typedef front_insert_iterator<Container> this_type; + typedef Container container_type; + typedef typename Container::const_reference const_reference; + + protected: + Container& container; + + public: + //front_insert_iterator(); // Not valid. Must construct with a Container. + + //front_insert_iterator(const this_type& x) // Compiler-implemented + // : container(x.container) { } + + explicit front_insert_iterator(Container& x) + : container(x) { } + + front_insert_iterator& operator=(const_reference value) + { container.push_front(value); return *this; } + + front_insert_iterator& operator*() + { return *this; } + + front_insert_iterator& operator++() + { return *this; } // This is by design. + + front_insert_iterator operator++(int) + { return *this; } // This is by design. + + protected: + void operator=(const this_type&){} // Declared to avoid compiler warnings about inability to generate this function. + }; + + + /// front_inserter + /// + /// Creates an instance of a front_insert_iterator. + /// + template <typename Container> + inline front_insert_iterator<Container> + front_inserter(Container& x) + { return front_insert_iterator<Container>(x); } + + + + + /// insert_iterator + /// + /// An insert_iterator is like an iterator except that when you assign a value to it, + /// the insert_iterator inserts the value into the container and increments the iterator. + /// + /// insert_iterator is an iterator adaptor that functions as an OutputIterator: + /// assignment through an insert_iterator inserts an object into a container. + /// Specifically, if ii is an insert_iterator, then ii keeps track of a container c and + /// an insertion point p; the expression *ii = x performs the insertion container.insert(p, x). + /// + /// If you assign through an insert_iterator several times, then you will be inserting + /// several elements into the underlying container. In the case of a sequence, they will + /// appear at a particular location in the underlying sequence, in the order in which + /// they were inserted: one of the arguments to insert_iterator's constructor is an + /// iterator p, and the new range will be inserted immediately before p. + /// + template <typename Container> + class insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void> + { + public: + typedef Container container_type; + typedef typename Container::iterator iterator_type; + typedef typename Container::const_reference const_reference; + + protected: + Container& container; + iterator_type it; + + public: + // This assignment operator is defined more to stop compiler warnings (e.g. VC++ C4512) + // than to be useful. However, it does allow an insert_iterator to be assigned to another + // insert iterator provided that they point to the same container. + insert_iterator& operator=(const insert_iterator& x) + { + EASTL_ASSERT(&x.container == &container); + it = x.it; + return *this; + } + + insert_iterator(Container& x, iterator_type itNew) + : container(x), it(itNew) {} + + insert_iterator& operator=(const_reference value) + { + it = container.insert(it, value); + ++it; + return *this; + } + + insert_iterator& operator*() + { return *this; } + + insert_iterator& operator++() + { return *this; } // This is by design. + + insert_iterator& operator++(int) + { return *this; } // This is by design. + + }; // insert_iterator + + + /// inserter + /// + /// Creates an instance of an insert_iterator. + /// + template <typename Container, typename Iterator> + inline eastl::insert_iterator<Container> + inserter(Container& x, Iterator i) + { + typedef typename Container::iterator iterator; + return eastl::insert_iterator<Container>(x, iterator(i)); + } + + + /// is_insert_iterator + /// + /// This is a type traits extension utility. + /// Given an iterator, tells if it's an insert_iterator vs anything else. + /// If it's a insert_iterator wrapped by another iterator then value is false. + /// + template <typename T> + struct is_insert_iterator + : public eastl::false_type {}; + + template<typename Iterator> + struct is_insert_iterator< eastl::insert_iterator<Iterator> > + : public eastl::true_type {}; + + + + + ////////////////////////////////////////////////////////////////////////////////// + /// distance + /// + /// Implements the distance() function. There are two versions, one for + /// random access iterators (e.g. with vector) and one for regular input + /// iterators (e.g. with list). The former is more efficient. + /// + template <typename InputIterator> + EA_CONSTEXPR + inline typename eastl::iterator_traits<InputIterator>::difference_type + distance_impl(InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag) + { + typename eastl::iterator_traits<InputIterator>::difference_type n = 0; + + while(first != last) + { + ++first; + ++n; + } + return n; + } + + template <typename RandomAccessIterator> + EA_CONSTEXPR + inline typename eastl::iterator_traits<RandomAccessIterator>::difference_type + distance_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag) + { + return last - first; + } + + // Special version defined so that std C++ iterators can be recognized by + // this function. Unfortunately, this function treats all foreign iterators + // as InputIterators and thus can seriously hamper performance in the case + // of large ranges of bidirectional_iterator_tag iterators. + //template <typename InputIterator> + //inline typename eastl::iterator_traits<InputIterator>::difference_type + //distance_impl(InputIterator first, InputIterator last, ...) + //{ + // typename eastl::iterator_traits<InputIterator>::difference_type n = 0; + // + // while(first != last) + // { + // ++first; + // ++n; + // } + // return n; + //} + + template <typename InputIterator> + EA_CONSTEXPR + inline typename eastl::iterator_traits<InputIterator>::difference_type + distance(InputIterator first, InputIterator last) + { + typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC; + + return eastl::distance_impl(first, last, IC()); + } + + + + + ////////////////////////////////////////////////////////////////////////////////// + /// advance + /// + /// Implements the advance() function. There are three versions, one for + /// random access iterators (e.g. with vector), one for bidirectional + /// iterators (list) and one for regular input iterators (e.g. with slist). + /// + template <typename InputIterator, typename Distance> + inline void + advance_impl(InputIterator& i, Distance n, EASTL_ITC_NS::input_iterator_tag) + { + while(n--) + ++i; + } + + template <bool signedDistance> + struct advance_bi_impl + { + template <typename BidirectionalIterator, typename Distance> + static void advance_impl(BidirectionalIterator& i, Distance n) // Specialization for unsigned distance type. + { + while(n--) + ++i; + } + }; + + template <> + struct advance_bi_impl<true> + { + template <typename BidirectionalIterator, typename Distance> + static void advance_impl(BidirectionalIterator& i, Distance n) // Specialization for signed distance type. + { + if(n > 0) + { + while(n--) + ++i; + } + else + { + while(n++) + --i; + } + } + }; + + template <typename BidirectionalIterator, typename Distance> + inline void + advance_impl(BidirectionalIterator& i, Distance n, EASTL_ITC_NS::bidirectional_iterator_tag) + { + advance_bi_impl<eastl::is_signed<Distance>::value>::advance_impl(i, n); + } + + template <typename RandomAccessIterator, typename Distance> + inline void + advance_impl(RandomAccessIterator& i, Distance n, EASTL_ITC_NS::random_access_iterator_tag) + { + i += n; + } + + // Special version defined so that std C++ iterators can be recognized by + // this function. Unfortunately, this function treats all foreign iterators + // as InputIterators and thus can seriously hamper performance in the case + // of large ranges of bidirectional_iterator_tag iterators. + //template <typename InputIterator, typename Distance> + //inline void + //advance_impl(InputIterator& i, Distance n, ...) + //{ + // while(n--) + // ++i; + //} + + template <typename InputIterator, typename Distance> + inline void + advance(InputIterator& i, Distance n) + { + typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC; + + eastl::advance_impl(i, n, IC()); + } + + + // eastl::next / eastl::prev + // Return the nth/-nth successor of iterator it. + // + // http://en.cppreference.com/w/cpp/iterator/next + // + template<typename InputIterator> + inline InputIterator + next(InputIterator it, typename eastl::iterator_traits<InputIterator>::difference_type n = 1) + { + eastl::advance(it, n); + return it; + } + + template<typename InputIterator> + inline InputIterator + prev(InputIterator it, typename eastl::iterator_traits<InputIterator>::difference_type n = 1) + { + eastl::advance(it, -n); + return it; + } + + +#if defined(EA_COMPILER_CPP11_ENABLED) && EA_COMPILER_CPP11_ENABLED + + // eastl::data + // + // http://en.cppreference.com/w/cpp/iterator/data + // + template <class Container> + EA_CPP14_CONSTEXPR auto data(Container& c) -> decltype(c.data()) + { return c.data(); } + + template <class Container> + EA_CPP14_CONSTEXPR auto data(const Container& c) -> decltype(c.data()) + { return c.data(); } + + template <class T, size_t N> + EA_CPP14_CONSTEXPR T* data(T(&array)[N]) EA_NOEXCEPT + { return array; } + + template <class E> + EA_CPP14_CONSTEXPR const E* data(std::initializer_list<E> il) EA_NOEXCEPT + { return il.begin(); } + + + // eastl::size + // + // http://en.cppreference.com/w/cpp/iterator/size + // + template <class C> + EA_CPP14_CONSTEXPR auto size(const C& c) -> decltype(c.size()) + { return c.size(); } + + template <class T, size_t N> + EA_CPP14_CONSTEXPR size_t size(const T (&)[N]) EA_NOEXCEPT + { return N; } + + + // eastl::ssize + // + // https://en.cppreference.com/w/cpp/iterator/size + // + template <class T, ptrdiff_t N> + EA_CPP14_CONSTEXPR ptrdiff_t ssize(const T(&)[N]) EA_NOEXCEPT + { return N; } + + template <class C> + EA_CPP14_CONSTEXPR auto ssize(const C& c) + -> eastl::common_type_t<ptrdiff_t, eastl::make_signed_t<decltype(c.size())>> + { + using R = eastl::common_type_t<ptrdiff_t, eastl::make_signed_t<decltype(c.size())>>; + return static_cast<R>(c.size()); + } + + + // eastl::empty + // + // http://en.cppreference.com/w/cpp/iterator/empty + // + template <class Container> + EA_CPP14_CONSTEXPR auto empty(const Container& c) -> decltype(c.empty()) + { return c.empty(); } + + template <class T, size_t N> + EA_CPP14_CONSTEXPR bool empty(const T (&)[N]) EA_NOEXCEPT + { return false; } + + template <class E> + EA_CPP14_CONSTEXPR bool empty(std::initializer_list<E> il) EA_NOEXCEPT + { return il.size() == 0; } + +#endif // defined(EA_COMPILER_CPP11_ENABLED) && EA_COMPILER_CPP11_ENABLED + + + // eastl::begin / eastl::end + // http://en.cppreference.com/w/cpp/iterator/begin + // + // In order to enable eastl::begin and eastl::end, the compiler needs to have conforming support + // for argument-dependent lookup if it supports C++11 range-based for loops. The reason for this is + // that in C++11 range-based for loops result in usage of std::begin/std::end, but allow that to + // be overridden by argument-dependent lookup: + // C++11 Standard, section 6.5.4, paragraph 1. + // "otherwise, begin-expr and end-expr are begin(__range) and end(__range), respectively, + // where begin and end are looked up with argument-dependent lookup (3.4.2). For the + // purposes of this name lookup, namespace std is an associated namespace." + // It turns out that one compiler has a problem: GCC 4.6. That version added support for + // range-based for loops but has broken argument-dependent lookup which was fixed in GCC 4.7. + // + #if (defined(EA_COMPILER_GNUC) && (EA_COMPILER_VERSION == 4006)) + #define EASTL_BEGIN_END_ENABLED 0 + #else + #define EASTL_BEGIN_END_ENABLED 1 + #endif + + #if EASTL_BEGIN_END_ENABLED + template <typename Container> + EA_CPP14_CONSTEXPR inline auto begin(Container& container) -> decltype(container.begin()) + { + return container.begin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto begin(const Container& container) -> decltype(container.begin()) + { + return container.begin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto cbegin(const Container& container) -> decltype(container.begin()) + { + return container.begin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto end(Container& container) -> decltype(container.end()) + { + return container.end(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto end(const Container& container) -> decltype(container.end()) + { + return container.end(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto cend(const Container& container) -> decltype(container.end()) + { + return container.end(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto rbegin(Container& container) -> decltype(container.rbegin()) + { + return container.rbegin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto rbegin(const Container& container) -> decltype(container.rbegin()) + { + return container.rbegin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto rend(Container& container) -> decltype(container.rend()) + { + return container.rend(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto rend(const Container& container) -> decltype(container.rend()) + { + return container.rend(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto crbegin(const Container& container) -> decltype(eastl::rbegin(container)) + { + return container.rbegin(); + } + + template <typename Container> + EA_CPP14_CONSTEXPR inline auto crend(const Container& container) -> decltype(eastl::rend(container)) + { + return container.rend(); + } + + template<typename T, size_t arraySize> + EA_CPP14_CONSTEXPR inline T* begin(T (&arrayObject)[arraySize]) + { + return arrayObject; + } + + template<typename T, size_t arraySize> + EA_CPP14_CONSTEXPR inline T* end(T (&arrayObject)[arraySize]) + { + return (arrayObject + arraySize); + } + + template <typename T, size_t arraySize> + EA_CPP14_CONSTEXPR inline reverse_iterator<T*> rbegin(T (&arrayObject)[arraySize]) + { + return reverse_iterator<T*>(arrayObject + arraySize); + } + + template <typename T, size_t arraySize> + EA_CPP14_CONSTEXPR inline reverse_iterator<T*> rend(T (&arrayObject)[arraySize]) + { + return reverse_iterator<T*>(arrayObject); + } + + template <typename E> + EA_CPP14_CONSTEXPR inline reverse_iterator<const E*> rbegin(std::initializer_list<E> ilist) + { + return eastl::reverse_iterator<const E*>(ilist.end()); + } + + template <typename E> + EA_CPP14_CONSTEXPR inline reverse_iterator<const E*> rend(std::initializer_list<E> ilist) + { + return eastl::reverse_iterator<const E*>(ilist.begin()); + } + + template <typename Iterator> + EA_CPP14_CONSTEXPR reverse_iterator<Iterator> make_reverse_iterator(Iterator i) + { return reverse_iterator<Iterator>(i); } + + #endif // EASTL_BEGIN_END_ENABLED + +} // namespace eastl + + + +// Some compilers (e.g. GCC 4.6) support range-based for loops, but have a bug with +// respect to argument-dependent lookup which results on them unilaterally using std::begin/end +// with range-based for loops. To work around this we #include <iterator> for this case in +// order to make std::begin/end visible to users of <eastl/iterator.h>, for portability. +#if !EASTL_BEGIN_END_ENABLED && !defined(EA_COMPILER_NO_RANGE_BASED_FOR_LOOP) + #include <iterator> +#endif + + + +EA_RESTORE_VC_WARNING(); +EA_RESTORE_VC_WARNING(); + +#endif // Header include guard |