迭代器的使用

2014/08/21 09:57
阅读数 160

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);

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部