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

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

博主介绍:程序喵大人

  • 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时,为了能够适配STLalgorithm,也需要实现iterator相关的方法。

iterator是什么类型?

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

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

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

注意上面我的代码中既有iterator,又有const_iterator,它俩有什么区别,估计你能猜得到,但这个其实也需要结合语境,比如string_view中,它是个视图的概念,iteratorconst_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,而不是自己usingtypedef一套自己的iterator,但值得注意的是std::iteratorC++17标准中已经被标记为**deprecated**


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

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

迭代器的使用与遍历

使用

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

遍历

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

遍历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_eachLambda表达式遍历一个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)