快捷導(dǎo)航

詳解C++?的STL迭代器原理和實(shí)現(xiàn)

更新時(shí)間：2022年01月15日 15:42:50 作者：05jin

這篇文章主要為大家介紹了C++的STL迭代器原理和實(shí)現(xiàn)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

1. 迭代器簡(jiǎn)介

為了提高C++編程的效率，STL（Standard Template Library）中提供了許多容器，包括vector、list、map、set等。然而有些容器（vector）可以通過(guò)下標(biāo)索引的方式訪問(wèn)容器里面的數(shù)據(jù)，但是大部分的容器（list、map、set）不能使用這種方式訪問(wèn)容器中的元素。為了統(tǒng)一訪問(wèn)不同容器時(shí)的訪問(wèn)方式，STL為每種容器在實(shí)現(xiàn)的時(shí)候設(shè)計(jì)了一個(gè)內(nèi)嵌的iterator類，不同的容器有自己專屬的迭代器（專屬迭代器負(fù)責(zé)實(shí)現(xiàn)對(duì)應(yīng)容器訪問(wèn)元素的具體細(xì)節(jié)），使用迭代器來(lái)訪問(wèn)容器中的數(shù)據(jù)。除此之外，通過(guò)迭代器可以將容器和通用算法結(jié)合在一起，只要給予算法不同的迭代器，就可以對(duì)不同容器執(zhí)行相同的操作，例如find查找函數(shù)（因?yàn)榈魈峁┝私y(tǒng)一的訪問(wèn)方式，這是使用迭代器帶來(lái)的好處）。迭代器對(duì)一些基本操作如*、->、++、==、!=、=進(jìn)行了重載，使其具有了遍歷復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力，其遍歷機(jī)制取決于所遍歷的容器，所有迭代器的使用和指針的使用非常相似。通過(guò)begin，end函數(shù)獲取容器的頭部和尾部迭代器，end迭代器不包含在容器之內(nèi)，當(dāng)begin和end返回的迭代器相同時(shí)表示容器為空。

STL主要由 容器、迭代器、算法、函數(shù)對(duì)象、和內(nèi)存分配器 五大部分構(gòu)成。

2. 迭代器的實(shí)現(xiàn)原理

首先，看看STL中迭代器的實(shí)現(xiàn)思路：

STL中迭代器的實(shí)現(xiàn)思路

從上圖中可以看出，STL通過(guò)類型別名的方式實(shí)現(xiàn)了對(duì)外統(tǒng)一；在不同的容器中類型別名的真實(shí)迭代器類型是不一樣的，而且真實(shí)迭代器類型對(duì)于++、--、*、->等基本操作的實(shí)現(xiàn)方式也是不同的。（PS：迭代器很好地詮釋了接口與實(shí)現(xiàn)分離的意義）

既然我們已經(jīng)知道了迭代器的實(shí)現(xiàn)思路，現(xiàn)在如果讓我們自己設(shè)計(jì)一個(gè)list容器的簡(jiǎn)單迭代器，應(yīng)該如何實(shí)現(xiàn)呢？

1.list類需要有操作迭代器的方法

1.begin/end

2.insert/erase/emplace

2.list類有一個(gè)內(nèi)部類list_iterator

1.有一個(gè)成員變量ptr指向list容器中的某個(gè)元素

2.iterator負(fù)責(zé)重載++、--、*、->等基本操作

3.list類定義內(nèi)部類list_iterator的類型別名

以上就是實(shí)現(xiàn)一個(gè)list容器的簡(jiǎn)單迭代器需要考慮的具體細(xì)節(jié)。

3. 迭代器的簡(jiǎn)單實(shí)現(xiàn)

my_list.h（重要部分有注釋說(shuō)明）

//
// Created by wengle on 2020-03-14.
//
 
#ifndef CPP_PRIMER_MY_LIST_H
#define CPP_PRIMER_MY_LIST_H
 
#include <iostream>
 
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容器中的某個(gè)元素的指針
 
    public:
        list_iterator(node<T> *p = nullptr) : ptr(p) {}
        
        //重載++、--、*、->等基本操作
        //返回引用，方便通過(guò)*it來(lái)修改對(duì)象
        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對(duì)象，前置++已經(jīng)被重載過(guò)
            ++(*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);
    }
 
    //其它成員函數(shù) insert/erase/emplace
};
 
#endif //CPP_PRIMER_MY_LIST_H

test.cpp

//// Created by wengle on 2020-03-14.//#include <string>#include "my_list.h"struct student {    std::string name;    int age;    student(std::string n, int a) : name(n), age(a) {}    //重載輸出操作符    friend std::ostream &operator<<(std::ostream &os, const student &stu) {        os << stu.name << " " << stu.age;        return os;    }};int main() {    my_list<student> l;    l.push_back(student("bob", 1)); //臨時(shí)量作為實(shí)參傳遞給push_back方法    l.push_back(student("allen", 2));    l.push_back(student("anna", 3));    l.print();    for (my_list<student>::iterator it = l.begin(); it != l.end(); it++) {        std::cout << *it << std::endl;        *it = student("wengle", 18);    }    return 0;}//
// Created by wengle on 2020-03-14.
//
 
#include <string>
#include "my_list.h"
 
struct student {
    std::string name;
    int age;
 
    student(std::string n, int a) : name(n), age(a) {}
 
    //重載輸出操作符
    friend std::ostream &operator<<(std::ostream &os, const student &stu) {
        os << stu.name << " " << stu.age;
        return os;
    }
};
 
int main() {
    my_list<student> l;
    l.push_back(student("bob", 1)); //臨時(shí)量作為實(shí)參傳遞給push_back方法
    l.push_back(student("allen", 2));
    l.push_back(student("anna", 3));
    l.print();
 
    for (my_list<student>::iterator it = l.begin(); it != l.end(); it++) {
        std::cout << *it << std::endl;
        *it = student("wengle", 18);
    }
    return 0;
}

4. 迭代器失效

// inserting into a vector
#include <iostream>
#include <vector>
 
int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;
 
  it = myvector.begin();
  it = myvector.insert ( it , 200 );
 
  myvector.insert (it,200,300);
  //it = myvector.insert (it,200,300);
  myvector.insert (it,5,500); //當(dāng)程序執(zhí)行到這里時(shí)，大概率會(huì)crash
  for (std::vector<int>::iterator it2=myvector.begin(); it2<myvector.end(); it2++)
    std::cout << ' ' << *it2;
  std::cout << '\n';
 
  return 0;
}

上面的代碼很好地展示了什么是迭代器失效？迭代器失效會(huì)導(dǎo)致什么樣的問(wèn)題？

當(dāng)執(zhí)行完myvector.insert (it,200,300);這條語(yǔ)句后，實(shí)際上myvector已經(jīng)申請(qǐng)了一塊新的內(nèi)存空間來(lái)存放之前已保存的數(shù)據(jù)和本次要插入的數(shù)據(jù)，由于it迭代器內(nèi)部的指針還是指向舊內(nèi)存空間的元素，一旦舊內(nèi)存空間被釋放，當(dāng)執(zhí)行myvector.insert (it,5,500);時(shí)就會(huì)crash（PS：因?yàn)槟阃ㄟ^(guò)iterator的指針正在操作一塊已經(jīng)被釋放的內(nèi)存，大多數(shù)情況下都會(huì)crash)。迭代器失效就是指：迭代器內(nèi)部的指針沒(méi)有及時(shí)更新，依然指向舊內(nèi)存空間的元素。

insert源碼

上圖展示了STL源碼中vector容器insert方法的實(shí)現(xiàn)方式。當(dāng)插入的元素個(gè)數(shù)超過(guò)當(dāng)前容器的剩余容量時(shí)，就會(huì)導(dǎo)致迭代器失效。這也是測(cè)試代碼中myvector.insert (it,200,300);插入200個(gè)元素的原因，為了模擬超過(guò)當(dāng)前容器剩余容量的場(chǎng)景，如果你的測(cè)試環(huán)境沒(méi)有crash，可以將插入元素設(shè)置的更多一些。