第10章 STL迭代器与算法

让 C++ 容器在 Python 中可迭代是扩展模块的常见需求。本章讲解如何使用 pybind11 将 C++ 迭代器暴露给 Python。

10.1 C++ 迭代器基础回顾

C++ 中，迭代器是一对方法：

• begin() 返回指向首元素的迭代器
• end() 返回指向「尾后」位置的迭代器

std::vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << std::endl;
}

pybind11 将这一模式映射到 Python 的迭代器协议。

10.2 Python 迭代器协议

Python 的迭代器协议要求对象实现两个方法：

• __iter__()：返回迭代器本身
• __next__()：返回下一个元素，迭代结束时抛出 StopIteration

使用 py::make_iterator 可以简化绑定：

#include <pybind11/pybind11.h>
#include <vector>
#include <string>

namespace py = pybind11;

class IntRange {
public:
    IntRange(int start, int end) : start_(start), end_(end) {}

    int start() const { return start_; }
    int end() const { return end_; }

private:
    int start_;
    int end_;
};

PYBIND11_MODULE(example, m) {
    py::class_<IntRange>(m, "IntRange")
        .def(py::init<int, int>())
        .def("start", &IntRange::start)
        .def("end", &IntRange::end)
        // 暴露迭代器
        .def("__iter__", [](IntRange& r) {
            return py::make_iterator(r.start(), r.end());
        }, py::keep_alive<0, 1>());  // 保持 IntRange 存活直到迭代结束
}

>>> import example
>>> r = example.IntRange(0, 5)
>>> for i in r:
...     print(i)
0
1
2
3
4

关键洞察：py::make_iterator(start, end) 创建迭代器对象。py::keep_alive<0, 1>() 确保被迭代的对象（第一个参数）在迭代器（第二个参数）销毁前不被释放。这防止「迭代过程中对象被回收」的use-after-free 错误。

10.3 容器切片操作

Python 支持切片语法 container[start:end]。要让 C++ 容器支持切片，需要实现 __getitem__：

#include <pybind11/pybind11.h>
#include <vector>
#include <stdexcept>

namespace py = pybind11;

class IntVector {
public:
    IntVector(std::vector<int> data) : data_(std::move(data)) {}

    // 支持 v[index] 访问
    int __getitem__(ssize_t index) {
        if (index < 0) index += data_.size();
        if (index < 0 || index >= static_cast<ssize_t>(data_.size())) {
            throw py::index_error();
        }
        return data_[index];
    }

    // 支持 v[start:end] 切片
    std::vector<int> __getitem__(py::slice slice) {
        ssize_t start, stop, step, slicelength;
        if (!slice.compute(data_.size(), &start, &stop, &step, &slicelength)) {
            throw py::error_already_set();
        }
        std::vector<int> result(slicelength);
        for (ssize_t i = 0; i < slicelength; ++i) {
            result[i] = data_[start + i * step];
        }
        return result;
    }

    ssize_t __len__() const { return data_.size(); }

private:
    std::vector<int> data_;
};

PYBIND11_MODULE(example, m) {
    py::class_<IntVector>(m, "IntVector")
        .def(py::init<std::vector<int>>())
        .def("__len__", &IntVector::__len__)
        .def("__getitem__", &IntVector::__getitem__)
        // Python 切片支持
        .def("__getitem__", [](IntVector& v, py::slice slice) {
            return v.__getitem__(slice);
        });
}

>>> v = example.IntVector([10, 20, 30, 40, 50])
>>> v[0]
10
>>> v[-1]
50
>>> v[1:4]
[20, 30, 40]
>>> v[::2]
[10, 30, 50]

10.4 range 对象

Python 的 range() 是惰性求值的迭代器。C++ 端可以实现类似功能：

class Range {
public:
    Range(int start, int stop, int step = 1)
        : start_(start), stop_(stop), step_(step) {}

    class Iterator {
    public:
        Iterator(int value, int step) : value_(value), step_(step) {}

        int operator*() const { return value_; }
        void operator++() { value_ += step_; }
        bool operator!=(const Iterator& other) const {
            return value_ < other.value_;
        }
        bool operator==(const Iterator& other) const {
            return value_ >= other.value_;
        }

    private:
        int value_;
        int step_;
    };

    Iterator begin() const { return Iterator(start_, step_); }
    Iterator end() const { return Iterator(stop_, step_); }

private:
    int start_;
    int stop_;
    int step_;
};

PYBIND11_MODULE(example, m) {
    py::class_<Range>(m, "Range")
        .def(py::init<int, int, int>(), "", py::arg("start"), py::arg("stop"), py::arg("step") = 1)
        .def("__iter__", [](const Range& r) {
            return py::make_iterator(r.begin(), r.end());
        }, py::keep_alive<0, 1>());
}

>>> r = example.Range(0, 10, 2)
>>> list(r)
[0, 2, 4, 6, 8]
>>> for x in example.Range(5, 0, -1):
...     print(x)
5
4
3
2
1

迭代器与容器的区别

Python 中有两类可迭代对象：

1. 容器（Container）：实现 __iter__()，每次调用创建新迭代器
2. 迭代器（Iterator）：实现 __iter__()（返回自身）和 __next__()

// 容器：每次 __iter__ 创建新迭代器
py::class_<MyContainer>(m, "MyContainer")
    .def("__iter__", [](MyContainer& c) {
        return py::make_iterator(c.begin(), c.end());
    }, py::keep_alive<0, 1>());

// 迭代器：__iter__ 返回 self，__next__ 推进
py::class_<MyIterator>(m, "MyIterator")
    .def("__iter__", [](MyIterator& self) -> MyIterator& { return self; })
    .def("__next__", [](MyIterator& self) {
        if (!self.has_next()) throw py::stop_iteration();
        return self.next();
    });

STL 算法支持

要让 C++ STL 算法在 Python 中可用，绑定核心函数即可：

#include <algorithm>

int find_in_sorted(const std::vector<int>& vec, int target) {
    auto it = std::lower_bound(vec.begin(), vec.end(), target);
    if (it != vec.end() && *it == target) {
        return std::distance(vec.begin(), it);
    }
    return -1;  // 未找到
}

PYBIND11_MODULE(example, m) {
    m.def("find_in_sorted", &find_in_sorted);
}

>>> example.find_in_sorted([1, 3, 5, 7, 9], 5)
2
>>> example.find_in_sorted([1, 3, 5, 7, 9], 4)
-1

关键洞察：C++ STL 算法（如 std::sort、std::find、std::transform）在 Python 中可以通过绑定关键函数来暴露。不必将整个算法库绑定——选择那些 Python 端高频使用的即可。结合 NumPy 的向量化操作，C++ 算法可以处理大规模数据。

常见陷阱

1. 迭代器生命周期

// 错误：迭代器引用的对象可能已被销毁
py::make_iterator(v.end(), v.end())  // v 已销毁！

2. 保持容器存活

// 正确：使用 keep_alive 确保容器存活
.def("__iter__", [](MyContainer& c) {
    return py::make_iterator(c.begin(), c.end());
}, py::keep_alive<0, 1>())

3. 迭代器协议返回类型

class BadIterator {
    def __iter__(self): return self
    def __next__(self): return self  # 错误！应返回元素

关键洞察：pybind11 的 py::make_iterator 是绑定迭代器的最简洁方式。但要记住三个要点：

1. 确保迭代器引用的对象在迭代期间有效（keep_alive）
2. __next__ 返回元素值，而非另一个迭代器
3. 迭代结束时抛出 py::stop_iteration() 或使用 py::make_iterator 自动处理