3
\$\begingroup\$

This is a class I implemented that can be thought of as a highly specialized version of std::list<> for pointers. It provides the additional feature that the elements can be removed in constant time with the element alone. This is accomplished with an std::unordered_map<> to associate list elements with their iterator.

I would appreciate any suggestions for improvement. I am particularly keen to know if there is a better way to enforce that the template parameter has to be a pointer type. The class currently does not work for std::unique_ptr<>, so any thoughts on what needs to be done on that front would be great. Also, if there is just a plain better way of doing the same thing, I would welcome those thoughts as well.

template <typename, typename> class ptr_list;

class ptr_list_helper {
    template <typename, typename> friend class ptr_list;
    typedef std::true_type true_type;
    template <typename T> struct is_ptr : std::is_pointer<T> {};
    template <typename T> struct is_ptr<std::shared_ptr<T>> : true_type {};
    template <typename T> struct is_ptr<std::unique_ptr<T>> : true_type {};
    struct void_ptr {
        void *p_;
        void_ptr (void *p = 0) : p_(p) {}
        template <typename T>
        operator T * () const { return static_cast<T *>(p_); }
        template <typename T>
        operator const T * () const { return static_cast<T *>(p_); }
        bool operator < (const void_ptr &p) const { return p_ < p.p_; }
        bool operator == (const void_ptr &p) const { return p_ == p.p_; }
    };
    struct const_void_ptr {
        const void *p_;
        const_void_ptr (const void *p = 0) : p_(p) {}
        template <typename T>
        operator const T * () const { return static_cast<T *>(p_); }
        bool operator < (const const_void_ptr &p) const { return p_ < p.p_; }
        bool operator == (const const_void_ptr &p) const { return p_ == p.p_; }
    };
    template <typename T>
    struct hash {
        std::ptrdiff_t operator () (T p) const {
            return reinterpret_cast<std::ptrdiff_t>(p.p_);
        }
    };
    template <typename T> struct traits;
    template <typename T> struct traits<T *> {
        typedef std::list<void_ptr> ListImpl;
        typedef T Type;
        typedef T *RealPtrType;
        typedef T *RefType;
        static RealPtrType get (RefType ptr) { return ptr; }
    };
    template <typename T> struct traits<const T *> {
        typedef std::list<const_void_ptr> ListImpl;
        typedef T Type;
        typedef const T *RealPtrType;
        typedef const T *RefType;
        static RealPtrType get (RefType ptr) { return ptr; }
    };
    template <typename T> struct traits<std::shared_ptr<T>> {
        typedef std::list<std::shared_ptr<T>> ListImpl;
        typedef T Type;
        typedef T *RealPtrType;
        typedef const std::shared_ptr<T> &RefType;
        static RealPtrType get (RefType ptr) { return ptr.get(); }
    };
    template <typename T> struct traits<std::unique_ptr<T>> {
        typedef std::list<std::unique_ptr<T>> ListImpl;
        typedef T Type;
        typedef T *RealPtrType;
        typedef const std::unique_ptr<T> &RefType;
        static RealPtrType get (RefType ptr) { return ptr.get(); }
    };
    template <typename PtrType, typename Allocator> struct impl {
        typedef traits<PtrType> Traits;
        typedef typename Traits::ListImpl ListImpl;
        typedef typename ListImpl::iterator SelfType;
        typedef typename ListImpl::const_iterator ConstSelfType;

        typedef typename Traits::Type Type;
        typedef const_void_ptr KeyPtrType;
        typedef hash<KeyPtrType> MapHash;
        typedef std::equal_to<KeyPtrType> MapEqual;
        typedef std::pair<const KeyPtrType, SelfType> MapPair;
        typedef typename Allocator::template rebind<MapPair>::other
            MapAllocator;
        typedef std::unordered_map<KeyPtrType, SelfType,
                                   MapHash, MapEqual, MapAllocator> SelfMap;

        typedef typename Traits::RefType RefType;

        static const Type * get (RefType p) { return Traits::get(p); }

        class Iterator {
            friend class ptr_list<PtrType, Allocator>;
            ConstSelfType self_;
            bool eq (const Iterator &i) const { return self_ == i.self_; }
        public:
            Iterator () : self_() {}
            Iterator (SelfType s) : self_(s) {}
            Iterator (ConstSelfType s) : self_(s) {}
            operator RefType () const { return *self_; }
            RefType operator -> () const { return *self_; }
            Type & operator * () const { return **self_; }
            const Iterator & operator ++ () { ++self_; return *this; }
            const Iterator & operator -- () { --self_; return *this; }
            Iterator operator ++ (int) { return self_++; }
            Iterator operator -- (int) { return self_--; }
            Iterator next () const { ConstSelfType s(self_); return ++s; }
            Iterator prev () const { ConstSelfType s(self_); return --s; }
            operator bool () const { return *self_; }
            bool operator == (const Iterator &i) const { return eq(i); }
            bool operator != (const Iterator &i) const { return !eq(i); }
        };

        class Rotareti {
            Iterator iter_;
            Iterator cur () const { return iter_.prev(); }
            bool eq (const Rotareti &i) const { return iter_ == i.iter_; }
        public:
            Rotareti () : iter_() {}
            Rotareti (Iterator i) : iter_(i) {}
            operator RefType () const { return cur(); }
            RefType operator -> () const { return cur(); }
            Type & operator * () const { return *cur(); }
            const Rotareti & operator ++ () { --iter_; return *this; }
            const Rotareti & operator -- () { ++iter_; return *this; }
            Rotareti operator ++ (int) { return iter_--; }
            Rotareti operator -- (int) { return iter_++; }
            Rotareti next () const { return iter_.prev(); }
            Rotareti prev () const { return iter_.next(); }
            operator bool () const { return cur(); }
            bool operator == (const Rotareti &i) const { return eq(i); }
            bool operator != (const Rotareti &i) const { return !eq(i); }
            Iterator base () const { return iter_; }
        };
    };
};

template <typename PtrType, typename Allocator = std::allocator<PtrType>>
class ptr_list {

    static_assert(ptr_list_helper::is_ptr<PtrType>::value,
                  "ptr_list requires pointer type");

    static_assert(std::is_copy_constructible<PtrType>::value,
                  "ptr_list requires copying");

    typedef typename ptr_list_helper::template impl<PtrType, Allocator> Traits;

    typedef typename Traits::Type Type;
    typedef typename Traits::RefType RefType;

    typedef typename Traits::ListImpl ListImpl;
    typedef typename Traits::SelfMap SelfMap;

    ListImpl impl_;
    SelfMap selfmap_;

    static const Type * ptr (RefType p) { return Traits::get(p); }

    ptr_list & replace (const ptr_list &l, bool clear_map = false) {
        if (clear_map) selfmap_.clear();
        impl_ = l.impl_;
        for (auto x = impl_.begin(); x != impl_.end(); ++x) {
            selfmap_[ptr(*x)] = x;
        }
        return *this;
    }

public:

    typedef typename Traits::Iterator iterator;
    typedef typename Traits::Rotareti reverse_iterator;
    typedef iterator const_iterator;
    typedef reverse_iterator const_reverse_iterator;

    typedef PtrType value_type;
    typedef RefType reference;
    typedef typename ListImpl::size_type size_type;
    typedef typename ListImpl::difference_type difference_type;
    typedef typename ListImpl::pointer pointer;
    typedef typename ListImpl::const_pointer const_pointer;

    typedef Allocator allocator_type;

    ptr_list () : impl_(), selfmap_() {}
    ptr_list (const ptr_list &l) : impl_(), selfmap_() { replace(l); }
    ptr_list & operator = (const ptr_list &l) { return replace(l, true); }

    allocator_type get_allocator () const { return impl_.get_allocator(); }

    iterator begin () const { return impl_.begin(); }
    iterator end () const { return impl_.end(); }

    const_iterator cbegin () const { return impl_.cbegin(); }
    const_iterator cend () const { return impl_.cend(); }

    reverse_iterator rbegin () const { return end(); }
    reverse_iterator rend () const { return begin(); }

    const_reverse_iterator crbegin () const { return cend(); }
    const_reverse_iterator crend () const { return cbegin(); }

    void clear () { selfmap_.clear(); impl_.clear(); }

    iterator find (RefType p) const {
        auto x = selfmap_.find(ptr(p));
        return (x != selfmap_.end() ? x->second : end());
    }

    iterator insert (iterator where, RefType p) {
        typename SelfMap::iterator x = selfmap_.find(ptr(p));
        if (x == selfmap_.end()) {
            typename SelfMap::value_type v(ptr(p), impl_.end());
            x = selfmap_.insert(v).first;
        } else {
            impl_.erase(x->second);
        }
        auto w = selfmap_.find(ptr(where));
        return x->second = ((w != selfmap_.end())
                            ? impl_.insert(w->second, p)
                            : impl_.insert(impl_.end(), p));
    }

    iterator erase (RefType p) {
        auto x = selfmap_.find(ptr(p));
        if (x == selfmap_.end()) return end();
        selfmap_.erase(x);
        return impl_.erase(x->second);
    }

    RefType front () const { return begin(); }
    RefType back () const { return end().prev(); }

    void push_front (RefType p) { insert(begin(), p); }
    void push_back (RefType p) { insert(end(), p); }

    void pop_front () { erase(front()); }
    void pop_back () { erase(back()); }

    bool empty () const { return impl_.empty(); }
    bool contains (RefType p) const { return find(p) != end(); }

    size_type size () const { return impl_.size(); }
    size_type max_size () const { return impl_.max_size(); }

    void swap (ptr_list &other) {
        selfmap_.swap(other.selfmap_);
        impl_.swap(other.impl_);
    }

    void splice (iterator where, ptr_list &other) {
        auto i = other.impl_.begin();
        while (i != other.impl_.end()) {
            PtrType x(*i++);
            insert(where, x);
        }
        other.clear();
    }

    void remove (RefType p) { erase(p); }
    template <typename Predicate> void remove_if (Predicate p) {
        auto i = impl_.begin();
        while (i != impl_.end()) {
            PtrType x(*i++);
            if (p(x)) remove(x);
        }
    }

    void reverse () { impl_.reverse(); }

    void sort () { impl_.sort(); }
    template <typename Compare> void sort (Compare c) { impl_.sort(c); }

};
\$\endgroup\$
8
  • \$\begingroup\$ Have you tried Boost.MultiIndex? \$\endgroup\$ – TemplateRex Sep 29 '13 at 13:53
  • \$\begingroup\$ @TemplateRex: Never heard of it before now. So, my class is like a multi_index_container of pointers that has a hashed_unique index? \$\endgroup\$ – jxh Sep 29 '13 at 16:47
  • \$\begingroup\$ Actually, the pointers are an implementation detail that Boost abstracts away. I'll write a proper answer later tonight. \$\endgroup\$ – TemplateRex Sep 29 '13 at 16:50
  • \$\begingroup\$ @TemplateRex: Looking forward to it, but realize I need it to be a container of pointers. \$\endgroup\$ – jxh Sep 29 '13 at 17:25
  • \$\begingroup\$ Which is the fundamental requirement? To have a std::list<T*>, and to add O(1) removal on top of that? Or, to have a std::multiset<T>, and to add bidirectional iteration on top of that? I just want to make sure that your pointer requirement is actually required or if you think you need that to efficiently implement the removal. \$\endgroup\$ – TemplateRex Sep 29 '13 at 18:34
1
\$\begingroup\$

I think this problem screams out for Boost.MultiIndex. It allows to add multiple indices to a container. In your case, you seem to want both a std::list<T> and a std::unordered_set interface. In Boost.MultiIndex, these index types are called sequenced and hashed_unique. A simple template definition would be

template<class T>
using my_container = multi_index_container<
  T,
  indexed_by<
    sequenced<>,
    hashed_unique< identity<T> >,
  >
>;

The documentation of Boost.MultiIndex is one of the best of all the Boost libraries, so you should be able to work out how to iterate over this container, and how to insert/erase elements. The library will guarantee you amortized O(1) insertion/erasure, as well as bidirectional iteration and O(1) splicing and O(N log N) sorting.

If you wonder how this is implemented, there is a special section about that in the docs. I think that this is much better than to build your own container. Writing proper containers (with correct complexity, exception safety, resource management and move semantics) is very hard. Leveraging high-quality libraries should be your first priority.

BTW, here's a somewhat related in-depth discussion of various ways to write an LRU-cache, starting with using combinations of STL containers and ending with Boost.Bimap (which is a special case of Boost.MultIndex). It shows how many of the pointer manipulations of hand-written solutions are quite intricate to get correct and efficient.

\$\endgroup\$

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.