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
时,为了能够适配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;
}
练习
- 使用
std::for_each
和Lambda
表达式遍历一个std::vector
,并输出每个元素的平方。 - 使用
std::find
在一个std::list
中查找指定元素,并输出其位置。 - 使用
std::sort
对一个std::deque
进行排序,并输出排序后的结果。 - 使用
std::copy
将一个std::vector
中的元素复制到一个std::list
中。 - 使用
std::transform
将一个std::vector
中的字符串转换为大写,并输出结果。
码字不易,欢迎大家点赞,关注,评论,谢谢!
C++训练营
专为校招、社招3年工作经验的同学打造的1V1 C++训练营,量身定制学习计划、每日代码review,简历优化,面试辅导,已帮助多名学员获得大厂offer!