6
\$\begingroup\$

This is my first attempt to create an STL-compliant container. I'd like to know whether it meets STL concepts & requirements, so feel free to critique.

list.h

#include    <cstdint>
#include    <limits>
#include    <memory>
#include    <iterator>
#include    <type_traits>
#include    <initializer_list>
#include    <algorithm>
#include    <utility>
#include    <functional>

template <typename T, typename Allocator = std::allocator<T>>
class clist
{
    private:
        struct node
        {
            public:
                node() : m_pT(nullptr), m_pNext(nullptr), m_pPrev(nullptr) {}

                void loop() {this->m_pNext = this; this->m_pPrev = this;}

                static void link(node *lhs, node *rhs) {lhs->m_pNext = rhs; rhs->m_pPrev = lhs;}
                void unlink()
                {
                    if (this->m_pPrev != nullptr) {this->m_pPrev->m_pNext = this->m_pNext;}
                    if (this->m_pNext != nullptr) {this->m_pNext->m_pPrev = this->m_pPrev;}
                }

                void reverse() {std::swap(this->m_pPrev, this->m_pNext);}

            private:
                T *m_pT;
                node *m_pNext;
                node *m_pPrev;

            friend class clist<T, Allocator>;
        };

        template <bool is_const_iter>
        class iterator_cnc : public std::iterator<std::bidirectional_iterator_tag, typename std::conditional<is_const_iter, const T, T>::type>
        {
            using node_ptr_type = typename std::conditional<is_const_iter, const node*, node*>::type;
            using const_reference = const T&;

            public:
                iterator_cnc() : m_pT(nullptr) {}
                iterator_cnc(node_ptr_type p) : m_pT(p) {}
                iterator_cnc(const iterator_cnc<false> &it) : m_pT(it.m_pT) {}

                bool operator == (const iterator_cnc &rhs) {return (this->m_pT == rhs.m_pT);}
                bool operator != (const iterator_cnc &rhs) {return !((*this) == rhs);}
                reference operator * () {return *(this->m_pT->m_pT);}
                const_reference operator * () const {return *(this->m_pT->m_pT);}
                iterator_cnc& operator ++ () {this->m_pT = this->m_pT->m_pNext; return (*this);}
                iterator_cnc& operator -- () {this->m_pT = this->m_pT->m_pPrev; return (*this);}
                iterator_cnc operator ++ (int) {iterator_cnc rv(*this); this->m_pT = this->m_pT->m_pNext; return rv;}
                iterator_cnc operator -- (int) {iterator_cnc rv(*this); this->m_pT = this->m_pT->m_pPrev; return rv;}
                pointer operator -> () {return &(*(*this));}

            private:
                node_ptr_type m_pT;

            friend class clist<T, Allocator>;
        };

        using       value_type              = T;
        using       reference               = T&;
        using       const_reference         = const T&;
        using       allocator_type          = Allocator;
        using       allocator_traits        = typename std::allocator_traits<allocator_type>;
        using       pointer                 = typename allocator_traits::pointer;
        using       const_pointer           = typename allocator_traits::const_pointer;
        using       iterator                = iterator_cnc<false>;
        using       const_iterator          = iterator_cnc<true>;
        using       reverse_iterator        = std::reverse_iterator<iterator>;
        using       const_reverse_iterator  = std::reverse_iterator<const_iterator>;
        using       difference_type         = typename iterator::difference_type;
        using       size_type               = std::size_t;

        using       node_allocator_type     = typename allocator_traits::template rebind_alloc<node>::other;
        using       node_allocator_traits   = typename std::allocator_traits<node_allocator_type>;

    //  [decl--virt]        [st]    [type]                          [cc]            [name]

        node_allocator_type& _alc() {return this->m_alloc_node;}
        allocator_type _alcv() {return allocator_type(this->m_alloc_node);}
        typename node_allocator_traits::pointer _mknode(pointer pv = nullptr);
        void _delnode(typename node_allocator_traits::pointer p, bool destrv = false);
        template <typename... Args> pointer _mkval(Args &&... args);
        void _delval(pointer p);
        void _mkinit() {node::link(this->m_head = this->_mknode(), this->m_tail = this->_mknode());}
        void _delinit() {if (this->m_head) {this->_delnode(this->m_head);} if (this->m_tail) {this->_delnode(this->m_tail);}};

    public:
        explicit clist(const Allocator &alloc = Allocator())
                  : m_alloc_node(node_allocator_type(alloc))
                  {this->_mkinit();}
        explicit clist(size_type count, const T &v, const Allocator &alloc = Allocator())
                  : clist(alloc)
                  {this->resize(count, v);}
        explicit clist(size_type count, const Allocator &alloc = Allocator())
                  : clist(alloc)
                  {this->resize(count);}

        template <typename InputIt>
        clist(InputIt first, InputIt last, const Allocator &alloc = Allocator())
         : clist(alloc)
         {this->insert(this->end(), first, last);}

        clist(const clist<T, Allocator> &l, const Allocator &alloc)
         : clist(alloc)
         {for (auto &v : l) {this->emplace_back(v);}}
        clist(const clist<T, Allocator> &l)
         : clist(l, node_allocator_traits::select_on_container_copy_construction(l._alc()))
         {}
        clist(clist<T, Allocator> &&l, const Allocator &alloc);
        clist(clist<T, Allocator> &&l)
         : clist(std::move(l), l._alcv())
         {}
        clist(std::initializer_list<T> l, const Allocator &alloc = Allocator())
         : clist(alloc)
         {this->insert(this->cbegin(), l);}
        ~clist()
         {this->clear(); this->_delinit();}

        clist<T, Allocator>& operator = (const clist<T, Allocator> &l);
        clist<T, Allocator>& operator = (clist<T, Allocator> &&l);
        clist<T, Allocator>& operator = (std::initializer_list<T> l);

        allocator_type get_allocator() const {return this->_alcv();}

        iterator begin() {return iterator(this->m_head->m_pNext);}
        iterator end() {return iterator(this->m_tail);}
        const_iterator begin() const {return const_iterator(this->m_head->m_pNext);}
        const_iterator end() const {return const_iterator(this->m_tail);}

        iterator rbegin() {return reverse_iterator(this->begin());}
        iterator rend() {return reverse_iterator(this->end());}
        const_iterator rbegin() const {return const_reverse_iterator(this->begin());}
        const_iterator rend() const {return const_reverse_iterator(this->end());}

        const_iterator cbegin() const {return const_cast<const clist<T, Allocator> *>(this)->begin();}
        const_iterator cend() const {return const_cast<const clist<T, Allocator> *>(this)->end();}
        const_iterator crbegin() const {return const_cast<const clist<T, Allocator> *>(this)->rend();}
        const_iterator crend() const {return const_cast<const clist<T, Allocator> *>(this)->rend();}

        void swap(clist<T, Allocator> &l);

        size_type size() const {return std::distance(this->cbegin(), this->cend());}
        size_type max_size() const {return (std::numeric_limits<std::size_t>::max() / sizeof(node));}
        void resize(size_type count) {this->resize(count, value_type());}
        void resize(size_type count, const value_type &v);
        bool empty() const {return (this->cbegin() == this->cend());}

        reference front() {return *(this->begin());}
        /*constexpr*/ const_reference front() const {return *(this->cbegin());}
        reference back() {return *(--(this->end()));}
        /*constexpr*/ const_reference back() const {return *(--(this->cend()));}

        iterator insert(const_iterator pos, const T &v);
        iterator insert(const_iterator pos, T &&v);
        iterator insert(const_iterator pos, size_type count, const T &v);
        template <typename InputIt> iterator insert(const_iterator pos, InputIt first, InputIt last);
        iterator insert(const_iterator pos, std::initializer_list<T> l);
        iterator erase(const_iterator pos) {auto posold = pos++; return this->erase(posold, pos);}
        iterator erase(const_iterator first, const_iterator last);
        void clear() {this->erase(this->begin(), this->end());}

        void push_back(const T &v) {this->insert(this->cend(), v);}
        void push_back(T &&v) {this->insert(this->cend(), std::move(v));}
        void pop_back() {this->erase(--(this->end()));}
        void push_front(const T &v) {this->insert(this->cbegin(), v);}
        void push_front(T &&v) {this->insert(this->cbegin(), std::move(v));}
        void pop_front() {this->erase(this->begin());}

        template <typename... Args> iterator emplace(const_iterator pos, Args &&... args);
        template <typename... Args> void emplace_front(Args &&... args) {this->emplace(this->cbegin(), std::forward<Args>(args)...);}
        template <typename... Args> void emplace_back(Args &&... args) {this->emplace(--(this->cend()), std::forward<Args>(args)...);}

        void assign(size_type count, const T &v) {this->clear(); this->insert(this->end(), count, v);}
        template <typename InputIt> void assign(InputIt first, InputIt last) {this->clear(); this->insert(this->end(), first, last);}
        void assign(std::initializer_list<T> l)  {this->clear(); this->insert(this->end(), l);}

        void splice(const_iterator pos, clist<T, Allocator> &l);
        void splice(const_iterator pos, clist<T, Allocator> &&l) {this->splice(pos, l);}
        void splice(const_iterator pos, clist<T, Allocator> &l, const_iterator i);
        void splice(const_iterator pos, clist<T, Allocator> &&l, const_iterator i) {this->splice(pos, l, i);}
        void splice(const_iterator pos, clist<T, Allocator> &l, const_iterator first, const_iterator last);
        void splice(const_iterator pos, clist<T, Allocator> &&l, const_iterator first, const_iterator last) {this->splice(pos, l, first, last);}

        void remove(const T &v);
        template <typename Pred> void remove_if(Pred pred);

        void unique() {this->unique(std::equal_to<>());}
        template <typename BinPred> void unique(BinPred binpred);

        void merge(clist<T, Allocator> &l) {this->merge(l, std::less<>());}
        void merge(clist<T, Allocator> &&l) {this->merge(l);}
        template <typename Compare> void merge(clist<T, Allocator> &l, Compare comp);
        template <typename Compare> void merge(clist<T, Allocator> &&l, Compare comp) {this->merge(l, comp);}

        void sort() {this->sort(std::less<>());}
        template <typename Compare> void sort(Compare comp);

        void reverse();

    private:
        node *m_head;
        node *m_tail;
        node_allocator_type m_alloc_node;

};

template <typename T, typename Allocator>
typename clist<T, Allocator>::node_allocator_traits::pointer clist<T, Allocator>::_mknode(pointer pv)
{
    node_allocator_traits::pointer  p = node_allocator_traits::allocate(this->_alc(), 1);
    node_allocator_traits::construct(this->_alc(), p);
    if (pv != nullptr) {p->m_pT = pv;}
    return                          p;
}

template <typename T, typename Allocator>
void clist<T, Allocator>::_delnode(typename node_allocator_traits::pointer p, bool destrv)
{
    if (destrv)
    {
        allocator_traits::destroy(this->_alcv(), p->m_pT);
        allocator_traits::deallocate(this->_alcv(), p->m_pT, 1);
    }

    node_allocator_traits::destroy(this->_alc(), p);
    node_allocator_traits::deallocate(this->_alc(), p, 1);
}

template <typename T, typename Allocator>
template <typename... Args>
typename clist<T, Allocator>::pointer clist<T, Allocator>::_mkval(Args &&... args)
{
    pointer     p = allocator_traits::allocate(this->_alcv(), 1);
    allocator_traits::construct(this->_alcv(), p, std::forward<Args>(args)...);
    return      p;
}

template <typename T, typename Allocator>
void clist<T, Allocator>::_delval(pointer p)
{
    allocator_traits::destroy(this->_alcv(), p);
    allocator_traits::deallocate(this->_alcv(), p, 1);
}

template <typename T, typename Allocator>
clist<T, Allocator>::clist(clist<T, Allocator> &&l, const Allocator &alloc)
{
    if (alloc == l._alcv())
    {
        this->_alc()    = std::move(l._alc());
        this->m_head    = l.m_head;
        this->m_tail    = l.m_tail;
        l.m_head        = nullptr;
        l.m_tail        = nullptr;
    }
    else
    {
        this->_alc()    = node_allocator_type(alloc);
        this->_mkinit();
        for (auto &v : l) {this->emplace_back(std::move(v));}
    }
}

template <typename T, typename Allocator>
clist<T, Allocator>& clist<T, Allocator>::operator = (const clist<T, Allocator> &l)
{
    if (this != &l)
    {
        this->clear();

        if (node_allocator_traits::propagate_on_container_copy_assignment::value)
         {this->_alc() = node_allocator_traits::select_on_container_copy_construction(l._alc());}
        for (auto &v : l) {this->emplace_back(v);}
    }

    return  (*this);
}

template <typename T, typename Allocator>
clist<T, Allocator>& clist<T, Allocator>::operator = (clist<T, Allocator> &&l)
{
    if (this != &l)
    {
        if (this->_alc() != l._alc())
        {
            if (node_allocator_traits::propagate_on_container_move_assignment::value) {std::swap(this->_alc(), l._alc());}
            else {this->clear(); for (auto &v : l) {this->emplace_back(std::move(v));} return (*this);}
        }

        std::swap(this->m_head, l.m_head);
        std::swap(this->m_tail, l.m_tail);
    }

    return  (*this);
}

template <typename T, typename Allocator>
clist<T, Allocator>& clist<T, Allocator>::operator = (std::initializer_list<T> l)
{
    this->clear();
    for (auto &v : l) {this->push_back(v);}
    return  (*this);
}

template <typename T, typename Allocator>
void clist<T, Allocator>::swap(clist<T, Allocator> &l)
{
    if (this->_alc() != l._alc())
    {
        if (node_allocator_traits::propagate_on_container_swap::value) {using std::swap; swap(this->_alc(), l._alc());}
        else {return;}
    }

    std::swap(this->m_head, l.m_head);
    std::swap(this->m_tail, l.m_tail);
}

namespace std
{
    template <typename T, typename Allocator>
    void swap(clist<T, Allocator> &lhs, clist<T, Allocator> &rhs) {lhs.swap(rhs);}
}

template <typename T, typename Allocator>
void clist<T, Allocator>::resize(size_type count, const value_type &v)
{
    difference_type diff    = this->size() - count;
    if (diff >= 0) {this->insert(this->cend(), n, v);}
    else {this->erase(std::next(this->cend(), diff), this->cend());}
}

template <typename T, typename Allocator>
typename clist<T, Allocator>::iterator clist<T, Allocator>::insert(const_iterator pos, const T &v)
{
    node    *pCur(const_cast<node *>(pos.m_pT)), *pNew(this->_mknode(this->_mkval(v)));

    node::link(pCur->m_pPrev, pNew);
    node::link(pNew, pCur);

    return  iterator(pNew);
}

template <typename T, typename Allocator>
typename clist<T, Allocator>::iterator clist<T, Allocator>::insert(const_iterator pos, T &&v)
{
    node    *pCur(const_cast<node *>(pos.m_pT)), *pNew(this->_mknode(this->_mkval(std::move(v))));

    node::link(pCur->m_pPrev, pNew);
    node::link(pNew, pCur);

    return  iterator(pNew);  
}

template <typename T, typename Allocator>
typename clist<T, Allocator>::iterator clist<T, Allocator>::insert(const_iterator pos, size_type count, const T &v)
{
    iterator    rv(pos.m_pT->m_pPrev);
    for (size_type i = 0; i < count; ++i) {this->insert(pos, v);}
    return      ++rv;
}

template <typename T, typename Allocator>
template <typename InputIt>
typename clist<T, Allocator>::iterator clist<T, Allocator>::insert(const_iterator pos, InputIt first, InputIt last)
{
    iterator    rv(pos.m_pT->m_pPrev);
    while (first != last) {this->insert(pos, *(first++));}
    return      ++rv;
}

template <typename T, typename Allocator>
typename clist<T, Allocator>::iterator clist<T, Allocator>::insert(const_iterator pos, std::initializer_list<T> l)
{
    iterator    rv(pos.m_pT->m_pPrev);
    this->insert(pos, l.begin(), l.end());
    return      ++rv;   
}

template <typename T, typename Allocator>
typename clist<T, Allocator>::iterator clist<T, Allocator>::erase(const_iterator first, const_iterator last)
{
    while (first != last)
    {
        node        *pCur = const_cast<node *>(first.m_pT);
        ++first;
        pCur->unlink();
        this->_delnode(pCur, true);
    }

    return  iterator(const_cast<node *>(last.m_pT));
}

template <typename T, typename Allocator>
template <typename... Args>
typename clist<T, Allocator>::iterator clist<T, Allocator>::emplace(const_iterator pos, Args &&... args)
{
    node    *pCur(const_cast<node *>(pos.m_pT)), *pNew(this->_mknode(this->_mkval(std::forward<Args>(args)...)));

    node::link(pCur->m_pPrev, pNew);
    node::link(pNew, pCur);

    return  iterator(pNew);
}

template <typename T, typename Allocator>
void clist<T, Allocator>::splice(const_iterator pos, clist<T, Allocator> &l)
{
    if ((this != &l) && (this->_alc() == l._alc()))
    {
        if (!l.empty())
        {
            node    *pCur(const_cast<node*>(pos.m_pT));
            node::link(pCur->m_pPrev, l.begin().m_pT);
            node::link((--l.end()).m_pT, pCur);
            node::link((--l.begin()).m_pT, l.end().m_pT);
        }
    }
}

template <typename T, typename Allocator>
void clist<T, Allocator>::splice(const_iterator pos, clist<T, Allocator> &l, const_iterator i)
{
    if (this->_alc() == l._alc())
    {
        if ((i != pos) && (std::next(i) != pos))
        {
            node    *pCur(const_cast<node*>(pos.m_pT)), *pNew(const_cast<node*>(i.m_pT));
            node::link(pNew->m_pPrev, pNew->m_pNext);
            node::link(pCur->m_pPrev, pNew);
            node::link(pNew, pCur);
        }
    }
}

template <typename T, typename Allocator>
void clist<T, Allocator>::splice(const_iterator pos, clist<T, Allocator> &l, const_iterator first, const_iterator last)
{
    if (this->_alc() == l._alc())
    {
        if (first != last)
        {
            node    *pCur(const_cast<node*>(pos.m_pT)), *pNewL(const_cast<node*>(first.m_pT)), *pNewR(const_cast<node*>((--last).m_pT));
            node::link(pNewL->m_pPrev, pNewR->m_pNext);
            node::link(pCur->m_pPrev, pNewL);
            node::link(pNewR, pCur);
        }
    }
}

template <typename T, typename Allocator>
void clist<T, Allocator>::remove(const T &v)
{
    if (!this->empty())
    {
        auto    it(this->begin()), e(this->end());
        while (it != e)
        {
            if ((*it) == v) {this->erase(it++);}
            else            {++it;}
        }
    }
}

template <typename T, typename Allocator>
template <typename Pred>
void clist<T, Allocator>::remove_if(Pred pred)
{
    if (!this->empty())
    {
        auto    it(this->begin()), e(this->end());
        while (it != e)
        {
            if (pred(*it) != false) {this->erase(it++);}
            else                    {++it;}
        }
    }
}

template <typename T, typename Allocator>
template <typename BinPred>
void clist<T, Allocator>::unique(BinPred binpred)
{
    if (!this->empty())
    {
        auto    it(++(this->begin())), e(this->end());
        while (it != e)
        {
            if (binpred(*it, *std::prev(it)))   {this->erase(it++);}
            else                                            {++it;}
        }
    }
}

template <typename T, typename Allocator>
template <typename Compare>
void clist<T, Allocator>::merge(clist<T, Allocator> &l, Compare comp)
{
    if ((this != &l) && (this->_alc() == l._alc()))
    {
        auto    it1(this->begin()), e1(this->end()), it2(l.begin()), e2(l.end());

        while ((it1 != e1) && (it2 != e2))
        {
            if (comp(*it2, *it1))   {this->splice(it1, l, it2++);}
            else                    {++it1;}
        }

        if (it2 != e2) {this->splice(it1, l, it2, e2);}
    }
}

template <typename T, typename Allocator>
template <typename Compare>
void clist<T, Allocator>::sort(Compare comp) // merge sort (at least it was intended to be)
{
std::function<void(clist<T, Allocator>&, size_type)> fn_sort = [&comp, &fn_sort] (clist<T, Allocator> &l, size_type lsz) -> void
{
    if (lsz > 1)
    {
        if (lsz == 2)
        {
            node    *pL(l.begin().m_pT), *pR(pL->m_pNext);
            if (comp(*(pR->m_pT), *(pL->m_pT))) {std::swap(pL->m_pT, pR->m_pT);}
        }
        else
        {
            clist<T, Allocator> rhs(l._alcv());
            size_type           sz2(lsz / 2);
            rhs.splice(rhs.begin(), l, l.begin(), std::next(l.begin(), sz2));
            fn_sort(rhs, sz2);
            fn_sort(l, sz2 + (lsz % 2));
            l.merge(rhs, comp);
        }
    }
};

fn_sort(*this, this->size());
}

template <typename T, typename Allocator>
void clist<T, Allocator>::reverse()
{
    this->m_head->reverse();
    this->m_tail->reverse();
    std::swap(this->m_head, this->m_tail);
    for (auto it = this->begin(), e = this->end(); it != e; ++it) {it.m_pT->reverse();}
}

template <typename T, typename Allocator>
bool operator == (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs)
 {return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());}

template <typename T, typename Allocator>
bool operator != (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs) {return !(lhs == rhs);}

template <typename T, typename Allocator>
bool operator < (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs)
 {return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());}

template <typename T, typename Allocator>
bool operator <= (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs) {return !(lhs > rhs);}

template <typename T, typename Allocator>
bool operator > (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs) {return (rhs < lhs);}

template <typename T, typename Allocator>
bool operator >= (const clist<T, Allocator> &lhs, const clist<T, Allocator> &rhs) {return !(lhs < rhs);}
\$\endgroup\$
  • 5
    \$\begingroup\$ Point #1: at least as it shows up here, the formatting renders the code excessively difficult to read. \$\endgroup\$ – Jerry Coffin Mar 6 '14 at 19:28
  • \$\begingroup\$ Yup, sorry, added mediafire link for .h file itself (you can view the file online fullscreen with the original formatting). \$\endgroup\$ – Desu_Never_Lies Mar 6 '14 at 19:33
  • 1
    \$\begingroup\$ Wherever did you get the idea to format it like this? How wide is your screen?? Could you use a more standard format for example like this which uses less horizontal space? IMO "excessively difficult to read" in the comment above means "nearly unreadable" and "difficult to review". \$\endgroup\$ – ChrisW Mar 6 '14 at 19:39
  • \$\begingroup\$ Done. Online version also updated. \$\endgroup\$ – Desu_Never_Lies Mar 6 '14 at 19:54
  • 1
    \$\begingroup\$ One tip: use alias templates instrad of typedefs: while keeping a consistent indentation, your subtype declarations will be even easier to read. \$\endgroup\$ – Morwenn Mar 6 '14 at 22:45
4
\$\begingroup\$

Why return a value:

value_type operator * () const {return *(this->m_pT->m_pT);}

I would return a const reference

 const_reference operator * () const {return *(this->m_pT->m_pT);}

Iterator does not seem to support operator-> which is a requirement of the iterator concept.

Personally I don't like the leading '_' you put on your private members. If this is short hand to indicate they are private it just means you are not using descriptive enough names to describe your methods. The whole point in writing complex code is that the functions should be self descriptive.

 allocator_type _alcv() {return allocator_type(this->m_alloc_node);}

 // why note use a descriptive name.
 // It will make the code easier to read and maintain.

allocator_type allocate_node() {return allocator_type(this->m_alloc_node);}

// Or I prefer camel case

allocator_type allocateNode() {return allocator_type(this->m_alloc_node);}

Also (another personal preference) I like type names to begin with an uppercase letter. That way you can easily spot types in comparison to objects (ie runtime Vs compile time things). Its a shame the standard libraries does not use this convention but we are now stuck for backwards compatibility (But user defined types tend to be defined with an upper case letter (but thats not universal and a style thing so follow your local guidelines)).

Personally I think size() should be O(1) not O(n). I know this means things like splice go from O(1) to O(n) so there is a trade off and you probably chose the correct one (as thats how the standard version deals with it). But you could cache the size value so you calculate it on first it can be just returned on subsequent calls; then on splice() you can mark it as dirty and recalculate the next time size() is called.

    size_type size() const {return std::distance(this->cbegin(), this->cend());}

Seems like empty() should be a bit more effecient.

    bool empty() const {return (this->cbegin() == this->cend());}

Creating two objects and checking for equivalence seems to be overkill. There seems like there could be a much simpler test for empty.

    bool empty() const {return m_head != NULL;} /* Does that work or is there a sentanal */

You seem to do a lot of functions this way when there seem to be easier alternatives:

    reference front() {return *(this->begin());}
    /*constexpr*/ const_reference front() const {return *(this->cbegin());}
    reference back() {return *(--(this->end()));}
    /*constexpr*/ const_reference back() const {return *(--(this->cend()));}
\$\endgroup\$
  • \$\begingroup\$ Thanks for pointing out the missing operator->. I've also followed your suggestion regarding returning const_reference. First post updated (also with fixes to .sort). I'd really love to know if there's anything else wrong or worth mentioning ;) \$\endgroup\$ – Desu_Never_Lies Mar 7 '14 at 19:28
  • \$\begingroup\$ @Desu_Never_Lies: Only have time for a cursory glance. I am away from home currently. But I will add more if I spot it. \$\endgroup\$ – Martin York Mar 8 '14 at 1:40
  • \$\begingroup\$ I thought about caching size, but just didn't want to complicate things. empty(), front(), etc are implemented as operational semantics suggest (on a side note - compiled release version of the code optimizes these functions to a mere inline pointer comparison; I shouldn't just rely on compiler optimizations though). \$\endgroup\$ – Desu_Never_Lies Mar 8 '14 at 8:13
2
\$\begingroup\$

I think it should include the headers (e.g. <memory>, <type_traits>) on which this type depends.

Is the loop method called from anywhere?

Should the iterator_cnc(const iterator_cnc<false> &it) constructor be iterator_cnc(const iterator_cnc<is_const_iter> &it) instead?

It's too new for Gimpel's Lint.

What have you done to satisfy yourself that it's correct: is there a standard list of test cases?

\$\endgroup\$
  • \$\begingroup\$ Loop isn't called from anywhere, guess I had some idea for it, but it didn't make it to the final version of the code. Constructor takes iterator_cnc<false> to allow implicit conversion from iterator to const_iterator. As for the tests all I did was check if I meet the standard & do a simple hand-written test, so there aren't any framework-driven ones (and I've never worked with them to be honest). \$\endgroup\$ – Desu_Never_Lies Mar 7 '14 at 21:27
  • 1
    \$\begingroup\$ If I were implementing a standard (e.g. writing a new HTML rendering engine) I would hope to find a pre-existing semi-standard list or lists of test cases, which I could use to test my implementation. Perhaps you could find an open-source test suite that is used to test std::list. \$\endgroup\$ – ChrisW Mar 7 '14 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.