專注電子技術(shù)學習與研究
當前位置:單片機教程網(wǎng) >> MCU設(shè)計實例 >> 瀏覽文章

C++標準庫中的list設(shè)計

作者:龔平   來源:本站原創(chuàng)   點擊數(shù):  更新時間:2014年03月13日   【字體:

在C++中采用了大量的標志模板庫(STL)實現(xiàn)程序的設(shè)計,這種設(shè)計方式使得不同類型的對象都能通用,而不再是C語言中的通常對于不同的類型需要重新設(shè)計或者或者比較采用間接的指針操作。C++中的這種方式簡化了寫代碼的復雜度,但是增加了編譯器的復雜度和難度。
 
在數(shù)據(jù)結(jié)構(gòu)中鏈表是比較基本的類型,在C++中鏈表是基于模板的類,因此在實際的使用過程中需要涉及到實際的類型。

    #include<list>

    list<int> lint;

在C++中關(guān)于list的接口比較豐富,主要是關(guān)于大小,數(shù)據(jù)的插入、刪除等。但是在C++中引入了迭代器的概念,這個迭代器是關(guān)于關(guān)于容器中比較重要的一部分,因為這種迭代器使得算法等問題與容器獨立開來,迭代器實質(zhì)上還是指針,準確的將是一個封裝了指針的類。
 
迭代器類的創(chuàng)建應(yīng)該包含下面的操作,首先應(yīng)該支持的操作符至少包括如下(operator*(),operator++(),operator++(int),operator==(), operator!=()),當然也會存在const_iterator這樣的常迭代器,也就是只允許訪問,不能修改對象的迭代器,當然存在迭代器的構(gòu)造函數(shù)、復制控制函數(shù),這些函數(shù)都是必須要存在的,因為設(shè)計到了指針的操作問題,構(gòu)造函數(shù)應(yīng)該存在參數(shù)是鏈表節(jié)點指針的定義,只有存在這個定義才能間接的訪問節(jié)點對象。
當然在類中至少存在返回迭代器的begin()和end()函數(shù),這兩個函數(shù)返回的迭代器分別指向鏈表的開始和鏈表結(jié)束的下一個地址,這是迭代器中經(jīng)常容易理解錯誤的地方。
 
在C++中通常創(chuàng)建const_iterator類,然后iterator直接繼承const_iterator。
 
下面說說list類設(shè)計的基本思路:
首先、創(chuàng)建鏈表節(jié)點對象,實質(zhì)上是完成對傳遞進來的類型的封裝操作,同時構(gòu)成一個雙向鏈表的基本要素(prev、next指針)。節(jié)點肯定要存在構(gòu)造函數(shù),而且是直接初始化三個成員變量。
其次、創(chuàng)建迭代器類,實質(zhì)上就是封裝一個節(jié)點指針,通過節(jié)點指針實現(xiàn)操作,至少要實現(xiàn)的操作符已說明。這兩個類都要設(shè)置List為友元類,因為這樣才能用List直接操作迭代器的相關(guān)操作。
最后、依靠上面的迭代器類和節(jié)點類,創(chuàng)建一個List類,該類中主要完成一些基本操作。其中需要注意的就是迭代器的操作,比如刪除元素和插入元素以后迭代器的變化問題等。
 
需要注意的是在List中采用了哨兵節(jié)點,這個哨兵節(jié)點并不算實際的操作對象,也就是為了保證肯定有目標所指向,存在一個head對象,這個對象的next就是實際的數(shù)據(jù),而tail是迭代器所能到達的最后一個對象,但是這個對象并不是合理的區(qū)域,實際上end()實際上就是指向了tail節(jié)點,這兩個節(jié)點head和tail就是哨兵節(jié)點。具體的參看代碼。
 
實現(xiàn)的基本形式如下:

    #ifndef __MYLIST_H_H_
    #define __MYLIST_H_H_

    #include<iostream>

    namespace myspace
    {

            template<typename Object>
            class List
            {
            private:
                    /*封裝對象,形成鏈表節(jié)點*/
                    struct Node
                    {
                            Object data;
                            struct Node *prev;
                            struct Node *next;

                            /*節(jié)點構(gòu)造函數(shù)*/
                            Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
                            :data(d), prev(p), next(n){}
                    };

            public:
                    /*創(chuàng)建一個常量迭代器類,這是容器設(shè)計的關(guān)鍵*/
                    class const_iterator
                    {
                    public:
                            const_iterator():current(NULL)
                            {}

                            /*重載迭代器的值*/
                            const Object & operator*()const
                            {
                                    return retrieve();
                            }
                            /*重載前向++操作符*/
                            const_iterator & operator++ ()
                            {
                                    current = current->next;

                                    return *this;
                            }
                            /*重載后向++操作符,因為是一個局部對象不能返回引用*/
                            const_iterator operator++(int)
                            {
                                    const_iterator old = *this;
                                    ++(*this);

                                    return old;
                            }
                            /*判斷迭代器是否相同,實質(zhì)上就是判斷指向的節(jié)點是否相同*/
                            bool operator==(const const_iterator &rhs) const
                            {
                                    return current == rhs.current;
                            }
                            /*調(diào)用==操作符*/
                            bool operator!=(const const_iterator &rhs)const
                            {
                                    return (!(*this == rhs));
                            }
                    protected:
                            /*迭代器實質(zhì)就是一個節(jié)點指針*/
                            Node *current;

                            /*獲得鏈表中的內(nèi)容*/
                            Object & retrieve() const
                            {
                                    return current->data;
                            }

                            /*基于指針參數(shù)的迭代器構(gòu)造函數(shù),保證只有List使用*/
                            const_iterator(Node *p):current (p)
                            {}

                            /*友元類,可以調(diào)用迭代器的私有成員*/
                            friend class List<Object>;
                    };
                    /*一般迭代器,直接繼承const_iterator*/
                    class iterator : public const_iterator
                    {
                    public:
                            iterator():const_iterator()
                            {}

                            /*得到對象的值*/
                            Object &operator*()
                            {
                                    return retrieve();
                            }

                            /*基于const的重載*/
                            const Object& operator*()const
                            {
                                    return const_iterator::operator*();
                            }
                            /*前向++操作符*/
                            iterator &operator++()
                           {
                                    current = current->next;

                                    return *this;
                            }
                            /*后向++操作符*/
                            iterator operator++(int)
                            {
                                    iterator *old = *this;
                                    ++(*this);
                                    return old;
                            }

                    protected:
                            /*基于節(jié)點的迭代器構(gòu)造函數(shù)*/
                            iterator(Node *p):const_iterator(p)
                            {}

                            friend class List<Object>;
                    };
            public:
                    List()
                    {
                            init();
                    }
                    ~List()
                    {
                            clear();
                            delete head;
                            delete tail;
                    }

                    List(const List &rhs)
                    {
                           /*創(chuàng)建哨兵節(jié)點*/
                            init();
                            /*復制數(shù)據(jù)*/
                            *this = rhs;
                    }

                    const List & operator=(const List &rhs)
                    {
                            if(this == &rhs)
                                    return *this;
                            /*清除原有的信息*/
                            clear();
                            /*添加新的對象*/
                            for(const_iterator itr = rhs.begin(); itr != rhs.end(); ++ itr)
                                    push_back(*itr);

                            return *this;
                    }

                    /*得到迭代器,實質(zhì)上就是得到節(jié)點指針*/
                    iterator begin()
                    {
                            /*iterator()是構(gòu)造函數(shù)*/
                            return iterator(head->next);
                    }

                    const_iterator begin()const
                    {
                            return const_iterator(head->next);
                    }

                    iterator end()
                   {
                            return iterator(tail);
                    }

                    const_iterator end()const
                    {
                            return const_iterator(tail);
                    }

                    int size()const
                    {
                            return theSize;
                    }

                    bool empty()const
                    {
                            return size() == 0;
                    }

                    void clear()
                    {
                            while( !empty())
                                    pop_front();
                    }

                    /*得到第一個元素*/
                    Object & front()
                    {
                            /*采用了迭代器begin()*/
                            return *begin();
                    }
                    const Object &front()const
                    {
                            return *begin();
                   }

                    Object &back()
                    {
                            /*end()指向最后一個對象的下一個地址,因此需要--*/
                            return *--end();
                    }
                    const Object &back()const
                    {
                            return *--end();
                    }
                    /***********************************************
                    *從頭插入新的節(jié)點,這時候的begin已經(jīng)不再是begin
                    *因此插入操作會導致迭代器出錯
                    ***********************************************/
                    void push_front(const Object &x)
                    {
                            insert(begin(), x);
                    }
                    /*從后插入新的節(jié)點,這時候會將end后移*/
                    void push_back(const Object &x)
                    {
                            insert(end(), x);
                    }

                    /*從頭彈出一個對象*/
                    void pop_front()
                    {
                            erase(begin());
                    }
                    void pop_back()
                    {
                           erase(--end());
                    }

                    /*插入對象,參數(shù)是迭代器和數(shù)據(jù)*/
                    iterator insert(iterator itr, const Object &x)
                    {
                            /*得到當前迭代器的指針*/
                            Node *p = itr.current;
                            theSize ++;

                            /*
                            *Node *np = Node(x,p->prev,p);
                            this means that np->prev = p->prev,
                            and np->next = p;

                            update the p->prev and p->prev->next;
                            *p->prev->next = np;
                            *p->prev = np;
                            */
                            return iterator(p->prev=p->prev->next= new Node(x,p->prev, p));
                    }

                    /*刪除迭代器處的對象,因此刪除也會導致迭代器破壞*/
                    iterator erase(iterator itr)
                    {
                            /*得到當前迭代器的指針*/
                            Node *p = itr.current;
                            /*得到新的迭代器,并初始化*/
                            iterator retVal(p->next);
                            /*更新鏈表的鏈接關(guān)系*/
                            p->prev->next = p->next;
                            p->next->prev = p->prev;
                            /*刪除對象*/
                            delete p;
                            /*使得對象數(shù)減少*/
                            theSize --;
                            /*返回新的迭代器*/
                            return retVal;
                    }

                    /*刪除迭代器指向的對象*/
                    iterator erase(iterator start, iterator end)
                    {
                            /*for中不使用++itr的原因是erase之后
                             *就是下一個迭代器,因此不需要++操作*/
                            for(iterator itr = start; itr != end; )
                            {
                                    /*該操作會導致迭代器更新到下一個*/
                                    itr = erase(itr);
                            }
                            return itr;
                    }

            private:
                    /*鏈表中的數(shù)據(jù)成員*/
                    int theSize;
                    Node *head;
                    Node *tail;
                    /*初始化函數(shù)*/
                    void init()
                    {
                            theSize = 0;
                            /*create two sentinel node*/
                            /*構(gòu)建兩個哨兵節(jié)點,也就是兩個并不算在結(jié)構(gòu)體中的對象*/
                            head = new Node;
                            tail = new Node;
                            /*綁定起來*/
                            head->next = tail;
                            tail->prev = head;
                    }
            };
    }

    #endif

 
 

關(guān)閉窗口

相關(guān)文章