C++：迭代器的设计与实现

迭代器：类似指针的对象，可以解引用、自增、比较(!=)等操作。

STL中，迭代器用来STL Algorithm与Container之间的粘合剂。

迭代器根据移动特性及施行操作，可以分为5类：

  • Input Iterator: 只读
  • Output Iterator: 只写
  • Forward Iterator: 可单向移动，支持读写。支持operator++
  • Bidirectional Iterator: 双向移动，可走访某个容器区间。支持operator++ 和 operator--
  • Random Access Iterator: 可涵盖所有指针算术能力，如数组连续内存空间的定义此类型

定义迭代器内嵌的型别：

  • using value_type = T; /* 迭代器所指对象类型 */
  • using reference = typename std::add_lvalue_reference<T>::type; /* 迭代所指对象引用类型 */
  • using pointer = typename std::add_pointer<T>::type; /* 迭代器所指对象指针类型 */
  • using difference_type = std::ptrdiff_t; /* 表示两个迭代器的距离 */
  • using iterator_category = std::forward_iterator_tag; /* 迭代器的类型 */

针对一个链表结构的容器：

定义两类迭代器: iterator/const iterator，迭代器基本的操作能力：

  • operator ++()
  • operator ++(int)
  • operator !=(para)
  • operator *()
  • operator ==()

针对容器本身，设计方法如下,注意在容器中使用了一个_root来连接链表的头和尾，初始化时，只有一个_root，next/prev指向自己：

  • begin()
  • end()
  • push_back()
  • push_front()
  • pop_back()
  • pop_front()
  • back()
  • insert(iterator pos,val)
  • erase(iterator)

实现代码如下，参考stl_list：

#include <iostream>
#include <algorithm>
#include <list>
#include <gtest/gtest.h>
#include <string>

/*
** 定义list，Node积累，主要包含前后指针
** 定义两个操作函数：分别是在此节点后插入，其次是将本身从list链表中移除
*/
struct list_base{
public:
    list_base* next;
    list_base* prev;
    list_base(){
        next = this;
        prev = this;
    }
    virtual void insert(list_base* e){
        e->next = this;
        e->prev = prev;
        prev->next = e;
        prev = e;
    }
    virtual void unlink(){
        next->prev = prev;
        next->prev->next = next;
        next = this;
        prev = this;
    }
    virtual ~list_base(){}
};

/*
** 存放数据
*/
template<typename T>
class Node: public list_base{
public:
    T ele;
public:
    Node(T ele):ele(ele){}
};

/*
** 定义迭代器iterator
*/
template<typename T>
class buffers_iterator{
public:

    list_base* cur;
    using _self = buffers_iterator<T>;
    using _Node = Node<T>;
public:
    
    using value_type = T;
    using reference = std::add_lvalue_reference_t<T>;
    using pointer = std::add_pointer_t<T>;
    using difference_type = std::ptrdiff_t;

    /* 
    * 由于是链表结构，因此只支持std::forward_iterator_tag 
    * 连续容器使用：std::random_access_iterator_tag
    */
    using iterator_category = std::forward_iterator_tag;

    buffers_iterator(list_base* const p)
    : cur(p){
    }
    buffers_iterator()=default;
    template<typename U>
    buffers_iterator(const buffers_iterator<U>& other)
    : cur(other.cur){
    }
    reference operator*(){
        return static_cast<_Node*>(cur)->ele;
    }
    pointer operator->(){
        return &(static_cast<_Node*>(cur)->ele);
    }
    _self& operator++(){
        cur = cur->next;
        return *this;
    }
    _self operator++(int){
        const auto temp(*this);
        ++*this;
        return temp;
    }
    template<typename U>
    _self& operator=(const buffers_iterator<U>& other){
        cur = other.cur;
        return *this;
    }
    bool operator==(const buffers_iterator& other){
        return cur==other.cur;
    }
    bool operator!=(const buffers_iterator& other){
        return !(*this==other);
    }
};

/*
** 定义const iterator
** iterator与const iterator区别：const reference及const pointer，以禁止通过此迭代器对存储的数据进行更改
*/
template<typename T>
class buffers_const_iterator{
public:
    list_base* cur;
    using _self = buffers_const_iterator<T>;
    using _Node = const Node<T>;
public:
    using value_type = T;
    using reference = std::add_lvalue_reference_t<std::add_const_t<T>>;
    using pointer = std::add_pointer_t<std::add_const_t<T>>;
    using difference_type = std::ptrdiff_t;
    /* 
    * 由于是链表结构，因此只支持std::forward_iterator_tag 
    * 连续容器使用：std::random_access_iterator_tag
    */
    using iterator_category = std::forward_iterator_tag;

    using iterator = buffers_iterator<T>;

    buffers_const_iterator(list_base* const p)
    : cur(p){
    }

    buffers_const_iterator(const iterator& p)
    :cur(p.cur){}

    buffers_const_iterator()=default;
    template<typename U>
    buffers_const_iterator(const buffers_const_iterator<U>& other)
    : cur(other.cur){
    }
    reference  operator*(){
        return static_cast<_Node*>(cur)->ele;
    }
    pointer operator->(){
        return &(static_cast<_Node*>(cur)->ele);
    }
    _self& operator++(){
        cur = cur->next;
        return *this;
    }
    _self operator++(int){
        const auto temp(*this);
        ++*this;
        return temp;
    }
    template<typename U>
    _self& operator=(const buffers_const_iterator<U>& other){
        cur = other.cur;
        return *this;
    }
    bool operator==(const buffers_const_iterator& other){
        return cur==other.cur;
    }
    bool operator!=(const buffers_const_iterator& other){
        return !(*this==other);
    }
};

/*
** 定义iterator与const iterator之间的比较函数
*/
template<typename _Val>
inline bool
  operator==(const buffers_iterator<_Val>& __x,
         const buffers_const_iterator<_Val>& __y)
  { return __x.cur == __y.cur; }

template<typename _Val>
  inline bool
  operator!=(const buffers_iterator<_Val>& __x,
         const buffers_const_iterator<_Val>& __y)
  { return __x.cur == __y.cur; }

/*
** 定义list容器，在容器内声明iterator及const iterator两种迭代器类型
** 定义接口函数
*/
template<typename T>
class buffers{
    using _Node = Node<T>;
    list_base _root;
public: 
    using iterator = buffers_iterator<T>;
    using const_iterator = buffers_const_iterator<T>;
    using value_type = T;

    buffers(){
        _root.next = &_root;
        _root.prev = &_root;
    }
    buffers(const buffers&) = delete;
    buffers(buffers&& other){
          _root.next = other._root.next == &other._root ? &_root : other._root.next;
          _root.prev = other._root.prev == &other._root ? &_root : other._root.prev;
          other._root.next = &other._root;
          other._root.prev = &other._root;
    }
    void push_back(value_type val) {
        list_base* item = new _Node(val);
        _root.insert(item);
      }

    void push_front(value_type val) {
        list_base* item = new _Node(val);
        begin().cur->insert(item);
    }
    const_iterator begin() const {
          return const_iterator(_root.next);
    }
    const_iterator end() const {
        return const_iterator(&_root);
    }
    iterator begin() {
        return iterator(_root.next);
    }
    iterator end() {
        return iterator(&_root);
    }

    iterator back() {
        return iterator(_root.prev);
    }

    const_iterator back() const{
        return iterator(_root.prev);
    }

    void pop_back(){
        if ( _root.prev == &_root){
            return;
        }
        _erase(_root.prev);
    }

    void pop_front(){
        if (_root.next == &_root){
            return;
        }
        _erase(_root.next);
    }

    iterator insert(iterator pos,const value_type& _val){
        list_base* item = new _Node(_val);
        pos.cur->insert(item);
        return pos.cur->prev;
    }

    iterator erase(iterator pos){
        iterator tmp = pos++;
        _erase(tmp);
        return pos;
    }

    void _erase(iterator pos){
        pos.cur->unlink();
        delete pos.cur;
    }

    bool empty(){
        return _root.next == &_root;
    }

    ~buffers(){
        list_base* head = _root.next;
        list_base* t = _root.next;
        while (head!=&_root){
            head = t->next;
            delete t;
            t = head;
        }
    }
};


TEST(INT,PUSH){
    buffers<int> t1;
    t1.push_back(1);
    EXPECT_EQ(*(t1.back()),1);
    t1.push_front(2);
    EXPECT_EQ(*(t1.begin()),2);
}
TEST(INT,POP){
    buffers<int> t1;
    t1.push_back(2);
    t1.pop_back();
    EXPECT_TRUE(t1.empty());
}
TEST(INT,ITERATOR){
    buffers<int> t1;
    t1.push_front(1);
    t1.insert(t1.begin(),2);
    EXPECT_EQ(*(t1.begin()),2);
    t1.erase(t1.begin());
    EXPECT_EQ(*(t1.begin()),1);
}

/*
** Test String
*/

TEST(STRING,PUSH){
    buffers<std::string> t1;
    t1.push_back("abc");
    EXPECT_EQ(*(t1.back()),"abc");
    t1.push_front("dc");
    EXPECT_EQ(*(t1.begin()),"dc");
}
TEST(STRING,POP){
    buffers<std::string> t1;
    t1.push_back("dc");
    t1.pop_back();
    EXPECT_TRUE(t1.empty());
}
TEST(STRING,ITERATOR){
    buffers<std::string> t1;
    t1.push_front("as");
    t1.insert(t1.begin(),"dc");
    EXPECT_EQ(*(t1.begin()),"dc");
    t1.erase(t1.begin());
    EXPECT_EQ(*(t1.begin()),"as");
}

TEST(ALGORITHM,FIND_IF){
    buffers<int> t1;
    t1.push_back(12);
    t1.push_back(10);
    t1.push_back(5);
    t1.push_back(20);
    auto it = std::find_if(t1.begin(),t1.end(),[](auto e){return e%5==0;});
    EXPECT_EQ(*it,10);
}

int main(int argc,char* argv[]){

    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
    
}

利用gtest单元测试：

# g++ --std=c++1y -g test_iter.cc -o test_iter -lgtest
# ./test_iter 
[==========] Running 7 tests from 3 test cases.
[----------] Global test environment set-up.
[----------] 3 tests from INT
[ RUN      ] INT.PUSH
[       OK ] INT.PUSH (0 ms)
[ RUN      ] INT.POP
[       OK ] INT.POP (0 ms)
[ RUN      ] INT.ITERATOR
[       OK ] INT.ITERATOR (0 ms)
[----------] 3 tests from INT (0 ms total)

[----------] 3 tests from STRING
[ RUN      ] STRING.PUSH
[       OK ] STRING.PUSH (0 ms)
[ RUN      ] STRING.POP
[       OK ] STRING.POP (0 ms)
[ RUN      ] STRING.ITERATOR
[       OK ] STRING.ITERATOR (0 ms)
[----------] 3 tests from STRING (1 ms total)

[----------] 1 test from ALGORITHM
[ RUN      ] ALGORITHM.FIND_IF
[       OK ] ALGORITHM.FIND_IF (0 ms)
[----------] 1 test from ALGORITHM (0 ms total)

[----------] Global test environment tear-down
[==========] 7 tests from 3 test cases ran. (1 ms total)
[  PASSED  ] 7 tests.
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,869评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,716评论 3赞 396
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 166,223评论 0赞 357
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 59,047评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 68,089评论 6赞 395
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,839评论 1赞 308
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,516评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,410评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,920评论 1赞 319
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,052评论 3赞 340
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,179评论 1赞 352
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,868评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,522评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,070评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,186评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,487评论 3赞 375
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,162评论 2赞 356