C++ STL迭代器的學(xué)習(xí)教程

發(fā)呆業(yè)務(wù)愛好者 2021-08-30 11:32:51 瀏覽數(shù) (3189)

反饋

C++ STL 迭代器

了解如何使用 C++ 標(biāo)準(zhǔn)模板庫 (STL) 的容器的關(guān)鍵之一是了解迭代器的工作原理。lists 和maps等容器的行為不像數(shù)組，因此您不能使用for循環(huán)來遍歷其中的元素。同樣，因?yàn)檫@些容器不能隨機(jī)訪問，所以不能使用簡單的整數(shù)索引。你可以使用迭代器來引用容器的元素。

STL 容器和算法可以很好地協(xié)同工作的原因是它們彼此一無所知 - Alex Stepanov

迭代器是類似指針的對象，它允許程序在不暴露底層表示的情況下順序地遍歷容器的元素。迭代器可以通過遞增和遞減它們從一個(gè)元素前進(jìn)到下一個(gè)元素。每個(gè)容器類型都有一個(gè)與之關(guān)聯(lián)的不同迭代器。例如，迭代器 forlist<int>聲明為：

 std::list<int>::iterator

迭代器類別

迭代器分為幾類，因?yàn)椴煌乃惴ㄐ枰褂貌煌牡鳌?/font>例如，該std::copy()算法需要一個(gè)可以通過遞增來推進(jìn)的迭代器，而該 std::reverse()算法需要一個(gè)可以遞減的迭代器。在 C++ 語言中，該標(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ī)訪問迭代器
- 已重載operator[]，指針運(yùn)算
- 例子：std::vector<int>::iterator。

你可以在此處獲得有關(guān)這些的更多信息

迭代器特征

迭代器特征允許算法以統(tǒng)一的方式訪問有關(guān)特定迭代器的信息，以避免在需要遍歷不同樣式的容器時(shí)為每個(gè)特定情況重新實(shí)現(xiàn)所有迭代器。例如，查找元素std::list是O(n)復(fù)雜性，而std::vector隨機(jī)訪問元素是O(1)復(fù)雜性（給定索引位置）。算法最好知道可以使用+=運(yùn)算符（隨機(jī)訪問）或僅使用++運(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看起來像：

// 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;
}

這些特征還通過利用iterator_category成員提供的有關(guān)基本迭代器類別的知識(shí)來提高算法的效率。算法可以使用這個(gè)“標(biāo)簽”來選擇迭代器能夠處理的最有效的實(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)（或簡稱為 range-for）以及auto，是 C++11 標(biāo)準(zhǔn)中添加的最重要的特性之一。

范圍for循環(huán)的語法模板如下所示：

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è)元素的迭代器，然后依次訪問向量的每個(gè)元素，直到迭代器到達(dá)向量的最后一個(gè)元素，然后循環(huán)終止。在cppinsight可以觀察到這種現(xiàn)象在這里。

C++

0 人點(diǎn)贊