迭代器定义
在C++ STL
(Standard Template Library,标准模板库)中,迭代器是一个非常重要的组成部分。迭代器像是一个指针,负责在容器的元素之间移动,并且能够访问到容器的元素。
C++ STL
提供了几种类型的迭代器,每种迭代器都有它独特的功能和特性:
- 输入迭代器(Input Iterators):只读不写,只能单向移动(自增++)。
- 输出迭代器(Output Iterators):只写不读,只能单向移动(自增++)。
- 前向迭代器(Forward Iterators):可读写,只能单向移动(自增++)。
- 双向迭代器(Bidirectional Iterators):可读写,可以双向移动(自增++,自减–)。
- 随机访问迭代器(Random Access Iterators):可读写,支持全部迭代器运算。可以进行任意跳跃的访问。
在使用时,可以像操作指针一样通过*
操作符来操作迭代器访问元素,例如*iter
。STL
中的标准容器像是vector
、list
、map
等都支持迭代器,你可以创建相应的迭代器来进行遍历操作。
例如:
std::vector<int> vec = {1, 2, 3, 4, 5};
for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << std::endl;
}
在这个例子中,vec.begin()
返回一个指向vector
开始的迭代器,vec.end()
返回一个指向vector
结尾后一位置的迭代器。这是STL
的一种惯用方式,end()
迭代器并不指向任何元素,它用来提供一种方便的判断遍历是否结束的条件。
迭代器的种类
输入迭代器 | 提供对数据的只读访问 | 支持++、==、!= |
---|---|---|
输出迭代器 | 提供对数据的只写访问 | 支持++ |
前向迭代器 | 提供读写操作,并能将迭代器向前推进 | 支持++、==、!= |
双向迭代器 | 提供读写操作,并能将迭代器向前推进也能向后推进 | 支持++、– |
随机访问迭代器 | 提供读写操作,并能任意位置访问容器,是功能最强的迭代器 | 支持++、–、[n]、-n、>、<、>=、<= |
手撕代码
类型信息定义
#ifndef __TYPE_TRAITS_HPP__
#define __TYPE_TRAITS_HPP__
// 这个头文件用于提取类型信息
#include <type_traits>
#include <utility>
namespace Stl
{
template <class T, T v>
struct m_integral_constant
{
static constexpr T value = v;
};
template <bool b>
using m_bool_constant = m_integral_constant<bool, b>;
typedef m_bool_constant<true> m_true_type;
typedef m_bool_constant<false> m_false_type;
// is_pair
// --- forward declaration end
template <class T>
struct is_pair : Stl::m_false_type
{
};
template <class T1, class T2>
struct is_pair<std::pair<T1, T2>> : Stl::m_true_type
{
};
}
#endif /* __TYPE_TRAITS_HPP__ */
迭代器设计
#ifndef __ITERATOR_HPP__
#define __ITERATOR_HPP__
// 这个头文件用于迭代器设计,包含了一些模板结构体与全局函数,
#include <cstddef>
#include "type_traits.hpp"
namespace Stl
{
// 五种迭代器类型
// 输入迭代器
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
{
};
// iterator 模板
template <class Category, class T, class Distance = ptrdiff_t,
class Pointer = T *, class Reference = T &>
struct iterator
{
typedef Category iterator_category; // 迭代器类型标签
typedef T value_type; // 所指对象类型
typedef Pointer pointer; // 指针类型
typedef Reference reference; // 引用类型
typedef Distance difference_type; // 两个迭代器之间距离的类型,通常是ptrdiff_t
};
// iterator traits
// 检查是否有迭代器类型标签
template <class T>
struct has_iterator_cat
{
private:
struct two
{
char a;
char b;
};
template <class U>
static two test(...);
template <class U>
static char test(typename U::iterator_category * = 0);
public:
static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <class Iterator, bool>
struct iterator_traits_impl
{
};
template <class Iterator>
struct iterator_traits_impl<Iterator, true>
{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::difference_type difference_type;
};
template <class Iterator, bool>
struct iterator_traits_helper
{
};
template <class Iterator>
struct iterator_traits_helper<Iterator, true>
: public iterator_traits_impl<Iterator,
std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value>
{
};
// 萃取迭代器的特性
template <class Iterator>
struct iterator_traits
: public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value>
{
};
// 针对原生指针的偏特化版本
// 辅助函数来访问迭代器的属性
template <class T>
struct iterator_traits<T *>
{
typedef random_access_iterator_tag iterator_category; // 获取迭代器类型标签
typedef T value_type; // 获取所指对象类型
typedef T *pointer; // 获取指针类型
typedef T &reference; // 获取引用类型
typedef ptrdiff_t difference_type; // 获取距离类型
};
template <class T>
struct iterator_traits<const T *>
{
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
typedef ptrdiff_t difference_type;
};
// 检查迭代器类型标签是否匹配
template <class T, class U, bool = has_iterator_cat<iterator_traits<T>>::value>
struct has_iterator_cat_of
: public m_bool_constant<std::is_convertible<
typename iterator_traits<T>::iterator_category, U>::value>
{
};
// 萃取某种迭代器
template <class T, class U>
struct has_iterator_cat_of<T, U, false> : public m_false_type
{
};
// 检查是否为输入迭代器
template <class Iter>
struct is_input_iterator : public has_iterator_cat_of<Iter, input_iterator_tag>
{
};
// 检查是否为输出迭代器
template <class Iter>
struct is_output_iterator : public has_iterator_cat_of<Iter, output_iterator_tag>
{
};
// 检查是否为前向迭代器
template <class Iter>
struct is_forward_iterator : public has_iterator_cat_of<Iter, forward_iterator_tag>
{
};
// 检查是否为双向迭代器
template <class Iter>
struct is_bidirectional_iterator : public has_iterator_cat_of<Iter, bidirectional_iterator_tag>
{
};
// 检查是否为随机访问迭代器
template <class Iter>
struct is_random_access_iterator : public has_iterator_cat_of<Iter, random_access_iterator_tag>
{
};
// 检查是否为迭代器(输入或输出)
template <class Iterator>
struct is_iterator : public m_bool_constant<is_input_iterator<Iterator>::value ||
is_output_iterator<Iterator>::value>
{
};
// 萃取某个迭代器的 category
template <class Iterator>
typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator &)
{
typedef typename iterator_traits<Iterator>::iterator_category Category;
return Category();
}
// 萃取某个迭代器的 distance_type
template <class Iterator>
typename iterator_traits<Iterator>::difference_type *
distance_type(const Iterator &)
{
return static_cast<typename iterator_traits<Iterator>::difference_type *>(0);
}
// 萃取某个迭代器的 value_type
template <class Iterator>
typename iterator_traits<Iterator>::value_type *
value_type(const Iterator &)
{
return static_cast<typename iterator_traits<Iterator>::value_type *>(0);
}
// 以下函数用于计算迭代器间的距离
// distance 的 input_iterator_tag 的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
typename iterator_traits<InputIterator>::difference_type n = 0;
while (first != last)
{
++first;
++n;
}
return n;
}
// distance 的 random_access_iterator_tag 的版本
template <class RandomIter>
typename iterator_traits<RandomIter>::difference_type
distance_dispatch(RandomIter first, RandomIter last,
random_access_iterator_tag)
{
return last - first;
}
// 计算两个迭代器之间的距离
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
return distance_dispatch(first, last, iterator_category(first));
}
// 以下函数用于让迭代器前进 n 个距离
// advance 的 input_iterator_tag 的版本
template <class InputIterator, class Distance>
void advance_dispatch(InputIterator &i, Distance n, input_iterator_tag)
{
while (n--)
++i;
}
// advance 的 bidirectional_iterator_tag 的版本
template <class BidirectionalIterator, class Distance>
void advance_dispatch(BidirectionalIterator &i, Distance n, bidirectional_iterator_tag)
{
if (n >= 0)
while (n--)
++i;
else
while (n++)
--i;
}
// advance 的 random_access_iterator_tag 的版本
template <class RandomIter, class Distance>
void advance_dispatch(RandomIter &i, Distance n, random_access_iterator_tag)
{
i += n;
}
// 将迭代器前进指定步数
template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n)
{
advance_dispatch(i, n, iterator_category(i));
}
/*****************************************************************************************/
// 模板类 : reverse_iterator
// 代表反向迭代器,使前进为后退,后退为前进
template <class Iterator>
class reverse_iterator
{
private:
Iterator current; // 记录对应的正向迭代器
public:
// 反向迭代器的五种相应型别
typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
typedef typename iterator_traits<Iterator>::value_type value_type;
typedef typename iterator_traits<Iterator>::difference_type difference_type;
typedef typename iterator_traits<Iterator>::pointer pointer;
typedef typename iterator_traits<Iterator>::reference reference;
typedef Iterator iterator_type;
typedef reverse_iterator<Iterator> self;
public:
// 构造函数
reverse_iterator() {}
explicit reverse_iterator(iterator_type i) : current(i) {}
reverse_iterator(const self &rhs) : current(rhs.current) {}
public:
// 取出对应的正向迭代器
iterator_type base() const
{
return current;
}
// 重载操作符
reference operator*() const
{ // 实际对应正向迭代器的前一个位置
auto tmp = current;
return *--tmp;
}
pointer operator->() const
{
return &(operator*());
}
// 前进(++)变为后退(--)
self &operator++()
{
--current;
return *this;
}
self operator++(int)
{
self tmp = *this;
--current;
return tmp;
}
// 后退(--)变为前进(++)
self &operator--()
{
++current;
return *this;
}
self operator--(int)
{
self tmp = *this;
++current;
return tmp;
}
self &operator+=(difference_type n)
{
current -= n;
return *this;
}
self operator+(difference_type n) const
{
return self(current - n);
}
self &operator-=(difference_type n)
{
current += n;
return *this;
}
self operator-(difference_type n) const
{
return self(current + n);
}
reference operator[](difference_type n) const
{
return *(*this + n);
}
};
// 重载 operator-
template <class Iterator>
typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return rhs.base() - lhs.base();
}
// 重载比较操作符
template <class Iterator>
bool operator==(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return lhs.base() == rhs.base();
}
template <class Iterator>
bool operator<(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return rhs.base() < lhs.base();
}
template <class Iterator>
bool operator!=(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return !(lhs == rhs);
}
template <class Iterator>
bool operator>(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return rhs < lhs;
}
template <class Iterator>
bool operator<=(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return !(rhs < lhs);
}
template <class Iterator>
bool operator>=(const reverse_iterator<Iterator> &lhs,
const reverse_iterator<Iterator> &rhs)
{
return !(lhs < rhs);
}
} // namespace mystl
#endif /* __ITERATOR_HPP__ */
源码解析 :
定义了五个迭代器标签类:
-
input_iterator_tag:输入迭代器
-
output_iterator_tag:输出迭代器
-
forward_iterator_tag:前向迭代器,继承自输入迭代器
-
bidirectional_iterator_tag:双向迭代器,继承自前向迭代器
-
random_access_iterator_tag:随机访问迭代器, 继承自双向迭代器
定义了一个迭代器模板类 iterator,其中包含以下类型别名:
-
iterator_category:迭代器类型标签
-
value_type:所指对象类型
-
pointer:指针类型
-
reference:引用类型
-
difference_type
:两个迭代器之间距离的类型,通常是ptrdiff_t
定义了一个迭代器 traits 模板类 iterator_traits,它提供一些辅助函数来访问迭代器的属性,例如:
-
iterator_category:获取迭代器类型标签
-
value_type:获取所指对象类型
-
pointer:获取指针类型
-
reference:获取引用类型
-
difference_type:获取距离类型
定义了一些类型判断模板类:
-
has_iterator_cat:检查是否有迭代器类型标签
-
has_iterator_cat_of:检查迭代器类型标签是否匹配
-
is_input_iterator:检查是否为输入迭代器
-
is_output_iterator:检查是否为输出迭代器
-
is_forward_iterator:检查是否为前向迭代器
-
is_bidirectional_iterator:检查是否为双向迭代器
-
is_random_access_iterator:检查是否为随机访问迭代器
-
is_iterator:检查是否为迭代器(输入或输出)
定义了一些迭代器操作函数:
-
distance:计算两个迭代器之间的距离
-
advance:将迭代器前进指定步数文章来源:https://www.toymoban.com/news/detail-518597.html
-
reverse_iterator:一个反向迭代器模板类,可以通过它来实现反向遍历文章来源地址https://www.toymoban.com/news/detail-518597.html
到了这里,关于【c++手撕STL】之迭代器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!