一、入门
1、什么是迭代器？它的作用是什么？
提供对容器元素次序访问的抽象接口，行为类似指针。
- std::vector<int> vec{1,2,3};
- for (auto it = vec.begin(); it != vec.end(); ++it) {
- std::cout << *it << " "; // 输出1 2 3
- }
迭代器就像一个「遥控器」，可以帮你逐个访问容器里的元素。好比用遥控器换台一样，迭代器可以一步步走到下一个元素。
2、迭代器有哪些类别？
- 输入/输出迭代器（只读/写，单遍扫描，如istream_iterator、ostream_iterator）
- 前向迭代器（可读写，多遍扫描，如forward_list的迭代器，好比单链表）
- 双向迭代器（支持--操作，如list的迭代器，好比双向链表）
- 随机访问迭代器（支持+n、-n，如vector的迭代器，好比数组的指针）
3、如何判断两个迭代器是否指向同一个元素？
直接比较迭代器是否相等：if (it1 == it2)。留意：只有同一个容器的迭代器才能比较，否则行为未界说
二、进阶
1、迭代器失效的典型场景有哪些？如何制止？
- vector插入/删除元素：插入可能导致所有迭代器失效（如 vector 插入元素超过容量时）；删除元素后，被删元素后的迭代器失效。 [C++面试] vector 面试点总结-CSDN博客
- for (auto it = vec.begin(); it != vec.end(); ++it) {
- if (*it == 5) {
- vec.erase(it); // it此时已失效！
- }
- }
- // 正确示范：erase返回下一个有效迭代器
- for (auto it = vec.begin(); it != vec.end(); ) {
- if (*it == 5) {
- it = vec.erase(it); // 直接更新it
- } else {
- ++it;
- }
- }
- map/unordered_map删除元素：被删元素的迭代器失效，其他迭代器仍有效。
解决：插入/删除后重新获取迭代器，或使用返回值（如erase返回下一个有效迭代器）
2、迭代器与性能：vector的迭代器访问比索引访问更快吗？
在Release模式下，两者性能几乎雷同（编译器优化后等价于指针运算）。但在list等非一连容器中，迭代器访问更高效（索引访问需要O(n)遍历）。
在非一连容器（如list、forward_list、树布局容器）中，迭代器直接通过指针跳转，无需计算偏移量，因此效率远高于索引访问。list[2]比++迭代器两次慢得多。
list的operator[]或std::advance(it, n)需要从头节点逐个遍历
- std::list<int> lst = {10, 20, 30, 40};
- // 模拟索引访问：获取第3个元素（索引2）
- auto it = lst.begin();
- std::advance(it, 2); // 需要从第1个节点 -> 第2个 -> 第3个
vector的内存是一连的，两者生成的汇编代码完全一致，性能无差异：
- vec会被编译器优化为*(vec.data() + i)（指针算术）
- vector::iterator本质是原生指针，++it等价于ptr +=
4、如何实现一个自界说的迭代器？
需要界说迭代器类，并实现一些必要的操作符重载，如 ++、*、==、!= 等。
- #include <iostream>
- // 自定义容器类
- template <typename T>
- class MyContainer {
- private:
- T* data;
- int size;
- public:
- MyContainer(T* arr, int s) : data(arr), size(s) {}
- // 自定义迭代器类
- class Iterator {
- private:
- T* ptr;
- public:
- Iterator(T* p) : ptr(p) {}
- Iterator& operator++() {
- ++ptr;
- return *this;
- }
- T& operator*() {
- return *ptr;
- }
- bool operator==(const Iterator& other) const {
- return ptr == other.ptr;
- }
- bool operator!=(const Iterator& other) const {
- return ptr != other.ptr;
- }
- };
- Iterator begin() {
- return Iterator(data);
- }
- Iterator end() {
- return Iterator(data + size);
- }
- };
- int main() {
- int arr[] = {1, 2, 3, 4, 5};
- MyContainer<int> container(arr, 5);
- for (auto it = container.begin(); it != container.end(); ++it) {
- std::cout << *it << " ";
- }
- std::cout << std::endl;
- return 0;
- }
1、迭代器traits技能是什么？（也就是：iterator_traits）有什么作用？
总结：Traits就像迭代器的「阐明书」，告诉算法这个迭代器能做什么（好比能否跳步）。
迭代器的 traits 技能是一种利用模板元编程实现的技能，用于在编译时获取迭代器的相干信息，如迭代器的范例、值范例、引用范例等。使算法可以或许根据迭代器的特性举行优化，提高代码的效率和通用性。
- template<typename Iter>
- void print(Iter it) {
- using ValueType = typename std::iterator_traits<Iter>::value_type;
- ValueType val = *it;
- std::cout << val;
- }
- std::vector<int> numbers = {1, 2, 3};
- std::list<double> data = {3.14, 2.71, 1.618};
- // 调用时自动推导类型
- print(vec.begin()); // ValueType是int
- print(data.begin()); // ValueType是double
例如，std::distance根据迭代器范例（随机访问或双向）选择最优实现（O(1)或O(n)）。
范例萃取（Type Traits）是什么？
范例萃取是模板元编程技能，通过编译时范例推断，获取范例的属性或行为。例如：
- 判断一个范例是否为指针。
- 获取迭代器指向元素的范例（value_type）。
- 判断迭代器是否支持随机访问（iterator_category）。
核心头脑：通过模板特化，为不同范例提供同一的接口。
value_type 的作用在泛型算法中声明临时变量或容器时，需要知道元素范例：
- template<typename Iterator>
- void print_element(Iterator it) {
- typename std::iterator_traits<Iterator>::value_type val = *it;
- std::cout << val;
- }
- std::vector<int>::iterator::value_type // int
- std::list<double>::iterator::value_type // double
- 随机访问迭代器：直接计算 end - begin，时间复杂度 O(1)。
- 其他迭代器：逐个递增直到到达终点，时间复杂度 O(n)。
2、C++20中的std::ranges如何依赖迭代器？
ranges库通过概念（Concepts）束缚迭代器范例，例如：
- template<std::random_access_iterator Iter>
- void my_sort(Iter begin, Iter end);
概念（Concepts） 是 C++20 引入的模板参数束缚机制，用于明白要求模板参数必须满足的接口或行为。你可以把它想象成一种“编译时合同”——假如范例不满足概念的要求，代码将无法编译。
为什么要用概念？
传统的 STL 算法（如 std::sort）依赖迭代器范例，但缺乏明白的束缚。例如，假如你误将 std::list 的迭代器传给 std::sort，代码会编译，但运行时崩溃（由于 std::list 迭代器不支持随机访问）。通过概念，错误会在编译时被捕获。
- #include <ranges>
- #include <vector>
- #include <list>
- // 只有支持随机访问的迭代器才能调用此函数
- // std::random_access_iterator 是一个预定义概念，要求迭代器支持 +, -, [] 等操作。
- void my_sort(std::random_access_iterator auto begin,
- std::random_access_iterator auto end) {
- // 实现排序...
- }
- int main() {
- std::vector<int> vec = {3, 1, 4}; // vector 的迭代器是随机访问类型
- std::list<int> lst = {3, 1, 4}; // list 的迭代器是双向类型
- my_sort(vec.begin(), vec.end()); // ✅ 编译通过
- my_sort(lst.begin(), lst.end()); // ❌ 编译错误：双向迭代器不满足随机访问概念
- }
传统 STL 的问题：
竣事迭代器必须与起始迭代器范例雷同。例如，std::find(begin, end, value) 中 begin 和 end 必须是同范例迭代器。
Sentinel 的改进：
std::ranges 答应 迭代器与竣事标记（Sentinel）范例不同。例如，可以用一个特殊值（如 nullptr）作为链表遍历的竣事标记。
示例：以空指针为哨兵的链表
- struct Node {
- int data;
- Node* next;
- };
- // 自定义迭代器（指向链表节点）
- struct Iterator {
- Node* ptr;
- int& operator*() const { return ptr->data; }
- Iterator& operator++() { ptr = ptr->next; return *this; }
- bool operator!=(std::nullptr_t) const { return ptr != nullptr; } // 与哨兵比较
- };
- // 遍历链表
- Node* head = ...; // 链表头节点
- for (Iterator it{head}; it != nullptr; ++it) { // ✅ 结束标记是 nullptr
- std::cout << *it;
- }
- 竣事标记 nullptr 是一个哨兵，范例与迭代器不同。
- 迭代器只需实现与哨兵的比较操作（如 operator!=），即可表现范围竣事。
std::ranges 如何联合概念和哨兵？std::ranges 的算法直接接受一个 范围（Range），而范围由迭代器和哨兵界说
- #include <ranges>
- #include <vector>
- int main() {
- std::vector<int> vec = {3, 1, 4, 1, 5};
- // 传统 STL：需要 begin 和 end
- std::sort(vec.begin(), vec.end());
- // Ranges 风格：直接传递整个范围
- std::ranges::sort(vec); // ✅ 更简洁
- // 自定义范围（迭代器 + 哨兵）
- // std::ranges::subrange 可以组合任意类型的迭代器和哨兵。
- auto custom_range = std::ranges::subrange(
- Iterator{head}, // 起始迭代器
- nullptr // 结束哨兵
- );
- std::ranges::for_each(custom_range, [](int x){ /*...*/ });
- }
- class AnyIterator {
- struct Concept { virtual void next() = 0; /*...*/ };
- template<typename Iter> struct Model : Concept { /*...*/ };
- std::unique_ptr<Concept> impl;
- public:
- template<typename Iter> AnyIterator(Iter it) : impl(new Model<Iter>(it)) {}
- // 重载operator*等接口
- };
- 运行时多态：将详细范例的操作抽象为接口（如虚函数）。
- 范例无关性：外部代码仅依赖接口，不关心内部详细范例。
常见应用：
- std::function：可保存任何可调用对象（函数、Lambda、函数对象）。
- std::any：可保存恣意范例的值。
- std::shared_ptr 的删除器：隐藏资源释放的详细逻辑。
4、为什么STL迭代器不通过继承实现多态（如抽象基类）？
为了制止虚函数调用开销，同时保持静态多态特性。通过模板和Traits，STL在编译期确定迭代器范例，生成高效代码。
STL（Standard Template Library）的迭代器设计依照 “零开销抽象” 原则，即在不牺牲性能的条件下提供泛型本领。若使用继承和虚函数实现多态（如抽象基类），会带来以下问题：
4.1 性能开销：虚函数与动态绑定的代价
- 虚函数需要通过虚表（vtable）举行动态绑定，每次调用需要额外的间接寻址（vptr → vtable → function），无法被编译器内联优化。
- 每个对象需要存储虚表指针（vptr），对于轻量级迭代器（如原生指针或简单包装类），这会明显增加内存占用。
- 虚函数调用可能导致缓存未命中，低落性能。
4.2 范例信息丢失与泛化本领
若迭代器继承自抽象基类，其详细范例在运行时才能确定，导致以下问题：(1)无法静态分派（static dispatch）特定操作（如 std::advance(it, n) 对随机访问迭代器的优化）。(2)无法通过迭代器标签（Iterator Tags） 在编译期选择最优算法实现（如 std::sort 需要随机访问迭代器）。(3)STL算法依赖迭代器的范例特性（Traits）（如 iterator_category、value_type），这些信息必须在编译期可知。若使用运行时多态，范例信息会被擦除，无法静态检查。
4.3 代码膨胀的衡量
固然模板可能导致代码膨胀（为不同范例生成多份代码），但：
- 当代编译器会对雷同底层范例的模板实例化举行代码归并（如 vector<int>::iterator 和 array<int>::iterator 可能共享实现）。
- STL迭代器通常轻量（如指针或简单包装类），模板生成的代码效率远高于虚函数动态绑定的开销。
4.4 STL迭代器的设计哲学
5、const_iterator与iterator的隐式转换
const迭代器不能隐式转为非const迭代器，但反之答应。
6、在多线程环境下，迭代器的使用需要留意什么？
假如多个线程同时访问和修改容器，可能会导致迭代器失效或数据不一致的问题。需要使用同步机制（如互斥锁）来保证线程安全。
在一个线程中使用的迭代器可能会由于另一个线程对容器的修改而失效。因此，需要确保迭代器在使用期间容器不会被修改。
- #include <iostream>
- #include <vector>
- #include <thread>
- #include <mutex>
- std::vector<int> vec = {1, 2, 3, 4, 5};
- std::mutex mtx;
- void printVector() {
- std::lock_guard<std::mutex> lock(mtx);
- for (auto it = vec.begin(); it != vec.end(); ++it) {
- std::cout << *it << " ";
- }
- std::cout << std::endl;
- }
- void modifyVector() {
- std::lock_guard<std::mutex> lock(mtx);
- vec.push_back(6);
- }
- int main() {
- std::thread t1(printVector);
- std::thread t2(modifyVector);
- t1.join();
- t2.join();
- return 0;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
