美文网首页
C++: 泛型编程

C++: 泛型编程

作者: 赵伯舟 | 来源:发表于2018-08-17 19:30 被阅读11次

    泛型编程也是C++多态的一种重要形式,其通过模板来实现代码的重用。一般而言,泛型编程将算法与数据结构分离,通过Template的形式,使得算法能够特化成不同的数据类型。下面来感受一下泛型编程的神奇之处。

    实现一个线性Find函数

    template <class Iterator, class T>
    Iterator Find(Iterator begin, Iterator end, const T& value)
    {
        while(begin != end && *begin != value)
            begin++;
        return begin;
    };
    

    上述是一个泛型函数,通过传入所要查询的数据集的起点与终点迭代器,以及目标值,如查询到目标值,则返回对应的迭代器,否则返回end。只要我们传入的数据集的迭代器支持线性的迭代,就都可以使用这个Find函数来进行查询,如:

        vector<int> data = {1, 2, 3 ,4 ,5};
        auto res = Find(data.begin(), data.end(), 4);
    
        ///  list<int> data = {1, 2, 3, 4, 5};
        ///  auto res = Find(data.begin(), data.end(), 4);
    
        ///  array<string, 10> data = { "hello", "world"};
        ///  auto res = tfind(data.begin(), data.end(), "hello");
    
        if(res != data.end())
            cout << *res << endl;
        else
            cout << "Not Found" << endl;
        return 0;
    

    如上,因为vector, array等支持线性迭代,所以可以在不用更改Find的情况下实现不同类型数据的查询。那这个迭代器能否用于二叉树,邻接表等更加复杂的数据结构呢?当然可以,只要我们实现按照这些数据结构的遍历方式,实现一个对应的Iterator,便可将上面的Find函数用于这些数据结构上了。
    那为了让我们的Iterator能够用于上面的Find函数,我们需要什么接口呢?仔细观察,需要:

    • 重载==!=
    • 重载++
    • 重载*
      下面,我们来实现一个链表的Iterator

    实现一个链表的Iterator

    首先,定义一个链表的节点:

    template <typename T>
    class list_node
    {
    public:
        T value;
        list_node* next;
        explicit list_node(T t)
        {
            value = t;
            next = nullptr;
        }
        bool operator == (const T t)const
        {
            return value == t;
        }
        bool operator != (const T t)const
        {
            return value != t;
        }
    };
    

    上述是一个模板类,内部有一个模板变量,并重载了==!=操作符。接下来,我们来实现上述list_nodeIterator:

    template <typename node>
    class list_iterator
    {
    private:
        node* curr_ptr;
    public:
        explicit list_iterator(node* p = nullptr) : curr_ptr(p){};
        node& operator * () const
        {
            return *curr_ptr;
        }
        node* get () const
        {
            return curr_ptr;
        }
        node* operator -> () const
        {
            return curr_ptr;
        }
    
        list_iterator<node>& operator ++ ()
        {
            curr_ptr = curr_ptr->next;
            return *this;
        }
    
        list_iterator<node>& operator ++ (int)
        {
            this->operator++();
            return *this;
        }
    
        bool operator == (const list_iterator<node>& src) const
        {
            return src.get() == curr_ptr;
        }
    
        bool operator != (const list_iterator<node>& src) const
        {
            return src.get() != curr_ptr;
        }
    };
    

    在重载++时,我们依据list_node的实际情况,使用next指针得到下一个元素,测试如下:

    int main()
    {
      auto n1 = new list_node(1);
      auto n2 = new list_node(2);
      auto n3 = new list_node(3);
    
      n1->next = n2;
      n2->next = n3;
    
      auto res = Find(list_iterator<list_node<int>>(n1), 
                      list_iterator<list_node<int>>(),
                      3);
    
      if (res.get())
          cout << res->value << endl;
      else
          cout << "Not found" << endl;
    
      return 0;
    }
    

    这里使用list_iterator<list_node<int>>()作为end,注意,Find返回的是一个Iterator,而这个Iterator具体有什么方法使我们自己来实现的。

    相关文章

      网友评论

          本文标题:C++: 泛型编程

          本文链接:https://www.haomeiwen.com/subject/plvtiftx.html