C++中的迭代器和指针

在前面的内容中我们简单讲过，STL主要是由三部分组成

1. 容器（container），包括vector，list，set，map等
2. 泛型算法（generic algorithm），用来操作这些容器，包括find()，sort()，replace()等
3. 迭代器（iterator），泛型算法操作容器的工具，是连接容器和算法的粘合剂

一、迭代器（iterator）

在介绍STL之前，首先了解一下什么是迭代器。STL中的泛型算法提供了很多可作用于容器类以及数组类上的操作，这些算法与他们想要操作的元素类型无关（int，double，string等）且与容器类独立（vector，list，array等）。很容易想到，泛型算法通过函数模板（function template）技术来达到 “与操作对象的元素类型无关” 的目的，而实现与 “容器无关” 则不直接在容器本身进行操作，而是借助一对 iterator 来标示我们要进行迭代的元素范围。我们通过一个具体的问题来引入 iterator 的设计动机。

问题描述：
给定一个存储整数的vector，如果vector内存在目标值value，就返回指向该值的指针；否则返回0。

首先很容易想到的一种做法是：

int* find(vector<int>& nums, const int& value){
    for(int i=0; i<nums.size(); i++){
        if(nums[i]==value)	return &nums[i];
    }
    return 0;
}

接下来我们使用函数模板技术来扩充这个函数的功能，使其能够处理不同类型的数据类型：

template <typename T>
T* find(vector<T>& nums, const T& value){
    for(int i=0; i<nums.size(); i++){
        if(nums[i]==value)	return &nums[i];
    }
    return 0;
}

紧接着我们会想，函数能不能同时实现对vector和array类型的输入进行查找，一种解决办法是通过函数重载的技术来实现，但是如果要实现很多种类型的容器，那么便需要写很多个重载函数。另一种更好的解决办法是：我们便不将容器本身作为参数传入，而是传入需要处理的数据的开始和结束位置，这样便对任意的输入有了普遍性。

对于 array 数组类型的数据 int array[10]而言，array=&arran[0] 即数组名就代表数组的开始地址，也代表数组第一个元素的地址。由于在传递时，无论是 array[10],array[24]，都不会传递 array 的结束地址，因此需要额外传递一个参数 size，或者一个结尾地址，那么程序便可以写成：

方法一：传递数组的大小作为参数来标示结束为止
template <typename T>
T* find(const T* array, int size, const T& value){...}
方法二：传递数组的结尾指针来标示结束为止
template <typename T>
T* find(const T* begin, const T* end, const T& value){...}

上面我们已经完成了 array 类型输入的find 函数的编写，下面我们就来简单看一下调用方式：

int 	in_array[5] = {1, 4, 5, 7, 2};
double 	do_array[7] = {1.5, 2.7, 3.2, 4, 7, 2, 1.7};
int* f1 = find(array, 5, 4);	//采用第一种调用方式，传入开始位置和数组大小
int* f2 = find(do_array, do_array+7, 2); //采用第二种调用方式，传入开始位置和结束位置即[开始位置，结束位置)

那么针对 vector 类型的容器，它的存储方式跟 array 相同，都是以一块连续的内存存储所有元素，因此可以采用跟 array 相同的方式来实现 find 函数。但是二者不同的是：vector 容器可以为空而 array 不能为空，因此：

vector<int> nums;	find(&nums[0], &nums[0+n], value);	//正确
int array[];	//无法对 array[0] 取地址

所以为了避免每次在计算 array 的首地址时，array 为空的情况，抽象出一个新的函数 begin()，具体定义如下：

template <typename T>
inline T* begin(const vector<T>& vec){
    return vec.empty() ? 0:&vec[0];
}

我们以同样的方式封装成 end() 函数，返回 vector 的结束地址。因此我们便有了放之四海而皆准的调用方式：

find( begin(vec), end(vec), value ); // 开始地址，结束地址，查找值

再进一步，我们可以尝试将 find 函数应用在所有的容器类型，但是由于大部分容器（比如：list，map，set）并不是顺序存储，因此 vector 和 array 的这种指针寻址的方式并不适合其他非连续内存空间存储的容器类型。解决这个问题的方法是，在底层指针的行为之上提供一层抽象，取代程序原本的 “指针直接操作” 方式。我们把底层指针的处理全部放在此抽象层中，将原本的指针操作根据具体的容器类型进行重载，这样我们便可以处理标准库所提供的的所有容器类，这便是 iterator 的创建原因。iterator 的操作方式跟指针一样，但是 iterator 的 ++, !=, * 等运算符是根据具体的容器类型重载过得。对 list 而言，++ 会按照链表的方式前进到下一个元素，对 vector 而言，++ 会直接指向下一个内存位置。

/*************定义单链表的类************/
template<typename T>
class node {
public:
    T value;
    node *next;
    node() : next(nullptr) {}
    node(T val, node *p = nullptr) : value(val), next(p) {}
};
/*************封装单链表***************/
template<typename T>
class my_list {
private:
    node<T> *head;
    node<T> *tail;
    int size;
private:
    //单链表迭代器的实现
    class list_iterator {
    private:
        node<T> *ptr; //指向list容器中的某个元素的指针
    public:
        list_iterator(node<T> *p = nullptr) : ptr(p) {}     
        //重载++、--、*、->等基本操作
        //返回引用，方便通过*it来修改对象
        T &operator*() const {
            return ptr->value;
        }
        node<T> *operator->() const {
            return ptr;
        }
        list_iterator &operator++() {
            ptr = ptr->next;
            return *this;
        }
        list_iterator operator++(int) {
            node<T> *tmp = ptr;
            // this 是指向list_iterator的常量指针，因此*this就是list_iterator对象，前置++已经被重载过
            ++(*this);
            return list_iterator(tmp);
        }
        bool operator==(const list_iterator &t) const {
            return t.ptr == this->ptr;
        }
        bool operator!=(const list_iterator &t) const {
            return t.ptr != this->ptr;
        }
    };

public:
    typedef list_iterator iterator; //类型别名
    my_list() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    //从链表尾部插入元素
    void push_back(const T &value) {
        if (head == nullptr) {
            head = new node<T>(value);
            tail = head;
        } else {
            tail->next = new node<T>(value);
            tail = tail->next;
        }
        size++;
    }
    //打印链表元素
    void print(std::ostream &os = std::cout) const {
        for (node<T> *ptr = head; ptr != tail->next; ptr = ptr->next)
            os << ptr->value << std::endl;
    }
public:
    //操作迭代器的方法
    //返回链表头部指针
    iterator begin() const {
        return list_iterator(head);
    }
    //返回链表尾部指针
    iterator end() const {
        return list_iterator(tail->next);
    }
    //其它成员函数 insert/erase/emplace
};

二、容器（container）：物之所置也

2.1 顺序性容器

1. vector 以一块连续的内存来存放元素，对 vector 进行随机访问很有效率，但是由于 vector 的每个元素都被存储在距离起始点的固定偏移位置，如果将元素插在任意位置，那么效率很低。同理，删除任意位置的元素也缺乏效率；
2. list 以双向链接而非连续内存来存储内容，因此实现 list 内部任意位置的插入和删除操作效率很高，但是如果要对 list 进行随机访问，则效率很低；
3. deque 与 vector 一样都是使用连续内存来存放元素，deque 在最前端插入元素，最后端删除元素。

2.2 关联容器

map：被定义为一对（key-value）数值，其中的 key 通常是个字符串，扮演索引的角色，另一个数值是 value。value 是 key 通过映射函数 f 得到的值，可以记录 key 出现的次数等。map 对象中 key 用 first 对象来表示，value 用 second 对象来表示，即：

map<string, int>::iterator it = words.begin();
while(it != words.end()){
	cout << "key:" << it->first << "\nvalue:" << it->second << endl;
}

查询map是否存在 key 有三种方法：

/**********************方法一**********************/
string target="a";
int count = words[target]; // 查询words中是否存在 "a"
/**********************方法二**********************/
string target="a";
map<string, int>::iterator it = words.find(target);
/**********************方法三**********************/
string target="a";
int count = words.count(target);

其中：

1. 方法一：如果 words 中存在 "a"，count 中就记录了 "a" 的个数。**但是，当 words 中本来就不含有 "a" 时，该方法会通过 words[target] 自动添加进 words，此时 words[target]=0 **，因此该方法不建议用在查询中；
2. 方法二：类似于上一节中写的 find 函数，当找到该元素时，返回指向该元素的迭代器，否则返回指向最有一个元素的后一个位置的迭代器 words.end()。所以通过判断函数返回值是否为 words.end() 便可以知道结果；
3. 方法三：count 会返回某个特定项在 map 内的个数。

set：set的操作方式跟map差不多，set中相当于只记录了 key 值。

无论是 map 还是 set，在进行插入元素后会对其中的元素进行排序，因此当不需要排序时，需要定义：

unordered_map<pair<type1, type2>>my_map;
unordered_set<pair<type1, type2>>my_set;

2.3 所有容器的共通操作

1. ==, != ：返回 true 或者 false， 判断是否相等；
2. empty()：在容器为空时返回 true，否则返回 false；
3. size()：返回容器内的元素个数；
4. clear()：清空容器内的元素，但是保留容器的长度；
5. begin()：返回容器第一个元素的 iterator；
6. end()：返回容器最后一个元素的后一个位置的 iterator；
7. insert()：在容器的指定位置插入元素；
8. erase()：在容器的指定位置删除元素；
9. push_back()：在容器的末端插入元素；
10. pop_back()：在容器的首端取出元素.......

上面列举的都是比较常见的一部分，由于精力有限难免有错误和疏漏，欢迎大家在阅读的同时对文中的不当之处进行指正、补充，不胜感激 ！

三、参考内容

1. 《Essential C++》中文版，侯捷译
2. https://www.cnblogs.com/wengle520/p/12492708.html