Generic (Multi)SkipList adapter class

Question

Today I have written my first implementation of a SkipList (on top of a std::vector), because I was tired in using std::lower_bound and the other functions manually. I tried to create it as generic as possible to provide the user as much freedom as healthy. During the implementation I always had an eye on the std::set and std::multiset documentations, to keep the interface similar to those.

At first I decided to hide the non-const iterators from the public interface to prevent the SkipList from getting manipulated on accident, but after the first iteration the usage it was very inelegant. At latest when you tried to use just one property of the value_type Objects as key it revealed its weaknesses.To change any of the other variables of that element I had to remove it first and insert it again afterwards. That was neither good, clean or elegant; that's the reason why I decided to expose the non-const-iterators, too. Btw, std::set and std::multiset expose them, too, thus it shouldn't be a huge surprise for the user of that classes.

Here is the code for both, the SkipList (unique elements) and the MultiSkipList.

#include <vector>
#include <algorithm>
#include <iterator>

namespace detail
{
    template <class T, bool UniqueElements, class Compare = std::less<>, class Container = std::vector<T>>
    class BaseSkipList
    {
    public:
        using container_type = Container;
        using value_type = typename Container::value_type;
        using size_type = typename Container::size_type;
        using iterator = typename Container::iterator;
        using reverse_iterator = typename Container::reverse_iterator;
        using const_iterator = typename Container::const_iterator;
        using const_reverse_iterator = typename Container::const_reverse_iterator;

        BaseSkipList() = default;

        explicit BaseSkipList(Compare&& _compare) :
            m_Compare(std::move(_compare))
        {}

        explicit BaseSkipList(Container _container, Compare&& _compare = Compare()) :
            m_Container(std::move(_container)),
            m_Compare(std::move(_compare))
        {
            std::sort(std::begin(m_Container), std::end(m_Container), m_Compare);
        }

        BaseSkipList(const BaseSkipList&) = default;
        BaseSkipList(BaseSkipList&&) = default;
        BaseSkipList& operator =(const BaseSkipList&) = default;
        BaseSkipList& operator =(BaseSkipList&&) = default;

        bool empty() const
        {
            return std::empty(m_Container);
        }

        size_type size() const
        {
            return std::size(m_Container);
        }

        void clear()
        {
            m_Container.clear();
        }

        void reserve(size_type _new_cap)
        {
            m_Container.reserve(_new_cap);
        }

        size_type capacity() const noexcept
        {
            return m_Container.capacity();
        }

        void shrink_to_fit()
        {
            return m_Container.shrink_to_fit();
        }

        template <class TValueType>
        std::pair<iterator, bool> insert(TValueType&& _value)
        {
            return _insert(begin(), std::forward<TValueType>(_value));
        }

        template <class TIterator>
        void insert(TIterator _itr, const TIterator& _end)
        {
            for (; _itr != _end; ++_itr)
                _insert(*_itr);
        }

        void insert(std::initializer_list<value_type> _ilist)
        {
            insert(std::begin(_ilist), std::end(_ilist));
        }

        iterator erase(const_iterator _itr)
        {
            return m_Container.erase(_itr);
        }

        iterator erase(const_iterator _first, const_iterator _last)
        {
            return m_Container.erase(_first, _last);
        }

        template <class TComparable>
        iterator erase(const TComparable& _value)
        {
            auto itr = std::lower_bound(std::begin(m_Container), std::end(m_Container), _value, m_Compare);
            if (itr != end())
                return m_Container.erase(itr);
            return end();
        }

        template <class TComparable>
        iterator find(const TComparable& _value)
        {
            return _find(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator find(const TComparable& _value) const
        {
            return _find(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        iterator lower_bound(const TComparable& _value)
        {
            return _lower_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator lower_bound(const TComparable& _value) const
        {
            return _lower_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        iterator upper_bound(const TComparable& _value)
        {
            return _upper_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator upper_bound(const TComparable& _value) const
        {
            return _upper_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        bool contains(const TComparable& _value) const
        {
            return find(_value) != end();
        }

        /*#####
        # multi element stuff
        #####*/
        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        std::pair<iterator, iterator> equal_range(const TComparable& _value)
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        std::pair<const_iterator, const_iterator> equal_range(const TComparable& _value) const
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        iterator find_last(const TComparable& _value)
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        const_iterator find_last(const TComparable& _value) const
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        iterator erase_all_of(const TComparable& _value)
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return m_Container.erase(range.first, range.second);
        }

        template <class TComparable, typename = std::enable_if_t<!UniqueElements>>
        size_type count(const TComparable& _value) const
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return std::distance(range.first, range.second);
        }

        template <class TValueType = value_type, typename = std::enable_if_t<!UniqueElements>>
        void unique()
        {
            m_Container.erase(std::unique(std::begin(m_Container), std::end(m_Container),
                [&compare = m_Compare](const auto& _lhs, const auto& _rhs)
            {
                return !compare(_lhs, _rhs) && !compare(_rhs, _lhs);
            }
            ), end());
        }

        /*#####
        # comparison stuff
        #####*/
        bool operator ==(const BaseSkipList& _other) const
        {
            return std::equal(begin(), end(), std::begin(_other), std::end(_other),
                [&compare = m_Compare](const auto& _elLhs, const auto& _elRhs)
            {
                return !compare(_elLhs, _elRhs) && !compare(_elRhs, _elLhs);
            }
            );
        }

        friend bool operator !=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs == _rhs);
        }

        bool operator <(const BaseSkipList& _other) const
        {
            return std::lexicographical_compare(begin(), end(), std::begin(_other), std::end(_other), m_Compare);
        }

        friend bool operator >=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs < _rhs);
        }

        friend bool operator >(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return _rhs < _lhs;
        }

        friend bool operator <=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs > _rhs);
        }

        /*#####
        # Iterator stuff
        #####*/
        iterator begin() noexcept
        {
            return std::begin(m_Container);
        }

        const_iterator begin() const noexcept
        {
            return std::begin(m_Container);
        }

        const_iterator cbegin() const noexcept
        {
            return std::cbegin(m_Container);
        }

        iterator end() noexcept
        {
            return std::end(m_Container);
        }

        const_iterator end() const noexcept
        {
            return std::end(m_Container);
        }

        const_iterator cend() const noexcept
        {
            return std::cend(m_Container);
        }

        iterator rbegin() noexcept
        {
            return std::rbegin(m_Container);
        }

        const_reverse_iterator rbegin() const noexcept
        {
            return std::rbegin(m_Container);
        }

        const_reverse_iterator crbegin() const noexcept
        {
            return std::crbegin(m_Container);
        }

        iterator rend() noexcept
        {
            return std::rend(m_Container);
        }

        const_reverse_iterator rend() const noexcept
        {
            return std::rend(m_Container);
        }

        const_reverse_iterator crend() const noexcept
        {
            return std::crend(m_Container);
        }

    private:
        Container m_Container;
        Compare m_Compare;

        template <class TValueType>
        std::pair<iterator, bool> _insert(TValueType&& _value)
        {
            auto itr = _lower_bound(m_Container, m_Compare, _value);
            if constexpr (UniqueElements)
            {
                if (itr == end() || m_Compare(_value, *itr))
                {
                    m_Container.insert(itr, std::forward<TValueType>(_value));
                    return { itr, true };
                }
            }
            else
            {
                m_Container.insert(itr, std::forward<TValueType>(_value));
                return { itr, true };
            }
            return { itr, false };
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _find(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            auto itr = _lower_bound(_container, _compare, _value);
            if (itr != std::end(_container) && !_compare(_value, *itr))
                return itr;
            return std::end(_container);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _find_last(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            auto range = _equal_range(_container, _compare, _value);
            auto dist = std::distance(range.first, range.second);
            if (0 < dist)
            {
                std::advance(range.first, dist - 1);
                return range.first;
            }
            return std::end(_container);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _lower_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::lower_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _upper_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::upper_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _equal_range(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::equal_range(std::begin(_container), std::end(_container), _value, _compare);
        }
    };
} // namespace detail

template <class T, class Compare = std::less<>, class Container = std::vector<T>>
using SkipList = detail::BaseSkipList<T, true, Compare, Container>;
template <class T, class Compare = std::less<>, class Container = std::vector<T>>
using MultiSkipList = detail::BaseSkipList<T, false, Compare, Container>;

Here is a simple example program; please be aware, that in the second example the member x of the Test objects is used as key. We can search for concrete objects or simply key values.

int main()
{
    SkipList<int> ints({ 3, 4, 1, 2 });

    auto intItr = ints.find(1);
    // intItr = ints.find_last(5);  // not available for SkipLists
    ints.insert({ 5, 2, 3, 10, 0 });
    ints.erase(4);


    struct TestCompare
    {
        bool operator ()(const Test& _lhs, const Test& _rhs) const
        {
            return _lhs.x < _rhs.x;
        }

        bool operator ()(const Test& _lhs, int _rhs) const
        {
            return _lhs.x < _rhs;
        }

        bool operator ()(int _lhs, const Test& _rhs) const
        {
            return _lhs < _rhs.x;
        }
    };

    MultiSkipList<Test, TestCompare> tests({
        { 3 },
        { 4 },
        { 1 },
        { 2 },
        { 2 }
    });
    auto testItr = tests.find(2);
    testItr = tests.find_last(2);
    if (testItr == tests.find_last(Test{ 2 }))
        tests.unique();             // that line removes the second Test object with x == 2
    auto count = tests.count(2);    // there is only one element with x == 2 left

    tests.insert({ { 5}, { 2}, {3}, {10}, {0} });   // again 2 of x == 2

    tests <= tests;
    tests == tests;

    tests.erase_all_of(2);      // all twos are gone
}

Answer 1

Is that a skip list?

Frankly, I don't see how it can be described as a skip list. Skip lists are meant to replace balanced trees, since they offer a similar service (fast insertion in a sorted container -so fast look-up also) with the added value of greater simplicity; they work by having different tracks -some faster, some more complete- to go through the elements they contain.

Then what is it exactly?

I believe that what you did was to build a kind of generic interface over containers, and then use that interface to provide what you thought was easier access to standard algorithms. But please correct me if I'm wrong. If not -if I'm right- what you did amounts to a crime in the eye of the STL police. Decoupling containers and algorithms is one of the greatest features of the STL, and going back on that -even if it involves some clever genericity- would buy you a direct ticket to the Java prison.

What you could have done instead

I understand that typing algorithm(std::begin(container), std::end(container); seems backwards when so many other languages have algorithm(container) or even container.algorithm. And I would very much agree that saving keystrokes is worth investing in the long term. Then simply take all those static private functions, and make them free and public, and put them into their own namespace.

namespace adapt {
    template <typename Container, typename Compare = std::less<>>
    void sort(Container& container, Compare cmp) {
        std::sort(std::begin(container), std::end(container), cmp);
    }
    // ... and so on
}

Then if those toilsome keystrokes really bother you, it's only a matter of introducing the adapted function at the beginning of your file:

using adapt::lower_bound;
// ...
lower_bound(my_vec, my_val);

Or, if you want to be very clever, and aren't afraid of evil hacks and macros, you can write a generic adaptor for algorithms. It could be a lot cleaner if there were a standard way to turn generic functions into generic lambdas (because the latter can be deduced whereas the former can't), but it isn't that ugly either:

#include <iostream>
#include <algorithm>
#include <vector>

#define AS_LAMBDA(fn) [](auto&&... args) { return fn(std::forward<decltype(args)>(args)...); }

#define CONTAINER_APPLY(algorithm, container, ...) \
container_apply_impl(AS_LAMBDA(algorithm), container, __VA_ARGS__)

template <typename Algorithm, typename Container, typename... Args> 
auto container_apply_impl(Algorithm algorithm, Container& container, Args&&... args) { 
    return algorithm(std::begin(container), std::end(container), std::forward<Args>(args)...); 
}

int main() {
    std::vector<int> vec{1, 2, 3, 4, 8, 7, 2, 8, 6, 4, 2, 3 };
    CONTAINER_APPLY(std::for_each, vec, [](auto i) { std::cout << i << ", "; });
}

Answer 2

After a few days in use, I discovered a few mistakes and would like to share them to you. I also fixed a compile error in clang, because the MultiSkipList functions weren't disabled in a correct way.

I still would like to receive some opinions about style, usability and correctness.

#pragma once

#include <vector>
#include <algorithm>
#include <iterator>

namespace detail
{
    template <class T, bool UniqueElements, class Compare = std::less<>, class Container = std::vector<T>>
    class BaseSkipList
    {
    public:
        using container_type = Container;
        using value_type = typename Container::value_type;
        using size_type = typename Container::size_type;
        using iterator = typename Container::iterator;
        using reverse_iterator = typename Container::reverse_iterator;
        using const_iterator = typename Container::const_iterator;
        using const_reverse_iterator = typename Container::const_reverse_iterator;

        BaseSkipList() = default;

        explicit BaseSkipList(Compare _compare) :
            m_Compare(std::move(_compare))
        {
        }

        explicit BaseSkipList(Container _container, Compare _compare = Compare()) :
            m_Container(std::move(_container)),
            m_Compare(std::move(_compare))
        {
            std::sort(std::begin(m_Container), std::end(m_Container), m_Compare);
        }

        ~BaseSkipList() = default;

        BaseSkipList(const BaseSkipList&) = default;
        BaseSkipList(BaseSkipList&&) noexcept = default;

        BaseSkipList& operator =(const BaseSkipList&) = default;
        BaseSkipList& operator =(BaseSkipList&&) noexcept = default;

        bool empty() const
        {
            return std::empty(m_Container);
        }

        size_type size() const
        {
            return std::size(m_Container);
        }

        void clear()
        {
            m_Container.clear();
        }

        void reserve(size_type _new_cap)
        {
            m_Container.reserve(_new_cap);
        }

        size_type capacity() const noexcept
        {
            return m_Container.capacity();
        }

        void shrink_to_fit()
        {
            return m_Container.shrink_to_fit();
        }

        template <class TValueType>
        std::pair<iterator, bool> insert(TValueType&& _value)
        {
            return _insert(std::forward<TValueType>(_value));
        }

        template <class TIterator>
        void insert(TIterator _itr, const TIterator& _end)
        {
            for (; _itr != _end; ++_itr)
            {
                _insert(*_itr);
            }
        }

        void insert(std::initializer_list<value_type> _ilist)
        {
            insert(std::begin(_ilist), std::end(_ilist));
        }

        iterator erase(const_iterator _itr)
        {
            return m_Container.erase(_itr);
        }

        iterator erase(const_iterator _first, const_iterator _last)
        {
            return m_Container.erase(_first, _last);
        }

        template <class TComparable>
        iterator erase(const TComparable& _value)
        {
            auto itr = std::lower_bound(std::begin(m_Container), std::end(m_Container), _value, m_Compare);
            if (itr != end())
            {
                return m_Container.erase(itr);
            }
            return end();
        }

        template <class TComparable>
        iterator find(const TComparable& _value)
        {
            return _find(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator find(const TComparable& _value) const
        {
            return _find(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        iterator lower_bound(const TComparable& _value)
        {
            return _lower_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator lower_bound(const TComparable& _value) const
        {
            return _lower_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        iterator upper_bound(const TComparable& _value)
        {
            return _upper_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        const_iterator upper_bound(const TComparable& _value) const
        {
            return _upper_bound(m_Container, m_Compare, _value);
        }

        template <class TComparable>
        bool contains(const TComparable& _value) const
        {
            return find(_value) != end();
        }

        /*#####
        # multi element stuff
        #####*/
        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        std::pair<iterator, iterator> equal_range(const TComparable& _value)
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        std::pair<const_iterator, const_iterator> equal_range(const TComparable& _value) const
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        iterator find_last(const TComparable& _value)
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        const_iterator find_last(const TComparable& _value) const
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        iterator erase_all_of(const TComparable& _value)
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return m_Container.erase(range.first, range.second);
        }

        template <class TComparable, bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        size_type count(const TComparable& _value) const
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return std::distance(range.first, range.second);
        }

        template <bool Unique = UniqueElements, typename = std::enable_if_t<!Unique>>
        void unique()
        {
            m_Container.erase(std::unique(std::begin(m_Container), std::end(m_Container),
                                          [&compare = m_Compare](const auto& _lhs, const auto& _rhs)
                                          {
                                              return !compare(_lhs, _rhs) && !compare(_rhs, _lhs);
                                          }), end());
        }

        /*#####
        # comparison stuff
        #####*/
        bool operator ==(const BaseSkipList& _other) const
        {
            return std::equal(begin(), end(), std::begin(_other), std::end(_other),
                              [&compare = m_Compare](const auto& _elLhs, const auto& _elRhs)
                              {
                                  return !compare(_elLhs, _elRhs) && !compare(_elRhs, _elLhs);
                              });
        }

        friend bool operator !=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs == _rhs);
        }

        bool operator <(const BaseSkipList& _other) const
        {
            return std::lexicographical_compare(begin(), end(), std::begin(_other), std::end(_other), m_Compare);
        }

        friend bool operator >=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs < _rhs);
        }

        friend bool operator >(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return _rhs < _lhs;
        }

        friend bool operator <=(const BaseSkipList& _lhs, const BaseSkipList& _rhs)
        {
            return !(_lhs > _rhs);
        }

        /*#####
        # Iterator stuff
        #####*/
        iterator begin() noexcept
        {
            return std::begin(m_Container);
        }

        const_iterator begin() const noexcept
        {
            return std::begin(m_Container);
        }

        const_iterator cbegin() const noexcept
        {
            return std::cbegin(m_Container);
        }

        iterator end() noexcept
        {
            return std::end(m_Container);
        }

        const_iterator end() const noexcept
        {
            return std::end(m_Container);
        }

        const_iterator cend() const noexcept
        {
            return std::cend(m_Container);
        }

        iterator rbegin() noexcept
        {
            return std::rbegin(m_Container);
        }

        const_reverse_iterator rbegin() const noexcept
        {
            return std::rbegin(m_Container);
        }

        const_reverse_iterator crbegin() const noexcept
        {
            return std::crbegin(m_Container);
        }

        iterator rend() noexcept
        {
            return std::rend(m_Container);
        }

        const_reverse_iterator rend() const noexcept
        {
            return std::rend(m_Container);
        }

        const_reverse_iterator crend() const noexcept
        {
            return std::crend(m_Container);
        }

    private:
        Container m_Container;

        Compare m_Compare;

        template <class TValueType>
        std::pair<iterator, bool> _insert(TValueType&& _value)
        {
            auto itr = _lower_bound(m_Container, m_Compare, _value);
            if constexpr (UniqueElements)
            {
                if (itr == end() || m_Compare(_value, *itr))
                {
                    m_Container.insert(itr, std::forward<TValueType>(_value));
                    return {itr, true};
                }
            }
            else
            {
                m_Container.insert(itr, std::forward<TValueType>(_value));
                return {itr, true};
            }
            return {itr, false};
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _find(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            auto itr = _lower_bound(_container, _compare, _value);
            if (itr != std::end(_container) && !_compare(_value, *itr))
            {
                return itr;
            }
            return std::end(_container);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _find_last(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            auto [begin, end] = _equal_range(_container, _compare, _value);
            auto dist         = std::distance(begin, end);
            if (0 < dist)
            {
                std::advance(begin, dist - 1);
                return begin;
            }
            return std::end(_container);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _lower_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::lower_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _upper_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::upper_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

        template <class TContainer, class TCompare, class TComparable>
        static auto _equal_range(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::equal_range(std::begin(_container), std::end(_container), _value, _compare);
        }
    };
} // namespace detail

template <class T, class Compare = std::less<>, class Container = std::vector<T>>
using SkipList = detail::BaseSkipList<T, true, Compare, Container>;
template <class T, class Compare = std::less<>, class Container = std::vector<T>>
using MultiSkipList = detail::BaseSkipList<T, false, Compare, Container>;