A set based on a sorted vector

set.hpp

#pragma once
#include <algorithm>
#include <functional>
#include <vector>

namespace pal {

template <typename Key,
          typename Compare = std::less<Key>,
          typename Allocator = std::allocator<Key>>
class Set {
    using VectorType = std::vector<Key, Allocator>;

public:
    using key_type = Key;
    using value_type = Key;
    using size_type = typename VectorType::size_type;
    using difference_type = typename VectorType::difference_type;
    using key_compare = Compare;
    using value_compare = Compare;
    using allocator_type = Allocator;
    using reference = typename VectorType::reference;
    using const_reference = typename VectorType::const_reference;
    using pointer = typename VectorType::pointer;
    using const_pointer = typename VectorType::const_pointer;
    using iterator = typename VectorType::iterator;
    using const_iterator = typename VectorType::const_iterator;
    using reverse_iterator = typename VectorType::reverse_iterator;
    using const_reverse_iterator = typename VectorType::const_reverse_iterator;

public:
    Set() = default;
    ~Set() = default;

    explicit Set(const Compare &comp,
                 const Allocator &alloc = Allocator())
        : m_vec(alloc)
        , m_cmp(comp)
    {}

    explicit Set(const Allocator &alloc)
        : m_vec(alloc)
    {}

    template <typename InputIterator>
    Set(InputIterator first, InputIterator last,
        const Compare &comp = Compare(),
        const Allocator &alloc = Allocator())
        : m_vec(alloc)
        , m_cmp(comp)
    {
        assign(first, last);
    }

    template <typename InputIterator>
    Set(InputIterator first, InputIterator last, const Allocator &alloc)
        : Set(first, last, Compare(), alloc)
    {}

    explicit Set(std::initializer_list<value_type> init,
        const Compare &comp = Compare(),
        const Allocator &alloc = Allocator())
        : m_vec(alloc)
        , m_cmp(comp)
    {
        assign(init.begin(), init.end());
    }

    Set(std::initializer_list<value_type> init, const Allocator &alloc)
        : Set(std::move(init), Compare(), alloc)
    {}

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

    Set(const Set &other, const Allocator &alloc)
        : m_vec(other.m_vec, alloc)
        , m_cmp(other.m_cmp)
    {}

    Set(Set &&other, const Allocator &alloc)
        : m_vec(std::move(other.m_vec), alloc)
        , m_cmp(std::move(other.m_cmp))
    {}

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

    Set& operator=(std::initializer_list<value_type> list) {
        assign(list.begin(), list.end());
        return *this;
    }

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

    /// Iterators

    iterator begin() noexcept { return m_vec.begin(); }
    const_iterator begin() const noexcept { return m_vec.begin(); }
    const_iterator cbegin() const noexcept { return m_vec.begin(); }

    iterator end() noexcept { return m_vec.end(); }
    const_iterator end() const noexcept { return m_vec.end(); }
    const_iterator cend() const noexcept { return m_vec.end(); }

    reverse_iterator rbegin() noexcept { return m_vec.rbegin(); }
    const_reverse_iterator rbegin() const noexcept { return m_vec.rbegin(); }
    const_reverse_iterator crbegin() const noexcept { return m_vec.crbegin(); }

    reverse_iterator rend() noexcept { return m_vec.rend(); }
    const_reverse_iterator rend() const noexcept { return m_vec.rend(); }
    const_reverse_iterator crend() const noexcept { return m_vec.crend(); }

    /// Capacity

    bool empty() const noexcept { return m_vec.empty(); }
    size_type size() const noexcept { return m_vec.size(); }
    size_type max_size() const noexcept { return m_vec.max_size(); }
    void reserve(size_type sz) { m_vec.reserve(sz); }

    /// Modifiers

    void clear() noexcept { m_vec.clear(); }

    template <typename It>
    void assign(It beg, It end) {
        clear();
        insert(beg, end);
    }

    std::pair<iterator, bool> insert(const key_type &t) {
        auto i = lower_bound(t);
        if (i == end() || m_cmp(t, *i)) {
            i = m_vec.insert(i, t);
            return {i, true};
        }
        return {i, false};
    }

    std::pair<iterator, bool> insert(iterator hint, const key_type &t) {
        if (hint != begin() && !m_cmp(*(hint-1), t))
            hint = begin();
        auto i = std::lower_bound(hint, m_vec.end(), t, m_cmp);
        if (i == end() || m_cmp(t, *i)) {
            i = m_vec.insert(i, t);
            return {i, true};
        }
        return {i, false};
    }

    std::pair<iterator, bool> insert(key_type &&t) {
        auto i = lower_bound(t);
        if (i == end() || m_cmp(t, *i)) {
            i = m_vec.insert(i, std::move(t));
            return {i, true};
        }
        return {i, false};
    }

    std::pair<iterator, bool> insert(iterator hint, key_type &&t) {
        if (hint != begin() && !m_cmp(*(hint-1), t))
            hint = begin();
        auto i = std::lower_bound(hint, m_vec.cend(), t, m_cmp);
        if (i == end() || m_cmp(t, *i)) {
            i = m_vec.insert(i, std::move(t));
            return {i, true};
        }
        return {i, false};
    }

    template <typename InputIterator>
    void insert(InputIterator beg, InputIterator end) {
        const auto len = std::distance(beg, end);
        const bool emp = empty();
        VectorType buf;
        if (emp)
            std::swap(buf, m_vec);

        buf.resize(size() + len);
        auto bmid = buf.begin() + size();
        std::copy(beg, end, bmid);

        std::sort(bmid, buf.end(), m_cmp);
        auto blast = std::unique(bmid, buf.end(), [&] (auto &&a, auto &&b) {
            return !m_cmp(a, b) && !m_cmp(b, a);
        });

        if (!emp) {
            blast = std::set_union(
                std::make_move_iterator(m_vec.begin()),
                std::make_move_iterator(m_vec.end()),
                std::make_move_iterator(bmid),
                std::make_move_iterator(blast),
                buf.begin(),
                m_cmp);
        }

        buf.erase(blast, buf.end());
        std::swap(m_vec, buf);
    }

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

    void insert(const Set &other) {
        merge(other);
    }

    void insert(Set &&other) {
        merge(std::move(other));
    }

    template <typename ...Args>
    std::pair<iterator, bool> emplace(Args&& ...args) {
        return insert(Key(std::forward<Args>(args)...));
    }

    iterator erase_at(size_type idx) {
        return erase(m_vec.begin() + idx);
    }

    iterator erase(const_iterator pos) {
        return m_vec.erase(pos);
    }

    iterator erase(const_iterator first, const_iterator last) {
        return m_vec.erase(first, last);
    }

    size_type erase(const key_type &key) {
        auto it = std::remove(m_vec.begin(), m_vec.end(), key);
        size_type count = std::distance(it, m_vec.end());
        m_vec.erase(it, m_vec.end());
        return count;
    }

    template <typename Pred>
    size_type erase_if(Pred pred) {
        auto it = std::remove_if(m_vec.begin(), m_vec.end(), pred);
        size_type count = std::distance(it, m_vec.end());
        m_vec.erase(it, m_vec.end());
        return count;
    }

    void swap(Set &other) noexcept {
        using std::swap;
        swap(m_vec, other.m_vec);
        swap(m_cmp, other.m_cmp);
    }

    void merge(const Set &source) {
        VectorType d;
        d.reserve(size() + source.size());
        std::swap(m_vec, d);
        auto first1 = d.begin();
        auto first2 = source.begin();

        while (first1 != d.end()) {
            if (first2 == source.end()) {
                std::move(first1, d.end(), std::back_inserter(m_vec));
                return;
            }
            if (m_cmp(*first2, *first1)) {
                m_vec.push_back(*first2);
                ++first2;
            }
            else {
                if (!m_cmp(*first1, *first2))
                    ++first2;
                m_vec.emplace_back(std::move(*first1));
                ++first1;
            }
        }

        std::copy(first2, source.end(), std::back_inserter(m_vec));
    }

    void merge(Set &&source) {
        VectorType d;
        d.reserve(size() + source.size());
        std::swap(m_vec, d);
        auto first1 = d.begin();
        auto first2 = source.begin();

        while (first1 != d.end()) {
            if (first2 == source.end()) {
                std::move(first1, d.end(), std::back_inserter(m_vec));
                return;
            }
            if (m_cmp(*first2, *first1)) {
                m_vec.emplace_back(std::move(*first2));
                ++first2;
            }
            else {
                if (!m_cmp(*first1, *first2))
                    ++first2;
                m_vec.emplace_back(std::move(*first1));
                ++first1;
            }
        }

        std::move(first2, source.end(), std::back_inserter(m_vec));
    }

    template <typename Compare2>
    void merge(const Set<key_type, Compare2, Allocator> &source) {
        insert(source.begin(), source.end());
    }

    template <typename Compare2>
    void merge(Set<key_type, Compare2, Allocator> &&source) {
        insert(std::make_move_iterator(source.begin()),
               std::make_move_iterator(source.end()));
    }

    /// Lookup

    template <typename K>
    bool contains(const K &k) const {
        return find(k) != cend();
    }

    template <typename K>
    size_type count(const K &k) const {
        return static_cast<size_type>(contains(k));
    }

    template <typename K>
    iterator find(const K &k) {
        iterator i = lower_bound(k);
        return i == end() || m_cmp(k, *i) ? end() : i;
    }

    template <typename K>
    const_iterator find(const K &k) const {
        const_iterator i = lower_bound(k);
        return i == end() || m_cmp(k, *i) ? end() : i;
    }

    const_pointer data() const {
        return m_vec.data();
    }

    const_reference operator[](size_type idx) const {
        return m_vec[idx];
    }

    const_reference at(size_type idx) const {
        return m_vec.at(idx);
    }

    template <typename K>
    std::pair<iterator, iterator> equal_range(const K &x) {
        return std::equal_range(m_vec.begin(), m_vec.end(), x, m_cmp);
    }

    template <typename K>
    std::pair<const_iterator, const_iterator> equal_range(const K &x) const {
        return std::equal_range(m_vec.cbegin(), m_vec.cend(), x, m_cmp);
    }

    template <typename K>
    iterator lower_bound(const K &x) {
        return std::lower_bound(m_vec.begin(), m_vec.end(), x, m_cmp);
    }

    template <typename K>
    const_iterator lower_bound(const K &x) const {
        return std::lower_bound(m_vec.cbegin(), m_vec.cend(), x, m_cmp);
    }

    template <typename K>
    iterator upper_bound(const K &x) {
        return std::upper_bound(m_vec.begin(), m_vec.end(), x, m_cmp);
    }

    template <typename K>
    const_iterator upper_bound(const K &x) const {
        return std::upper_bound(m_vec.cbegin(), m_vec.cend(), x, m_cmp);
    }

    /// set operations

    void substract(const Set &other) {
        Set tmp = substraction(other);
        std::swap(tmp.m_vec, m_vec);
    }

    void intersect(const Set &other) {
        Set tmp = intersection(other);
        std::swap(tmp.m_vec, m_vec);
    }

    void disjoint(const Set &other) {
        Set tmp = disjonction(other);
        std::swap(tmp.m_vec, m_vec);
    }

    Set substraction(const Set &other) const {
        Set out;
        out.reserve(size());
        std::set_difference(begin(), end(), other.begin(), other.end(),
                            std::back_inserter(out.m_vec), m_cmp);
        return out;
    }

    Set disjonction(const Set &other) const {
        Set out;
        out.reserve(size() + other.size());
        std::set_symmetric_difference(begin(), end(), other.begin(), other.end(),
                                      std::back_inserter(out.m_vec), m_cmp);
        return out;
    }

    Set intersection(const Set &other) const {
        Set out;
        out.reserve(std::max(size(), other.size()));
        std::set_intersection(begin(), end(), other.begin(), other.end(),
                              std::back_inserter(out.m_vec), m_cmp);
        return out;
    }

    Set fusion(const Set &other) const {
        Set out;
        out.reserve(size() + other.size());
        std::set_union(begin(), end(), other.begin(), other.end(),
                       std::back_inserter(out.m_vec), m_cmp);
        return out;
    }

    friend inline Set& operator-=(Set &v, const Set &o) {
        v.substract(o);
        return v;
    }

    friend inline Set operator-(const Set &v, const Set &o) {
        return v.substraction(o);
    }

    friend inline Set& operator+=(Set &v, const Set &o) {
        v.insert(o);
        return v;
    }

    friend inline Set operator+(const Set &v, const Set &o) {
        return v.fusion(o);
    }

    friend inline Set& operator&=(Set &v, const Set &o) {
        v.intersect(o);
        return v;
    }

    friend inline Set operator&(const Set &v, const Set &o) {
        return v.intersection(o);
    }

    friend inline Set& operator^=(Set &v, const Set &o) {
        v.disjoint(o);
        return v;
    }

    friend inline Set operator^(const Set &v, const Set &o) {
        return v.disjonction(o);
    }

    /// Comparisons
public:
    friend inline bool operator==(const Set &l, const Set &r) {
        return l.m_vec == r.m_vec;
    }

    friend inline bool operator!=(const Set &l, const Set &r) {
        return l.m_vec != r.m_vec;
    }

    friend inline bool operator<(const Set &l, const Set &r) {
        return l.m_vec < r.m_vec;
    }

    friend inline bool operator<=(const Set &l, const Set &r) {
        return l.m_vec <= r.m_vec;
    }

    friend inline bool operator>(const Set &l, const Set &r) {
        return l.m_vec > r.m_vec;
    }

    friend inline bool operator>=(const Set &l, const Set &r) {
        return l.m_vec >= r.m_vec;
    }

private:
    template <typename K2, typename C2, typename A2>
    friend class Set;

    std::vector<key_type, allocator_type> m_vec;
    key_compare m_cmp;
};

} // namespace pal

namespace std {

template <typename K, typename C, typename A>
void swap(pal::Set<K, C, A> &l, pal::Set<K, C, A> &r) {
    l.swap(r);
}

} // namespace std