/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996-1998
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H
#define __SGI_STL_INTERNAL_ITERATOR_BASE_H
// This file contains all of the general iterator-related utilities.
// The internal file stl_iterator.h contains predefined iterators,
// such as front_insert_iterator and istream_iterator.
#include <concept_checks.h>
__STL_BEGIN_NAMESPACE
// 首先，必须明白，迭代器实际上是智能指针
// 迭代器最重要的編程工作就是對operator* 和 operator-> 進行多載化（overloading）工程
// iterator_traits 是标准的 STL 的迭代器规范，获得的仅仅是关于 {迭代器的特征}，
// ######## 注意对比， SGI 实现的 __type_traits 是另一种东西，它获得的是{型别特征}
// 定义的特征类型：
// 每个自定义的容器都应该支持 iterator_category 的嵌套定义类型标志。
// 以下为已知的几种迭代器的类型。
// 模板借由此标志，优化对迭代器的操作。
// 这里另一个实作技巧，重点：
// 任何一个迭代器，其类型永远应该落在{该迭代器所隶属之各种类型中}，最强化了的那个。
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 {}; // 允许随机访问
// The base classes input_iterator, output_iterator, forward_iterator,
// bidirectional_iterator, and random_access_iterator are not part of
// the C++ standard. (They have been replaced by struct iterator.)
// They are included for backward compatibility with the HP STL.
// 只读的迭代器
template <class _Tp, class _Distance> struct input_iterator {
typedef input_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// 只写的迭代器
struct output_iterator {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
// 可读写的迭代器
template <class _Tp, class _Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// 双向访问迭代器 ++ p ; p ++; -- p; p --;
template <class _Tp, class _Distance> struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// 随机访问迭代器，支持 p+n, p-n, p[n], p1-p2, p1<p2
template <class _Tp, class _Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// 一个辅助的结构定义，辅助方便为自己写的（非STL已经提供的）类提供 特征获取
// 否则无法与 STL 架构相容（即参与不了STL实现的算法，这些算法需要容器，提供这五种特征供 traits 萃取）
// 一般来说，只要继承这个类，然后指明前两个模板参数，后面的三个均带有默认值
#ifdef __STL_USE_NAMESPACES
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type; // 指迭代器所指物件的型別
typedef _Distance difference_type; // 用來表示兩個迭代器之間的距离
typedef _Pointer pointer; // 提供了指针形式的左值传递的方法，用 *p = 1; 访问
typedef _Reference reference; // 提供了引用左值传递的方法，用 p[0] = 1; 访问
};
// 注意左值和右值：
// 左值在 C++ 定义为返回值引用，操作的是原数据的地址空间内容;
// 即 list::iterator p; *p = 1; 访问的是 T&
// 或者 list::const_iterator p; *p = 1; 访问的是 const T&
// 而右值被定义为返回值，这只是一个临时的内存空间，改不了原数据。 int ll = *p; 在访问 T 而不是 T&
// 定义为指针访问时，同引用方式：
// list::pointer p; *p = 1; 在使用 const / T& 返回
// 而单纯地
#endif /* __STL_USE_NAMESPACES */
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
// STL 的五种类型特征的 榨汁机 : )，需要编译器提供偏特化支持
// 一般来说，它使用默认迭代器提供的类型定义
template <class _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 <class _Tp>
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
// 这是 const 指针
template <class _Tp>
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
// The overloaded functions iterator_category, distance_type, and
// value_type are not part of the C++ standard. (They have been
// replaced by struct iterator_traits.) They are included for
// backward compatibility with the HP STL.
// We introduce internal names for these functions.
// 这里是说HP 为了兼容后面的，不知其所指
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)
{
return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}
// 这个函式直接返回迭代器的类型：
// 实际上它调用 __iterator_category，从而构建了一个 iterator_category类型的实例
// 小技巧：可以看到，STL写的代码比较细，这里全是用的 const + & 传值
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return __iterator_category(__i); } // 这个是正常的，返回类型
// 返回迭代器的 difference_type：
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
distance_type(const _Iter& __i) { return __distance_type(__i); } // 奇怪，它竟然返回是指针类型
// 返回迭代器的 value type：
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
value_type(const _Iter& __i) { return __value_type(__i); } // 奇怪，它竟然返回是指针类型
// 更简单的宏写法，含义同上面一致的
#define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
#define __DISTANCE_TYPE(__i) __distance_type(__i)
#define __VALUE_TYPE(__i) __value_type(__i)
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// 这里又整了一套，在不支持模板部分修饰的情况下工作
// 无法模板部分修饰，就没办法使用 iterator_traits， 因为它巧妙运用了模板部分修饰来榨取类型信息
// 这里是一个一个写的，
/// iterator_category ////////////////////////////////////////////////////
template <class _Tp, class _Distance>
inline input_iterator_tag
iterator_category(const input_iterator<_Tp, _Distance>&)
{ return input_iterator_tag(); }
inline output_iterator_tag
iterator_category(const output_iterator&)
{ return output_iterator_tag(); }
template <class _Tp, class _Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<_Tp, _Distance>&)
{ return forward_iterator_tag(); }
template <class _Tp, class _Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
{ return bidirectional_iterator_tag(); }
template <class _Tp, class _Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<_Tp, _Distance>&)
{ return random_access_iterator_tag(); }
template <class _Tp>
inline random_access_iterator_tag iterator_category(const _Tp*)
{ return random_access_iterator_tag(); }
/// value_type ////////////////////////////////////////////////////
template <class _Tp, class _Distance>
inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp>
inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
/// distance_type ////////////////////////////////////////////////////
template <class _Tp, class _Distance>
inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const bidirectional_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const random_access_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp>
inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
// Without partial specialization we can't use iterator_traits, so
// we must keep the old iterator query functions around.
#define __ITERATOR_CATEGORY(__i) iterator_category(__i)
#define __DISTANCE_TYPE(__i) distance_type(__i)
#define __VALUE_TYPE(__i) value_type(__i)
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// 首先，这里用到了 __STL_REQUIRES 宏，它在未打开 __STL_USE_CONCEPT_CHECKS 开关时定义为空
// distance 先定义了一种通过引用方式的返回值：由于特例化模板修饰，它最终被分为两个调用方向
// 征对一般的
template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
_Distance& __n, input_iterator_tag)
{
while (__first != __last) { ++__first; ++__n; }
}
// 偏特化了支持随机访问的，它可以直接减
template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Distance& __n, random_access_iterator_tag)
{
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__n += __last - __first;
}
// 这是直接要调用的模板函数，它被 iterator_category 技法分开模板调用的实际内容
template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first,
_InputIterator __last, _Distance& __n)
{
__STL_REQUIRES(_InputIterator, _InputIterator);
__distance(__first, __last, __n, iterator_category(__first));
}
// 这里是另一种通过返回值来计算距离的模板
// 具体不解释，同上面一种
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) {
++__first; ++__n;
}
return __n;
}
template <class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag) {
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
return __last - __first;
}
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last) {
typedef typename iterator_traits<_InputIterator>::iterator_category
_Category;
__STL_REQUIRES(_InputIterator, _InputIterator);
return __distance(__first, __last, _Category());
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// advance 是整快进或快退的 : )
// _InputIter 这是只有一个正方向的，所以连 __n 的方向都不用判断
template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
while (__n--) ++__i;
}
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1183
#endif
// 双向的，需要先判断往哪边快进
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
if (__n >= 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1183
#endif
// 随机访问的最简单，它直接 + 正值或负值就可以了
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag) {
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__i += __n;
}
// 这是主调用的函数，根据参数类型，偏特化具体的实现
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
__STL_REQUIRES(_InputIterator, _InputIterator);
__advance(__i, __n, iterator_category(__i));
}
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */
// Local Variables:
// mode:C++
// End: