// Types used in iterator implementation -*- C++ -*-
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
-// Free Software Foundation, Inc.
+// Copyright (C) 2001-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
+// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
-// You should have received a copy of the GNU General Public License along
-// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
-// USA.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
-// As a special exception, you may use this file as part of a free software
-// library without restriction. Specifically, if other files instantiate
-// templates or use macros or inline functions from this file, or you compile
-// this file and link it with other files to produce an executable, this
-// file does not by itself cause the resulting executable to be covered by
-// the GNU General Public License. This exception does not however
-// invalidate any other reasons why the executable file might be covered by
-// the GNU General Public License.
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
/*
*
* purpose. It is provided "as is" without express or implied warranty.
*/
-/** @file stl_iterator_base_types.h
+/** @file bits/stl_iterator_base_types.h
* This is an internal header file, included by other library headers.
- * You should not attempt to use it directly.
+ * Do not attempt to use it directly. @headername{iterator}
*
* This file contains all of the general iterator-related utility types,
* such as iterator_traits and struct iterator.
#pragma GCC system_header
#include <bits/c++config.h>
-#include <cstddef>
-_GLIBCXX_BEGIN_NAMESPACE(std)
+#if __cplusplus >= 201103L
+# include <type_traits> // For __void_t, is_convertible
+#endif
+
+#if __cplusplus > 201703L && __cpp_concepts
+# include <bits/iterator_concepts.h>
+#endif
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ /**
+ * @defgroup iterators Iterators
+ * Abstractions for uniform iterating through various underlying types.
+ */
+ //@{
- //@{
/**
* @defgroup iterator_tags Iterator Tags
* These are empty types, used to distinguish different iterators. The
* distinction is not made by what they contain, but simply by what they
* are. Different underlying algorithms can then be used based on the
- * different operations supporetd by different iterator types.
+ * different operations supported by different iterator types.
*/
+ //@{
/// Marking input iterators.
- struct input_iterator_tag {};
+ struct input_iterator_tag { };
+
/// Marking output iterators.
- struct output_iterator_tag {};
+ struct output_iterator_tag { };
+
/// Forward iterators support a superset of input iterator operations.
- struct forward_iterator_tag : public input_iterator_tag {};
+ struct forward_iterator_tag : public input_iterator_tag { };
+
/// Bidirectional iterators support a superset of forward iterator
/// operations.
- struct bidirectional_iterator_tag : public forward_iterator_tag {};
- /// Random-access iterators support a superset of bidirectional iterator
- /// operations.
- struct random_access_iterator_tag : public bidirectional_iterator_tag {};
- //@}
+ struct bidirectional_iterator_tag : public forward_iterator_tag { };
+ /// Random-access iterators support a superset of bidirectional
+ /// iterator operations.
+ struct random_access_iterator_tag : public bidirectional_iterator_tag { };
+
+#if __cplusplus > 201703L
+ /// Contiguous iterators point to objects stored contiguously in memory.
+ struct contiguous_iterator_tag : public random_access_iterator_tag { };
+#endif
+ //@}
/**
* @brief Common %iterator class.
};
/**
+ * @brief Traits class for iterators.
+ *
* This class does nothing but define nested typedefs. The general
- * version simply "forwards" the nested typedefs from the Iterator
+ * version simply @a forwards the nested typedefs from the Iterator
* argument. Specialized versions for pointers and pointers-to-const
* provide tighter, more correct semantics.
*/
+ template<typename _Iterator>
+ struct iterator_traits;
+
+#if __cplusplus >= 201103L
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 2408. SFINAE-friendly common_type/iterator_traits is missing in C++14
+ template<typename _Iterator, typename = __void_t<>>
+ struct __iterator_traits { };
+
+#if ! __cpp_lib_concepts
+
+ template<typename _Iterator>
+ struct __iterator_traits<_Iterator,
+ __void_t<typename _Iterator::iterator_category,
+ typename _Iterator::value_type,
+ typename _Iterator::difference_type,
+ typename _Iterator::pointer,
+ typename _Iterator::reference>>
+ {
+ 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;
+ };
+#endif // ! concepts
+
+ template<typename _Iterator>
+ struct iterator_traits
+ : public __iterator_traits<_Iterator> { };
+
+#else // ! C++11
template<typename _Iterator>
struct iterator_traits
{
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
+#endif // C++11
+#if __cplusplus > 201703L
+ /// Partial specialization for object pointer types.
+ template<typename _Tp>
+#if __cpp_concepts
+ requires is_object_v<_Tp>
+#endif
+ struct iterator_traits<_Tp*>
+ {
+ using iterator_concept = contiguous_iterator_tag;
+ using iterator_category = random_access_iterator_tag;
+ using value_type = remove_cv_t<_Tp>;
+ using difference_type = ptrdiff_t;
+ using pointer = _Tp*;
+ using reference = _Tp&;
+ };
+#else
+ /// Partial specialization for pointer types.
template<typename _Tp>
struct iterator_traits<_Tp*>
{
typedef _Tp& reference;
};
+ /// Partial specialization for const pointer types.
template<typename _Tp>
struct iterator_traits<const _Tp*>
{
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
+#endif
/**
* This function is not a part of the C++ standard but is syntactic
* sugar for internal library use only.
*/
template<typename _Iter>
- inline typename iterator_traits<_Iter>::iterator_category
+ inline _GLIBCXX_CONSTEXPR
+ typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{ return typename iterator_traits<_Iter>::iterator_category(); }
-_GLIBCXX_END_NAMESPACE
+ //@}
-#endif /* _STL_ITERATOR_BASE_TYPES_H */
+#if __cplusplus >= 201103L
+ template<typename _Iter>
+ using __iterator_category_t
+ = typename iterator_traits<_Iter>::iterator_category;
+
+ template<typename _InIter>
+ using _RequireInputIter =
+ __enable_if_t<is_convertible<__iterator_category_t<_InIter>,
+ input_iterator_tag>::value>;
+ template<typename _It,
+ typename _Cat = __iterator_category_t<_It>>
+ struct __is_random_access_iter
+ : is_base_of<random_access_iterator_tag, _Cat>
+ {
+ typedef is_base_of<random_access_iterator_tag, _Cat> _Base;
+ enum { __value = _Base::value };
+ };
+#else
+ template<typename _It, typename _Traits = iterator_traits<_It>,
+ typename _Cat = typename _Traits::iterator_category>
+ struct __is_random_access_iter
+ { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; };
+#endif
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
+
+#endif /* _STL_ITERATOR_BASE_TYPES_H */