迭代器的使用

2016-02-04 ruki 更多博文 » 博客 » GitHub »

tbox 迭代器

原文链接 https://waruqi.github.io/2016/02/04/iterator.cn/
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。


stl的容器库常用模式就是将容器、迭代器和算法的进行分离,容器专于存储,迭代器负责枚举,这样互相独立好处多多。

因此TBOX也借鉴了这种模式,不同的是没用模板,仅仅用了c语言来实现。容器库里面的大部分容器都是继承自迭代器的,所以迭代起来相当的方便。

下面先看个迭代器使用的例子:

    // 初始化一个双向链表,元素类型为tb_long_t, 满256个元素自动增长
    tb_list_ref_t list = tb_list_init(256, tb_item_func_long());
    if (list)
    {
        // 插入一些元素
        tb_list_insert_tail(list, (tb_cpointer_t)1);
        tb_list_insert_tail(list, (tb_cpointer_t)2);
        tb_list_insert_tail(list, (tb_cpointer_t)3);
        tb_list_insert_tail(list, (tb_cpointer_t)4);
        tb_list_insert_tail(list, (tb_cpointer_t)5);

        // 迭代遍历所有元素
        tb_for_all (tb_long_t, item, list)
        {
            tb_trace_i("item: %ld", item);
        }

        // 迭代遍历所有 > 3 的元素
        tb_for_all_if (tb_long_t, item, list, item > 3)
        {
            tb_trace_i("item: %ld", item);
        }

        // 反向迭代遍历所有元素,注:只有支持反向迭代的容器,才行,例如单链tb_single_list_t就不行
        tb_rfor_all (tb_long_t, item, list)
        {
            tb_trace_i("item: %ld", item);
        }

        // 反向迭代遍历所有 > 3 的元素
        tb_rfor_all_if (tb_long_t, item, list, item > 3)
        {
            tb_trace_i("item: %ld", item);
        }

        // 迭代遍历部分元素,这里认为传入迭代的头部和尾部,进行遍历所有
        tb_for (tb_long_t, item, tb_iterator_head(list), tb_iterator_tail(list), list)
        {
            tb_trace_i("item: %ld", item);
        }

        // 退出链表
        tb_list_exit(list);
    }

怎么样简单吧,其实这里的 tb_for_all 是一个宏,如果把它展开的话,其实也可以这样遍历只不过看上去繁琐些,但是更加灵活:

    // 获取list的头部索引
    tb_size_t itor = tb_iterator_head(list);

    // 获取list的尾部索引
    tb_size_t tail = tb_iterator_tail(list);

    // 进行遍历,这里没去删除元素,所以不需要实时更新tail的值
    for (; itor != tail; itor = tb_iterator_next(list, itor))
    {
        // 获取索引itor对应的元素
        tb_long_t item = (tb_long_t)tb_iterator_item(list, itor);
    }

    // 进行遍历,并且删除元素,需要更新tail, 所以这个tb_for 就办不到了
    // tb_for为了效率,不会去更新tail的值
    while (itor != tb_iterator_tail(list, itor))
    {
        // 获取索引itor对应的元素
        tb_long_t item = (tb_long_t)tb_iterator_item(list, itor);
        if (item > 3)
        {
            // 先保存下一个索引,避免删除当前元素后itor变为无效索引
            tb_size_t next = tb_iterator_next(list, itor);

            // 使用迭代器删除
            tb_iterator_remove(list, itor);

            // 或者使用容器删除
    //      tb_list_remove(list, itor);

            // 继续下一个
            itor = next;
            continue ;
        }

        // 继续下一个
        itor = tb_iterator_next(list, itor);
    }

这种方式其实也已经相当方便了,如果觉得上面的删除比较繁琐的话,可以使用算法库提供的remove函数来进行遍历删除,并且更加高效。

    // 回调函数
    tb_long_t tb_list_item_func(tb_iterator_ref_t iterator, tb_cpointer_t item, tb_cpointer_t priv);
    {
        // 如果 > 3 就删除它
        if ((tb_long_t)item > 3)
        {
            /* 标记这个元素为删除
             * 
             * 注:
             * 这个时候容器内部还没有真正的删除它,里面做了些优化
             * 来一次性删除一块连续的元素,这样效率会高好多
             *
             * 这种删除模式,是最快速的,尤其是对tb_vector_t这种有连续内存的容器,更为高效
             * 避免了每删除一个元素,都要进行一遍tb_memmov内存的搬运
             *
             * 名字类似,vector的遍历删除使用:tb_vector_walk
             */
            return 0;
        }

        // 返回1则继续下一个,返回-1则中断遍历
        return 1;
    }

    // 遍历所有元素,并对每个元素调用回调函数
    tb_remove_if(list, tb_list_item_func, tb_null);

还有一种遍历方式,就是使用算法库的tb_walk函数,这个和 tb_list_walk类似,但不提供删除功能。 主要应用在通用化,模块化复杂遍历代码的地方:

    tb_bool_t tb_walk_item_func(tb_iterator_ref_t iterator, tb_pointer_t item, tb_pointer_t priv)
    {
        // ...
    }

    // 遍历所有
    tb_walk_all(list, tb_walk_item_func, tb_null);

    // 反向遍历所有
    tb_rwalk_all(list, tb_walk_item_func, tb_null);

    // 通过迭代器索引,局部遍历
    tb_walk(list, tb_iterator_head(list), tb_iterator_tail(list), tb_walk_item_func, tb_null);

    // 反向通过迭代器索引,局部遍历
    tb_rwalk(list, tb_iterator_head(list), tb_iterator_tail(list), tb_walk_item_func, tb_null);

总结下:

  1. tb_for系列:用于小代码块的简单逻辑遍历
  2. 直接使用迭代器:用于小代码块复杂逻辑遍历
  3. 容器的tb_xxx_walk:用于复杂代码块、高效删除元素时的遍历
  4. tb_walk系列:用于复杂代码块,不需要删除时的遍历

迭代器主要由如下几种访问模式,不同容器支持的力度不一样:

    /// the iterator mode type
    typedef enum __tb_iterator_mode_t
    {
        TB_ITERATOR_MODE_FORWARD        = 1     //!< 前向遍历迭代器,大部分容器都支持
    ,   TB_ITERATOR_MODE_REVERSE        = 2     //!< 反向向遍历迭代器, 单链不支持
    ,   TB_ITERATOR_MODE_RACCESS        = 4     //!< 随机访问迭代器,链表、队列、堆栈等不支持,最常用就是vector
    ,   TB_ITERATOR_MODE_MUTABLE        = 8     //!< 易变的迭代器,同一个迭代器索引的值有可能因为删除某个元素而改变,例如:vector
    ,   TB_ITERATOR_MODE_READONLY       = 16    //!< 只读访问迭代器,不提供删除、替换等操作

    }tb_iterator_mode_t;
常用的一些迭代器接口:

    // 获取迭代器访问模式
    tb_size_t       tb_iterator_mode(tb_iterator_ref_t iterator);

    // 获取迭代器对应容器的元素总数
    tb_size_t       tb_iterator_size(tb_iterator_ref_t iterator);

    // 获取迭代器的头部索引
    tb_size_t       tb_iterator_head(tb_iterator_ref_t iterator);

    // 获取迭代器的最后一个元素的索引
    tb_size_t       tb_iterator_last(tb_iterator_ref_t iterator);

    // 获取迭代器的尾部索引,不指向实际元素,一般用于判断结束
    tb_size_t       tb_iterator_tail(tb_iterator_ref_t iterator);

    // 获取迭代器的先前一个元素的索引
    tb_size_t       tb_iterator_prev(tb_iterator_ref_t iterator, tb_size_t itor);

    // 获取迭代器的下一个元素的索引
    tb_size_t       tb_iterator_next(tb_iterator_ref_t iterator, tb_size_t itor);

    // 获取迭代器索引指向的元素
    tb_pointer_t    tb_iterator_item(tb_iterator_ref_t iterator, tb_size_t itor);

    // 删除迭代器索引指向的元素
    tb_void_t       tb_iterator_remove(tb_iterator_ref_t iterator, tb_size_t itor);

    // 复制迭代器索引指向的元素
    tb_void_t       tb_iterator_copy(tb_iterator_ref_t iterator, tb_size_t itor, tb_cpointer_t item);

    // 比较迭代器索引指向的两个元素
    tb_long_t       tb_iterator_comp(tb_iterator_ref_t iterator, tb_cpointer_t ltem, tb_cpointer_t rtem);

你也可以将常用的原始数组,迭代器化,来支持迭代,并用于所有算法:

    // 根据一个tb_long_t[]数组,生成迭代器, size 为数组元素个数
    tb_iterator_t   tb_iterator_init_long(tb_long_t* data, tb_size_t size);

    // 根据一个tb_size_t[]数组,生成迭代器, size 为数组元素个数
    tb_iterator_t   tb_iterator_init_size(tb_size_t* data, tb_size_t size);

    // 根据一个tb_char_t*[]字符串数组,生成迭代器, size 为数组元素个数
    tb_iterator_t   tb_iterator_init_str(tb_char_t** data, tb_size_t size);

    // 根据一个tb_pointer_t[]指针数组,生成迭代器, size 为数组元素个数
    tb_iterator_t   tb_iterator_init_ptr(tb_pointer_t* data, tb_size_t size);

    // 根据一个tb_struct_xxxx_t[]结构体数组,生成迭代器, size 为数组元素个数, step == sizeof(tb_struct_xxxx_t)
    tb_iterator_t   tb_iterator_init_mem(tb_pointer_t data, tb_size_t size, tb_size_t step);