#include <iostream>
#include <vector>       // 向量，提供随机访问迭代器
#include <list>         // 双向链表，提供双向迭代器
#include <forward_list> // 单向链表，提供前向迭代器
#include <algorithm>    // 算法库，如 find, sort, reverse
using namespace std;

int main() {
    // ---------- 1. 前向迭代器示例：forward_list ----------
    forward_list<int> flist = {5, 2, 8, 1};  // 单向链表
    cout << "forward_list (只能向前): ";
    auto it_f = flist.begin();  // 获取起始迭代器
    auto saved = it_f;          // 保存副本（可以多次遍历）
    while (it_f != flist.end()) {  // 第一次遍历
        cout << *it_f << " ";      // 读取元素
        ++it_f;                    // 前进一步
    }
    cout << endl;

    // 用保存的副本再次遍历
    cout << "第二次遍历 saved: ";
    while (saved != flist.end()) {
        cout << *saved << " ";
        ++saved;
    }
    cout << endl;

    // ---------- 2. 双向迭代器示例：list ----------
    list<int> lst = {9, 4, 7, 2};  // 双向链表
    auto it_l = lst.begin();      // 起始迭代器
    // 向前走两步
    ++it_l;   // 现在指向 4
    ++it_l;   // 现在指向 7
    cout << "list 当前元素: " << *it_l << endl;   // 输出 7
    // 后退一步
    --it_l;   // 现在指向 4
    cout << "后退后元素: " << *it_l << endl;     // 输出 4

    // 反向遍历（使用双向迭代器的递减）
    cout << "反向遍历list: ";
    auto rit = lst.end();   // 注意：end() 指向最后一个元素之后
    while (rit != lst.begin()) {
        --rit;              // 先退一步，再读取
        cout << *rit << " ";
    }
    cout << endl;

    // ---------- 3. 随机访问迭代器示例：vector ----------
    vector<int> vec = {1, 2, 3, 4, 5, 6};  // 动态数组
    auto it_v = vec.begin();               // 起始迭代器
    // 直接跳转
    cout << "vector 第3个元素 (it+2): " << *(it_v + 2) << endl;  // 输出 3
    cout << "vector 第5个元素 via []: " << it_v[4] << endl;      // 输出 5
    // 计算两个迭代器之间的距离
    cout << "两个迭代器距离 (end - begin): " << (vec.end() - vec.begin()) << endl;  // 输出 6

    // sort 需要随机访问迭代器，vector 满足
    sort(vec.begin(), vec.end());  // 默认从小到大排序
    cout << "排序后 vector: ";
    for (int x : vec) cout << x << " ";
    cout << endl;

    // ---------- 4. 算法对不同迭代器等级的要求 ----------
    // find 只需要输入迭代器，vector 的随机访问迭代器也可以使用
    auto found = find(vec.begin(), vec.end(), 4);
    if (found != vec.end()) {
        cout << "找到4在位置: " << (found - vec.begin()) << endl;
    }

    // reverse 需要双向迭代器，list 满足
    reverse(lst.begin(), lst.end());  // 翻转 list
    cout << "翻转后 list: ";
    for (int x : lst) cout << x << " ";
    cout << endl;

    // 下面这行会编译错误，因为 forward_list 不是双向：
    // reverse(flist.begin(), flist.end());  // 错误！

    return 0;
}

from collections import deque

# 1. 前向迭代器模拟（用生成器只能向前）
def forward_iterator(iterable):
    """只允许前向移动的迭代器（通过yield from）"""
    it = iter(iterable)  # 获取迭代器
    for x in it:         # 只能往前
        yield x

# 使用
flist = [5, 2, 8, 1]
print("前向迭代器遍历:")
for x in forward_iterator(flist):
    print(x, end=" ")
print()

# 2. 双向迭代器模拟（deque 支持正向和反向遍历）
d = deque([9, 4, 7, 2])
print("\ndeque 正向遍历:")
for x in d:
    print(x, end=" ")
print("\ndeque 反向遍历:")
for x in reversed(d):
    print(x, end=" ")
print()

# 3. 随机访问迭代器（Python 列表天然支持）
vec = [1, 2, 3, 4, 5, 6]
print("\n向量第3个元素:", vec[2])   # 下标访问
print("向量第5个元素:", vec[4])
print("索引距离:", len(vec))       # 长度
vec.sort()                         # 排序
print("排序后:", vec)
print("倒数第2个元素:", vec[-2])   # 也支持负索引