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

C++基础系列【24】STL迭代器和算法

article 2025/3/18 13:12:07

博主介绍：程序喵大人

  • 35- 资深C/C++/Rust/Android/iOS客户端开发
  • 10年大厂工作经验
  • 嵌入式/人工智能/自动驾驶/音视频/游戏开发入门级选手
  • 《C++20高级编程》《C++23高级编程》等多本书籍著译者
  • 更多原创精品文章，首发gzh，见文末
  • 👇👇记得订阅专栏，以防走丢👇👇
    😉C++基础系列专栏
    😃C语言基础系列专栏
    🤣C++大佬养成攻略专栏
    🤓C++训练营

迭代器是STL的核心组件之一，它提供了一种统一的方式来遍历容器中的元素。

而STL算法库则提供了大量高效的通用算法，方便程序员操作容器中的数据。

迭代器

C++中，iterator（迭代器）是个很重要的理念。

有了它，STL容器和算法才能解耦，而它可以理解为两者之间联系的一个桥梁。

iterator的语义其实和指针比较相似，可以++又可以--的。

迭代器类似于指针，它用于遍历容器中的元素。

它的主要特点就是它提供了一种统一的方式来访问容器中的元素，而不需要关心容器的具体实现。

先看下它的简单使用：

#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main() {
    vector<int> ar = {1, 2, 3, 4, 5};
    for (vector<int>::iterator ptr = ar.begin(); ptr < ar.end(); ptr++) {
        cout << *ptr << " ";
    }
}

根据功能的不同，迭代器可以分为以下几类：

  • 输入迭代器（Input Iterator）：支持读取元素，只能单向遍历。
  • 输出迭代器（Output Iterator）：支持写入元素，只能单向遍历。
  • 前向迭代器（Forward Iterator）：支持读取和写入元素，只能单向遍历。
  • 双向迭代器（Bidirectional Iterator）：支持读取和写入元素，可以双向遍历。
  • 随机访问迭代器（Random Access Iterator）：支持读取和写入元素，可以随机访问。

它们之间的关系如图：

通过图片你应该就能明白这几种iterator的作用和关系了，如果你想知道自己使用的iterator是什么类型，可以访问一下它的iterator_category，一般的iterator都会指定它的category，这里不理解没关系，继续往下看，后面有代码示例。

像常见的STL，都会实现一套自己的iterator方法，主要就是begin()，end()这种，比如vector，这里贴一下vector的源码：

其它的STL也是类似的。

我们自定义class时，为了能够适配STL的algorithm，也需要实现iterator相关的方法。

那iterator是什么类型？

这个我们可以自己定义，需要结合实际情况，一般情况下是个指针，比如我之前的代码中是这样定义的：

在begin()时候返回首地址即可，然后它++、–其实就是指针的++、--。

当然iterator的标准实现比我这个复杂，一般都会单独写一个iterator类，然后自己的class再依赖它。

注意上面我的代码中既有iterator，又有const_iterator，它俩有什么区别，估计你能猜得到，但这个其实也需要结合语境，比如string_view中，它是个视图的概念，iterator和const_iterator没啥区别，但是在其它语境下可能就不一样了。

我再贴一个比较容易理解的自定义iterator的代码：

#include <cstddef>
#include <iterator>
class Integers {
public:
struct Iterator {
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = int;
using pointer = int*;
using reference = int&;
Iterator(pointer ptr) : m_ptr(ptr) {}
reference operator*() const { return *m_ptr; }
pointer operator->() { return m_ptr; }
Iterator& operator++() {
    m_ptr++;
    return *this;
}
Iterator operator++(int) {
    Iterator tmp = *this;
    ++(*this);
    return tmp;
}
friend bool operator==(const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
friend bool operator!=(const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };
private:
pointer m_ptr;
};
Iterator begin() { return Iterator(&m_data[0]); }
Iterator end() { return Iterator(&m_data[200]); }
private:
int m_data[200];
};

大家一定要确保自己理解了上面代码。

可能有些人会直接使用std::iterator，而不是自己using或typedef一套自己的iterator，但值得注意的是std::iterator在C++17标准中已经被标记为**deprecated**。


估计在未来std::iterator会退出C++的舞台，所以还是建议自定义iterator。

我们平时编程中可能不一定会用到自定义iterator，但是有一点我们需要知道：iterator是container和algorithm之间的桥梁、润滑剂而存在，这个设计理念值得我们学习。

迭代器的使用与遍历

使用

  • 解引用：使用*操作符访问迭代器指向的元素。
  • 递增：使用++操作符将迭代器移动到下一个元素。
  • 递减：使用--操作符将迭代器移动到上一个元素（仅适用于双向迭代器和随机访问迭代器）。
  • 比较：使用==和!=操作符比较两个迭代器是否指向同一个元素。

遍历

使用迭代器可以方便地遍历容器中的元素。

遍历std::vector

#include <iostream>
#include <vector>

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

    // 使用迭代器遍历vector
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " "; // 输出：1 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}

遍历std::list

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 使用迭代器遍历list
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " "; // 输出：1 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}

遍历std::map

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> m = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};

    // 使用迭代器遍历map
    for (std::map<std::string, int>::iterator it = m.begin(); it != m.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
    // 输出：
    // Alice: 25
    // Bob: 30
    // Charlie: 35

    return 0;
}

STL算法库

STL算法库提供了大量高效的通用算法，用于操作容器中的数据。这些算法通常通过迭代器来访问容器中的元素。

迭代器是算法与容器的桥梁。

std::for_each

std::for_each用于对容器中的每个元素执行指定的操作。

#include <iostream>
#include <vector>
#include <algorithm>

void print(int num) {
    std::cout << num << " ";
}

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

    // 使用std::for_each遍历vector
    std::for_each(vec.begin(), vec.end(), print); // 输出：1 2 3 4 5
    std::cout << std::endl;

    return 0;
}

std::find

std::find用于在容器中查找指定值的元素。

#include <iostream>
#include <vector>
#include <algorithm>

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

    // 使用std::find查找元素
    std::vector<int>::iterator it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found: " << *it << std::endl; // 输出：Found: 3
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

std::sort

std::sort用于对容器中的元素进行排序。

#include <iostream>
#include <vector>
#include <algorithm>

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

    // 使用std::sort排序
    std::sort(vec.begin(), vec.end());

    // 输出排序后的vector
    for (int num : vec) {
        std::cout << num << " "; // 输出：1 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}

std::copy

std::copy用于将一个容器中的元素复制到另一个容器中。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2(5);

    // 使用std::copy复制元素
    std::copy(vec1.begin(), vec1.end(), vec2.begin());

    // 输出复制后的vector
    for (int num : vec2) {
        std::cout << num << " "; // 输出：1 2 3 4 5
    }
    std::cout << std::endl;

    return 0;
}

std::transform

std::transform用于对容器中的元素进行转换。

#include <iostream>
#include <vector>
#include <algorithm>

int square(int num) {
    return num * num;
}

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2(5);

    // 使用std::transform对元素进行平方运算
    std::transform(vec1.begin(), vec1.end(), vec2.begin(), square);

    // 输出转换后的vector
    for (int num : vec2) {
        std::cout << num << " "; // 输出：1 4 9 16 25
    }
    std::cout << std::endl;

    return 0;
}

std::accumulate

std::accumulate用于计算容器中元素的累加和。

#include <iostream>
#include <vector>
#include <numeric>

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

    // 使用std::accumulate计算累加和
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "Sum: " << sum << std::endl; // 输出：Sum: 15

    return 0;
}

练习

  1. 使用std::for_each和Lambda表达式遍历一个std::vector，并输出每个元素的平方。
  2. 使用std::find在一个std::list中查找指定元素，并输出其位置。
  3. 使用std::sort对一个std::deque进行排序，并输出排序后的结果。
  4. 使用std::copy将一个std::vector中的元素复制到一个std::list中。
  5. 使用std::transform将一个std::vector中的字符串转换为大写，并输出结果。

码字不易，欢迎大家点赞，关注，评论，谢谢！

C++训练营

专为校招、社招3年工作经验的同学打造的1V1 C++训练营，量身定制学习计划、每日代码review，简历优化，面试辅导，已帮助多名学员获得大厂offer！

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

相关文章：

  • leetcode501-二叉搜索树中的众数
  • Blender-MCP服务源码4-初始化项目解读
  • c++ 类和对象 —— 中 【复习笔记】
  • 物联网中RFID标签需要人为赋予信息和手动粘贴/挂载的问题
  • 【NeurIPS 2024】LLM-ESR：用大语言模型破解序列推荐的长尾难题
  • 4张图，9个方法，搞定 “信贷风控策略调优”
  • 使用unplugin-auto-import自动导入vue3的api，不需要在每一个.vue文件中重复去导入操作
  • 蓝桥杯嵌入式赛道复习笔记1(按键控制LED灯，双击按键，单击按键，长按按键）
  • SpringBoot（6）——Springboot整合springmvc
  • 量子计算 × 虚拟现实：未来科技的双剑合璧
  • 遥感数据处理
  • Linux:信号的生命周期分析，以及捕捉信号时中断触发的内核态拦截与用户态处理时机
  • 下拉菜单+DoTween插件
  • Houdini :《哪吒2》神话与科技碰撞的创新之旅
  • C语言经典代码题
  • 从 YOLOv1 到 YOLOv2：目标检测的进化之路
  • 轨迹规划：基于查找的(search-based)路径规划算法
  • C#特性和反射
  • MySQL高频八股——事务过程中Undo log、Redo log、Binlog的写入顺序（涉及两阶段提交）
  • 异常（11）