在这一节, 我们将尝试探讨一个沟通了算法与容器的重要概念–迭代器

前言

参考资料

 

正文

从指针到迭代器

迭代器iterator这个名词初见可能比较陌生, 因此在前一篇有关STL的文章 C++ | STL I 中, 我使用了指针来类比这个概念. 今天让我们继续从指针重新开始, 来理解迭代器.

数组是最简单的容器辣!

让我们考虑实现一个数组容器吧, 也不需要支持特别复杂的算法, 有最简单的增改删查就可以了, 因此我们直接考虑用C艹自带的数组来实现我们的数组, 仿照STL的习惯, 我们把成员函数作如下命名

template <class ItemType, int Size>
class my_array{
    private:
        ItemType array[Size];
    public:
        my_array(ItemType initial, int num = Size); //将前num个元素赋初值initial
        void push_back(ItemType val);   //增加元素val
        ItemType* find(ItemType val);   //查找元素val
        ItemType& at(ItemType* target); //用于修改target指向元素,返回数组元素的引用
        void erase(ItemType val);   //删除元素val,后面的元素前移
};

如果没有学习迭代器, 上面的写法已经是一个很优秀的回答了 (因为是Vanadium写的), 我们主要关注查找函数的实现, 相信聪明的你很快就能做出实现

template <class ItemType, int Size>
ItemType* my_array<ItemType, Size>::find(ItemType val){
    int iterator;
    for(iterator = 0;iterator < Size;++iterator){
        if(*(array + iterator) == val)  break;
    }
    return (array + iterator);  //未找到则返回末地址的下一位
}

这个写法已经很完美了, 基本可以满足需求demand. 但是, 这是针对我们只有my_array这么一个需求的时候. 当我们需求扩大, 比如STL这样一个十分庞大的需求, 返回一个ItemType*是远不足以满足需求的. 比如我们需要一个my_map, 我们知道map在STL中是用红黑树red black tree实现的, 我们就要针对红黑树实现另外一个find函数–因为我们使用了指针的++运算和*解引用运算, 而这样的简单运算是不足以遍历红黑树的, 但是我们重新写一个这样的函数, 而不是选择重载, 就大大的违背了泛型编程的逻辑了.

最好的解决办法是保留这个弱爆了的遍历函数不动, 我们修改ItemType*为另外一个变量, 它能唯一的指向特定容器的某一个元素, 也能通过重载++运算和*解引用运算的方式实现对任一算法的适配, 定义这个新的变量类型, 用来代替指针的过程就被称为指针的抽象, 与此同时, 迭代器产生了.

假如我们已经拥有了迭代器类型iterator, 我们就可以改写那个find函数了.

template <class ItemType, int Size>
my_array<ItemType, Size>::iterator my_array<ItemType, Size>::find(ItemType val){
    my_array<ItemType, Size>::iterator i;
    for(i = this->begin();i != this->end();++i){
        if(*i == val)  break;
    }
    return i;   //未找到则返回末迭代器的后继
}
//Tips: 行5的边界条件使用了`!=`而不是`<`是因为不是所有迭代器都是可以比较大小的

在我们的写法中, 迭代器的定义更像是一个模板类中的类, 事实上也是如此, 以my_array为例, 我们会在类中定义一个类来实现迭代器(略去了影响观感的多余成员函数)

template <class ItemType, int Size>
class my_array{
    private:
        ItemType array[Size];
    public:
        class iterator;
        iterator begin(){
            return iterator(this);
        }
        iterator end(){
            return iterator(this+Size);
        }
        iterator find(ItemType val);   //查找元素val
};

template <class ItemType, int Size>
class my_array<ItemType, Size>::iterator{
    private:
        ItemType* ptrItem;
    public:
        iterator(ItemType _ptrItem){
            ptrItem = _ptrItem;
        }

        iterator& operator++(){
            ++ptrItem;
            return *this;
        }

        bool operator!=(iterator tmp){
            return ptrItem != tmp.ptrItem;
        }

        ItemType& operator*(){
            return (*ptrItem);
        }
};

经过这样子的改写, 我们的my_array终于能支持迭代器了, 虽然对数组使用迭代器显得有些多余, 但我们的目标可是星辰大海! 况且, 我们目前已经跨出了第一步–从指针到迭代器

除此以外, 我们的find函数(算法)已经脱离了容器my_array, 这也从另一个侧面说明了STL的迭代器的作用, 沟通算法与容器, 避免算法错误的对不应被操作的容器操作, 以及方便算法的实现和重载

 

最后一个迭代器

不论是数组还是抽象的遍历函数, 我们判断终点的方法都是i != this->end(), 这是由于我们想要程序在越过容器边界之后再进行退出. 之所这么做是有很多考量的, 其中之一就是方便程序的编写.

 

迭代器的分类

好的, 编写一个STL的小活动到此结束(当然我们也没有能力编写一个完整的STL, 毕竟一个<array>都有910行代码, 而<algorithm>包含了9948行代码!!!), 接下来我们继续往应用层面讨论迭代器的分类.

我们知道, 对于不同的容器, STL实现时, 采用了不同的数据结构, 同样的, 迭代器的实现也会使用不同的方法. 一个最简单的例子就是, 你无法对一个set容器使用sort函数, 但是vector却可以.

我们知道, STL的sort函数主要使用的是快速排序算法 (不知道就去看文档!), 实现快速排序算法的必要条件就是能够以O(1)的代价随机访问元素, 并且能以O(1)的代价计算任意两个元素之间的距离; 用迭代器的语气说, 就是你要对迭代器与整型之间的+=, -=, +, -运算符和迭代器之间的-运算符有定义.

然而, 由于set的底层是红黑树, 我们并没有办法通过迭代器随机访问, 也没有办法计算距离, 因此sort无法对set使用; 对于vector, 我们知道它的实现其实是数组, 其迭代器的实现是指针, 而且拥有一块连续的内存, 因而可以满足要求.

让我们拿回上一篇有关STL的文章 C++ | STL II 的图

图源: Github | PPT | Back to Basics: Classic STL - Bob Steagall - CppCon 2021

先不看表格的前面两行与输入输出有关的特化迭代器, 我们关注后面四个常见的迭代器, 我们从上往下看, 因为下面的迭代器是上面迭代器的加强版本.

前向迭代器forward iterator

前向迭代器支持多趟的对容器遍历, 并且在读写后依然指向同一个元素.

支持的操作: * -> ++ == != =

应用于: forward_list(单向链表), unordered_*(hash维护的单链表)

双向迭代器bidirectional iterator

在前者的基础上, 可以双向移动

额外支持的操作: --

应用于: list(双向链表), set, map, multi*(红黑树)

随机访问迭代器random access iterator

在前者的基础上, 可以以O(1)的代价访问任一元素

额外支持的操作: [] += -= + - < > <= >=

应用于: deque(多个定长数组)

连续迭代器contiguous iterator

(C艹17+)在前者的基础上, 逻辑相邻的元素, 物理也相邻

额外支持的操作: 无

应用于: array, vector(数组)

 

一个容器的迭代器的种类决定了他能应用的算法. 因此, 我们不必机械的记忆适用于某一个或某一类的算法有哪些, 我们只需要思考算法的实现过程, 判断算法需求的迭代器的种类, 即可以更加普遍的方式获知算法的适用的容器. 当然, 比这种方法更加便捷的应当是查询文档–当且仅当无法确认时.

 

比较器专栏

在STL | III的最后, 我们来探讨一下比较器数的原理和用法. 在前一篇有关STL的文章 C++ | STL I 中, 我在最后提了一嘴降序序列如何设置cmp函数, 然而当时我们并没有系统的理解迭代器, 因此编写的cmp函数并不是一个良好的函数.

匿名函数

在C艹11+中, 提供了匿名函数(也被称为lambda表达式)以解决我们在使用STL的过程中, 定义了过多仅仅使用了一两次的函数类, 导致编译变慢或代码冗长臃肿的情况. 由于匿名函数可以在使用域内部定义使用, 我们也将其称作匿名的内联函数.

匿名函数的语法格式如下:

[capture](parameters) -> return TypeName{}

在上面的定义中,

  • [capture]被称为捕获列表, 用于捕获外部变量
  • (parameters)被称为参数列表, 相当于普通函数的参数列表, 采用形参传值的方法
  • -> return TypeName规定了匿名函数的返回值类型, 一般情况下可缺省, 交由编译器推导
  • {}为函数体, 不要求只能包含一条语句, 也可以是语句块(但是语句过多, 就不适合使用匿名函数了)

我们直接通过例子来理解匿名函数, 至于更细节的东西, 我们可以放到之后有机会再讲.

#include<iostream>
using namespace std;

int main(){
    auto my_max = [](int x, int y){ return x>y? x:y; };
    cout<<max(3,5)<<endl;
}

同样的, 我们也可以在当时的代码中, 使用匿名函数.

//原始代码
bool cmp(int x, int y){
    return !(x<y);
}
int main(){
    int _array[] = {1,4,6,2,4,5};
    vector<int> array(_array, _array+6);
    sort(array.begin(), array.end(), cmp);
    for(auto i=array.begin();i<array.end();++i){
        cout<<*i<<' ';
    }
    cout<<endl;
}

//使用匿名函数
int main(){
    int _array[] = {1,4,6,2,4,5};
    vector<int> array(_array, _array+6);
    sort(array.begin(), array.end(), [](int x, int y){ return !(x<y); });
    for(auto i=array.begin();i<array.end();++i){
        cout<<*i<<' ';
    }
    cout<<endl;
}

可以看到, 假如我们使用生命周期更短的匿名函数, 就可以减少对cmp函数的重载(因为我们不一定只需要一个特殊的cmp函数), 而是可以完全交由匿名函数完成.

 

比较器的本质

让我们回到比较器, 回到使用比较器的典型函数sort, 参阅官方标准文档, 我们发现, sort只有两个函数签名

一个是缺省了比较器的版本(这个时候会调用重载后的<运算符完成比较); 另一个就是带有比较器的版本, 但是奇怪的是, 我们可以使用很多种方式为sort传递比较器, 比如下列方法都是可以接受的

// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // using lambda as comp
  std::sort (myvector.begin(), myvector.end(), [](int x, int y){ return !(x<y); }) 

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

然而, 这么多种方法对应的仅有一个重载, 这说明, 这么多实现方法的比较器的类型, 应该是一样的.

事实上, 这个相同的类型, 就是函数对象function object, 要注意的是, 函数对象中的对象, 与我们OOP中熟知的对象并不相同, 与此同时, 也要清楚函数并不是对象–包括结构体, 以及他们的模板和实例化, 他们统统都是一段代码而已.

具体来说, 函数对象指的, 就是函数指针, 可以转化为函数指针或是重载了()运算符的东西. 因此我们回头看上面的代码, 就可以理解他们分别调用了什么函数对象了

  • 行20: 函数指针
  • 行23: 重载后的()运算符
  • 行26: 可以转化为函数指针