multiset.hpp

#ifndef MSTL_CORE_CONTAINER_MULTISET_HPP__
#define MSTL_CORE_CONTAINER_MULTISET_HPP__
#include "rb_tree.hpp"
MSTL_BEGIN_NAMESPACE__
 
template <typename Key, typename Compare = less<Key>, typename Alloc = allocator<rb_tree_node<Key>>>
class multiset : icollector<multiset<Key, Compare, Alloc>> {
#ifdef MSTL_STANDARD_20__
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
#endif
    static_assert(is_same_v<rb_tree_node<Key>, typename Alloc::value_type>,
        "allocator type mismatch.");
    static_assert(is_object_v<Key>, "multiset only contains object types.");
 
    using base_type = rb_tree<Key, Key, identity<Key>, Compare, Alloc>;
 
public:
    using key_type          = Key;
    using value_type        = Key;
    using key_compare       = Compare;
    using value_compare     = Compare;
 
    using size_type         = typename base_type::size_type;
    using difference_type   = typename base_type::difference_type;
    using pointer           = typename base_type::pointer;
    using const_pointer     = typename base_type::const_pointer;
    using reference         = typename base_type::reference;
    using const_reference   = typename base_type::const_reference;
 
    using iterator                  = typename base_type::iterator;
    using const_iterator            = typename base_type::const_iterator;
    using reverse_iterator          = typename base_type::reverse_iterator;
    using const_reverse_iterator    = typename base_type::const_reverse_iterator;
 
    using allocator_type    = typename base_type::allocator_type;
 
private:
    base_type tree_;
 
public:
    multiset() : tree_(Compare()) {}
    explicit multiset(const key_compare& comp) : tree_(comp) {}
 
    multiset(const multiset& x) : tree_(x.tree_) {}
 
    multiset& operator =(const multiset& x) = default;
 
    multiset(multiset&& x) noexcept(is_nothrow_move_constructible_v<base_type>)
        : tree_(_MSTL move(x.tree_)) {
    }
 
    multiset& operator =(multiset&& x) noexcept(noexcept(swap(x))) {
        tree_ = _MSTL move(x.tree_);
        return *this;
    }
 
    template <typename Iterator>
    multiset(Iterator first, Iterator last) : tree_(Compare()) {
        tree_.insert_equal(first, last);
    }
    template <typename Iterator>
    multiset(Iterator first, Iterator last, const key_compare& comp) : tree_(comp) {
        tree_.insert_equal(first, last);
    }
 
    multiset(std::initializer_list<value_type> l) : multiset(l.begin(), l.end()) {}
    multiset(std::initializer_list<value_type> l, const key_compare& comp) : multiset(l.begin(), l.end(), comp) {}
 
    multiset& operator =(std::initializer_list<value_type> l) {
        clear();
        insert(l.begin(), l.end());
        return *this;
    }
    ~multiset() = default;
 
    MSTL_NODISCARD iterator begin() noexcept { return tree_.begin(); }
    MSTL_NODISCARD iterator end() noexcept { return tree_.end(); }
    MSTL_NODISCARD const_iterator cbegin() const noexcept { return tree_.cbegin(); }
    MSTL_NODISCARD const_iterator cend() const noexcept { return tree_.cend(); }
    MSTL_NODISCARD reverse_iterator rbegin() noexcept { return reverse_iterator(tree_.begin()); }
    MSTL_NODISCARD reverse_iterator rend() noexcept { return reverse_iterator(tree_.end()); }
    MSTL_NODISCARD const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(tree_.cbegin()); }
    MSTL_NODISCARD const_reverse_iterator crend() const noexcept { return const_reverse_iterator(tree_.cend()); }
 
    MSTL_NODISCARD size_type size() const noexcept { return tree_.size(); }
    MSTL_NODISCARD size_type max_size() const noexcept { return tree_.max_size(); }
    MSTL_NODISCARD bool empty() const noexcept { return tree_.empty(); }
 
    MSTL_NODISCARD allocator_type get_allocator() const noexcept { return allocator_type(); }
 
    MSTL_NODISCARD key_compare key_comp() const noexcept { return tree_.key_comp(); }
    MSTL_NODISCARD value_compare value_comp() const noexcept { return value_compare(tree_.key_comp()); }
 
    template <typename... Args>
    iterator emplace(Args&&... args) {
        return tree_.emplace_equal(_MSTL forward<Args>(args)...);
    }
    iterator insert(const value_type& x) {
        return tree_.insert_equal(x);
    }
    iterator insert(value_type&& x) {
        return tree_.insert_equal(_MSTL move(x));
    }
 
    template <typename... Args>
    iterator emplace_hint(iterator position, Args&&... args) {
        return tree_.emplace_equal_hint(position, _MSTL forward<Args>(args)...);
    }
    iterator insert(iterator position, const value_type& x) {
        return tree_.insert_equal(position, x);
    }
    iterator insert(iterator position, value_type&& x) {
        return tree_.insert_equal(position, _MSTL move(x));
    }
 
    template <typename Iterator>
    void insert(Iterator first, Iterator last) {
        tree_.insert_equal(first, last);
    }
 
    void erase(iterator position) noexcept { tree_.erase(position); }
    size_type erase(const key_type& x) noexcept { return tree_.erase(x); }
    void erase(iterator first, iterator last) noexcept { tree_.erase(first, last); }
 
    void clear() noexcept { tree_.clear(); }
 
    MSTL_NODISCARD iterator find(const key_type& x) { return tree_.find(x); }
    MSTL_NODISCARD const_iterator find(const key_type& x) const { return tree_.find(x); }
    MSTL_NODISCARD size_type count(const key_type& x) const { return tree_.count(x); }
 
    MSTL_NODISCARD iterator lower_bound(const key_type& x) { return tree_.lower_bound(x); }
    MSTL_NODISCARD const_iterator lower_bound(const key_type& x) const { return tree_.lower_bound(x); }
    MSTL_NODISCARD iterator upper_bound(const key_type& x) { return tree_.upper_bound(x); }
    MSTL_NODISCARD const_iterator upper_bound(const key_type& x) const { return tree_.upper_bound(x); }
 
    MSTL_NODISCARD pair<iterator, iterator> equal_range(const key_type& x) { return tree_.equal_range(x); }
    MSTL_NODISCARD pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
        return tree_.equal_range(x);
    }
 
    void swap(multiset& x) noexcept(noexcept(tree_.swap(x.tree_))) { tree_.swap(x.tree_); }
 
    MSTL_NODISCARD bool operator ==(const multiset& rhs) const
    noexcept(noexcept(tree_ == rhs.tree_)) {
        return tree_ == rhs.tree_;
    }
    MSTL_NODISCARD bool operator <(const multiset& rhs) const
    noexcept(noexcept(tree_ < rhs.tree_)) {
        return tree_ < rhs.tree_;
    }
};
#if MSTL_SUPPORT_DEDUCTION_GUIDES__
template <typename Iterator, typename Compare = less<iter_value_t<Iterator>>,
    typename Alloc = allocator<iter_value_t<Iterator>>>
multiset(Iterator, Iterator, Compare = Compare(), Alloc = Alloc())
-> multiset<iter_value_t<Iterator>, Compare, Alloc>;
 
template <typename Key, typename Compare = less<Key>, typename Alloc = allocator<Key>>
multiset(std::initializer_list<Key>, Compare = Compare(), Alloc = Alloc()) -> multiset<Key, Compare, Alloc>;
 
template <typename Iterator, typename Alloc>
multiset(Iterator, Iterator, Alloc) -> multiset<iter_value_t<Iterator>, less<iter_value_t<Iterator>>, Alloc>;
 
template <typename Key, typename Alloc>
multiset(std::initializer_list<Key>, Alloc) -> multiset<Key, less<Key>, Alloc>;
#endif
 
MSTL_END_NAMESPACE__
#endif // MSTL_CORE_CONTAINER_MULTISET_HPP__