当前位置：首页 > article >正文

STL 迭代器iteratior 详解

article 2024/12/26 12:44:32

C++的标准模板库（STL）中，迭代器是一种重要的工具，用于访问容器中的元素。

迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。

分类

1) 正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

2) 常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

3) 反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

4) 常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

用法

通过迭代器指向它指向的元素， * 迭代器名就代表迭代器指向的元素。常量迭代器是只读权限，以const来修饰，非常量迭代器还能修改元素

++ 自增操作：

正向迭代器进行++操作，指向容器的后一个元素

反向迭代器进行++操作，则指向容器的前一个元素

我们通过迭代器来遍历容器中全部元素，一般来说有四种方式（本人习惯用）：

以下使用vector为例：

基本的迭代器循环
C++11之后，增强版for
lambda表达式与for_each结合，需引用头文件 #include<algorithm>
不需要修改容器元素的话,可以使用常量迭代器

#include<iostream>

//以vector为例

#include<vector>

// 需要使用for_eacj必须引入的算法库函数

#include<algorithm>



using namespace std;



// 遍历

void Test() {

    vector<int> v;

    v.push_back(20);

    v.push_back(10);

    v.push_back(5);



    // 1.基本的循环

    for (auto it = v.begin(); it !=  v.end(); ++it) {

        cout << *it << " ";

    }

    cout << endl;

    // 2.C++11之后，增强版for

    for (const auto& elem : v) {

        cout << elem << " ";

    }

    cout << endl;

    // 3.lambda表达式

    for_each(v.begin(), v.end(), [](int elem) { cout << elem << " "; });

    cout << endl;

    // 4.不需要修改容器元素的话,可以使用常量迭代器

    for (auto it = v.cbegin(); it != v.cend(); ++it) {

        cout << *it << " ";

    }

    cout << endl;

}



void Test_reverse() {

    vector<int> vec;

    for (int i = 0; i < 5; i++) {

        vec.push_back(i);

    }

    // 反向迭代器

    for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {

        cout << *it << " ";

    }

    cout << endl;

    //lambda

    for_each(vec.rbegin(), vec.rend(), [](const auto& elem)-> void { cout << elem << " "; });

}



int main() {

    Test();

    Test_reverse();

    return 0;

}

程序运行结果是:

我们可能会疑惑，在使用基本循环时，为什么用前自增

无论是正向迭代器，还是反向迭代器

我们来回一下 ++重载成前置和后置运算符是这样的：

OPerator OPerator::operator++() {

    // 前置++

    ++n;

    return *this;

}

OPerator OPerator::operator++(int k) {

    // 后置++

    OPerator temp(*this);// 记录修改前的对象

    n++;

    return temp;

}

后置++的底层实现，我们要先保存一个对象temp，多了步骤，肯定执行速度慢于前置++。相同的，迭代器实质上也是一个对象，STL中，在重载迭代器的++运算符时，后置也是慢于前置的，一次可能相差不多，但在次数多的迭代中，差异就会变得明显了。

不同迭代器的具体操作

不同容器的迭代器，其功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。

常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问五种，这里只介绍常用的三种。

1) 正向迭代器。假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。

2) 双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则--p和p--都是有定义的。--p使得 p 朝和++p相反的方向移动。

3) 随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

p+=i：使得 p 往后移动 i 个元素。

p-=i：使得 p 往前移动 i 个元素。

p+i：返回 p 后面第 i 个元素的迭代器。

p-i：返回 p 前面第 i 个元素的迭代器。

p[i]：返回 p 后面第 i 个元素的引用。

此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。p1<p2的含义是：p1 经过若干次（至少一次）++操作后，就会等于 p2。其他比较方式的含义与此类似。

对于两个随机访问迭代器 p1、p2，表达式p2-p1也是有定义的，其返回值是 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。

模拟实现迭代器

（手撕套餐【包括：正向迭代器，反向迭代器，常量正向迭代器，常量反向迭代器】）

我们还需要再模拟一个适配器，以达到使用统一的迭代器对不同的容器都能进行操作

我们知道，迭代器中提供的功能有：

构造函数
operator++函数重载
operator++(int)函数重载
operator--函数重载
operator--(int)函数重载
operator*函数重载
operator->函数重载
operator!=函数重载
operator==函数重载

而正向，反向，常量迭代器，具体的实现内容也有差别，这个时候我们就可以将之分开封装，然后放入我们自己的namespace，也就做到了实现自己的迭代器。

封装好的模板类工程代码

Iterator_for_all_container.h;



#pragma once

#include <iostream>

#include <vector>

#include <list>



using namespace std;



// 正向迭代器

template <class Iterator>

class ForwardIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = typename iterator_traits<Iterator>::reference;

    using pointer = typename iterator_traits<Iterator>::pointer;



    explicit ForwardIterator(Iterator it) : current(it) {}



    reference operator*() {

        return *current;

    }



    // 前置++

    ForwardIterator& operator++() {

        ++current;

        return *this;

    }



    // 后置++

    ForwardIterator operator++(int) {

        ForwardIterator tmp = *this;

        ++(*this);

        return tmp;

    }



    bool operator!=(const ForwardIterator& other) const {

        return current != other.current;

    }

};



// 常量正向迭代器

template <class Iterator>

class ConstForwardIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = const typename iterator_traits<Iterator>::value_type&;

    using pointer = const typename iterator_traits<Iterator>::value_type*;



    explicit ConstForwardIterator(Iterator it) : current(it) {}



    reference operator*() const {

        return *current;

    }



    // 前置++

    ConstForwardIterator& operator++() {

        ++current;

        return *this;

    }



    // 后置++

    ConstForwardIterator operator++(int) {

        ConstForwardIterator tmp = *this;

        ++(*this);

        return tmp;

    }



    bool operator!=(const ConstForwardIterator& other) const {

        return current != other.current;

    }

};



// 反向迭代器

template <class Iterator>

class ReverseIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = typename iterator_traits<Iterator>::reference;



    // 从 std::reverse_iterator 构造

    explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it)

        : current(rev_it.base()) {}



    // 解引用操作符，返回当前迭代器指向的元素

    auto operator*() const {

        Iterator tmp = current;

        --tmp;  // 反向迭代

        return *tmp;

    }



    // 前置递增操作符

    ReverseIterator& operator++() {

        --current;

        return *this;

    }



    // 后置递增操作符

    ReverseIterator operator++(int) {

        ReverseIterator tmp = *this;

        --current;

        return tmp;

    }



    // 比较操作符

    bool operator!=(const ReverseIterator& other) const {

        return current != other.current;

    }



    // 基本迭代器（返回底层迭代器）

    Iterator base() const {

        return current;

    }

};



// 常量反向迭代器

template <class Iterator>

class ConstReverseIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = const typename iterator_traits<Iterator>::value_type&;



    explicit ConstReverseIterator(const std::reverse_iterator<Iterator>& rev_it)

        : current(rev_it.base()) {}



    // 解引用操作符

    auto operator*() const {

        Iterator tmp = current;

        --tmp;  // 反向迭代

        return *tmp;

    }



    // 前置递增

    ConstReverseIterator& operator++() {

        --current;

        return *this;

    }



    // 不等于操作符

    bool operator!=(const ConstReverseIterator& other) const {

        return current != other.current;

    }



    // 基本迭代器（返回底层迭代器）

    Iterator base() const {

        return current;

    }

};



// 适配容器

template <class Container>

class ContainerAdapter {

private:

    Container& container;



public:

    using iterator = typename Container::iterator;

    using const_iterator = typename Container::const_iterator;



    // 构造，初始化

    ContainerAdapter(Container& container) : container(container) {}



    // 正向迭代器

    ForwardIterator<iterator> begin() {

        return ForwardIterator<iterator>(container.begin());

    }



    ForwardIterator<iterator> end() {

        return ForwardIterator<iterator>(container.end());

    }



    // 正向常量迭代器

    ConstForwardIterator<const_iterator> cbegin() const {

        return ConstForwardIterator<const_iterator>(container.cbegin());

    }



    ConstForwardIterator<const_iterator> cend() const {

        return ConstForwardIterator<const_iterator>(container.cend());

    }



   

    // 反向

    ReverseIterator<typename Container::iterator> rbegin() {

        return ReverseIterator<typename Container::iterator>(container.rbegin());

    }



    ReverseIterator<typename Container::iterator> rend() {

        return ReverseIterator<typename Container::iterator>(container.rend());

    }



    // 常量反向迭代器

    ConstReverseIterator<typename Container::const_iterator> crbegin() const {

        return ConstReverseIterator<typename Container::const_iterator>(container.crbegin());

    }



    ConstReverseIterator<typename Container::const_iterator> crend() const {

        return ConstReverseIterator<typename Container::const_iterator>(container.crend());

    }

};

接下来我们来详解一下其中一类迭代器，其他的三个都与之类似，

就以反向迭代器为例吧

这个类 ReverseIterator 实现了一个反向迭代器的自定义模板类，用于使容器支持反向遍历。其主要功能是提供与标准反向迭代器类似的行为，即从容器的尾部开始迭代，并且支持解引用、递增、比较等常见的迭代器操作。

1. 类模板声明与成员变量

template <class Iterator>

class ReverseIterator {

private:

    Iterator current;
    ...
}

这是一个模板类，接受一个类型参数 Iterator，代表底层容器的迭代器类型。
current 是一个成员变量，保存当前迭代器的位置，它将被用来访问容器中的元素。

2. 类型别名

using value_type = typename iterator_traits<Iterator>::value_type;

using reference = typename iterator_traits<Iterator>::reference;

value_type 和 reference 是类型别名，分别代表迭代器所指向的元素类型和值类型的引用。
iterator_traits 是标准库中的一个结构体模板，用于提取给定迭代器类型的相关类型信息，如 value_type 和 reference。
- value_type 是容器中元素的类型。
- reference 是该元素的引用类型，提供通过迭代器对元素进行修改的能力。

3. 构造函数

explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it)

    : current(rev_it.base()) {}

构造函数接收一个 std::reverse_iterator 类型的迭代器 rev_it，并将它转换为该类的 current 成员。
std::reverse_iterator 是标准库提供的反向迭代器，它是通过反向迭代一个正向迭代器来实现的。调用 rev_it.base() 获取底层的正向迭代器，然后将它赋值给 current。

4. 解引用操作符 (operator*)

auto operator*() const {

    Iterator tmp = current;

    --tmp;  // 反向迭代

    return *tmp;

}

该操作符实现了解引用操作，即当迭代器通过 *it 被访问时，返回迭代器当前指向的元素。
由于这是反向迭代器，当你解引用时，实际上要访问 current 前一个位置的元素。所以，使用 --tmp 将迭代器向前移动一个位置，然后返回 *tmp，即当前元素的值。
这样实现确保反向迭代器能从尾部向头部正确地遍历容器。

5. 前置递增操作符 (operator++)

ReverseIterator& operator++() {

    --current;

    return *this;

}

前置递增操作符 (++it) 是标准的递增操作。对于反向迭代器，递增操作实际上是使 current 向前（逆向）移动一个位置。
--current; 使 current 向容器的前一个元素移动。注意，这里实现了递减，而不是递增，因为我们是在进行反向遍历。
返回 *this 是为了支持链式调用，即 ++it; 后可以继续使用迭代器。

6. 后置递增操作符 (operator++(int))

ReverseIterator operator++(int) {

    ReverseIterator tmp = *this;

    --current;

    return tmp;

}

后置递增操作符 (it++) 会先返回当前的迭代器副本，再递增迭代器。
ReverseIterator tmp = *this; 保存当前迭代器的副本。
--current; 递减 current，使迭代器指向前一个元素。
返回 tmp，即递增前的迭代器副本。这与前置递增不同，前置递增直接返回递增后的迭代器，而后置递增返回递增前的迭代器。

7. 不等于操作符 (operator!=)

bool operator!=(const ReverseIterator& other) const {

    return current != other.current;

}

这个操作符用于比较两个反向迭代器是否不相等。
比较的是它们内部的 current 成员（即底层迭代器），如果 current 不相等，表示两个迭代器指向不同的位置，返回 true，表示迭代器不相等。

8. base() 方法

Iterator base() const {

    return current;

}

base() 方法返回底层的正向迭代器 current，它指向容器的一个元素。
这个方法是为了兼容标准库中的 std::reverse_iterator，通过 base() 可以获取反向迭代器的底层正向迭代器。
例如，可以通过 rev_it.base() 获取反向迭代器 rev_it 对应的正向迭代器。

9. 总结

ReverseIterator 类提供了一个反向迭代器的实现，可以用于反向遍历容器。它的关键特性包括：

从正向迭代器转换而来：通过 std::reverse_iterator 构造反向迭代器。
解引用与递增操作：支持解引用操作符（operator*）和递增操作符（operator++），允许反向访问容器的元素。
支持标准迭代器的操作：与标准库的反向迭代器兼容，支持不等于操作符（operator!=）以及底层迭代器的访问（base()）。

该迭代器可以与标准库容器（如 std::vector、std::list 等）配合使用，提供灵活的反向遍历能力

在实现了一个容器的多种迭代器之后，我们就需要再封装一个适配器，以来适应多种容器的不同，让我们的迭代器能够操作，访问不同的容器

我们可以显而易见的看到，ContainerAdapter 类提供了一种方式，将不同类型的迭代器（正向迭代器、常量正向迭代器、反向迭代器和常量反向迭代器）包装起来，并与实际容器相适配。通过这种方式，你可以通过 ContainerAdapter 对容器进行灵活的遍历，而无需直接依赖容器原生的迭代器接口。

主要功能

适配正向迭代器：提供 begin() 和 end() 方法，支持正向遍历容器。
适配常量正向迭代器：提供 cbegin() 和 cend() 方法，支持常量正向遍历容器。
适配反向迭代器：提供 rbegin() 和 rend() 方法，支持反向遍历容器。
适配常量反向迭代器：提供 crbegin() 和 crend() 方法，支持常量反向遍历容器。

我们对模拟的迭代器及其适配进行一个测试

Test.cpp

#include<iostream>

//以vector和list为例

#include<vector>

// 需要使用for_eacj必须引入的算法库函数

#include<algorithm>

#include"Iterator_for_all_container.h"



using namespace std;



// 使用适配器类进行容器的遍历

template <class Container>

void testContainerAdapter(Container& container) {

    // 创建适配器实例

    ContainerAdapter<Container> adapter(container);



    // 正向迭代器测试

    std::cout << "正向迭代器: ";

    for (auto it = adapter.begin(); it != adapter.end(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 正向常量迭代器测试

    std::cout << "正向常量迭代器: ";

    for (auto it = adapter.cbegin(); it != adapter.cend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 反向迭代器测试

    std::cout << "反向迭代器: ";

    for (auto it = adapter.rbegin(); it != adapter.rend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 常量反向迭代器测试

    std::cout << "常量反向迭代器: ";

    for (auto it = adapter.crbegin(); it != adapter.crend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;

    // lambda

    for_each(adapter.crbegin(), adapter.crend(), [](const auto& elem) ->void { std::cout << elem << " "; });

}



void Test_iterator() {

    // 测试 vector

    std::vector<int> vec = { 1, 2, 3, 4, 5 };

    std::cout << "测试 vector 容器:" << std::endl;

    testContainerAdapter(vec);



    // 测试 list

    std::list<int> lst = { 10, 20, 30, 40, 50 };

    std::cout << "\n测试 list 容器:" << std::endl;

    testContainerAdapter(lst);

}



int main() {

    Test_iterator();

    return 0;

}

我们来看看打印出来的结果：

很好，符合预期，特别注明，我们的反向就是在正向的基础上，做相反的操作，这样可以有效减少代码的复用

至于最后一排为什么会有多的一排，那是因为本人又使用for_each算法，结合lambda表达式，遍历了一次反向常量迭代器。

附录（完整的代码声明及定义，以及测试函数）

#pragma once

#include <iostream>

#include <vector>

#include <list>



using namespace std;



// 正向迭代器

template <class Iterator>

class ForwardIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = typename iterator_traits<Iterator>::reference;

    using pointer = typename iterator_traits<Iterator>::pointer;



    explicit ForwardIterator(Iterator it) : current(it) {}



    reference operator*() {

        return *current;

    }



    // 前置++

    ForwardIterator& operator++() {

        ++current;

        return *this;

    }



    // 后置++

    ForwardIterator operator++(int) {

        ForwardIterator tmp = *this;

        ++(*this);

        return tmp;

    }



    bool operator!=(const ForwardIterator& other) const {

        return current != other.current;

    }

};



// 常量正向迭代器

template <class Iterator>

class ConstForwardIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = const typename iterator_traits<Iterator>::value_type&;

    using pointer = const typename iterator_traits<Iterator>::value_type*;



    explicit ConstForwardIterator(Iterator it) : current(it) {}



    reference operator*() const {

        return *current;

    }



    // 前置++

    ConstForwardIterator& operator++() {

        ++current;

        return *this;

    }



    // 后置++

    ConstForwardIterator operator++(int) {

        ConstForwardIterator tmp = *this;

        ++(*this);

        return tmp;

    }



    bool operator!=(const ConstForwardIterator& other) const {

        return current != other.current;

    }

};



// 反向迭代器

template <class Iterator>

class ReverseIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = typename iterator_traits<Iterator>::reference;



    // 从 std::reverse_iterator 构造

    explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it)

        : current(rev_it.base()) {}



    // 解引用操作符，返回当前迭代器指向的元素

    auto operator*() const {

        Iterator tmp = current;

        --tmp;  // 反向迭代

        return *tmp;

    }



    // 前置递增操作符

    ReverseIterator& operator++() {

        --current;

        return *this;

    }



    // 后置递增操作符

    ReverseIterator operator++(int) {

        ReverseIterator tmp = *this;

        --current;

        return tmp;

    }



    // 比较操作符

    bool operator!=(const ReverseIterator& other) const {

        return current != other.current;

    }



    // 基本迭代器（返回底层迭代器）

    Iterator base() const {

        return current;

    }

};



// 常量反向迭代器

template <class Iterator>

class ConstReverseIterator {

private:

    Iterator current;



public:

    using value_type = typename iterator_traits<Iterator>::value_type;

    using reference = const typename iterator_traits<Iterator>::value_type&;



    explicit ConstReverseIterator(const std::reverse_iterator<Iterator>& rev_it)

        : current(rev_it.base()) {}



    // 解引用操作符

    auto operator*() const {

        Iterator tmp = current;

        --tmp;  // 反向迭代

        return *tmp;

    }



    // 前置递增

    ConstReverseIterator& operator++() {

        --current;

        return *this;

    }



    // 不等于操作符

    bool operator!=(const ConstReverseIterator& other) const {

        return current != other.current;

    }



    // 基本迭代器（返回底层迭代器）

    Iterator base() const {

        return current;

    }

};



// 适配容器

template <class Container>

class ContainerAdapter {

private:

    Container& container;



public:

    using iterator = typename Container::iterator;

    using const_iterator = typename Container::const_iterator;



    // 构造，初始化

    ContainerAdapter(Container& container) : container(container) {}



    // 正向迭代器

    ForwardIterator<iterator> begin() {

        return ForwardIterator<iterator>(container.begin());

    }

    ForwardIterator<iterator> end() {

        return ForwardIterator<iterator>(container.end());

    }



    // 正向常量迭代器

    ConstForwardIterator<const_iterator> cbegin() const {

        return ConstForwardIterator<const_iterator>(container.cbegin());

    }

    ConstForwardIterator<const_iterator> cend() const {

        return ConstForwardIterator<const_iterator>(container.cend());

    }

 

    // 反向迭代器

    ReverseIterator<typename Container::iterator> rbegin() {

        return ReverseIterator<typename Container::iterator>(container.rbegin());

    }

    ReverseIterator<typename Container::iterator> rend() {

        return ReverseIterator<typename Container::iterator>(container.rend());

    }

    // 常量反向迭代器

    ConstReverseIterator<typename Container::const_iterator> crbegin() const {

        return ConstReverseIterator<typename Container::const_iterator>(container.crbegin());

    }

    ConstReverseIterator<typename Container::const_iterator> crend() const {

        return ConstReverseIterator<typename Container::const_iterator>(container.crend());

    }

};



#include<iostream>

//以vector和list为例

#include<vector>

// 需要使用for_eacj必须引入的算法库函数

#include<algorithm>

#include"Iterator_for_all_container.h"



// 使用适配器类进行容器的遍历

template <class Container>

void testContainerAdapter(Container& container) {

    // 创建适配器实例

    ContainerAdapter<Container> adapter(container);



    // 正向迭代器测试

    std::cout << "正向迭代器: ";

    for (auto it = adapter.begin(); it != adapter.end(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 正向常量迭代器测试

    std::cout << "正向常量迭代器: ";

    for (auto it = adapter.cbegin(); it != adapter.cend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 反向迭代器测试

    std::cout << "反向迭代器: ";

    for (auto it = adapter.rbegin(); it != adapter.rend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;



    // 常量反向迭代器测试

    std::cout << "常量反向迭代器: ";

    for (auto it = adapter.crbegin(); it != adapter.crend(); ++it) {

        std::cout << *it << " ";

    }

    std::cout << std::endl;

    // lambda

    for_each(adapter.crbegin(), adapter.crend(), [](const auto& elem) ->void { std::cout << elem << " "; });

}



void Test_iterator() {

    // 测试 vector

    std::vector<int> vec = { 1, 2, 3, 4, 5 };

    std::cout << "测试 vector 容器:" << std::endl;

    testContainerAdapter(vec);



    // 测试 list

    std::list<int> lst = { 10, 20, 30, 40, 50 };

    std::cout << "\n测试 list 容器:" << std::endl;

    testContainerAdapter(lst);

}



int main() {

    Test_iterator();

    return 0;

}

查看全文

http://www.kler.cn/a/381723.html