泛型(多)SkipList适配器类

Question

今天，我编写了SkipList的第一个实现(在std::vector之上)，因为我厌倦了手动使用std::lower_bound和其他函数。我试图尽可能地创建它，以便为用户提供尽可能多的健康自由。在实现过程中，我总是关注std::set和std::multiset文档，以保持接口类似于这些文档。

起初，我决定将非const迭代器隐藏在公共接口中，以防止在意外情况下对SkipList进行操作，但在第一次迭代之后，它的使用非常不优雅。至少，当您尝试使用value_type对象的一个属性作为键时，它显示了它的weaknesses.To，更改了该元素的任何其他变量，我必须先删除它，然后再插入它。这既不好，也不干净，也不优雅；这也是我决定公开非const迭代器的原因。顺便说一句，std::set和std::multiset也公开了它们，因此对于该类的用户来说，这不应该是一个很大的惊喜。

以下是SkipList (唯一元素)和MultiSkipList的代码。

#include 
#include 
#include 

namespace detail
{
    template , class Container = std::vector>
    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 
        std::pair insert(TValueType&& _value)
        {
            return _insert(begin(), std::forward(_value));
        }

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

        void insert(std::initializer_list _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 
        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 
        iterator find(const TComparable& _value)
        {
            return _find(m_Container, m_Compare, _value);
        }

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

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

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

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

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

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

        /*#####
        # multi element stuff
        #####*/
        template >
        std::pair equal_range(const TComparable& _value)
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template >
        std::pair equal_range(const TComparable& _value) const
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template >
        iterator find_last(const TComparable& _value)
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template >
        const_iterator find_last(const TComparable& _value) const
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template >
        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 >
        size_type count(const TComparable& _value) const
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return std::distance(range.first, range.second);
        }

        template >
        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 
        std::pair _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(_value));
                    return { itr, true };
                }
            }
            else
            {
                m_Container.insert(itr, std::forward(_value));
                return { itr, true };
            }
            return { itr, false };
        }

        template 
        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 
        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 
        static auto _lower_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::lower_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

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

        template 
        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 Container = std::vector>
using SkipList = detail::BaseSkipList;
template , class Container = std::vector>
using MultiSkipList = detail::BaseSkipList;

下面是一个简单的示例程序；请注意，在第二个示例中，Test对象的成员D12被用作键。我们可以搜索具体的对象或简单的键值。

int main()
{
    SkipList 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 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

在使用了几天之后，我发现了一些错误，并想将它们分享给您。我还修正了clang中的编译错误，因为MultiSkipList函数没有以正确的方式禁用。

我仍然希望收到一些关于风格，可用性和正确性的意见。

#pragma once

#include 
#include 
#include 

namespace detail
{
    template , class Container = std::vector>
    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 
        std::pair insert(TValueType&& _value)
        {
            return _insert(std::forward(_value));
        }

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

        void insert(std::initializer_list _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 
        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 
        iterator find(const TComparable& _value)
        {
            return _find(m_Container, m_Compare, _value);
        }

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

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

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

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

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

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

        /*#####
        # multi element stuff
        #####*/
        template >
        std::pair equal_range(const TComparable& _value)
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template >
        std::pair equal_range(const TComparable& _value) const
        {
            return _equal_range(m_Container, m_Compare, _value);
        }

        template >
        iterator find_last(const TComparable& _value)
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template >
        const_iterator find_last(const TComparable& _value) const
        {
            return _find_last(m_Container, m_Compare, _value);
        }

        template >
        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 >
        size_type count(const TComparable& _value) const
        {
            auto range = _equal_range(m_Container, m_Compare, _value);
            return std::distance(range.first, range.second);
        }

        template >
        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 
        std::pair _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(_value));
                    return {itr, true};
                }
            }
            else
            {
                m_Container.insert(itr, std::forward(_value));
                return {itr, true};
            }
            return {itr, false};
        }

        template 
        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 
        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 
        static auto _lower_bound(TContainer&& _container, TCompare&& _compare, const TComparable& _value)
        {
            return std::lower_bound(std::begin(_container), std::end(_container), _value, _compare);
        }

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

        template 
        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 Container = std::vector>
using SkipList = detail::BaseSkipList;
template , class Container = std::vector>
using MultiSkipList = detail::BaseSkipList;