19.7 迭代器与Circulator

在本节中你将学到…

Circulator的概念和设计理念
Circulator与STL迭代器的区别
如何编写自定义Circulator
CGAL中Circulator的实际应用
迭代器适配器的使用技巧

19.7.1 概念解释

什么是Circulator？

Circulator（循环器）是CGAL提供的一种特殊迭代器，用于遍历环形数据结构。与STL迭代器不同，Circulator没有”终点”的概念——当你到达结构的末尾时，会自动回到开头。

类比理解：想象你在一个圆形跑道上跑步：

STL迭代器：像在有终点的直道上跑步，到达终点就不能继续了
Circulator：像在圆形跑道上跑步，跑完一圈自动回到起点，可以无限循环

Circulator vs 迭代器

特性	STL迭代器	Circulator
范围	[begin, end)	循环结构
终点	有明确的end()	没有终点
递增	++it可能到达end()	++it循环回到开头
大小	std::distance给出元素个数	size()给出循环中的元素数
适用场景	线性容器	环形结构（多边形顶点、网格半边等）

为什么需要Circulator？

几何数据结构通常是循环的：

多边形：顶点构成一个环
网格面：边界顶点/边构成环
Delaunay三角剖分：每个顶点的邻接点构成环

使用STL迭代器处理这些结构会很笨拙：

// 笨拙的STL方式：需要特殊处理首尾连接
for (auto it = polygon.vertices_begin(); it \!= polygon.vertices_end(); ++it) {
    auto next = std::next(it);
    if (next == polygon.vertices_end()) next = polygon.vertices_begin();
    // 处理 *it 和 *next 的关系
}
 
// 优雅的Circulator方式：自动循环
auto circ = polygon.vertices_circulator();
auto start = circ;
 do {
    auto next = circ;
    ++next;  // 自动循环，无需检查终点
    // 处理 *circ 和 *next 的关系
    ++circ;
} while (circ \!= start);

19.7.2 代码示例

基础示例：理解Circulator

#include <iostream>
#include <vector>
#include <memory>
 
// ============================================
// 简单的Circulator实现
// ============================================
 
template <typename T>
class SimpleCirculator {
    const std::vector<T>* container;
    size_t index;
    
public:
    // 迭代器类型定义
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
    
    // 构造函数
    SimpleCirculator() : container(nullptr), index(0) {}
    SimpleCirculator(const std::vector<T>* c, size_t i) 
        : container(c), index(i) {}
    
    // 解引用
    reference operator*() const { return (*container)[index]; }
    pointer operator->() const { return &((*container)[index]); }
    
    // 递增（循环）
    SimpleCirculator& operator++() {
        if (container) {
            index = (index + 1) % container->size();
        }
        return *this;
    }
    
    SimpleCirculator operator++(int) {
        SimpleCirculator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    // 递减（循环）
    SimpleCirculator& operator--() {
        if (container) {
            index = (index == 0) ? container->size() - 1 : index - 1;
        }
        return *this;
    }
    
    SimpleCirculator operator--(int) {
        SimpleCirculator tmp = *this;
        --(*this);
        return tmp;
    }
    
    // 比较
    bool operator==(const SimpleCirculator& other) const {
        return container == other.container && index == other.index;
    }
    
    bool operator\!=(const SimpleCirculator& other) const {
        return \!(*this == other);
    }
    
    // Circulator特有：获取循环大小
    size_t size() const { return container ? container->size() : 0; }
    
    // Circulator特有：判断是否为空循环
    bool is_empty() const { return \!container || container->empty(); }
};
 
// ============================================
// 使用示例
// ============================================
 
int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    
    // 创建Circulator
    SimpleCirculator<int> circ(&data, 0);
    
    std::cout << "Forward traversal (2 cycles):" << std::endl;
    auto start = circ;
    int count = 0;
    do {
        std::cout << *circ << " ";
        ++circ;
        ++count;
    } while (circ \!= start && count < 10);  // 限制循环次数防止无限循环
    
    std::cout << "\n\nBackward traversal:" << std::endl;
    count = 0;
    do {
        std::cout << *circ << " ";
        --circ;
        ++count;
    } while (circ \!= start && count < 5);
    
    std::cout << "\n\nCirculator size: " << circ.size() << std::endl;
    
    return 0;
}

中级示例：多边形Circulator

#include <iostream>
#include <vector>
#include <math>
 
// ============================================
// 多边形顶点和边的Circulator
// ============================================
 
struct Point2D {
    double x, y;
    Point2D(double x = 0, double y = 0) : x(x), y(y) {}
};
 
// 顶点Circulator
template <typename Polygon>
class VertexCirculator {
    const Polygon* poly;
    size_t vertex_idx;
    
public:
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef typename Polygon::Point Point;
    typedef Point value_type;
    typedef const Point* pointer;
    typedef const Point& reference;
    typedef std::ptrdiff_t difference_type;
    
    VertexCirculator() : poly(nullptr), vertex_idx(0) {}
    VertexCirculator(const Polygon* p, size_t idx) : poly(p), vertex_idx(idx) {}
    
    reference operator*() const { return poly->vertex(vertex_idx); }
    pointer operator->() const { return &poly->vertex(vertex_idx); }
    
    VertexCirculator& operator++() {
        vertex_idx = (vertex_idx + 1) % poly->number_of_vertices();
        return *this;
    }
    
    VertexCirculator operator++(int) {
        VertexCirculator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    VertexCirculator& operator--() {
        size_t n = poly->number_of_vertices();
        vertex_idx = (vertex_idx == 0) ? n - 1 : vertex_idx - 1;
        return *this;
    }
    
    VertexCirculator operator--(int) {
        VertexCirculator tmp = *this;
        --(*this);
        return tmp;
    }
    
    bool operator==(const VertexCirculator& other) const {
        return poly == other.poly && vertex_idx == other.vertex_idx;
    }
    
    bool operator\!=(const VertexCirculator& other) const {
        return \!(*this == other);
    }
    
    // 获取当前顶点索引
    size_t index() const { return vertex_idx; }
};
 
// 边Circulator（遍历多边形的边）
template <typename Polygon>
class EdgeCirculator {
    const Polygon* poly;
    size_t edge_idx;  // 边的起始顶点索引
    
public:
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::pair<typename Polygon::Point, typename Polygon::Point> Edge;
    typedef Edge value_type;
    typedef Edge* pointer;
    typedef Edge reference;  // 返回pair需要值返回
    typedef std::ptrdiff_t difference_type;
    
    EdgeCirculator() : poly(nullptr), edge_idx(0) {}
    EdgeCirculator(const Polygon* p, size_t idx) : poly(p), edge_idx(idx) {}
    
    Edge operator*() const {
        size_t n = poly->number_of_vertices();
        size_t next_idx = (edge_idx + 1) % n;
        return Edge(poly->vertex(edge_idx), poly->vertex(next_idx));
    }
    
    EdgeCirculator& operator++() {
        edge_idx = (edge_idx + 1) % poly->number_of_vertices();
        return *this;
    }
    
    EdgeCirculator operator++(int) {
        EdgeCirculator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    EdgeCirculator& operator--() {
        size_t n = poly->number_of_vertices();
        edge_idx = (edge_idx == 0) ? n - 1 : edge_idx - 1;
        return *this;
    }
    
    bool operator==(const EdgeCirculator& other) const {
        return poly == other.poly && edge_idx == other.edge_idx;
    }
    
    bool operator\!=(const EdgeCirculator& other) const {
        return \!(*this == other);
    }
};
 
// ============================================
// 多边形类
// ============================================
 
class Polygon2D {
    std::vector<Point2D> vertices;
    
public:
    typedef Point2D Point;
    
    void add_vertex(const Point2D& p) { vertices.push_back(p); }
    
    const Point2D& vertex(size_t i) const { return vertices[i]; }
    size_t number_of_vertices() const { return vertices.size(); }
    
    // 获取Circulator
    VertexCirculator<Polygon2D> vertices_circulator(size_t start = 0) const {
        return VertexCirculator<Polygon2D>(this, start);
    }
    
    EdgeCirculator<Polygon2D> edges_circulator(size_t start = 0) const {
        return EdgeCirculator<Polygon2D>(this, start);
    }
    
    // 计算周长
    double perimeter() const {
        if (vertices.size() < 2) return 0;
        
        double perim = 0;
        auto circ = edges_circulator();
        auto start = circ;
        do {
            Edge<Polygon2D> edge = *circ;
            double dx = edge.second.x - edge.first.x;
            double dy = edge.second.y - edge.first.y;
            perim += std::sqrt(dx * dx + dy * dy);
            ++circ;
        } while (circ \!= start);
        
        return perim;
    }
    
    // 计算面积（鞋带公式）
    double area() const {
        if (vertices.size() < 3) return 0;
        
        double a = 0;
        auto circ = vertices_circulator();
        auto start = circ;
        do {
            auto current = *circ;
            ++circ;
            auto next = *circ;
            a += current.x * next.y - next.x * current.y;
        } while (circ \!= start);
        
        return std::abs(a) / 2;
    }
};
 
// 边类型定义
template <>
struct Edge<Polygon2D> {
    typedef std::pair<Point2D, Point2D> type;
};
 
int main() {
    Polygon2D poly;
    poly.add_vertex(Point2D(0, 0));
    poly.add_vertex(Point2D(4, 0));
    poly.add_vertex(Point2D(4, 3));
    poly.add_vertex(Point2D(0, 3));
    
    std::cout << "Vertices:" << std::endl;
    auto v_circ = poly.vertices_circulator();
    auto v_start = v_circ;
    do {
        std::cout << "  (" << v_circ->x << ", " << v_circ->y <> ")" << std::endl;
        ++v_circ;
    } while (v_circ \!= v_start);
    
    std::cout << "\nPerimeter: " << poly.perimeter() << std::endl;
    std::cout << "Area: " << poly.area() << std::endl;
    
    return 0;
}

高级示例：CGAL风格Circulator

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/iterator/iterator_facade.hpp>
 
// ============================================
// 使用Boost.IteratorFacade的完整Circulator
// ============================================
 
template <typename T>
class Circulator : public boost::iterator_facade<
    Circulator<T>,           // 派生类
    T,                       // 值类型
    boost::bidirectional_traversal_tag,  // 遍历类别
    T&                      // 引用类型
> {
    std::vector<T>* container;
    size_t index;
    
public:
    Circulator() : container(nullptr), index(0) {}
    Circulator(std::vector<T>* c, size_t i) : container(c), index(i) {}
    
    // Circulator特有接口
    bool is_empty() const { return \!container || container->empty(); }
    size_t size() const { return container ? container->size() : 0; }
    
    // 从iterator_facade派生需要实现的方法
private:
    friend class boost::iterator_core_access;
    
    T& dereference() const { return (*container)[index]; }
    
    void increment() {
        index = (index + 1) % container->size();
    }
    
    void decrement() {
        index = (index == 0) ? container->size() - 1 : index - 1;
    }
    
    bool equal(const Circulator& other) const {
        return container == other.container && index == other.index;
    }
};
 
// ============================================
// Circulator适配器：将迭代器转换为Circulator
// ============================================
 
template <typename Iterator>
class CirculatorFromIterator {
    Iterator begin_, end_, current_;
    bool is_empty_;
    
public:
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
    typedef typename std::iterator_traits<Iterator>::pointer pointer;
    typedef typename std::iterator_traits<Iterator>::reference reference;
    
    CirculatorFromIterator() : is_empty_(true) {}
    
    CirculatorFromIterator(Iterator begin, Iterator end)
        : begin_(begin), end_(end), current_(begin), is_empty_(begin == end) {}
    
    CirculatorFromIterator(Iterator begin, Iterator end, Iterator current)
        : begin_(begin), end_(end), current_(current), is_empty_(begin == end) {}
    
    reference operator*() const { return *current_; }
    pointer operator->() const { return &(*current_); }
    
    CirculatorFromIterator& operator++() {
        ++current_;
        if (current_ == end_) current_ = begin_;
        return *this;
    }
    
    CirculatorFromIterator operator++(int) {
        CirculatorFromIterator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    CirculatorFromIterator& operator--() {
        if (current_ == begin_) {
            current_ = end_;
        }
        --current_;
        return *this;
    }
    
    bool operator==(const CirculatorFromIterator& other) const {
        return is_empty_ == other.is_empty_ && 
               begin_ == other.begin_ &&
               current_ == other.current_;
    }
    
    bool operator\!=(const CirculatorFromIterator& other) const {
        return \!(*this == other);
    }
    
    bool is_empty() const { return is_empty_; }
    
    size_t size() const {
        return std::distance(begin_, end_);
    }
};
 
// ============================================
// 使用Circulator的算法
// ============================================
 
// 计算循环中满足谓词的元素数量
template <typename Circulator, typename Predicate>
size_t count_if_circulator(Circulator circ, Predicate pred) {
    if (circ.is_empty()) return 0;
    
    size_t count = 0;
    auto start = circ;
    do {
        if (pred(*circ)) ++count;
        ++circ;
    } while (circ \!= start);
    
    return count;
}
 
// 在循环中查找元素
template <typename Circulator, typename T>
Circulator find_in_circulator(Circulator circ, const T& value) {
    if (circ.is_empty()) return circ;
    
    auto start = circ;
    do {
        if (*circ == value) return circ;
        ++circ;
    } while (circ \!= start);
    
    return circ;  // 未找到，返回起始位置
}
 
// 对循环应用函数
template <typename Circulator, typename Func>
void for_each_in_circulator(Circulator circ, Func f) {
    if (circ.is_empty()) return;
    
    auto start = circ;
    do {
        f(*circ);
        ++circ;
    } while (circ \!= start);
}
 
int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    
    // 使用Circulator
    Circulator<int> circ(&data, 0);
    
    std::cout << "Circulator traversal:" << std::endl;
    auto start = circ;
    int count = 0;
    do {
        std::cout <> *circ << " ";
        ++circ;
        ++count;
    } while (circ \!= start && count < 10);
    
    // 使用适配器
    std::cout << "\n\nCirculator from iterator:" << std::endl;
    CirculatorFromIterator<std::vector<int>::iterator> 
        circ2(data.begin(), data.end(), data.begin() + 2);
    
    auto start2 = circ2;
    count = 0;
    do {
        std::cout << *circ2 << " ";
        ++circ2;
        ++count;
    } while (circ2 \!= start2 && count < 10);
    
    // 使用算法
    std::cout << "\n\nCount even numbers: " 
              << count_if_circulator(circ, [](int x) { return x % 2 == 0; }) << std::endl;
    
    return 0;
}

19.7.3 CGAL中的应用

CGAL的Circulator实现

CGAL在Circulator/include/CGAL/circulator.h中提供了完整的Circulator框架：

// 来自CGAL源代码的简化展示
namespace CGAL {
 
// Circulator类别标签
struct Circulator_tag {};
struct Forward_circulator_tag : Circulator_tag {};
struct Bidirectional_circulator_tag : Forward_circulator_tag {};
struct Random_access_circulator_tag : Bidirectional_circulator_tag {};
 
// Circulator特征
template <class C>
struct Circulator_traits {
    typedef typename std::iterator_traits<C>::iterator_category iterator_category;
    typedef typename internal::Get_category<iterator_category>::type category;
    typedef typename std::iterator_traits<C>::value_type value_type;
    // ...
};
 
// Circulator断言
template <class C>
void Assert_circulator(const C&) {
    typedef typename Circulator_traits<C>::category category;
    static_assert(std::is_convertible<category, Circulator_tag>::value);
}
 
} // namespace CGAL

在Surface_mesh中使用Circulator

#include <CGAL/Surface_mesh.h>
 
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex;
typedef Mesh::Face_index Face;
 
void process_vertex_neighbors(Mesh& mesh, Vertex v) {
    // 遍历顶点的邻接顶点（使用Circulator）
    auto vc = mesh.vertices_around_target(mesh.halfedge(v));
    
    std::cout << "Neighbors of vertex " << v << ": ";
    for (auto nv : vc) {
        std::cout << nv << " ";
    }
    std::cout << std::endl;
}
 
void process_face_boundary(Mesh& mesh, Face f) {
    // 遍历面的边界顶点（使用Circulator）
    auto vc = mesh.vertices_around_face(mesh.halfedge(f));
    
    std::cout << "Vertices of face " << f << ": ";
    for (auto v : vc) {
        std::cout << v << " ";
    }
    std::cout << std::endl;
}

Circulator与迭代器的转换

#include <CGAL/circulator.h>
 
// 将Circulator转换为迭代器范围
template <typename Circulator>
std::vector<typename Circulator::value_type> 
circulator_to_vector(Circulator circ) {
    std::vector<typename Circulator::value_type> result;
    if (circ.is_empty()) return result;
    
    auto start = circ;
    do {
        result.push_back(*circ);
        ++circ;
    } while (circ \!= start);
    
    return result;
}
 
// 使用STL算法与Circulator
template <typename Circulator, typename OutputIterator>
void copy_circulator(Circulator circ, OutputIterator out) {
    if (circ.is_empty()) return;
    
    auto start = circ;
    do {
        *out++ = *circ;
        ++circ;
    } while (circ \!= start);
}

19.7.4 常见陷阱

陷阱1：空Circulator检查

// 错误：未检查空Circulator
auto circ = mesh.vertices_around_target(h);
do {
    // 如果circ为空，这里会崩溃！
    process(*circ);
    ++circ;
} while (circ \!= start);
 
// 正确：先检查是否为空
auto circ = mesh.vertices_around_target(h);
if (\!circ.is_empty()) {
    do {
        process(*circ);
        ++circ;
    } while (circ \!= start);
}

陷阱2：无限循环

// 危险：如果循环中修改了结构，可能导致无限循环
auto circ = mesh.vertices_around_target(h);
auto start = circ;
do {
    if (condition(*circ)) {
        mesh.remove_vertex(*circ);  // 危险！可能使circulator失效
    }
    ++circ;
} while (circ \!= start);
 
// 解决方案：先收集，后修改
std::vector<Vertex> to_remove;
auto circ = mesh.vertices_around_target(h);
auto start = circ;
do {
    if (condition(*circ)) to_remove.push_back(*circ);
    ++circ;
} while (circ \!= start);
 
for (auto v : to_remove) mesh.remove_vertex(v);

陷阱3：Circulator失效

// 问题：存储Circulator供后续使用
auto circ = mesh.vertices_around_target(h);
// ... 修改mesh ...
// circ可能已失效！

解决方案：存储索引而非Circulator

std::vector<Vertex> neighbors;
auto circ = mesh.vertices_around_target(h);
auto start = circ;
do {
    neighbors.push_back(*circ);  // 存储索引
    ++circ;
} while (circ \!= start);
// 现在可以安全地修改mesh

19.7.5 最佳实践

实践1：使用范围for循环（C++11）

// 现代CGAL支持范围for
for (auto v : mesh.vertices_around_target(h)) {
    process(v);
}
 
// 等同于
do {
    process(*circ);
    ++circ;
} while (circ \!= start);

实践2：Circulator与STL算法结合

#include <algorithm>
#include <numeric>
 
// 使用Circulator与STL算法
template <typename Circulator, typename Func>
void circulator_for_each(Circulator circ, Func f) {
    if (circ.is_empty()) return;
    auto start = circ;
    do {
        f(*circ);
        ++circ;
    } while (circ \!= start);
}
 
template <typename Circulator, typename T, typename BinaryOp>
T circulator_accumulate(Circulator circ, T init, BinaryOp op) {
    if (circ.is_empty()) return init;
    auto start = circ;
    do {
        init = op(init, *circ);
        ++circ;
    } while (circ \!= start);
    return init;
}

实践3：文档化Circulator的使用

/**
 * @brief 计算顶点的一环邻域平均位置
 * @param mesh 输入网格
 * @param v 中心顶点
 * @return 邻域顶点的质心位置
 * @note 使用vertices_around_target circulator遍历邻域
 */
Point_3 compute_one_ring_centroid(const Mesh& mesh, Vertex v) {
    Vector_3 sum(0, 0, 0);
    int count = 0;
    
    for (auto nv : mesh.vertices_around_target(mesh.halfedge(v))) {
        sum = sum + (mesh.point(nv) - CGAL::ORIGIN);
        ++count;
    }
    
    return CGAL::ORIGIN + sum / count;
}

本节要点

Circulator是循环结构的理想抽象：没有终点概念，自动循环回到起点。
适用于几何数据结构：多边形顶点、网格邻域、三角剖分邻接关系等。
与STL迭代器的区别：Circulator需要do-while循环模式，而非传统的for循环。
空检查至关重要：使用Circulator前必须检查is_empty()。
注意失效问题：修改数据结构可能使Circulator失效。
现代C++支持：CGAL提供范围for循环支持，简化Circulator使用。

进一步阅读

CGAL文档：Circulator模块和Halfedge Data Structures
《The Boost Graph Library》：迭代器概念和适配器
CGAL Surface_mesh文档：Circulator在实际数据结构中的应用

Chunibyo

Explorer

19.7 迭代器与Circulator

19.7 迭代器与Circulator

相关章节

在本节中你将学到…

19.7.1 概念解释

什么是Circulator？

Circulator vs 迭代器

为什么需要Circulator？

19.7.2 代码示例

基础示例：理解Circulator

中级示例：多边形Circulator

高级示例：CGAL风格Circulator

19.7.3 CGAL中的应用

CGAL的Circulator实现

在Surface_mesh中使用Circulator

Circulator与迭代器的转换

19.7.4 常见陷阱

陷阱1：空Circulator检查

陷阱2：无限循环

陷阱3：Circulator失效

19.7.5 最佳实践

实践1：使用范围for循环（C++11）

实践2：Circulator与STL算法结合

实践3：文档化Circulator的使用

本节要点

进一步阅读

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

19.7 迭代器与Circulator

19.7 迭代器与Circulator §

相关章节 §

在本节中你将学到… §

19.7.1 概念解释 §

什么是Circulator？ §

Circulator vs 迭代器 §

为什么需要Circulator？ §

19.7.2 代码示例 §

基础示例：理解Circulator §

中级示例：多边形Circulator §

高级示例：CGAL风格Circulator §

19.7.3 CGAL中的应用 §

CGAL的Circulator实现 §

在Surface_mesh中使用Circulator §

Circulator与迭代器的转换 §

19.7.4 常见陷阱 §

陷阱1：空Circulator检查 §

陷阱2：无限循环 §

陷阱3：Circulator失效 §

19.7.5 最佳实践 §

实践1：使用范围for循环（C++11） §

实践2：Circulator与STL算法结合 §

实践3：文档化Circulator的使用 §

本节要点 §

进一步阅读 §

Graph View

Table of Contents

Backlinks

19.7 迭代器与Circulator

相关章节

在本节中你将学到…

19.7.1 概念解释

什么是Circulator？

Circulator vs 迭代器

为什么需要Circulator？

19.7.2 代码示例

基础示例：理解Circulator

中级示例：多边形Circulator

高级示例：CGAL风格Circulator

19.7.3 CGAL中的应用

CGAL的Circulator实现

在Surface_mesh中使用Circulator

Circulator与迭代器的转换

19.7.4 常见陷阱

陷阱1：空Circulator检查

陷阱2：无限循环

陷阱3：Circulator失效

19.7.5 最佳实践

实践1：使用范围for循环（C++11）

实践2：Circulator与STL算法结合

实践3：文档化Circulator的使用

本节要点

进一步阅读