sparse_map.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_SPARSE_MAP_HPP__
#define NEFORCE_CORE_CONTAINER_SPARSE_MAP_HPP__

 
#include "NeForce/core/container/sparse_vector.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <typename Key, typename T, typename Compare = less<Key>, typename Alloc = allocator<pair<Key, T>>>
class sparse_map : public icollector<sparse_map<Key, T, Compare, Alloc>> {
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
    static_assert(is_same_v<pair<Key, T>, typename Alloc::value_type>, "allocator type mismatch.");
    static_assert(is_object_v<T>, "sparse_map only contains object types.");
 
public:
    using key_type = Key;            
    using data_type = T;             
    using mapped_type = T;           
    using value_type = pair<Key, T>; 
    using key_compare = Compare;     

    struct value_compare {
    private:
        Compare comp_; 
        friend class sparse_map;
 
    public:
        explicit value_compare(Compare comp) :
        comp_(comp) {}

        bool operator()(const value_type& lhs, const value_type& rhs) const noexcept {
            return comp_(lhs.first, rhs.first);
        }
    };
 
private:
    using base_type = sparse_vector<Key, pair<Key, T>, select1st<pair<Key, T>>, Compare, Alloc>; 
 
public:
    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 data_; 
 
public:
    sparse_map() :
    data_(Compare()) {}

    explicit sparse_map(const key_compare& comp) :
    data_(comp) {}

    sparse_map(const sparse_map& other) :
    data_(other.data_) {}

    sparse_map& operator=(const sparse_map& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        data_ = other.data_;
        return *this;
    }

    sparse_map(sparse_map&& other) noexcept(is_nothrow_move_constructible_v<base_type>) :
    data_(_NEFORCE move(other.data_)) {}

    sparse_map& operator=(sparse_map&& other) noexcept(is_nothrow_move_assignable_v<base_type>) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        data_ = _NEFORCE move(other.data_);
        return *this;
    }

    template <typename Iterator>
    sparse_map(Iterator first, Iterator last) :
    data_(Compare()) {
        data_.insert_unique(first, last);
    }

    template <typename Iterator>
    sparse_map(Iterator first, Iterator last, const key_compare& comp) :
    data_(comp) {
        data_.insert_unique(first, last);
    }

    sparse_map(std::initializer_list<value_type> ilist) :
    sparse_map(ilist.begin(), ilist.end()) {}

    sparse_map(std::initializer_list<value_type> ilist, const key_compare& comp) :
    sparse_map(ilist.begin(), ilist.end(), comp) {}

    sparse_map& operator=(std::initializer_list<value_type> ilist) {
        clear();
        insert(ilist.begin(), ilist.end());
        return *this;
    }

    ~sparse_map() = default;

    NEFORCE_NODISCARD iterator begin() noexcept { return data_.begin(); }

    NEFORCE_NODISCARD iterator end() noexcept { return data_.end(); }

    NEFORCE_NODISCARD const_iterator begin() const noexcept { return data_.cbegin(); }

    NEFORCE_NODISCARD const_iterator end() const noexcept { return data_.cend(); }

    NEFORCE_NODISCARD const_iterator cbegin() const noexcept { return data_.cbegin(); }

    NEFORCE_NODISCARD const_iterator cend() const noexcept { return data_.cend(); }

    NEFORCE_NODISCARD reverse_iterator rbegin() noexcept { return data_.rbegin(); }

    NEFORCE_NODISCARD reverse_iterator rend() noexcept { return data_.rend(); }

    NEFORCE_NODISCARD const_reverse_iterator rbegin() const noexcept { return data_.rbegin(); }

    NEFORCE_NODISCARD const_reverse_iterator rend() const noexcept { return data_.rend(); }

    NEFORCE_NODISCARD const_reverse_iterator crbegin() const noexcept { return data_.crbegin(); }

    NEFORCE_NODISCARD const_reverse_iterator crend() const noexcept { return data_.crend(); }

    NEFORCE_NODISCARD size_type size() const noexcept { return data_.size(); }

    NEFORCE_NODISCARD size_type max_size() const noexcept { return data_.max_size(); }

    NEFORCE_NODISCARD bool empty() const noexcept { return data_.empty(); }

    NEFORCE_NODISCARD key_compare key_comp() const noexcept { return data_.key_compare(); }

    NEFORCE_NODISCARD value_compare value_comp() const noexcept { return value_compare(data_.key_compare()); }

    template <typename... Args>
    pair<iterator, bool> emplace(Args&&... args) {
        return data_.emplace_unique(_NEFORCE forward<Args>(args)...);
    }

    pair<iterator, bool> insert(const value_type& value) { return data_.insert_unique(value); }

    pair<iterator, bool> insert(value_type&& value) { return data_.emplace_unique(_NEFORCE move(value)); }

    template <typename... Args>
    iterator emplace_hint(iterator position, Args&&... args) {
        return data_.emplace_unique_hint(position, _NEFORCE forward<Args>(args)...);
    }

    iterator insert(iterator position, const value_type& value) { return data_.insert_unique(position, value); }

    iterator insert(iterator position, value_type&& value) {
        return data_.insert_unique(position, _NEFORCE move(value));
    }

    template <typename Iterator>
    void insert(Iterator first, Iterator last) {
        data_.insert_unique(first, last);
    }

    void erase(iterator position) noexcept(noexcept(data_.erase(position))) { data_.erase(position); }

    size_type erase(const key_type& key) noexcept(noexcept(data_.erase(key))) { return data_.erase(key); }

    void erase(iterator first, iterator last) noexcept(noexcept(data_.erase(first, last))) { data_.erase(first, last); }

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

    NEFORCE_NODISCARD iterator find(const key_type& key) { return data_.find(key); }

    NEFORCE_NODISCARD const_iterator find(const key_type& key) const { return data_.find(key); }

    NEFORCE_NODISCARD size_type count(const key_type& key) const { return data_.count(key); }

    NEFORCE_NODISCARD iterator lower_bound(const key_type& key) { return data_.lower_bound(key); }

    NEFORCE_NODISCARD const_iterator lower_bound(const key_type& key) const { return data_.lower_bound(key); }

    NEFORCE_NODISCARD iterator upper_bound(const key_type& key) { return data_.upper_bound(key); }

    NEFORCE_NODISCARD const_iterator upper_bound(const key_type& key) const { return data_.upper_bound(key); }

    NEFORCE_NODISCARD pair<iterator, iterator> equal_range(const key_type& key) { return data_.equal_range(key); }

    NEFORCE_NODISCARD pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return data_.equal_range(key);
    }

    NEFORCE_NODISCARD mapped_type& operator[](const key_type& key) {
        iterator iter = data_.lower_bound(key);
        if (iter == end() || key_comp()(key, iter->first)) {
            iter = data_.emplace_unique_hint(iter, key, initialize<T>());
        }
        return iter->second;
    }

    NEFORCE_NODISCARD mapped_type& operator[](key_type&& key) {
        iterator iter = data_.lower_bound(key);
        if (iter == end() || key_comp()(key, iter->first)) {
            iter = data_.emplace_unique_hint(iter, _NEFORCE move(key), initialize<T>());
        }
        return iter->second;
    }

    NEFORCE_NODISCARD const mapped_type& at(const key_type& key) const {
        const_iterator iter = data_.lower_bound(key);
        if (iter == end() || key_comp()(key, iter->first)) {
            NEFORCE_THROW_EXCEPTION(value_exception("the value of this key does not exists."));
        }
        return iter->second;
    }

    NEFORCE_NODISCARD mapped_type& at(const key_type& key) {
        iterator iter = data_.lower_bound(key);
        if (iter == end() || key_comp()(key, iter->first)) {
            NEFORCE_THROW_EXCEPTION(value_exception("the value of this key does not exists."));
        }
        return iter->second;
    }

    void reserve(size_type n) { data_.reserve(n); }

    NEFORCE_NODISCARD size_type capacity() const noexcept { return data_.capacity(); }

    void shrink_to_fit() { data_.shrink_to_fit(); }

    void swap(sparse_map& other) noexcept(noexcept(data_.swap(other.data_))) { data_.swap(other.data_); }

    NEFORCE_NODISCARD bool equal_to(const sparse_map& rhs) const noexcept(noexcept(data_ == rhs.data_)) {
        return data_ == rhs.data_;
    }

    NEFORCE_NODISCARD bool less_than(const sparse_map& rhs) const noexcept(noexcept(data_ < rhs.data_)) {
        return data_ < rhs.data_;
    }
};
 
#ifdef NEFORCE_STANDARD_17
template <typename Iterator, typename Compare,
          typename Alloc = allocator<pair<iter_map_key_t<Iterator>, iter_map_value_t<Iterator>>>>
sparse_map(Iterator, Iterator, Compare = Compare(), Alloc = Alloc())
        -> sparse_map<iter_map_key_t<Iterator>, iter_map_value_t<Iterator>, Compare, Alloc>;
 
template <typename Key, typename T, typename Compare = less<Key>, typename Alloc = allocator<pair<Key, T>>>
sparse_map(std::initializer_list<pair<Key, T>>, Compare = Compare(), Alloc = Alloc())
        -> sparse_map<Key, T, Compare, Alloc>;
 
template <typename Iterator, typename Alloc>
sparse_map(Iterator, Iterator, Alloc)
        -> sparse_map<iter_map_key_t<Iterator>, iter_map_value_t<Iterator>, less<iter_map_key_t<Iterator>>, Alloc>;
 
template <typename Key, typename T, typename Alloc>
sparse_map(std::initializer_list<pair<Key, T>>, Alloc) -> sparse_map<Key, T, less<Key>, Alloc>;
#endif
 // Container
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_SPARSE_MAP_HPP__