An STL-like C++ list class

A long time ago I written an STL-like implementation of such simple thing as linked list, probably it sounds a bit strange, but it does not use if operator at all Smile

Single linked list

template <class T>
class single_link 
{
public :
  
  T * next;
  single_link(T * n) : next(n) {}

protected:
  
  single_link() : next(NULL) {}

  bool included() const
  {
      return next != NULL;
  }
};

template <class T, class Link>
class single_iterator 
{
public:
  
    typedef T * value_type;

    single_iterator(T *p) : pPrev(p) {}

    single_iterator(const single_iterator & r) : pPrev(r.pPrev)
    {
    }

    T * operator-> () const { return cur();}

    T * operator* () const { return cur();}

    single_iterator& operator++ ()
    {
        MoveNext();
        
        return *this;
    }

    single_iterator operator++ (int)
    {
        single_iterator tmp = *this;
        
        MoveNext();
        
        return tmp;
    }

    bool operator == (const single_iterator & r)
    {
      return pPrev == r.pPrev;
    }

    bool operator != (const single_iterator & r)
    {
      return !(*this == r);
    }

    T * prev() const { return pPrev;}

    T * cur() const { return pPrev->Link::next;}

private:
  
    void MoveNext() { pPrev = pPrev->Link::next;}

    T * pPrev;
};

template < class T, class Link = single_link<T> >
class single_list 
{
public :
  
    typedef T * value_type;

    typedef single_iterator<T, Link> iterator;
    typedef single_iterator<const T, Link> const_iterator;

    single_list() : m_null(null()) {}
    ~single_list() {}

    T * null() { return (T *)&m_null;}
    const T * null() const { return (T *)&m_null;}

    T * front() { return m_null.next;}
    const T * front() const { return m_null.next;}

    iterator begin() { return null();}
    const_iterator begin() const { return null();}

    //TSingleList can't access the last element
    //i != list.end() should be replaced with *i != list.null()
    
    //iterator end() { return iterator(back());}
    //const_iterator end() const { return const_iterator(back());}

    static void insert(iterator i, T * a) { insert_after(i.prev(), a);}

    static void insert_after(T * p, T * a)
    {
        a->Link::next = p->Link::next;
        p->Link::next = a;
    }

    static T * remove_after(T * p)
    {
        T * r = p->Link::next;
        p->Link::next = r->Link::next;
        r->Link::next = NULL;
        return r;
    }

    void push_front(T * a) { insert_after(null(), a);}

    T * pop_front() { return remove_after(null());}

    bool empty() const { return front() == null();}
    bool has_one_or_less() const { return front()->Link::next == null();}
    bool has_one() const { return !empty() && has_one_or_less();}

    //void erase_after(T * p) { GC::destroy(remove_after(p));}

    //void erase_range(T * pre_first, T * post_last)
    //{
    //    iterator it = pre_first;
    //    while (it++ != post_last)
    //      erase_after(*it);
    //}

    //void erase_all() { erase_range(null(), null());}

    void clear() { m_null.next = null(); }

    void attach(T * first, T * last)
    {
        m_null.next = first;

        last->Link::next = null();
    }

    //SingList does not know its last element so it should be provided by QuickList

    void push_front(T * first, T * last)
    {
        T * old_first = front();
        
        m_null.next = first;

        last->Link::next = old_first;
    }

    void push_back(T * first, T * last, T * old_last)
    {
        old_last->Link::next = first;
        
        last->Link::next = null();
    }

protected:
  
    Link  m_null;
};

Double linked list based on two Single linked lists

//convertion between iterator and const_interator

template <class T>
class TFakeConvertFrom
{
public:
    T * operator* () const { return 0;}
};
    
template <class T, class Link, class ConvertFrom = TFakeConvertFrom<T> >
class quick_iterator 
{
public:
  
    typedef T * value_type;

    quick_iterator(T *p) : pCur(p) {}

    quick_iterator(const quick_iterator & r) : pCur(r.pCur) {}

    quick_iterator(const ConvertFrom & r) : pCur(*r) {}

    T * operator-> () const { return cur();}

    T * operator* () const { return cur();}

    quick_iterator& operator++ ()
    {
        MoveNext();
        
        return *this;
    }

    quick_iterator operator++ (int)
    {
        quick_iterator tmp = *this;
        
        MoveNext();
        
        return tmp;
    }

    bool operator == (const quick_iterator & r)
    {
      return pCur == r.pCur;
    }

    bool operator != (const quick_iterator & r)
    {
      return !(*this == r);
    }

private:
  
    T * cur() const { return pCur;}
    
    void MoveNext() { pCur = pCur->Link::next;}

    T *pCur;
};

template <class T>
class TForwardLink : public single_link<T> 
{
protected:
  TForwardLink() {}
public:
  TForwardLink(T * n) : single_link<T>(n) {}
};

template <class T>
class TBackwardLink : public single_link<T> 
{
protected:
  TBackwardLink() {}
public:
  TBackwardLink(T * n) : single_link<T>(n) {}
};

template <class T>
class quick_link : public TForwardLink<T>, public TBackwardLink<T> 
{
public:

    typedef TForwardLink<T> ForwardLink;
    typedef TBackwardLink<T> BackwardLink;

protected:
    
    typedef single_list<T, ForwardLink> TForwardList;
    typedef single_list<T, BackwardLink> TBackwardList;

    quick_link() {}

    bool included() const
    {
        return ForwardLink::included() && BackwardLink::included();
    }

    void exclude()
    {
        T * prev = this->BackwardLink::next;
        T * next = this->ForwardLink::next;
        TForwardList::remove_after(prev);
        TBackwardList::remove_after(next);
    }

    template < class T, class DLink = quick_link<T> > friend class quick_list;

public:

    quick_link(T * next, T * prev) : TForwardLink(next), TBackwardLink(prev)
    {
    }
};

template < class T, class DLink > //= quick_link<T> removed default because it already defaulted in above forward declaration
class quick_list
{
private:

    typedef typename DLink::ForwardLink ForwardLink;
    typedef typename DLink::BackwardLink BackwardLink;
    
    typedef single_list<T, ForwardLink> TForwardList;
    typedef single_list<T, BackwardLink> TBackwardList;

public:

    typedef T * value_type;

    typedef quick_iterator<T, ForwardLink> iterator;
    typedef quick_iterator<const T, ForwardLink, iterator> const_iterator;
    
    typedef quick_iterator<T, BackwardLink> reverse_iterator;
    typedef quick_iterator<const T, BackwardLink, reverse_iterator> const_reverse_iterator;

    T * front() { return Forward.front();}
    const T * front() const { return Forward.front();}

    T * back() { return Backward.front();}
    const T * back() const { return Backward.front();}

    iterator begin() { return Forward.front();}
    const_iterator begin() const { return Forward.front();}

    iterator end() { return iterator(Forward.null());}
    const_iterator end() const {return const_iterator(Forward.null());}

    reverse_iterator rbegin() { return Backward.front();}
    const_reverse_iterator rbegin() const { return Backward.front();}

    reverse_iterator rend() { return Backward.null();}
    const_reverse_iterator rend() const { return Backward.null();}

    //returns true if the list is empty
    bool empty() const { return Forward.empty();}
    bool has_one_or_less() const { return Forward.has_one_or_less();}
    bool has_one() const { return Forward.has_one();}

    //Add... includes specified element to the list

    static void insert(iterator i, T * a) { insert_before(*i, a);}
    static void insert(reverse_iterator i, T * a) { insert_after(*i, a);}

    static void remove(iterator i) { remove(*i);}
    static void remove(reverse_iterator i) { remove(*i);}

    //static void erase(iterator i) { erase(*i);}
    //static void erase(reverse_iterator i) { erase(*i);}

    static void insert_after(T * p, T * a)
    {
        T * next = p->ForwardLink::next;
        TForwardList::insert_after(p, a);
        TBackwardList::insert_after(next, a);
    }

    static void insert_before(T * p, T * a)
    {
        T * prev = p->BackwardLink::next;
        TForwardList::insert_after(prev, a);
        TBackwardList::insert_after(p, a);
    }

    void push_front(T * a) { insert_after(Forward.null(), a);}
    void push_back(T * a) { insert_before(Forward.null(), a);}

    //excludes specified element from the list

    static T * remove(T * a)
    {
        a->exclude();
        return a;
    }

    T * pop_front() { return remove(Forward.front());}
    T * pop_back() { return remove(Backward.front());}

    //void erase(T * a) { GC::destroy(remove(a));}

    void attach(T * first, T * last)
    {
        Forward.attach(first, last);
        Backward.attach(last, first);
    }

    void attach(quick_list & src)
    {
        if (src.empty())
        {
            clear();
        }
        else
        {
            T * first = src.front();
            T * last = src.back();

            attach(first, last);

            src.clear();
        }
    }

    void push_front(quick_list & src)
    {
        if (!src.empty())
        {
            T * first = src.front();
            T * last = src.back();

            T * old_last = front(); //the last element in the backward list

            Forward.push_front(first, last);
            Backward.push_back(last, first, old_last);

            src.clear();
        }
    }

    void push_back(quick_list & src)
    {
        if (!src.empty())
        {
            T * first = src.front();
            T * last = src.back();

            T * old_last = back(); //the last element in the forward list

            Forward.push_back(first, last, old_last);
            Backward.push_front(last, first);

            src.clear();
        }
    }

    void clear()
    {
        Forward.clear();
        Backward.clear();
    }

    size_t count() const
    {
        size_t count = 0;
        
        for (const_iterator i = begin(); i != end(); ++i)
        {
            ++count;
        }

        return count;
    }

private:

    //forward and backward lists
    TForwardList Forward;
    TBackwardList Backward;
};

Example

class TBubbleWnd : public awl::quick_link<TBubbleWnd>
{
public:
    int m_nIndex;
};

awl::quick_list<TBubbleWnd> Windows;

TBubbleWnd * pHeadWnd = Windows.front();

//do something with pHeadWnd

//find an element with m_nIndex == 25

awl::quick_list<TBubbleWnd>::iterator i = Windows.begin();

for (;i != Windows.end(); ++i)
{
    if (i->m_nIndex == 25)
    {
        break;
    }
}

//insert something after the found element
//even if the end of the list has been reached

Windows.insert(i, new TBubbleWnd());

Leave a Reply

Your email address will not be published. Required fields are marked *