笔记

深浅模式

迭代器 ​

迭代器(iterator)模式又称为游标(Cursor)模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器是一种遍历容器内元素的数据类型，这种数据类型给我们的感觉有点像指针，我们可以理解为迭代器指向容器中的元素。

通过迭代器我们可以读取容器中的某个元素值，也可以通过迭代器来改变该元素值。

迭代器产生原因(或者本质) ​

iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

迭代器的类型 ​

输入迭代器(InputIterator)、输出迭代器(OutputIterator)、前向迭代器(ForwardIterator)、双向迭代器(BidirectionalIterator)、随机访问迭代器(RandomAccessIterator)。

每个迭代器类型对应的操作。

类别简写输出output输入input前向forward双向bidirection随机random
读=*p=*p=*p=*p
访问->->->->[]
写*p=*p=*p=*p=
迭代++++++++、--++、--、+、-、+=、-=
比较==、!===、!===、!===、!=、<、>、<=、>=

五种迭代器之间的关系图

以vector容器为例，我们可以定义一个迭代器变量，这个变量就是用来操作vector容器的。

cpp
vector<int> vi = {10, 20, 30, 40, 50};
vector<int>::iterator iter; //定义操作vi的迭代器，必须是vector<int>类型

我们可以把vector<int>::iterator理解成一种类型，这种类型就是用来创建迭代器的。当我们使用这个类型创建变量的时间，这个变量就是一个迭代器，在这里iter就是一个迭代器。

为什么定义这么多迭代器 ​

物尽其用，使得具体的操作使用具体类型的迭代器，避免迭代器的功能太大或者太小，导致使用起来不方便。每个容器及其对应的迭代器的类型图表如下：

容器类内迭代器类别
vector随机访问迭代器
deque随机访问迭代器
list双向迭代器
set双向迭代器
multiset双向迭代器
map双向迭代器
multimap双向迭代器
unordered_set前向迭代器
unordered_multiset前向迭代器
unordered_map前向迭代器
unordered_multimap前向迭代器

迭代器依赖于容器，不同类型容器的迭代器也是不同的，手动实现迭代器可以查看之前 手动实现的string容器 和 手动实现vector容器

流迭代器 ​

流迭代器是特殊的迭代器，可以将输入/输出流作为容器看待(因为输入输出都有缓冲区的概念)。因此，任何接受迭代器参数的算法都可以和流一起工作。关于流迭代器的模板形式：

cpp
#include <iterator>
template <class T,
          class CharT = char,
          class Traits = std::char_traits<CharT>,
          class Distance = std::ptrdiff_t>
class istream_iterator
    : public std::iterator<std::input_iterator_tag, T, Distance, const T *, const T &>;

template <class T,
          class CharT = char,
          class Traits = std::char_traits<CharT>,
          class Distance = std::ptrdiff_t>
class istream_iterator;

template <class T,
          class CharT = char,
          class Traits = std::char_traits<CharT>>
class ostream_iterator
    : public std::iterator<std::output_iterator_tag, void, void, void, void>;

template <class T,
          class CharT = char,
          class Traits = std::char_traits<CharT>>
class ostream_iterator;

以及两种流迭代器的构造函数

cpp
// 输出流迭代器的构造函数
ostream_iterator(ostream_type& stream, const CharT* delim);
ostream_iterator(ostream_type& stream);

// 输入流迭代器的构造函数
constexpr istream_iterator();
istream_iterator( istream_type& stream );
istream_iterator( const istream_iterator& other ) = default;

输入输出流迭代器的使用示例：

cpp
void test() {
    vector<int> numbers{1, 2, 3, 4, 5};
    ostream_iterator<int> osi(cout, "\n");
    copy(numbers.begin(), numbers.end(), osi);
}

void test() {
    vector<int> numbers;
    istream_iterator<int> isi(cin);
    ////对于vector插入元素应该调用push_back
    // copy(isi, istream_iterator<int>(), numbers.begin());
    copy(isi, istream_iterator<int>(), std::back_inserter(numbers));
    copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, "\n"));
}

思考题：可以自己查阅源码，看看上述两份代码背后如何实现的？

迭代器适配器 ​

back_inserter是函数模板，返回类型是back_insert_iterator，而back_insert_iterator是类模板，底层调用了push_back函数。

front_inserter是函数模板，返回类型是front_insert_iterator，而front_insert_iterator是类模板，底层调用了push_front函数。

inserter是函数模板，返回类型是insert_iterator，而insert_iterator是类模板，底层调用了insert函数。

cpp
template <class Container>
std::back_insert_iterator<Container> back_inserter(Container &c);

template <class Container>
std::front_insert_iterator<Container> front_inserter(Container &c);

template <class Container>
std::insert_iterator<Container>
inserter(Container &c, typename Container::iterator i);

三者对应的可能实现如下：

cpp
template <class Container>
std::back_insert_iterator<Container> back_inserter(Container &c) {
    return std::back_insert_iterator<Container>(c);
}

template <class Container>
std::front_insert_iterator<Container> front_inserter(Container &c) {
    return std::front_insert_iterator<Container>(c);
}

template <class Container>
std::insert_iterator<Container>
inserter(Container &c, typename Container::iterator i) {
    return std::insert_iterator<Container>(c, i);
}

具体的使用示例：

cpp
void test() {
    vector<int> number1{1, 3, 5};
    list<int> number2{20, 30, 40};
    
    // back_insert_iterator底层是调用了push_back
    copy(number2.begin(), number2.end(), back_insert_iterator<vector<int>>(number1));
    copy(number1.begin(), number1.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    // front_insert_iterator底层是调用了push_front
    copy(number1.begin(), number1.end(), front_insert_iterator<list<int>>(number2));
    copy(number2.begin(), number2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    set<int> number3{12, 13, 16, 13};
    auto sit = number3.begin();
    ++sit;
    
    // insert_iterator底层是调用了insert
    copy(number1.begin(), number1.end(), insert_iterator<set<int>>(number3, sit));
    copy(number3.begin(), number3.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

迭代器的begin()/end()操作和反向的rbegin()/rend()操作 ​

begin()/end()和rbegin()/rend()都返回一个迭代器类型，使用的时间一般都是成对使用的。

  • begin() 返回一个迭代器类型（可以理解成返回一个迭代器）。如果容器不为空返回一个指向容器中首元素的迭代器类型；如果容器为空返回的值与end()相同。
  • end()返回一个迭代器类型。它返回的并不是指向末端元素的迭代器类型，而是返回末端元素后面的位置。可以把这个位置理解成容器中的一个标记位，或者是一个不存在的元素。
  • 如果想反向遍历一个容器就要使用rbegin()和rend()来进行操作了。和begin()/end()结合着进行理解就可以了，一个是正向遍历一个是反向遍历。
cpp
void test() {
    vector<int> number{1, 4, 6, 90, 34};
    vector<int>::reverse_iterator it = number.rbegin();
    /* auto it = number.rbegin(); */
    for (; it != number.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

迭代器运算符 ​

  • *iter返回迭代器iter指向的元素的引用，必须保证这个迭代器指向的是容器中有效的元素，如指向end()就不可以，因为不是有效元素。
  • iter++/iter--，指向容器中的上一个元素/下一个元素，已经指向end()以后就不能在进行++操作，指向开头就不能再进行–-操作。
  • ==、!=判断两个迭代器指向的是否为同一个位置。

const_iterator迭代器 ​

const_iterator迭代器是表示这个迭代器指向的元素的值不能改变，迭代器本身可以进行改变指向。只能通过这个迭代器从容器中读取数据，不能通过这个迭代器改变容器中的数据。感觉起来更像是常量指针。

C++ 11中引入了两个新函数cbegin()、cend()，返回的是常量迭代器。

迭代器失效 ​

如果在for循环中改变了容器的容量（插入或删除了元素），可能会导致指向该容器中元素的指针、引用、迭代器失效。失效就表示不能再代表容器中的元素，一旦使用了失效的东西就等于犯了严重的错误，很多情况下程序会直接崩溃。

对容器的操作影响了元素的存放位置，会导致迭代器失效

失效的情况 ​

以vector容器为例来演示一下迭代器失效的现象

cpp
#include <iostream>
#include <vector>

int main() {
    srand(time(nullptr));

    std::vector<int> v;

    for (int i = 0; i < 20; ++i) {
        v.push_back(rand() % 100 + 1);
    }

    for (auto i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 迭代器失效
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            v.erase(it);
        }
    }

    for (auto i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}
bash
98 57 68 51 89 81 85 69 100 76 97 58 98 61 64 46 53 2 56 66 
Segmentation fault (core dumped)

失效的迭代器范围为 被删除元素的位置 至 容器末尾，因为其范围内的元素位置改变了，所以原来指向这些位置的迭代器就失效了；被删除元素的位置 至 容器起始位置 的迭代器还是有效的。同样的insert方法也会导致后续范围迭代器失效。

解决失效问题 ​

解决迭代器失效就是接收erase/insert返回的新迭代器。将原来操作迭代器的for循环改写

cpp
// 解决失效问题
    for (auto it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }

返回的是删除元素后删除点新元素的迭代器，因此这个元素也要判断。因此是不满足条件才++迭代器，满足条件的话删除旧元素后要判断新元素是否也满足条件。如果是insert导致的失效要少判断一次，因为插入元素导致了判断过的元素进行了后移。

cpp
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        it = v.insert(it, *it - 1);
        ++it;
    }
}

失效的原理 ​

参考自定义vector容器部分内容

参考资料 ​