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
}