迭代器定義
在C++ STL(Standard Template Library，標(biāo)準(zhǔn)模板庫)中，迭代器是一個(gè)非常重要的組成部分。迭代器像是一個(gè)指針，負(fù)責(zé)在容器的元素之間移動(dòng)，并且能夠訪問到容器的元素。
C++ STL提供了幾種類型的迭代器，每種迭代器都有它獨(dú)特的功能和特性：
- 輸入迭代器（Input Iterators）：只讀不寫，只能單向移動(dòng)（自增++）。
- 輸出迭代器（Output Iterators）：只寫不讀，只能單向移動(dòng)（自增++）。
- 前向迭代器（Forward Iterators）：可讀寫，只能單向移動(dòng)（自增++）。
- 雙向迭代器（Bidirectional Iterators）：可讀寫，可以雙向移動(dòng)（自增++，自減–）。
- 隨機(jī)訪問迭代器（Random Access Iterators）：可讀寫，支持全部迭代器運(yùn)算?？梢赃M(jìn)行任意跳躍的訪問。
在使用時(shí)，可以像操作指針一樣通過*操作符來操作迭代器訪問元素，例如*iter。STL中的標(biāo)準(zhǔn)容器像是vector、list、map等都支持迭代器，你可以創(chuàng)建相應(yīng)的迭代器來進(jìn)行遍歷操作。
例如：
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;
}
在這個(gè)例子中，vec.begin()返回一個(gè)指向vector開始的迭代器，vec.end()返回一個(gè)指向vector結(jié)尾后一位置的迭代器。這是STL的一種慣用方式，end()迭代器并不指向任何元素，它用來提供一種方便的判斷遍歷是否結(jié)束的條件。
迭代器的種類
| 輸入迭代器 | 提供對(duì)數(shù)據(jù)的只讀訪問 | 支持++、==、！= |
|---|---|---|
| 輸出迭代器 | 提供對(duì)數(shù)據(jù)的只寫訪問 | 支持++ |
| 前向迭代器 | 提供讀寫操作，并能將迭代器向前推進(jìn) | 支持++、==、！= |
| 雙向迭代器 | 提供讀寫操作，并能將迭代器向前推進(jìn)也能向后推進(jìn) | 支持++、– |
| 隨機(jī)訪問迭代器 | 提供讀寫操作，并能任意位置訪問容器，是功能最強(qiáng)的迭代器 | 支持++、–、[n]、-n、>、<、>=、<= |
手撕代碼
類型信息定義
#ifndef __TYPE_TRAITS_HPP__
#define __TYPE_TRAITS_HPP__
// 這個(gè)頭文件用于提取類型信息
#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__ */
迭代器設(shè)計(jì)
#ifndef __ITERATOR_HPP__
#define __ITERATOR_HPP__
// 這個(gè)頭文件用于迭代器設(shè)計(jì)，包含了一些模板結(jié)構(gòu)體與全局函數(shù)，
#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
{
};
// 隨機(jī)訪問迭代器
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; // 迭代器類型標(biāo)簽
typedef T value_type; // 所指對(duì)象類型
typedef Pointer pointer; // 指針類型
typedef Reference reference; // 引用類型
typedef Distance difference_type; // 兩個(gè)迭代器之間距離的類型，通常是ptrdiff_t
};
// iterator traits
// 檢查是否有迭代器類型標(biāo)簽
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>
{
};
// 針對(duì)原生指針的偏特化版本
// 輔助函數(shù)來訪問迭代器的屬性
template <class T>
struct iterator_traits<T *>
{
typedef random_access_iterator_tag iterator_category; // 獲取迭代器類型標(biāo)簽
typedef T value_type; // 獲取所指對(duì)象類型
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;
};
// 檢查迭代器類型標(biāo)簽是否匹配
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>
{
};
// 檢查是否為隨機(jī)訪問迭代器
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>
{
};
// 萃取某個(gè)迭代器的 category
template <class Iterator>
typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator &)
{
typedef typename iterator_traits<Iterator>::iterator_category Category;
return Category();
}
// 萃取某個(gè)迭代器的 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);
}
// 萃取某個(gè)迭代器的 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);
}
// 以下函數(shù)用于計(jì)算迭代器間的距離
// 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;
}
// 計(jì)算兩個(gè)迭代器之間的距離
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
return distance_dispatch(first, last, iterator_category(first));
}
// 以下函數(shù)用于讓迭代器前進(jìn) n 個(gè)距離
// 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;
}
// 將迭代器前進(jìn)指定步數(shù)
template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n)
{
advance_dispatch(i, n, iterator_category(i));
}
/*****************************************************************************************/
// 模板類 : reverse_iterator
// 代表反向迭代器，使前進(jìn)為后退，后退為前進(jìn)
template <class Iterator>
class reverse_iterator
{
private:
Iterator current; // 記錄對(duì)應(yīng)的正向迭代器
public:
// 反向迭代器的五種相應(yīng)型別
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:
// 構(gòu)造函數(shù)
reverse_iterator() {}
explicit reverse_iterator(iterator_type i) : current(i) {}
reverse_iterator(const self &rhs) : current(rhs.current) {}
public:
// 取出對(duì)應(yīng)的正向迭代器
iterator_type base() const
{
return current;
}
// 重載操作符
reference operator*() const
{ // 實(shí)際對(duì)應(yīng)正向迭代器的前一個(gè)位置
auto tmp = current;
return *--tmp;
}
pointer operator->() const
{
return &(operator*());
}
// 前進(jìn)(++)變?yōu)楹笸?--)
self &operator++()
{
--current;
return *this;
}
self operator++(int)
{
self tmp = *this;
--current;
return tmp;
}
// 后退(--)變?yōu)榍斑M(jìn)(++)
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__ */
源碼解析 :
定義了五個(gè)迭代器標(biāo)簽類：
-
input_iterator_tag：輸入迭代器
-
output_iterator_tag：輸出迭代器
-
forward_iterator_tag：前向迭代器，繼承自輸入迭代器
-
bidirectional_iterator_tag：雙向迭代器，繼承自前向迭代器
-
random_access_iterator_tag：隨機(jī)訪問迭代器, 繼承自雙向迭代器
定義了一個(gè)迭代器模板類 iterator，其中包含以下類型別名：
-
iterator_category：迭代器類型標(biāo)簽
-
value_type：所指對(duì)象類型
-
pointer：指針類型
-
reference：引用類型
-
difference_type：兩個(gè)迭代器之間距離的類型，通常是ptrdiff_t
定義了一個(gè)迭代器 traits 模板類 iterator_traits，它提供一些輔助函數(shù)來訪問迭代器的屬性，例如：
-
iterator_category：獲取迭代器類型標(biāo)簽
-
value_type：獲取所指對(duì)象類型
-
pointer：獲取指針類型
-
reference：獲取引用類型
-
difference_type：獲取距離類型
定義了一些類型判斷模板類：
-
has_iterator_cat：檢查是否有迭代器類型標(biāo)簽
-
has_iterator_cat_of：檢查迭代器類型標(biāo)簽是否匹配
-
is_input_iterator：檢查是否為輸入迭代器
-
is_output_iterator：檢查是否為輸出迭代器
-
is_forward_iterator：檢查是否為前向迭代器
-
is_bidirectional_iterator：檢查是否為雙向迭代器
-
is_random_access_iterator：檢查是否為隨機(jī)訪問迭代器
-
is_iterator：檢查是否為迭代器（輸入或輸出）
定義了一些迭代器操作函數(shù)：
-
distance：計(jì)算兩個(gè)迭代器之間的距離
-
advance：將迭代器前進(jìn)指定步數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-518597.html
-
reverse_iterator：一個(gè)反向迭代器模板類，可以通過它來實(shí)現(xiàn)反向遍歷文章來源地址http://www.zghlxwxcb.cn/news/detail-518597.html
到了這里，關(guān)于【c++手撕STL】之迭代器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[ C++ ] STL---反向迭代器的模擬實(shí)現(xiàn)](https://imgs.yssmx.com/Uploads/2024/04/852660-1.gif)
![[C++] STL_vector 迭代器失效問題](https://imgs.yssmx.com/Uploads/2024/02/675234-1.png)
