C++ STL 迭代器
了解如何使用 C++ 標(biāo)準(zhǔn)模板庫(kù) (STL) 的容器的關(guān)鍵之一是了解迭代器的工作原理。lists 和maps等容器的行為不像數(shù)組，因此您不能使用for循環(huán)來(lái)遍歷其中的元素。同樣，因?yàn)檫@些容器不能隨機(jī)訪問(wèn)，所以不能使用簡(jiǎn)單的整數(shù)索引。你可以使用迭代器來(lái)引用容器的元素。
STL 容器和算法可以很好地協(xié)同工作的原因是它們彼此一無(wú)所知 - Alex Stepanov
迭代器是類似指針的對(duì)象，它允許程序在不暴露底層表示的情況下順序地遍歷容器的元素。迭代器可以通過(guò)遞增和遞減它們從一個(gè)元素前進(jìn)到下一個(gè)元素。每個(gè)容器類型都有一個(gè)與之關(guān)聯(lián)的不同迭代器。例如，迭代器 forlist<int>聲明為：
std::list<int>::iterator迭代器類別
迭代器分為幾類，因?yàn)椴煌乃惴ㄐ枰褂貌煌牡鳌?/font>例如，該std::copy()算法需要一個(gè)可以通過(guò)遞增來(lái)推進(jìn)的迭代器，而該 std::reverse()算法需要一個(gè)可以遞減的迭代器。在 C++ 語(yǔ)言中，該標(biāo)準(zhǔn)定義了五個(gè)不同的類別。
-
輸入迭代器
- 只讀且只能讀取一次。
- 例子：
std::istream_iterator(istream& is)
-
輸出迭代器
- 只寫
- 例如：
std::ostream_iterator<int> out_it (std::cout,", ");
-
前向迭代器
- 收集輸入+輸出迭代器
- 示例：
std::forward_list::iterator,std::unordered_map::iterator
-
雙向迭代器
- 像前向迭代器，但也有
operator– - 例子：
std::list::iterator
- 像前向迭代器，但也有
-
隨機(jī)訪問(wèn)迭代器
- 已重載
operator[]，指針運(yùn)算 - 例子：
std::vector<int>::iterator。
- 已重載
你可以在此處獲得有關(guān)這些的更多信息
迭代器特征
迭代器特征允許算法以統(tǒng)一的方式訪問(wèn)有關(guān)特定迭代器的信息，以避免在需要遍歷不同樣式的容器時(shí)為每個(gè)特定情況重新實(shí)現(xiàn)所有迭代器。例如，查找元素std::list是O(n)復(fù)雜性，而std::vector隨機(jī)訪問(wèn)元素是O(1)復(fù)雜性（給定索引位置）。算法最好知道可以使用+=運(yùn)算符（隨機(jī)訪問(wèn)）或僅使用++運(yùn)算符（轉(zhuǎn)發(fā)）遍歷容器，以選擇更好的選擇以降低計(jì)算的算法的復(fù)雜度。
迭代器特征如下：
-
difference_type：- 表示迭代器距離的類型
- 迭代器的類型差異
p2 - p1。
-
value_type：- 迭代器指向的值的類型
-
pointer：- 迭代器指向的指針值
- 通常
value_type*
-
reference：- 迭代器指向的引用值
- 通常
value_type&
-
iterator category：- 標(biāo)識(shí)由迭代器建模的迭代器概念。
- 以下之一：
struct input_iterator_tag {}; struct output_iterator_tag {}; struct forward_iterator_tag : input_iterator_tag {}; struct bidirectional_iterator_tag : forward_iterator_tag {}; struct random_access_iterator_tag : bidirectional_iterator_tag {};
的定義iterator_traits看起來(lái)像：
// The basic version works for iterators with the member type
template <class Iterator>
struct iterator_traits
{
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};
// A partial specialization takes care of pointer types
template <class T>
struct iterator_traits<T *>
{
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef T &reference;
typedef random_access_iterator_tag iterator_category;
};
// pointers to const type
template <class T>
struct iterator_traits<const T *>
{
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T *pointer;
typedef const T &reference;
typedef random_access_iterator_tag iterator_category;
};有時(shí)，泛型算法需要知道其迭代器參數(shù)的值類型，即迭代器指向的類型。例如，要交換兩個(gè)迭代器指向的值，就需要一個(gè)臨時(shí)變量。
template <class Iterator>
void swap (Iterator a, Iterator b)
{
typename Iterator::value_type tmp = *a;
*a = *b;
*b = tmp;
}這些特征還通過(guò)利用iterator_category成員提供的有關(guān)基本迭代器類別的知識(shí)來(lái)提高算法的效率。算法可以使用這個(gè)“標(biāo)簽”來(lái)選擇迭代器能夠處理的最有效的實(shí)現(xiàn)，而不會(huì)影響處理各種迭代器類型的靈活性。
在下面的例子中，我們的目標(biāo)是有一個(gè)單一的advance算法，可以根據(jù)迭代器類別自動(dòng)執(zhí)行正確的版本。
template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n,
input_iterator_tag)
{
for (; n > 0; --n)
++i;
}
template <class BidirectionalIterator, class Distance>
void advance(BidirectionalIterator &i, Distance n
bidirectional_iterator_tag)
{
if (n <= 0)
for (; n > 0; --n)
++i;
else
for (; n < 0; ++n)
--i;
}
template <class RandomAccessIterator, class Distance>
void advance(RandomAccessIterator &i, Distance n,
random_access_iterator_tag)
{
i += n;
}
// Generic advance algorithm using compile-time dispatching based on function overloading
template <class InputIterator, class Distance>
void advance(InputIterator i, Distance n)
{
advance(i, n, typename iterator_traits<Iterator>::iterator_category());
}編寫自定義迭代器
迭代器特征將自動(dòng)適用于定義適當(dāng)成員類型的任何迭代器類。自定義迭代器應(yīng)該支持以下指針：
- 如何檢索該點(diǎn)的值
- 如何增加/減少迭代點(diǎn)
- 如何與其他迭代點(diǎn)進(jìn)行比較
#include <algorithm>
#include <exception>
#include <iostream>
#include <iterator>
#include <typeinfo>
#include <vector>
template <typename ArrType>
class MyArray {
private:
ArrType *m_data;
unsigned int m_size;
public:
class Iterator {
public:
// iterator_trait associated types
typedef Iterator itr_type;
typedef ArrType value_type;
typedef ArrType &reference;
typedef ArrType *pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
Iterator(pointer ptr) : m_itr_ptr(ptr) {}
itr_type operator++() {
itr_type old_itr = *this;
m_itr_ptr++;
return old_itr;
}
itr_type operator++(int dummy) {
m_itr_ptr++;
return *this;
}
itr_type operator--() {
itr_type old_itr = *this;
m_itr_ptr--;
return old_itr;
}
itr_type operator--(int dummy) {
m_itr_ptr--;
return *this;
}
reference operator*() const { return *m_itr_ptr; }
pointer operator->() const { return m_itr_ptr; }
bool operator==(const itr_type &rhs) { return m_itr_ptr == rhs.m_itr_ptr; }
bool operator!=(const itr_type &rhs) { return m_itr_ptr != rhs.m_itr_ptr; }
private:
pointer m_itr_ptr;
};
MyArray(unsigned int size) : m_size(size) { m_data = new ArrType[m_size]; }
unsigned int size() const { return m_size; }
ArrType &operator[](unsigned int idx) {
if (idx >= m_size)
throw std::runtime_error("Index out of range");
return m_data[idx];
}
Iterator begin() { return Iterator(m_data); }
Iterator end() { return Iterator(m_data + m_size); }
};
int main()
{
MyArray<double> arr(3);
arr[0] = 2.6;
arr[1] = 5.2;
arr[2] = 8.9;
std::cout << "MyArray Contents: ";
for (MyArray<double>::Iterator it = arr.begin(); it != arr.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::vector<double> vec;
std::copy(arr.begin(), arr.end(), std::back_inserter(vec));
std::cout << "Vector Contents after copy: ";
for (std::vector<double>::iterator it = vec.begin(); it != vec.end(); it++) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::cout << typeid(std::iterator_traits<
MyArray<double>::Iterator>::iterator_category())
.name()
<< std::endl;
return 0;
}
/*OUTPUT
MyArray Contents: 2.6 5.2 8.9
Vector Contents after copy: 2.6 5.2 8.9
FSt26bidirectional_iterator_tagvE
*/迭代器和循環(huán)范圍
基于范圍的 for 循環(huán)（或簡(jiǎn)稱為 range-for）以及auto，是 C++11 標(biāo)準(zhǔn)中添加的最重要的特性之一。
范圍for循環(huán)的語(yǔ)法模板如下所示：
for (range_declaration : range_expression)
{
// loop body
}在 C++11/C++14 中，上述格式產(chǎn)生類似于以下的代碼：
{
auto&& range = range_expression ;
// beginExpr is range.begin() and endExpr is range.end()
for (auto b = beginExpr, e = endExpr; b != e; ++b) {
range_declaration = *b;
// loop body
}
} 基于范圍的 for 循環(huán)的典型用法：
// Iterate over STL container
std::vector<int> v{1, 2, 3, 4};
for (const auto &i : v)
std::cout << i << "\n";range for 循環(huán)的工作方式是創(chuàng)建一個(gè)指向向量第一個(gè)元素的迭代器，然后依次訪問(wèn)向量的每個(gè)元素，直到迭代器到達(dá)向量的最后一個(gè)元素，然后循環(huán)終止。在cppinsight可以觀察到這種現(xiàn)象在這里。
